一、带头双向循环链表的一些介绍
1.带头双向循环链表的逻辑结构
带头双向循环链表
2.为什么要学习带头双向循环链表
在单链表的实现中我们说：单链表是基础。那它为什么被我们叫基础呢？那是因为在实际使用过程中，由于单链表结构简单，一般不会单独用来存数据，实际中更多是作为其他数据结构的子结构。如哈希桶、图的邻接表等等。
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
3.带头双向循环链表节点的实现
整体逻辑与单链表相似，但是由于是是双向链表，所以我们在结构体中要再加上一个指向前一个节点的指针。
代码实现
typedef int SLDataType;//对类型进行改造，增加代码的可移植性 typedef struct ListNode { SLDataType data;//数据域中的数据 struct ListNode* prev;//指向前一个节点的指针 struct ListNode* next;//指向后一个节点的指针 }ListNode;
二、带头双向循环链表的实现
1.申请一个节点
与单链表中的操作类似，不过多讲解。
ListNode* BuyListNode(SLDataType e) { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); if (!newnode) { perror("malloc"); exit(-1); } newnode->data = e; newnode->prev = NULL;//新申请的前后指针都置为空指针，防止野指针的出现 newnode->next = NULL; return newnode; }
2.链表的初始化
由于我们要实现的链表要带头，而头节点不存储有效数据，只是起到指引作用并放便我们进行尾插，所以我们进行初始化先申请一个头节点，又由于我们是循环双向链表，所以头节点的前指针（prev）在没有数据时应该先指向自己，同理头节点的后指针（next）也应该指向自己。整个逻辑并不复杂，我们很容易实现。
头指针初始化后的结构
代码实现
ListNode* ListInit() { ListNode* phead = BuyListNode(-1); phead->prev = phead; phead->next = phead; return phead; }
3.链表的尾插
对于单链表，尾删需要遍历整个链表，但是对于循环双向链表，我们头节点前面不就是尾节点吗？所以尾删，对于我们也并不复杂了，先申请一个新节点
然后将尾节点的 next指针指向新节点，新节点的prev指针指向尾节点，这样就实现双向链接了，最后同样的方式处理一下头节点与新节点的链接关系就行了！
尾插前
尾插后
代码实现
void LTPushBack(ListNode* phead, SLDataType e) { assert(phead); ListNode* newnode = BuyListNode(e);//申请新节点 ListNode* tail =phead->prev;//找到尾节点 tail->next = newnode;//尾节点链接新节点 newnode->prev = tail;//新节点的prev指针指向尾节点，从而实现双向链接 newnode->next = phead;//新节点的next指针指向头节点 phead->prev = newnode;//头节点的prev指针指向新指针，完成双向链接 }
4.链表的尾删
尾删也很简单，我们可以通过头节点的prev指针找到尾指针，然后对尾节点使用prev指针找到倒数第二给节点，释放尾节点，改变链接关系就行了！
代码实现
void LTPopBack(ListNode* phead) { assert(phead); assert(phead->next != phead); ListNode* tail = phead->prev; tail->prev->next = phead; phead->prev = tail->prev; free(tail); }
5.链表的头插
头插也很简单，我们直接在头节点后面插入就行了，然后别忘了改变链接关系就行了！
void LTPushFront(ListNode* phead, SLDataType e) { ListNode* newnode = BuyListNode(e); newnode->next = phead->next; phead->next->prev = newnode; phead->next = newnode; newnode->prev = phead; }
6.链表的头删
头删也很不难的，我们直接在头节点后面删除就行了，然后别忘了改变链接关系就行了！
void LTPopFront(ListNode* phead) { assert(phead); assert(phead->next!=phead);//防止没有有效节点 ListNode* cur = phead->next; ListNode* follow = cur->next; phead->next = follow; follow->prev = phead; free(cur); }
7.链表的打印
打印也很简单，我们直接在遍历链表打印就行了，特别要注意的点就是链表打印的结束条件是尾节点的下一个节点不能是头节点。
void LTPrint(ListNode* phead) { assert(phead); ListNode* ptail = phead->next; while (ptail!= phead)//尾节点的下一个节点不能是头节点 { printf("%d ", ptail->data); ptail = ptail->next; } }
8.链表的查找
有了单链表的基础，查找也很简单，我们直接在遍历链表比对就行了，特别要注意的点就是链表比对的结束条件是尾节点的下一个节点不能是头节点。
ListNode* LTFind(ListNode* phead,SLDataType e) { assert(phead); ListNode* ptail = phead->next; while (ptail != phead) { if (ptail->data == e) { return ptail; } ptail = ptail->next; } return NULL; }
9.链表的插入(在pos之前插入)
我们可以通过链表的查找找到节点位置，然后正常插入就行了，最后别忘了改变链接关系就行了！
void LTInsert(ListNode* pos, SLDataType e) { assert(pos); ListNode* newnode = BuyListNode(e); ListNode* prev = pos->prev; prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode; }
10.删除pos位置
我们可以通过链表的查找找到节点位置，然后删除pos位置，就把pos位置的节点释放掉就行了，最后别忘了改变链接关系。
void LTErase(ListNode* pos) { assert(pos); pos->prev->next = pos->next; pos->next->prev = pos->prev; free(pos); }
11.链表的判空
只需要判断头节点的下一个节点是不是头节点就可以了。
bool LTEmpty(ListNode* phead) { return phead->next == phead; }
12.链表的长度
求链表的长度，只需要加一个统计变量然后向后遍历链表就行了，链表遍历的结束条件是尾节点的下一个节点不能是头节点。
size_t LTsize(ListNode*phead) { assert(phead); ListNode* cur = phead->next; size_t count = 0; while (cur != phead) { count++; cur = cur->next; } return count; }
13.链表的销毁
链表的销毁,只需要提前保存下一个节点，然后挨个释放就行了。
void LTDestroy(ListNode* phead) { ListNode* cur = phead->next; while (cur != phead) { ListNode* follow = cur->next; free(cur); cur = follow; } free(phead); }
14.函数汇总
头文件
#include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int SLDataType; typedef struct ListNode { SLDataType data; struct ListNode* prev; struct ListNode* next; }ListNode; //链表的初始化 ListNode* ListInit(); //申请一个节点 ListNode* BuyListNode(SLDataType e); //链表的尾插 void LTPushBack(ListNode*phead,SLDataType e); //链表的尾删 void LTPopBack(ListNode* phead); //链表的头插 void LTPushFront(ListNode*phead,SLDataType e); //链表的头删 void LTPopFront(ListNode* phead); //链表的打印 void LTPrint(ListNode* phead); //链表的查找 ListNode* LTFind(ListNode* phead,SLDataType e); //链表的插入(在pos位置之前) void LTInsert(ListNode* pos, SLDataType x); //删除pos位置 void LTErase(ListNode* pos); //链表的判空 bool LTEmpty(ListNode* phead); //链表的个数 size_t LTsize(ListNode* phead); //销毁链表 void LTDestroy(ListNode* phead);
函数实现文件
#include"List.h" //链表的初始化 ListNode* ListInit() { ListNode* phead = BuyListNode(-1); phead->prev = phead; phead->next = phead; return phead; } //申请一个节点 ListNode* BuyListNode(SLDataType e) { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); if (!newnode) { perror("malloc"); exit(-1); } newnode->data = e; newnode->prev = NULL; newnode->next = NULL; return newnode; } //链表的尾插 void LTPushBack(ListNode* phead, SLDataType e) { assert(phead); ListNode* newnode = BuyListNode(e); ListNode* tail =phead->prev; tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; } //链表的尾删 void LTPopBack(ListNode* phead) { assert(phead); assert(phead->next != phead); ListNode* tail = phead->prev; tail->prev->next = phead; phead->prev = tail->prev; free(tail); } //链表的头插 void LTPushFront(ListNode* phead, SLDataType e) { ListNode* newnode = BuyListNode(e); newnode->next = phead->next; phead->next->prev = newnode; phead->next = newnode; newnode->prev = phead; } //链表的头删 void LTPopFront(ListNode* phead) { assert(phead); assert(phead->next!=phead); ListNode* cur = phead->next; ListNode* follow = cur->next; phead->next = follow; follow->prev = phead; free(cur); } //链表的打印 void LTPrint(ListNode* phead) { assert(phead); ListNode* ptail = phead->next; while (ptail!= phead) { printf("%d ", ptail->data); ptail = ptail->next; } } //链表的查找 ListNode* LTFind(ListNode* phead,SLDataType e) { assert(phead); ListNode* ptail = phead->next; while (ptail != phead) { if (ptail->data == e) { return ptail; } ptail = ptail->next; } return NULL; } //链表的插入(在pos之前插入) void LTInsert(ListNode* pos, SLDataType e) { assert(pos); ListNode* newnode = BuyListNode(e); ListNode* prev = pos->prev; prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode; } //删除pos位置 void LTErase(ListNode* pos) { assert(pos); pos->prev->next = pos->next; pos->next->prev = pos->prev; free(pos); } //链表的判空 bool LTEmpty(ListNode* phead) { return phead->next == phead; } //链表的长度 size_t LTsize(ListNode*phead) { assert(phead); ListNode* cur = phead->next; size_t count = 0; while (cur != phead) { count++; cur = cur->next; } return count; } //链表的销毁 void LTDestroy(ListNode* phead) { ListNode* cur = phead->next; while (cur != phead) { ListNode* follow = cur->next; free(cur); cur = follow; } free(phead); }
结语
可以看出我们的带头循环双向链表在我们掌握单链表后并不难，只需要稍加改动就行了，由于有prev指针，我们可以随意访问节点了，这比单链表方便很多。
当然如果本篇文章有错误的地方，欢迎评论或私信讨论！那么我们下期见，byebye!
