鏈表 - 數據結構和算法教學

鏈表基礎知識

連接表是通過鏈接連接在一起的數據結構的一個序列。

鏈表是一個序列的鏈接，其中包含項目。每個鏈接中包含到另一條連接。鏈表是數組之後第二種最常用的數據結構。以下是理解鏈表的概念，重要術語。

Link − 鏈表中的每個鏈路可以存儲數據稱爲一個元素。
Next − 鏈表的每個鏈接包含一個鏈接到下一個被稱爲下一個。
LinkedList − LinkedList 包含連接鏈接到名爲 First 的第一個環節。

鏈表表示

按照如上所示圖中，以下是要考慮的重要問題。

鏈表包含一個名爲第一個(first)的鏈接元素。
每個鏈路進行數據字段和鏈接域叫做下一個(next)。
每一個Link鏈接，其利用其下一個鏈接的下一個鏈接。
最後一個鏈接帶有鏈接的空標記列表的末尾。

鏈表的類型

以下是鏈表的各種版本。

簡單的鏈表 − 項目導航是向前。
雙向鏈表 − 項目可以導航向前和向後的方式。
循環鏈表 − 最後一個項目中包含的第一個元素的鏈接在下一個以及第一個元素鏈接到最後一個元素的上一個。

基本操作

以下是通過一個列表支持的基本操作。

插入 − 在列表的開頭添加元素。
刪除 − 刪除在列表開頭的元素。
顯示 − 顯示完整列表。
搜索 − 搜索給定鍵的元素。
刪除 − 刪除給定鍵的元素。

插入操作

插入是三個步驟的過程 -

使用提供的數據創建一個新的連接。
指向新建鏈接到舊的第一個鏈接。
第一個鏈接指向到這個新鏈接。

Linked

//insert link at the first location
void insertFirst(int key, int data){
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;

//point it to old first node
link->next = head;

//point first to new first node
head = link;
}

刪除操作

刪除是兩個步驟過程-

找第一個鏈接指向作爲臨時鏈路相連。
第一個鏈接指向到臨時鏈接的下一個鏈接。

Linked

//delete first item
struct node* deleteFirst(){
//save reference to first link
struct node *tempLink = head;

//mark next to first link as first
head = head->next;

//return the deleted link
return tempLink;
}

導航操作

導航是一個遞歸步驟的過程，是許多操作的基礎，如：搜索，刪除等 −

獲取指向的第一個鏈接是當前鏈接的鏈接。
檢查如果當前鏈接不爲空則顯示它。
指向當前鏈接到下一個鏈接，並移動到上面的步驟。

Linked

注意 −

//display the list
void printList(){
struct node *ptr = head;
printf("\n[ ");

//start from the beginning
while(ptr != NULL){
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}

printf(" ]");
}

高級操作

以下是一個列表中指定的高級操作

排序 − 排序基於一個特定列表上的順序的
反轉 − 反轉鏈表

排序操作

我們使用冒泡排序排序列表。

void sort(){

int i, j, k, tempKey, tempData ;
struct node *current;
struct node *next;
int size = length();
k = size ;

for ( i = 0 ; i < size - 1 ; i++, k-- ) {
current = head ;
next = head->next ;

  for ( j = 1 ; j < k ; j++ ) {

     if ( current->data > next->data ) {
        tempData = current->data ;
        current->data = next->data;
        next->data = tempData ;

        tempKey = current->key;
        current->key = next->key;
        next->key = tempKey;
     }

     current = current->next;
     next = next->next;                        
  }

}
}

反轉操作

下面的代碼演示了逆轉單向鏈表。

void reverse(struct node** head_ref) {
struct node* prev = NULL;
struct node* current = *head_ref;
struct node* next;

while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*head_ref = prev;
}

要查看 C編程語言鏈表實現，請點擊。

數據結構和算法教程

鏈表

鏈表基礎知識

鏈表表示

鏈表的類型

基本操作

插入操作

刪除操作

導航操作

高級操作

排序操作

反轉操作