前一篇讲的单链表又可以被叫做不带哨兵位单向非循环链表，大家理解后再来看着篇文章会更加舒服哦
链接我就放这儿了单链表（C语言实现）感谢支持！
下面我们直接进入正文的讲解
1.带哨兵位双向循环链表的结构
带哨兵位双向循环链表的结构包含了一个数据域和两个指针域，它的特点就是通过指针域的指针指向下一个结点的地址来达到链式存储，另一个指针域的指针指向上一个结点达到能循环的效果，且头尾结点也会链接起来
typedef int DLTDataType;//数据类型 typedef struct DListNode { struct DListNode* next;//指向下一个结点的指针 struct DListNode* prev;//指向上一个结点的指针 DLTDataType data;//数据 }DLTNode;
图示：
这一结构看似麻烦，实则是一个完美结构，实现起来比单链表还要简单，且功能方面也会带来很多优势
下面我们拭目以待吧：
2.接口实现
2.1创建一个结点
带哨兵位双向循环链表是由一个个独立的结点链接起来的，新增节点时就需要向内存申请一个对应的结点空间
//创建一个结点 DLTNode* BuyDLTNode(DLTDataType x) { DLTNode* newnode = (DLTNode*)malloc(sizeof(DLTNode)); if (newnode == NULL)//防止申请失败 { perror("malloc fail"); exit(-1); } //赋值 newnode->data = x; newnode->next = NULL; newnode->prev = NULL; //这里置空后方便尾部结点不需要再进行置空操作 //返回新节点 return newnode; }
2.2初始化链表
创建哨兵位结点，并将其两个指针都指向自己（避免接下来涉及到与哨兵位的链接操作时不会出现空指针问题）
//初始化链表 DLTNode* DLTInit() { //创建哨兵位结点 DLTNode* phead = BuyDLTNode(-1); phead->next = phead; phead->prev = phead; return phead; }
2.3打印链表
遍历带哨兵位双向循环链表将其数据域打印出来，由于链表是循环的，所以再次回到哨兵位遍历就结束，断言哨兵位是为了防止没有初始化而直接向哨兵位传参NULL的情况
//打印链表 void DLTPrint(DLTNode* phead) { assert(phead); DLTNode* cur = phead->next; while (cur != phead) //cur指针遍历回到哨兵位就结束 { printf("%d->", cur->data); cur = cur->next; } printf("\n"); }
2.4尾插
首先创建一个新结点，由于头尾结点链接起来了，这里哨兵位的prev就是指向尾结点，先保存尾结点，再将尾结点与新结点链接起来，最后将新结点与头结点链接起来即可
//尾插 void DLTPushBack(DLTNode* phead, DLTDataType x) { assert(phead); DLTNode* newnode = BuyDLTNode(x); //保存尾结点 DLTNode* tail = phead->prev; //链接尾结点和新结点 tail->next = newnode; newnode->prev = tail; //链接头结点和新结点 newnode->next = phead; phead->prev = newnode; }
2.5尾删
首先找到尾结点，然后将尾结点的前一个结点保存起来，再将其与头结点链接，最后释放掉尾结点即可，这里需要断言只剩一个哨兵位的情况，当只剩一个哨兵位时就表示链表为空
//尾删 void DLTPopBack(DLTNode* phead) { assert(phead); //断言只有一个哨兵位的情况 assert(phead->next != phead); //找到尾结点 并保存其前一个结点 DLTNode* tail = phead->prev; DLTNode* tailPrev = tail->prev; //与头结点链接 tailPrev->next = phead; phead->prev = tailPrev; //释放尾结点 free(tail); //tail为局部变量，出作用域后无效，无需置空 }
2.6头插
这里的头插是在哨兵位之后插入，万万不可理解错了。首先创建一个新结点，再将新结点与哨兵位后一结点链接起来，最后再将新结点与哨兵位链接起来即可，当然也可以先将哨兵位后一结点记录下来，这样就无需考虑顺序了
//头插 void DLTPushFront(DLTNode* phead, DLTDataType x) { assert(phead); DLTNode* newnode = BuyDLTNode(x); //链接新结点与哨兵位后一结点 newnode->next = phead->next; phead->next->prev = newnode; //链接新结点与哨兵位 phead->next = newnode; newnode->prev = phead; //无需考虑顺序链接 //DLTNode* first = phead->next; //phead->next = newnode; //newnode->prev = phead; //newnode->next = first; //first->prev = newnode; }
2.7头删
首先保存哨兵位的后两个结点，然后释放掉第一个结点，最后再将哨兵位与其后面第二个结点链接起来即可，这里依旧需要断言只剩一个哨兵位不能删的情况
//头删 void DLTPopFront(DLTNode* phead) { assert(phead); //断言只有一个哨兵位的情况 assert(phead->next != phead); //保存哨兵位后两个结点 DLTNode* first = phead->next; DLTNode* second = first->next; //释放第一个结点 free(first); //链接哨兵位和第二个结点 phead->next = second; second->prev = phead; }
2.8查找
从哨兵位的下一个结点开始遍历查找，直到返回哨兵位结束，找到了返回其地址，反之则返回NULL，这里要断言只有一个哨兵位的情况，防止形成死循环
//查找 DLTNode* DLTFind(DLTNode* phead, DLTDataType x) { assert(phead); //只有一个哨兵位遍历会形成死循环 assert(phead->next != phead); //从哨兵位的下一个结点开始遍历查找 DLTNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { //找到了返回地址 return cur; } cur = cur->next; } //遍历完没找到返回NULL return NULL; }
2.9任意位置之前插入
首先创建一个新节点，并记录目标位置前一个结点的位置，再将前一个结点与新节点链接，最后将新节点与目标位置结点链接即可，这里需要断言一下pos，防止没找到目标位置（pos为NULL）的情况
//任意位置之前插入 void DLTInsert(DLTNode* pos, DLTDataType x) { assert(pos); DLTNode* newnode = BuyDLTNode(x); //记录目标位置前一个结点 DLTNode* Prev = pos->prev; //链接前一个结点和新节点 Prev->next = newnode; newnode->prev = Prev; //链接新节点和目标位置结点 newnode->next = pos; pos->prev = newnode; }
2.10任意位置删除
首先保存目标位置的前一个结点和后一个结点，然后释放掉目标位置结点，最后将目标位置的前后结点链接起来即可，当然这里也需要断言一下pos
//任意位置删除 void DLTErase(DLTNode* pos) { assert(pos); //记录前后结点 DLTNode* Prev = pos->prev; DLTNode* Next = pos->next; //释放目标位置结点 free(pos); //链接前后结点 Prev->next = Next; Next->prev = Prev; }
这里有个问题就是为什么单链表都需要传二级指针而带哨兵位双向循环链表都传一级指针呢？
这是因为单链表的头插和最后一个结点的删除都需要改变头结点的位置，改变一级指针需要二级指针来操作，而为了达到代码优美我们尽量传参的一致性，所以都传了二级指针，而带哨兵位双向循环链表已经有了哨兵位头结点，头结点并不会发生改变，所以只需要传一级指针即可
2.11链表判空
只有一个哨兵位时就为空链表
//链表判空 bool DLTEmpty(DLTNode* phead) { assert(phead); //只有一个哨兵位 return phead->next == phead; }
2.12求链表中结点个数
从哨兵位的下一个结点开始遍历链表，记录结点个数，直到回到哨兵位结束
//求链表中结点个数 size_t DLTSize(DLTNode* phead) { assert(phead); size_t size = 0; DLTNode* cur = phead->next; while (cur != phead)// 回到哨兵位结束 { cur = cur->next; size++; } return size; }
2.13销毁链表
从哨兵位的下一个结点遍历释放掉所有结点（先记录下一个结点的位置，然后释放该结点，再从下一个结点依次向后释放），回到哨兵位结束，最后释放掉哨兵位，由于局部变量在函数中置空出作用域后无效，无法置空，这里必须到主函数中手动置空
void DLTDestroy(DLTNode* phead) { assert(phead); DLTNode* cur = phead->next; while (cur != phead) { DLTNode* Next = cur->next; free(cur); cur = Next; } //释放哨兵位,局部变量在此不能置空，需到主函数手动置空 free(phead); }
释放哨兵位后，由于局部变量在函数中置空出作用域后无效，无法置空，这里必须到主函数中手动置空，如：
3.复用优化
既然我们写了任意位置之前插入和任意位置删除的接口,那么我们可以直接将其复用给头插尾插,头删尾删，下面让我们来对其进行优化
3.1头插尾插优化
头插：
在哨兵位后面一个位置的前一个位置插入即为头插
//头插 void DLTPushFront(DLTNode* phead, DLTDataType x) { assert(phead); //在哨兵位后面一个位置的前一个位置插入 DLTInsert(phead->next, x); }
尾插：
哨兵位前一个结点就是尾结点，在哨兵位前一个位置插入即为尾插
//尾插 void DLTPushBack(DLTNode* phead, DLTDataType x) { assert(phead); //在哨兵位前一个位置插入 DLTInsert(phead, x); }
3.2头删尾删优化
头删：
删除哨兵位的后一个结点即为头删
//头删 void DLTPopFront(DLTNode* phead) { assert(phead); //断言只有一个哨兵位的情况 assert(phead->next != phead); //删除哨兵位的后一个结点 DLTErase(phead->next); }
尾删：
哨兵位前一个结点就是尾结点，删除哨兵位的前一个结点即为尾删
//尾删 void DLTPopBack(DLTNode* phead) { assert(phead); //断言只有一个哨兵位的情况 assert(phead->next != phead); //删除哨兵位的前一个结点 DLTErase(phead->prev); }
4.链表和顺序表的区别
不同点 顺序表 链表
存储空间上 物理上一定连续 逻辑上连续，但物理上不一定连续
随机访问 支持O(1) 不支持
任意位置插入或删除元素 可能需要搬移元素，效率低O(N) 只需修改指针指向
插入 动态顺序表，空间不够时需要扩容 没有容量的概念
应用场景 元素高效率存储 + 频繁访问 任意位置插入和删除频繁
缓存利用率 高 低
带哨兵位双向循环链表到这里就介绍结束了，期待大佬们的三连！你们的支持是我最大的动力！
文章有写的不足或是错误的地方，欢迎评论或私信指出，我会在第一时间改正
