詳解C語言如何實現(xiàn)雙向帶頭循環(huán)鏈表

第詳解C語言如何實現(xiàn)雙向帶頭循環(huán)鏈表目錄一、雙向循環(huán)鏈表與順序表的區(qū)別二、List.h三、List.c1、帶頭雙向循環(huán)鏈表的初始化2、帶頭雙向循環(huán)鏈表的銷毀3、帶頭雙向循環(huán)鏈表的打印4、動態(tài)開辟一個節(jié)點5、帶頭雙向循環(huán)鏈表的判空6、帶頭雙向循環(huán)鏈表的尾插、尾刪7、帶頭雙向循環(huán)鏈表的頭插、頭刪8、帶頭雙向循環(huán)鏈表的長度9、帶頭雙向循環(huán)鏈表的查找、任意位置插入、刪除

一、雙向循環(huán)鏈表與順序表的區(qū)別

不同點順序表雙向帶頭循環(huán)鏈表在內(nèi)存中的存儲方式連續(xù)存儲不一定連續(xù)隨機訪問支持隨機訪問不支持隨訪問任意元素插入或刪除尾插O(1)，其他O(N)，可能需要挪動元素通過修改指針指向即可應(yīng)用場景元素高效存儲、頻繁訪問任意位置插入刪除頻繁三級緩存命中率高低

寄存器的速度遠(yuǎn)快于主存，所以需要三級緩存先將數(shù)據(jù)取出，寄存器讀取時將相鄰地址的數(shù)據(jù)進(jìn)行讀取，所以順序表內(nèi)存地址連續(xù)的特點使其三級緩存命中率高。

雙向帶頭循環(huán)鏈表雖然在鏈表中結(jié)構(gòu)最復(fù)雜，但是解決了單鏈表找前一個節(jié)點需要遍歷、要判斷頭結(jié)點是否為空的缺點。

二、List.h

#pragmaonce

#includestdio.h

#includeassert.h

#includestdbool.h

#includestdlib.h

typedefintListDateType;

typedefstructListNode

structListNode*next;

structListNode*prev;

ListDateTypedate;

}ListNode;

ListNode*ListInit();//初始化

voidListDestroy(ListNode*phead);//銷毀

voidPrintList(ListNode*phead);//打印

boolListEmpty(ListNode*phead);//判斷鏈表是否為空（只有頭節(jié)點）

voidListPushBack(ListNode*phead,ListDateTypex);//尾插

voidListPopback(ListNode*phead);//尾刪

voidListPushFront(ListNode*phead,ListDateTypex);//頭插

voidListPopFront(ListNode*phead);//頭刪

size_tListSize(ListNode*phead);//有效節(jié)點個數(shù)

ListNode*ListFind(ListNode*phead,ListDateTypex);//查找（可用于修改）

voidListInsert(ListNode*pos,ListDateTypex);//pos位置插入

voidListErase(ListNode*pos);//刪除pos位置

結(jié)構(gòu)體內(nèi)包含指向下一個節(jié)點的指針next、指向上一個節(jié)點的指針prev和本節(jié)點存儲的數(shù)據(jù)date

三、List.c

1、帶頭雙向循環(huán)鏈表的初始化

ListNode*ListInit()//初始化，返回帶哨兵位的頭結(jié)點

ListNode*guard=(ListNode*)malloc(sizeof(ListNode));

if(guard==NULL)

perror("ListInitfail:\n");

exit(-1);

guard-next=guard;

guard-prev=guard;

returnguard;

malloc一個哨兵位的頭結(jié)點，并將其next和prev指針置空。

2、帶頭雙向循環(huán)鏈表的銷毀

voidListDestroy(ListNode*phead)//銷毀，傳一級指針調(diào)用方需要在外部將頭結(jié)點指針置空

assert(phead);

ListNode*cur=phead-next;

while(cur!=phead)//釋放非頭結(jié)點

ListNode*next=cur-next;

free(cur);

cur=next;

free(phead);//再釋放頭結(jié)點

為了保持接口的一致性，形參用一級指針，所以需要調(diào)用者在外部對頭指針置空。

先釋放非頭結(jié)點，再釋放頭結(jié)點。

3、帶頭雙向循環(huán)鏈表的打印

voidPrintList(ListNode*phead)//打印

assert(phead);

ListNode*cur=phead-next;

while(cur!=phead)

printf("%d=",cur-date);

cur=cur-next;

printf("\n");

從頭結(jié)點的next開始，遍歷打印

4、動態(tài)開辟一個節(jié)點

ListNode*BuyNode(ListDateTypex)//動態(tài)開辟一個節(jié)點

ListNode*newnode=(ListNode*)malloc(sizeof(ListNode));

if(newnode==NULL)

perror("BuyNode:\n");

exit(-1);

newnode-date=x;

newnode-prev=NULL;

newnode-next=NULL;

returnnewnode;

將值放入這個節(jié)點，并將兩個指針置空

5、帶頭雙向循環(huán)鏈表的判空

boolListEmpty(ListNode*phead)//判斷鏈表是否只有頭節(jié)點

assert(phead);

returnphead-next==phead;

只有哨兵位這一個頭結(jié)點即為空

6、帶頭雙向循環(huán)鏈表的尾插、尾刪

voidListPushBack(ListNode*phead,ListDateTypex)//尾插

assert(phead);

ListNode*tail=phead-prev;

ListNode*newnode=BuyNode(x);

newnode-next=phead;

newnode-prev=tail;

tail-next=newnode;

phead-prev=newnode;

voidListPopback(ListNode*phead)//尾刪

assert(phead);

assert(!ListEmpty(phead));

ListNode*tail=phead-prev;

ListNode*prev=tail-prev;

free(tail);

prev-next=phead;

phead-prev=prev;

}

注意尾刪前需要判空

7、帶頭雙向循環(huán)鏈表的頭插、頭刪

voidListPushFront(ListNode*phead,ListDateTypex)//頭插

assert(phead);

ListNode*cur=phead-next;

ListNode*newnode=BuyNode(x);

newnode-next=cur;

newnode-prev=phead;

cur-prev=newnode;

phead-next=newnode;

voidListPopFront(ListNode*phead)//頭刪

assert(phead);

assert(!ListEmpty(phead));

ListNode*cur=phead-next;

ListNode*next=cur-next;

free(cur);

phead-next=next;

next-prev=phead;

}

注意頭刪前需要判空

8、帶頭雙向循環(huán)鏈表的長度

size_tListSize(ListNode*phead)//有效節(jié)點個數(shù)

assert(phead);

ListNode*cur=phead-next;

size_tcount=0;

while(cur!=phead)

cur=cur-next;

++count;

returncount;

循環(huán)計數(shù)即可，哨兵位不算

9、帶頭雙向循環(huán)鏈表的查找、任意位置插入、刪除

ListNode*ListFind(ListNode*phead,ListDateTypex)//查找（可用于修改）

assert(phead);

ListNode*cur=phead-next;

while(cur!=phead)

if(cur-date==x)

returncur;

cur=cur-next;

returnNULL;

voidListInsert(ListNode*pos,ListDateTypex)//pos位置之前插入

assert(pos);

ListNode*newnode=BuyNode(x);

ListNode*prev=pos-prev;

prev-next=newnode;

newnode-prev=prev;

newnode-next=pos;

pos-prev=newnode;

voidListErase(ListNode*pos)//刪除pos位置

assert(pos);