單鏈表中只有一個指向其后繼結點的指針，使得單鏈表只能從前向后依次遍歷，若要訪問某個結點的前驅結點（或插入，刪除操作時），只能從頭開始遍歷，訪問后繼結點的時間復雜度為O(1)，而訪問前驅結點時，其事件復雜度為O(n)。 為了克服單鏈表的上述缺點，引入了雙鏈表。 ## 一.雙鏈表的定義 在雙鏈表中引入了兩個指針，分別為指向前驅結點的指針prior和指向后繼結點的指針next。如下圖所示：  對于雙鏈表結點的描述如下： ~~~ typedef struct DNode{ ElemType data; struct DNode *prior, *next; }DNode, *DLinkList; ~~~ 雙鏈表僅僅在單鏈表的基礎上增加了一個指向前驅的prior指針，因此，在雙鏈表執行按值查找和按位查找時的操作與單鏈表無異。但雙鏈表在插入和刪除操作的實現上與單鏈表相比有著較大的不同，因為在對“鏈”進行修改時不僅僅需要修改next指針域，此時還需要照顧到prior指針域，此時在操作時就必需保證在修改過程中不會斷鏈。此外雙鏈表可以很方便的找到其前驅結點，因此插入，刪除結點時的時間復雜度僅為O(1)。 ## 二.雙鏈表基本操作的實現 ### 2.1建立雙鏈表 #### 2.1.1頭插法建立雙鏈表 該方法中，首先建立一個具有頭結點的空雙鏈表，然后每生成一個讀取到數據的新節點，就將其放置到頭結點之后。如下圖所示：  算法描述如下： ~~~ DLinkList CreatList(DNode *head) { DNode *s; ElemType x; scanf("%d",&x); while(x!=999){ s=(DNode*)malloc(sizeof(DNode)); s->data=x; s->next=head->next; if(head->next){ head->next->prior=s; } s->prior=head; head->next=s; scanf("%d",&x); } return head; } ~~~ #### 2.1.2尾插法建立雙鏈表 該方法中同樣首先建立一個具有頭結點的空雙鏈表，然后每生成一個讀取到數據的新節點，就將它插入到表尾；為了達到這樣的目的，必須增加一個尾指針r，使其始終指向當前鏈表的尾結點。如下圖所示：  算法描述如下： ~~~ DLinkList CreatList(DNode *head) { DNode *s; DNode *r=head; ElemType x; scanf("%d",&x); while(x!=999){ s=(DNode*)malloc(sizeof(DNode)); s->next=NULL; s->data=x; r->next=s; s->prior=r; r=s; scanf("%d",&x); } r->next=NULL; return head; } ~~~ ### 2.2雙鏈表的插入操作 #### 2.2.1插入后繼結點 在雙鏈表p所指的結點之后插入結點*s，其指針的變化過程一定不能亂，否則會斷鏈，具體過程如下圖所示：  ~~~ void InsertDNode(DNode* p, ElemType x) { DNode *s; s=(DNode*)malloc(sizeof(DNode)); s->data=x; s->next=p->next; p->next->prior=s; s->prior=p; p->next=s; } ~~~ #### 2.2.2插入前驅結點 在雙鏈表p所指的結點之前插入結點*s，其指針的變化過程一定不能亂，否則會斷鏈，具體過程如下圖所示：  算法描述如下所示： ~~~ void InsertDNode(DNode* p, ElemType x) { DNode *s; s=(DNode*)malloc(sizeof(DNode)); s->data=x; s->next=p; p->prior->next=s; s->prior=p->prior; p->prior=s; } ~~~ ### 2.3雙鏈表的刪除操作 刪除雙鏈表中結點*p的后繼結點*q，其指針的變化過程如下圖所示：  算法描述如下： ~~~ void DelList(DNode *p) { DNode *q=p->next; p->next=q->next; q->next->prior=p; free(q); } ~~~