个人主页：欢迎大家光临——>沙漠下的胡杨
☄： 本期重点：双向带头循环链表的实现
希望大家每天都心情愉悦的学习工作。
☄： 本期重点：双向带头循环链表的实现
链表的8种结构：
双向带头循环的实现：
头文件的创建和初始化：
源文件：函数接口的实现
创建新的节点：
链表的初始化：
链表的打印：
链表的尾插：
链表的头插：
链表的尾删：
链表的头删：
判断链表的是否为空：
链表的长度：
链表的销毁：
如何10分钟之内写出一个链表呢？
在pos位置之前插入x
删除pos位置的结点：
整体代码展示
头文件：
函数实现的源文件：
带头双向循环链表总结：
链表的8种结构：
链表的属性上大体分为：单向和双向，带头和不带头，循环和不循环，这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 #include #include //使用布尔值引用的头文件#include //断言头文件下面是函数的接口
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位置之前插入xvoid 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分钟之内写出一个链表呢？
下面就进入最精华的部分，10分钟以内写出一个链表的关键：
// 在pos位置之前插入xvoid ListInsert(LTNode* pos, LTDataType x);// 删除pos位置的节点void ListErase(LTNode* pos);关于上面两个函数的实现，就可以帮助我们同时写出 头删头插和尾删尾插 。
在pos位置之前插入x
void ListInsert(LTNode* pos, LTDataType x){assert(pos);//断言pos不为NULLLTNode* 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 #include #include #include 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位置之前插入xvoid 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位置之前插入xvoid 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的哦。