引言

單鏈表結點中只有一個指向其后繼的指針，這使得單鏈表只能從頭結點依次順序地向后遍歷。若要訪問某個結點的前驅結點（插入、刪除操作時），只能從頭開始遍歷 ，訪問后繼結點的時間復雜度為 0(1），訪問前驅結點的時間復雜度為 O(n）。

為了克服單鏈表的上述缺點，引入了雙鏈表，雙鏈表結點中有兩個指針 prior 和 next， 分別
指向其前驅結點和后繼結點。如下圖：

雙鏈表的結點結構體

typedef struct DNode{ //定義單鏈表結點類型 ElemType data; //數據域 struct DNode *prior,*next; //前驅和后繼指針 }DNode, *DLinkList;

雙鏈表的操作

1.插入（方式不唯一）

① s->next=p->next;
② p->next->prior=s;
③ s->prior=p;
④ p->next=s;

注意：順序不唯一，可自行分析。但不能過早執行④ ，如果過早修改p的后繼，就會丟失a3，就無法建立a3和a5的關系

2.刪除

① p->next=q->next;
② q->next->prior=p;
③ free(q);

雙向鏈表的特點是節點可以可以輕易的訪問當前元素的前節點或后節點，相對單向鏈表每個節點多了一個前指針，因此相對要多一些空間的開銷。用空間換時間。

參考資料

王道數據結構

總結

以上是生活随笔為你收集整理的【数据结构】线性表的链式存储-双链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。