第C語言實現(xiàn)帶頭雙向循環(huán)鏈表目錄前言1.創(chuàng)建結(jié)構(gòu)體2.malloc新節(jié)點3.創(chuàng)建哨兵位節(jié)點4.尾插5.打印6.尾刪7.頭插8.在指定位置pos的前面進行插入9.刪除指定位置pos節(jié)點10.銷毀鏈表

前言

在實際生活中最常用的就是這兩種鏈表。無頭單向非循環(huán)鏈表。和帶頭雙向循環(huán)鏈表。

無頭單向非循環(huán)鏈表：結(jié)構(gòu)簡單，一般不會單獨用來存數(shù)據(jù)。實際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。

帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復雜，一般用在單獨存儲數(shù)據(jù)。實際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。另外這個結(jié)構(gòu)雖然結(jié)構(gòu)復雜，但是使用代碼實現(xiàn)以后會發(fā)現(xiàn)結(jié)構(gòu)會帶來很多優(yōu)勢，實現(xiàn)反而簡單了，后面我們代碼實現(xiàn)了就知道了。

1.創(chuàng)建結(jié)構(gòu)體

注意：typedef起作用是在第7行哦。所以第5,6還需要寫structListNode類型。

typedefintLNDataType;

typedefstructListNode

structListNode*prev;

structListNode*next;

LNDataTypeval;

2.malloc新節(jié)點

注意：需判斷新開辟的節(jié)點是否為空。

//申請一個新節(jié)點

LN*BuynewNode(LNDataTypex)

LN*newNode=(LN*)malloc(sizeof(LN));

if(newNode==NULL)

printf("mallocfail");

exit(-1);

newNode-next=NULL;

newNode-prev=NULL;

newNode-val=x;

returnnewNode;

3.創(chuàng)建哨兵位節(jié)點

注意：這里因為需要改變plist指針的內(nèi)容，也就是改變plist指針的指向，所以需要傳遞plist的地址。

一句話就是：需要改變誰的內(nèi)容，就傳誰的地址。

這里有一點非常巧非常妙，就是phead的后繼和前驅(qū)都是指向自己（phead），這里是模仿C++STL庫里的哨兵位節(jié)點。

只能佩服想出來這些東西的大神。這樣設(shè)計哨兵位節(jié)點的話，后續(xù)尾插，尾刪，都特別的巧妙。

test.c

LN*plist=NULL;

ListNodeInit(plist);

List.h

//初始化節(jié)點

voidListNodeInit(LN**pphead)

LN*newNode=BuynewNode(0);

*pphead=newNode;

(*pphead)-next=*pphead;

(*pphead)-prev=*pphead;

4.尾插

注意：需要斷言的原因是因為，即使鏈表沒有一個節(jié)點，那鏈表至少還有個頭，所以phead肯定不為空。

這里沒有傳地址的原因是因為，你不需要改變plist的指向，你改變的是plist指向的結(jié)構(gòu)體里面的值。

多個節(jié)點尾插的情況如圖。

一個節(jié)點的尾插。

//尾插

voidListNodePushBack(LN*phead,LNDataTypex)

assert(phead);

LN*newNode=BuynewNode(x);

LN*tail=phead-prev;

tail-next=newNode;

newNode-prev=tail;

newNode-next=phead;

phead-prev=newNode;

5.打印

注意：因為帶個頭，所以cur從第二個位置開始。

//打印

voidListNodePrint(LN*phead)

LN*cur=phead-next;

while(cur!=phead)

printf("%d",cur-val);

cur=cur-next;

printf("\n");

6.尾刪

注意不能刪掉頭結(jié)點，free掉頭結(jié)點的話會造成野指針，再次訪問時會造成非法訪問。

所以要用assert斷言不為首節(jié)點。

//尾刪

voidListNodePopBack(LN*phead)

assert(phead);

assert(phead-next!=phead);

LN*tail=phead-prev;

LN*tailPrev=tail-prev;

free(tail);

tail=NULL;

phead-prev=tailPrev;

tailPrev-next=phead;

7.頭插

最好用next記錄下一個節(jié)點。這樣方便，思路清晰

//頭插

voidListNodePushFront(LN*phead,LNDataTypex)

assert(phead);

LN*newNode=BuynewNode(x);

LN*next=phead-next;

phead-next=newNode;

newNode-prev=phead;

newNode-next=next;

next-prev=newNode;

8.在指定位置pos的前面進行插入

一般情況

只有一個節(jié)點時。

兩種情況都適用以下代碼。

//指定位置前插入，極限是頭插

voidListNodeInsert(LN*pos,LNDataTypex)

if(pos==NULL)

printf("沒有找到這個數(shù)\n");

return;

LN*newNode=BuynewNode(x);

LN*tailPrev=pos-prev;

tailPrev-next=newNode;

newNode-prev=tailPrev;

newNode-next=pos;

pos-prev=newNode;

9.刪除指定位置pos節(jié)點

正常情況

極限尾刪

兩種情況都適用以下代碼。

//指定位置刪除

voidListNodeErease(LN*phead,LN*pos)

if(pos==phead||pos==NULL)

printf("pos指向頭，或為空\n");

return;

LN*posPrev=pos-prev;

LN*posNext=pos-next;

posPrev-next=posNext;

posNext-prev=posPrev;

free(pos);

pos=NULL;

10.銷毀鏈表

注意：這里相當于malloc用完之后的free。否則會造成內(nèi)存泄漏。

cur可以置空，但用處不大，因為cur是形參，形參是實參的一份臨時拷貝，形參置空并不能改變實參。外部的實參還是依舊能非法訪問到cur所指向的空間。

//鏈表銷毀

voidListNodeDestroy(LN*phead)

assert(phead);