雙向鏈表

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

• 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編程語言的實現，請點擊 。