連結串列 - tw511教學網

連結串列基礎知識

連線表是通過連結連線在一起的資料結構的一個序列。

連結串列是一個序列的連結，其中包含專案。每個連結中包含到另一條連線。連結串列是陣列之後第二種最常用的資料結構。以下是理解連結串列的概念，重要術語。

Link ? 連結串列中的每個鏈路可以儲存資料稱為一個元素。
Next ? 連結串列的每個連結包含一個連結到下一個被稱為下一個。
LinkedList ? LinkedList 包含連線連結到名為 First 的第一個環節。

連結串列表示

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

連結串列包含一個名為第一個(first)的連結元素。
每個鏈路進行資料欄位和連結域叫做下一個(next)。
每一個Link連結，其利用其下一個連結的下一個連結。
最後一個連結帶有連結的空標記列表的末尾。

連結串列的型別

以下是連結串列的各種版本。

簡單的連結串列 ? 專案導航是向前。
雙向連結串列 ? 專案可以導航向前和向後的方式。
迴圈連結串列 ? 最後一個專案中包含的第一個元素的連結在下一個以及第一個元素連結到最後一個元素的上一個。

基本操作

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

插入 ? 在列表的開頭新增元素。
刪除 ? 刪除在列表開頭的元素。
顯示 ? 顯示完整列表。
搜尋 ? 搜尋給定鍵的元素。
刪除 ? 刪除給定鍵的元素。

插入操作

插入是三個步驟的過程 -

使用提供的資料建立一個新的連線。
指向新建連結到舊的第一個連結。
第一個連結指向到這個新連結。

//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;
}

刪除操作

刪除是兩個步驟過程-

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

//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;
}

導航操作

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

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

注意 ?

//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程式設計語言連結串列實現，請點選。