个人主页：欢迎大家光临——>沙漠下的胡杨
各位大帅哥，大漂亮
如果觉得文章对自己有帮助
可以一键三连支持博主
你的每一分关心都是我坚持的动力
☄： 本期重点：双向带头循环链表的实现
希望大家每天都心情愉悦的学习工作。
链表的属性上大体分为：单向和双向，带头和不带头，循环和不循环，这3个属性，一共6中，我们排列组合之后就是8种结构。
下面我们就看下个链表的另一个常用的结构,也是链表的终极形态啦，叫双向带头循环结构：
我们可以看到这个链表每个结点上都有4个关系线，比起单链表要麻烦多了，但是虽然结构麻烦，但是使用时很方便哦。
头文件的创建和初始化：
首先，我们创建链表时，要先明白这个链表的结构，它有前指针和后指针，和存放数据的区域，所以我们应该如下创建：
typedef int LTDataType;//类型重命名，方便修改数据类型 typedef struct ListNode { struct ListNode *next;//前指针 struct ListNode *prev;//后指针 LTDataType data; }LTNode;//链表重命名还有要用的头文件
#pragma once//防止头文件重复包含 #define _CRT_SECURE_NO_WARNINGS//禁止4996报错 #include <stdio.h> #include <stdlib.h> #include <stdbool.h>//使用布尔值引用的头文件 #include <assert.h>//断言头文件下面是函数的接口
LTNode* BuyListNode(LTDataType x);//创建结点 LTNode* ListInit();//初始化 void ListPrint(LTNode *phead);//打印 void ListPushBack(LTNode *phead, LTDataType x);//尾插 void ListPushFront(LTNode *phead, LTDataType x);//头插 void ListPopBack(LTNode *phead);//尾删 void ListPopFront(LTNode *phead);//头删 bool ListEmpty(LTNode* phead);//判断链表是否为空 // 在pos位置之前插入x void ListInsert(LTNode* pos, LTDataType x); // 删除pos位置的节点 void ListErase(LTNode* pos); int ListSize(LTNode* phead);//求链表的长度 void ListDestroy(LTNode* phead);//链表的销毁
源文件：函数接口的实现
我们一个个来看下函数接口的实现：
创建新的节点：
LTNode* BuyListNode(LTDataType x)//创建结点 { //开辟新的节点 LTNode * newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { perror("malloc fail");//开辟失败结束程序 exit(-1); } newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode;//最后返回节点。 }首先我们使用返回值的方式，不像单链表一样使用二级指针的形式，是因为双向带头循环链表的头结点不会改变，所以没必要使用二级指针。我们单单使用返回值就可以啦。
链表的初始化：
LTNode* ListInit()//初始化 { //创建头结点，赋值可以随意。 LTNode *phead = BuyListNode(-1); phead->next = phead;//把前后指针都指向自己 phead->prev = phead; return phead;//返回头结点，初始化完成。 }在链表初始化时，我们其实只是创建了一个头结点，把它的前后指针都指向自己，进而完成后续的操作，这里我们保证链表的整体统一，所以也使用了返回值的形式。
链表的打印：
void ListPrint(LTNode *phead)//打印 { assert(phead);//断言节点不为空 //保存下一个结点，进行遍历 LTNode *cur = phead->next; //从头结点的下一个开始遍历，到头结点结束 while (cur != phead) { printf("%d ", cur->data); cur = cur->next; } printf("\n"); }在链表的打印中，我们要注意的是，这个链表是循环的链表，所以不可以指直接遍历，否则会导致链表死循环，所以我们从链表的头结点的下一个结点进行遍历，到链表的头结点结束，刚好把链表遍历一遍。
链表的尾插：
void ListPushBack(LTNode *phead, LTDataType x)//尾插 { assert(phead); LTNode* newnode = BuyListNode(x); LTNode* tail = phead->prev;//找到尾节点 tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; }上面的链表的尾插，其实就是找到链表的头结点的后指针，进而找到尾节点，在创建一个新节点，然后把他们连接起来就好啦。示意图如下（图画的确实有点丑啦）
链表的头插：
void ListPushFront(LTNode *phead, LTDataType x)//头插 { assert(phead); LTNode* newnode = BuyListNode(x); LTNode* tail = phead->next;//找到第一个节点 phead->next = newnode; newnode->prev = phead; newnode->next = tail; tail->prev = newnode; }头插和尾插大同小异，头插我们要先找出第一个节点，就是头结点的后指针，然后我们进行插入连接就好啦，图示和尾插类似。
链表的尾删：
void ListPopBack(LTNode *phead)//尾删 { assert(phead); assert(!ListEmpty(phead));//判断链表不为空 LTNode* tail = phead->prev;//保存尾节点 tail->prev->next = phead; phead->prev = tail->prev; free(tail); tail = NULL; }链表的尾删也不难，我们先找到尾节点，接着我们对节点进行修改，把尾节点的前一个的后指针连接到头结点，接着把头结点的前指针，连接到尾节点的前一个，最后free掉尾节点，把尾节点置NULL。
链表的头删：
void ListPopFront(LTNode *phead)//头删 { assert(phead); assert(!ListEmpty(phead)); LTNode* tail = phead->next; tail->next->prev = phead; phead->next = tail->next; free(tail); tail = NULL; }头删和尾删基本一样，就删除的结点不一样，我们只需要找到第一个结点就可以啦。
判断链表的是否为空：
bool ListEmpty(LTNode* phead)//判断链表是否为空 { assert(phead); return phead->next == phead;//判断是否为空 }我们一般判断链表为空时，我们采用的是 if 语句条件判断，看是否phead->next == phead这样进行判断，我们可以直接用 phead->next == phead 这个表达式的结果进行判断。
链表的长度：
int ListSize(LTNode* phead)//求链表的长度 { int size = 0; LTNode *cur = phead->next; while (cur != phead) { size++; cur = cur->next; } return size; }这个求链表的长度和打印链表的思路一致，我们不能直接遍历，所以我们保存头结点的下一个，然后进行遍历，一直到链表的头结点处遍历结束，最后我们返回size就可以啦。
链表的销毁：
void ListDestroy(LTNode* phead)//链表的销毁 { assert(phead); LTNode *cur = phead->next; while (cur != phead) { //头删前，要先保存下一个的结点。 LTNode* next = cur->next; ListPopFront(cur); cur = next; } free(phead); }链表的销毁中最值得注意的就是，我们在删除链表时必须要把删除前的下一个进行保存，这样不会导致访问不到，删除完成后，我们还要删除链表的头结点。
下面就进入最精华的部分，10分钟以内写出一个链表的关键：
// 在pos位置之前插入x void ListInsert(LTNode* pos, LTDataType x); // 删除pos位置的节点 void ListErase(LTNode* pos);关于上面两个函数的实现，就可以帮助我们同时写出 头删头插和尾删尾插 。
在pos位置之前插入x
void ListInsert(LTNode* pos, LTDataType x) { assert(pos);//断言pos不为NULL LTNode* tail = pos->prev;//找到pos结点的前一个。 LTNode* newnode = BuyListNode(x); tail->next = newnode; newnode->prev = tail; newnode->next = pos; pos->prev = newnode; }我们先判断pos不为NULL，然后找到pos结点的前一个，接着创建一个新节点，然后把这三个结点（pos pos->prev newnode ）进行连接就好啦。
删除pos位置的结点：
void ListErase(LTNode* pos) { assert(pos); LTNode* tailnext = pos->next;//找到pos的下一个结点 LTNode* tailprev = pos->prev;//找到pos的前一个结点 tailprev->next = tailnext; tailnext->prev = tailprev; free(pos); pos = NULL; }我们先找到pos的前 后 结点，接着我们进行连接这两个结点（pos->next pos->prev），最后free 掉pos结点，把pos结点处置为NULL。
头文件：
#pragma once #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <assert.h> typedef int LTDataType;//类型重命名，方便修改数据类型 typedef struct ListNode { struct ListNode *next;//前指针 struct ListNode *prev;//后指针 LTDataType data; }LTNode;//链表重命名 LTNode* BuyListNode(LTDataType x);//创建结点 LTNode* ListInit();//初始化 void ListPrint(LTNode *phead);//打印 void ListPushBack(LTNode *phead, LTDataType x);//尾插 void ListPushFront(LTNode *phead, LTDataType x);//头插 void ListPopBack(LTNode *phead);//尾删 void ListPopFront(LTNode *phead);//头删 bool ListEmpty(LTNode* phead);//判断链表是否为空 // 在pos位置之前插入x void ListInsert(LTNode* pos, LTDataType x); // 删除pos位置的节点 void ListErase(LTNode* pos); int ListSize(LTNode* phead);//求链表的长度 void ListDestroy(LTNode* phead);//链表的销毁函数实现的源文件：
#include "List.h" LTNode* BuyListNode(LTDataType x)//创建结点 { LTNode * newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; } LTNode* ListInit()//初始化 { LTNode *phead = BuyListNode(-1); phead->next = phead; phead->prev = phead; return phead; } void ListPrint(LTNode *phead)//打印 { assert(phead); LTNode *cur = phead->next; while (cur != phead) { printf("%d ", cur->data); cur = cur->next; } printf("\n"); } void ListPushBack(LTNode *phead, LTDataType x)//尾插 { assert(phead); //LTNode* newnode = BuyListNode(x); //LTNode* tail = phead->prev; //tail->next = newnode; //newnode->prev = tail; //newnode->next = phead; //phead->prev = newnode; ListInsert(phead->prev, x); } void ListPushFront(LTNode *phead, LTDataType x)//头插 { assert(phead); //LTNode* newnode = BuyListNode(x); //LTNode* tail = phead->next; //phead->next = newnode; //newnode->prev = phead; //newnode->next = tail; //tail->prev = newnode; ListInsert(phead->next, x); } void ListPopBack(LTNode *phead)//尾删 { assert(phead); assert(!ListEmpty(phead)); //LTNode* tail = phead->prev; // //tail->prev->next = phead; //phead->prev = tail->prev; //free(tail); //tail = NULL; ListErase(phead->prev); } void ListPopFront(LTNode *phead)//头删 { assert(phead); assert(!ListEmpty(phead)); //LTNode* tail = phead->next; //tail->next->prev = phead; //phead->next = tail->next; //free(tail); //tail = NULL; ListErase(phead->next); } bool ListEmpty(LTNode* phead)//判断链表是否为空 { assert(phead); return phead->next == phead; } // 在pos位置之前插入x void ListInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* tail = pos->prev; LTNode* newnode = BuyListNode(x); tail->next = newnode; newnode->prev = tail; newnode->next = pos; pos->prev = newnode; } // 删除pos位置的节点 void ListErase(LTNode* pos) { assert(pos); LTNode* tailnext = pos->next; LTNode* tailprev = pos->prev; tailprev->next = tailnext; tailnext->prev = tailprev; free(pos); pos = NULL; } int ListSize(LTNode* phead)//求链表的长度 { int size = 0; LTNode *cur = phead->next; while (cur != phead) { size++; cur = cur->next; } return size; } void ListDestroy(LTNode* phead)//链表的销毁 { assert(phead); LTNode *cur = phead->next; while (cur != phead) { LTNode* next = cur->next; ListErase(cur); cur = next; } free(phead); }
总的来说，这个链表的功能已经十分强大了，如果单独使用链表，我们就一般使用这个链表，虽然链表的结构上复杂些，但是我们写好以后的效率方面很高。在函数的接口方面，其实只要把任意位置的删除和插入写好，这个链表就完成了一大半了，所以在10分钟写一个链表是我完全OK的哦。
