😎前言
前面学习了单链表的结构，并且做了些许单链表的OJ练习，相信大家已经对单链表的结构了如指掌。因此，本章带来了与单链表同源的但拥有不同的结构的链表 — 带头双向循环链表供大家学习。
可能大家听到带头双向循环链表这个名字，就会认为该结构很复杂（的确很复杂，是链表当中结构最复杂的），肯定比单链表要难许多，说实在的，如果没有前面单链表的铺垫，直接上这个结构，那肯定挺难的。但现在我们有了单链表的基础，并且做了挺多单链表的题了，也就不用怕了。
实际上，带头双向循环链表只是 看起来难，听起来难，但它实现起来，比单链表简单多了。并且许多细节地方都不需要那么的繁琐。
注意：下面所说的头节点都是指那个哨兵位的头节点。
带头双向循环链表的初始化
既然是双向，也就是即指向前也指向后，因此每一个节点不光要存储一个数据，还要两个结构体指针，一个指针prev指向前，一个指针next指向后，也就是next指针指向下一个节点，prev指针指向前一个节点。按照这个形式由一个一个的节点组成的链表，就是双向的，这剔除了单链表的单向性。由此可知遍历这个双向链表不仅可以往后遍历，还可以往前遍历，这是不是方便了许多呢？
那循环在这是什么意思？循环就是链表的第一个节点的prev指向链表的最后一个节点，链表的最后一个节点的next指向链表的第一个节点，例如：
不带哨兵位的头节点的双向循环链表：
但是这里，我们讨论带头的双向循环链表。
为啥要带头呢？很简单，便于下面的一系列操作。想一下，如果没有哨兵位的头节点进行增删查改，遇到头删或者头插的话，此时需要更新一下头节点，既然要更新一下头节点，那就与单链表章节一样，需要用到二级指针，或者带返回值，这就很麻烦了。但如果带哨兵位头节点的话，二级指针和返回值都不需要用到，并且头删头插尾插尾删都特别的方便，它的优势处，下面会一一体现。
带头双向循环链表：
- 当然，有了前面的数据结构的学习，毫无疑问，这里也是需要三个文件来实现的，这里就不多说了，分别是
DList.h，DList.c，test.c - 有了上面的介绍，我们首先包含需要用到的头文件：
#include <stdio.h> // assert断言 #include <assert.h> // 动态内存函数所需 #include <stdlib.h> // 判空所需 bool 类型 #include <stdbool.h>
- 然后将节点的结构创建出来（两个指针一个数据）：
// 存储的数据的类型 typedef int LTDataType; typedef struct ListNode { // 存储数据 LTDataType _data; // 指向下一个节点的指针 struct ListNode* _next; // 指向前一个节点的指针 struct ListNode* _prev; }ListNode; // 重命名是为了方便
- 接着就是对各个函数接口一一实现了。各个函数接口的声明：（由于前面的与函数接口声明都在
.h文件，并且该文件只有这些，这里就直接放.h文件了）：
#include <stdio.h> // assert断言 #include <assert.h> // 动态内存函数所需 #include <stdlib.h> // 判空所需 bool 类型 #include <stdbool.h> // 带头+双向+循环链表增删查改实现 // 存储的数据的类型 typedef int LTDataType; typedef struct ListNode { // 存储数据 LTDataType _data; // 指向下一个节点的指针 struct ListNode* _next; // 指向前一个节点的指针 struct ListNode* _prev; }ListNode; // 重命名是为了方便 // 创建返回链表的头结点. ListNode* ListCreate(); // 得到一个结点 ListNode* BuyListNode(LTDataType x); // 双向链表清理 void ListClear(ListNode* phead); // 双向链表销毁 void ListDestory(ListNode* phead); // 双向链表打印 void ListPrint(ListNode* phead); // 判空 bool ListEmpty(ListNode* phead); // 双向链表尾插 void ListPushBack(ListNode* phead, LTDataType x); // 双向链表尾删 void ListPopBack(ListNode* phead); // 双向链表头插 void ListPushFront(ListNode* phead, LTDataType x); // 双向链表头删 void ListPopFront(ListNode* phead); // 双向链表在pos的前面进行插入 void ListInsert(ListNode* pos, LTDataType x); // 双向链表删除pos位置的节点 void ListErase(ListNode* pos); // 双向链表查找 ListNode* ListFind(ListNode* phead, LTDataType x); // 修改某一节点的数据 void ListModify(ListNode* pos, LTDataType x);
创造一个哨兵位头节点
- 我们首先得创造一个带哨兵位的头节点,这样才能进行后续的操作。
- 当然，我们每次创造的一个节点都是使用
malloc向内存申请一段空间来存储。 - 这里也是一样，我们向内存申请一个节点的空间后，将这个节点的两个指针都指向自己，并且里面的数据任意给（这里不做要求，也可以不给，它默认随机值，不过最好给-1），这样就得到一个哨兵位的头节点。有了该函数的功能，我们每次测试的时候，开始都要有这一步操作：
ListNode* plist = ListCreate(); // 将plist指向那个哨兵位头节点
下面是相关接口函数功能实现：
// 创建返回链表的头结点. ListNode* ListCreate() { // BuyListNode(),该函数是获取一个节点，下面有介绍，大概理解这样操作就欧克啦 ListNode* head = BuyListNode(-1); return head; }
得到节点
该函数在获取头节点函数和所有插入函数中都需要用到，因此这里把它抽离出来单独形成一个接口，以此来提高效率。
得到一个节点，那当然是在内存中申请一段空间，这个空间就作为新的那个节点的空间。
每次得到的这个节点，让它的两个指针都先指向自己，然后数据存放自己给出的值，之后将这个节点的地址返回即可，因为该节点的空间是在堆上的，函数栈帧销毁不会影响这段空间。
下面是相关接口函数功能实现：
// 得到一个结点 ListNode* BuyListNode(LTDataType x) { // 向内存中申请一个节点的空间 ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); // 判断一下是否申请失败 assert(newnode); // 将next和prev都指向自己 newnode->_next = newnode; newnode->_prev = newnode; // 存放自己给的数据 newnode->_data = x; // 返回这个节点的地址 return newnode; }
链表清理
- 当我们创建了一个带头双向循环链表后，不想要了但又还想继续操作怎么办👻？当然是将每个节点释放（
free）。
- 注意：清理是将每个有效的节点删除（释放），不会干掉头节点，因此，我们从头节点的下一个节点开始，向右遍历链表，一边遍历一边删除（所以这里需要创建一个节点指针来存放下一个节点的地址），直到最后遍历到头节点的时候结束操作。
下面是相关接口函数功能实现：
void ListClear(ListNode* phead) { // 避免传NULL的情况，phead是NULL就不能操作了 assert(phead); // 从phead的下一个节点开始操作 ListNode* cur = phead->_next; while (cur != phead) { // 存放当前节点的下一个节点的地址 ListNode* next = cur->_next; free(cur); cur = next; } }
链表销毁
我们在一系列操作后，一定要记得链表销毁，不然会出现内存泄漏的情况，尽管现在的编译器大部分都很明智了，会自动把申请的空间返还给操作系统。但是我们要养成这样一个好习惯，因此这里将该函数接口的实现放在前面。
销毁与清理可就不一样了，销毁是要将所有申请的空间释放，因此也就包括那个哨兵位的头节点。
前面已经实现了清理的函数，所以这里直接考虑复用清理的函数，最后再将头节点释放即可。
下面是相关接口函数功能实现：
// 双向链表销毁 void ListDestory(ListNode* phead) { // 判断phead是否是NULL assert(phead); // 复用 ListClear(phead); // 最后释放头节点 free(phead); }
打印链表
- 打印功能可以说必不可少，它在你进行操作的时候，可以直观的展现你进行了那些操作。
- 当然打印不需要打印头节点，你可以把头节点当作一个虚的。
- 因此这里需要从头节点的下一个节点开始依次打印，直到遍历链表遍历到头节点时结束打印。
下面是相关接口函数功能实现：
// 双向链表打印 void ListPrint(ListNode* phead) { assert(phead); // 从头节点的下一个开始 ListNode* cur = phead->_next; // 遍历到头结束 while (cur != phead) { // 打印当前节点的数据 printf("%d ", cur->_data); // 寻找下一个节点 cur = cur->_next; } printf("\n"); }
链表判空
- 这里还提供一个判空函数，这个判空是判断除头节点以外还有没有其它节点，如果没有，说明空，返回
true；如果有，说明不空，返回false。 - 如何来判？在前面初始化创建一个头节点时，将该节点的两个指针分别指向了自己，因此，当链表为空，没有其它节点的时候我们直接判断头节点的
next或者prev指针是否指向自己就好，如果是指向自己，说明为空，反之，不为空。 - 当在删除链表的节点的时候，判空会起到有效的作用。
下面是相关接口函数功能实现：
// 判空 bool ListEmpty(ListNode* phead) { assert(phead); // 判断头节点的next是否指向自己，判断prev也是可行的 return phead->_next == phead; }
链表尾插
- 链表的尾插，就是在链表的最后一个节点的后面连接一个节点，因此我们先要得到一个节点，然后找到链表的最后一个节点，再进行连接。
- 由于该链表是带头双向循环链表，既然是循环，要找到最后一个节点，那可是易如反掌。它不就是头节点的
prev嘛。 - 连接过程也是简简单单：
- 如果此时链表中没有有效的节点，那么此时直接得到一个节点与头节点连接即可，不需要考虑单链表章节是否要更新头指针的情况，这也体现了带头的优处。
下面是相关接口函数功能实现：
// 双向链表尾插 void ListPushBack(ListNode* phead, LTDataType x) { assert(phead); // 得到一个节点 ListNode* newnode = BuyListNode(x); // 存储最后一个节点的指针 ListNode* cur = phead->_prev; // 连接 cur->_next = newnode; newnode->_prev = cur; newnode->_next = phead; phead->_prev = newnode; }
