[資料結構] 雙向鏈結串列教學[1]: 新增與印出

MuLong PuYang

7 min readFeb 19, 2020

簡介

雙向鏈結串列，英文為 doubly linked list，是一種基於鏈結串列，但是前後結點互相連通了資料結構

實作

完整的程式碼

結構變數解析

首先一開始，我們看到 Node 結構變數這裡來，相較於鏈結串列，我們這裡新增了 struct node *prev; 這一個結構變數，我們會用這個結構變數指向前一個結點，這樣搭配著 *next 指向下一個結點，我們就能達到雙向鏈結串列的功能

typedef struct node
{
 int data;
 struct node *next;
 struct node *prev;
}Node;

新增結點函數: add_node

主函數新增第一個結點

int main(int argc, char* argv[])
{
 // create first node "head"
 Node *head = NULL;
 add_node(&head, 5);return 0; 
}

新增第一個結點的時候，這時候我們看到 add_node 函數裡面，除了與鏈結串列一樣新稱結點，然後將結點賦值 new_node->data = value;，next 暫時不要指向任何結點，同樣 prev 也暫時不要指向任何結點。

由於是新增的第一個結點，我們將 new_node 設定給 *start，就可以回傳整個函數了，目前整個雙向鏈結串列新增了一個數值為 5 的結點

Node *new_node = (Node*)malloc(sizeof(Node));
 new_node->data = value;
 new_node->next = NULL;
 new_node->prev = NULL;
 
 if(*start == NULL) {
  *start = new_node;
  return;
 }

主函數新增第二個結點

int main(int argc, char* argv[])
{
 // create first node "head"
 Node *head = NULL;
 add_node(&head, 5);
 add_node(&head, 128);return 0; 
}

接著我們來新增第二個數值為 128 的結點，由於不是第一個結點，我們會找尋至這個雙向鏈結串列中的最後一個結點，找到的時候，如同單向鍊結串列那樣，目前的結點的下一個結點，就是 new_node，不一樣的是，目前的這個結點，將會成為 new_node的上一個結點 (new_node->prev = current;)

else {
  Node *current; 
  current = *start;
  while(current->next != NULL) {
   current = current->next;
  }
  current->next = new_node;
  new_node->prev = current;
  return;
 }

主函數新增第三個結點

int main(int argc, char* argv[])
{
 // create first node "head"
 Node *head = NULL;
 add_node(&head, 5);
 add_node(&head, 128);
 add_node(&head, 41);return 0; 
}

道理等同於新增第二個結點，所以此時整個雙向鏈結串列會如同下圖所示

印出整個雙向鏈結串列的函數: print_list

當我們新增完成後，現在我們就可以開始印出整個串列了

主函數程式

int main(int argc, char* argv[])
{
 // create first node "head"
 Node *head = NULL;
 add_node(&head, 5);
 add_node(&head, 128);
 add_node(&head, 41);print_list(head); return 0; 
}

print_list

其實原理就跟單向鏈結串列的原理是一樣的，當結點本身並不等同於 NULL 的時候，就印出來數值，直到最後整個串列結束為止

輸出結果

5 128 41

反向印出整個雙向鏈結串列的函數: inverse_print_list

雙向鏈結串列與單向最大的不一樣就是，結點可以回朔找尋到上一個結點為何，所以現在我們在主函數中，我們先宣告一個結點，並讓這個結點是整個串列中的最後一個結點，然後使用這一個結點回朔至第一個結點並印出整個反向的串列數值

主函數

int main(int argc, char* argv[])
{
 // create first node "head"
 Node *head = NULL;
 add_node(&head, 5);
 add_node(&head, 128);
 add_node(&head, 41); // print_list(head);
 
 Node *last = head;
 while(last->next != NULL) {
  last = last->next;
 }
 inverse_print_list(last);return 0; 
}

inverse_print_list

這裡我們傳進來的 node 已經是整個串列中的最後一個結點了，如果結點不等於 NULL ，印出來它的數值，然後再指向前一個結點，直到前一個結點也是指向 NULL 為止

輸出結果

41 128 5

釋放掉所有結點的記憶體

最後讓我們釋放掉所有的結點記憶體

主函數

int main(int argc, char* argv[])
{
 // create first node "head"
 Node *head = NULL;
 add_node(&head, 5);
 add_node(&head, 128);
 add_node(&head, 41);print_list(head);
 
 Node *last = head;
 while(last->next != NULL) {
  last = last->next;
 }
 inverse_print_list(last);
 
 free_list(head);return 0; 
}

free_list

整個完整程式的輸出結果

5 128 41 
41 128 5

小結

雙向鏈結串列對比單向鏈結串列多了一個指向前一個結點的 prev 功能，有了 prev 的指引，我們可以回朔找尋前方的結點，如此就不會發生到了下一個結點而無法再回去找尋前面資料的情況