详解C语言如何实现双向带头循环链表

第详解C语言如何实现双向带头循环链表目录一、双向循环链表与顺序表的区别二、List.h三、List.c1、带头双向循环链表的初始化2、带头双向循环链表的销毁3、带头双向循环链表的打印4、动态开辟一个节点5、带头双向循环链表的判空6、带头双向循环链表的尾插、尾删7、带头双向循环链表的头插、头删8、带头双向循环链表的长度9、带头双向循环链表的查找、任意位置插入、删除

一、双向循环链表与顺序表的区别

不同点顺序表双向带头循环链表在内存中的存储方式连续存储不一定连续随机访问支持随机访问不支持随访问任意元素插入或删除尾插O(1)，其他O(N)，可能需要挪动元素通过修改指针指向即可应用场景元素高效存储、频繁访问任意位置插入删除频繁三级缓存命中率高低

寄存器的速度远快于主存，所以需要三级缓存先将数据取出，寄存器读取时将相邻地址的数据进行读取，所以顺序表内存地址连续的特点使其三级缓存命中率高。

双向带头循环链表虽然在链表中结构最复杂，但是解决了单链表找前一个节点需要遍历、要判断头结点是否为空的缺点。

二、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);//判断链表是否为空（只有头节点）

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

voidListPopback(ListNode*phead);//尾删

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

voidListPopFront(ListNode*phead);//头删

size_tListSize(ListNode*phead);//有效节点个数

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

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

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

结构体内包含指向下一个节点的指针next、指向上一个节点的指针prev和本节点存储的数据date

三、List.c

1、带头双向循环链表的初始化

ListNode*ListInit()//初始化，返回带哨兵位的头结点

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

if(guard==NULL)

perror("ListInitfail:\n");

exit(-1);

guard-next=guard;

guard-prev=guard;

returnguard;

malloc一个哨兵位的头结点，并将其next和prev指针置空。

2、带头双向循环链表的销毁

voidListDestroy(ListNode*phead)//销毁，传一级指针调用方需要在外部将头结点指针置空

assert(phead);

ListNode*cur=phead-next;

while(cur!=phead)//释放非头结点

ListNode*next=cur-next;

free(cur);

cur=next;

free(phead);//再释放头结点

为了保持接口的一致性，形参用一级指针，所以需要调用者在外部对头指针置空。

先释放非头结点，再释放头结点。

3、带头双向循环链表的打印

voidPrintList(ListNode*phead)//打印

assert(phead);

ListNode*cur=phead-next;

while(cur!=phead)

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

cur=cur-next;

printf("\n");

从头结点的next开始，遍历打印

4、动态开辟一个节点

ListNode*BuyNode(ListDateTypex)//动态开辟一个节点

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

if(newnode==NULL)

perror("BuyNode:\n");

exit(-1);

newnode-date=x;

newnode-prev=NULL;

newnode-next=NULL;

returnnewnode;

将值放入这个节点，并将两个指针置空

5、带头双向循环链表的判空

boolListEmpty(ListNode*phead)//判断链表是否只有头节点

assert(phead);

returnphead-next==phead;

只有哨兵位这一个头结点即为空

6、带头双向循环链表的尾插、尾删

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、带头双向循环链表的头插、头删

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、带头双向循环链表的长度

size_tListSize(ListNode*phead)//有效节点个数

assert(phead);

ListNode*cur=phead-next;

size_tcount=0;

while(cur!=phead)

cur=cur-next;

++count;

returncount;

循环计数即可，哨兵位不算

9、带头双向循环链表的查找、任意位置插入、删除

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);