1.雙鏈表的初始化

初始化雙鏈表：首先通過malloc函數(shù)分配一個(gè)頭結(jié)點(diǎn)空間，通過判斷鏈表L是否為空來確定是否分配成功。將頭結(jié)點(diǎn)的prior永遠(yuǎn)指向NULL，頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)暫時(shí)沒有所以也指向NULL

boolInitDLinkList(DLinkList&L){L=(DNode*)malloc(sizeof(DNode));if(L==NULL)returnfalse;L->prior=NULL;L->next=NULL;retruntrue;}

1.1判斷雙鏈表是否為空

要想判斷雙鏈表是否為空，即判斷頭結(jié)點(diǎn)的next的指針是否為空

boolEmpty(DLinkListL){if(L->next==NULL)returnfalse;elsereturntrue;}

2.雙鏈表的插入

實(shí)現(xiàn)需求：在p結(jié)點(diǎn)之后插入s結(jié)點(diǎn)

2.1p結(jié)點(diǎn)不是最后一個(gè)結(jié)點(diǎn)

點(diǎn)擊加載圖片

分析步驟：

首先會(huì)把s結(jié)點(diǎn)指向p->next結(jié)點(diǎn)

p的后繼結(jié)點(diǎn)的前向指針指向s

s結(jié)點(diǎn)的前向指針指向p結(jié)點(diǎn)

p的后向指針指向s結(jié)點(diǎn)

點(diǎn)擊加載圖片

代碼實(shí)現(xiàn)：

boolInsertNextDNode(DNode*p,DNode*s){s->nest=p->next;p->next->prior=s;s->prior=p;p->next=s;}

2.2p結(jié)點(diǎn)是最后一個(gè)結(jié)點(diǎn)

點(diǎn)擊加載圖片

當(dāng)p結(jié)點(diǎn)是最后一個(gè)結(jié)點(diǎn)的時(shí)候，顯然這時(shí)候p->next=NULL,所以就需要對(duì)p->next->prior=s改良，判斷p結(jié)點(diǎn)是否有后續(xù)結(jié)點(diǎn)，從而判斷是不是需要修改p下一個(gè)結(jié)點(diǎn)的前向指針

if(p==NULL||S==NULL)returnfalse;s->next=p->next;if(p->next!=NULL)p->next->prior=s;

3.雙鏈表的刪除

3.1刪除p的后繼節(jié)點(diǎn)

分析：和插入的思考方式一樣，同樣我們需要考慮p的后繼結(jié)點(diǎn)是否為NULL。

找到p的后繼結(jié)點(diǎn)

判斷p的后繼結(jié)點(diǎn)是否為NULL，為NULL即p沒有后繼

將p的下一個(gè)結(jié)點(diǎn)指向q的下一個(gè)結(jié)點(diǎn)

判斷q結(jié)點(diǎn)是否為最后一個(gè)結(jié)點(diǎn)

free(q)

代碼實(shí)現(xiàn)：

boolDeleteNextDNode(DNode*p){if(p==NULL)returnfalse;DNode*q=p->next;if(q==NULL)returnfalse;p->next=q->next;if(q->next!=NULL)q->next->prior=q;free(q);returntrue;}

3.2銷毀鏈表

實(shí)現(xiàn)步驟：

循環(huán)釋放各個(gè)數(shù)據(jù)結(jié)點(diǎn)

同時(shí)釋放頭結(jié)點(diǎn)

頭指針指向空

voidDestoryList(DLinkList&L){while(L->nex!=NULL)DeleteNextDNode(L);free(L);L=NULL;}

4.雙鏈表的遍歷

對(duì)結(jié)點(diǎn)p做相應(yīng)的處理，如打印

4.1后向遍歷

while(p!=NULL){p=p->next;}

4.2前向遍歷

while(p!=NULL){p=p->prior;}

4.3前向遍歷（跳過頭結(jié)點(diǎn)）

while(p->prior=NULL){p=p->prior;}

5.總結(jié)

修改指針的時(shí)候需要注意順序

雙鏈表可以很方便的找到給定結(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，對(duì)前驅(qū)節(jié)點(diǎn)執(zhí)行后插操作，這樣就可以實(shí)現(xiàn)按位序插入的前插操作。

雙鏈表不具備隨機(jī)存取特性，查找操作只能通過順序遍歷實(shí)現(xiàn)