雙向連結串列

雙向連結串列是連結串列變型，相比於單連結串列導航或者是向前和向後的兩種方式。以下是重要的術語來理解雙向連結串列的概念

• Link ? 連結串列的每個鏈路儲存資料稱為一個元素。

• Next ? 連結串列的每個連結包含一個連結到下一個被稱為下一個(Next)。

• Prev ? 連結串列的每個連結包含一個連結，稱為上一個連結(Prev)。

• LinkedList ? LinkedList包含連線連結到名為首先第一個連結，並稱為最後的最後一個連結(Last)。

雙向連結串列表示

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

• 雙向連結串列包含一個名為第一個（first）和最後一個連結(last)元素。
• 每個鏈路負責資料欄位和LINK域被稱為下一個(Next)。
• 每一個Link連結，其利用其下一個連結指向下一個連結。
• 每一個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;
	
   if(isEmpty()){
      //make it the last link
      last = link;
   }else {
      //update first prev link
      head->prev = link;
   }

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

刪除操作

下面的程式碼演示了刪除操作，在一個雙向連結串列的開始。

//delete first item
struct node* deleteFirst(){
   //save reference to first link
   struct node *tempLink = head;
	
   //if only one link
   if(head->next == NULL){
      last = NULL;
   }else {
      head->next->prev = NULL;
   }
	
   head = head->next;
	
   //return the deleted link
   return tempLink;
}

在結尾插入操作

下面的程式碼演示了在一個雙向連結串列的最後一個位置的插入操作。

//insert link at the last location
void insertLast(int key, int data){
   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
	
   if(isEmpty()){
      //make it the last link
      last = link;
   }else {
      //make link a new last link
      last->next = link;     
      //mark old last node as prev of new link
      link->prev = last;
   }

   //point last to new last node
   last = link;
}

要檢視 C程式設計語言的實現，請點選 。