【初阶数据结构】深入解析带头双向循环链表:探索底层逻辑
原创
🔥引言
本篇将介绍带头双向循环链表底层实现以及在实现中需要注意的事项，帮助各位在使用过程中根据底层实现考虑到效率上问题和使用时可能会导致的错误使用
🌈个人主页： 是店小二呀
🌈C语言笔记专栏： C语言笔记
🌈C++笔记专栏： C++笔记
🌈初阶数据结构笔记专栏： 初阶数据结构笔记
🌈喜欢的诗句:无人扶我青云志 我自踏雪至山巅
一、前文
链表的分类有很多种，只需要将无头单向非循环链表和带头双向循环链表掌握，也就理解了剩下链表构成和实现。带头双向循环链表，结构复杂，一般只用于单独存储数据。但是也由于结构，带来了很多的优势，从而复杂结构，反而简单低实现。
二、实现带头双向循环链表
2.1 认识头节点
头节点(哨兵位)是指链表里面第一个节点，它不存放任何信息或存储任何有效元素，起到"放哨"作用，作用是减少了对一个节点是否为空的判断。
对于之前实现的单链表是不带哨兵位的，但是称第一个节点为头节点是不规范的，但是那样方便学习中称呼。
2.2 链表中节点成员
首先节点的成员:有效带数值，前驱指针，后继指针
- 前驱指针:以当前节点为参照物，向左就是前驱指针
- 后继指针：以当前节点为参照物，向右就是后继指针
typedef int LTDataType;//处理不同的数据类型
typedef struct SLTlistNode
{
LTDataType val;
struct SLTlistNode* next;
struct SLTlistNode* prev;
}SLNode;2.3 创建双向循环链表的节点
SLNode* CreatNewNode(LTDataType x)
{
SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
if (newnode == NULL)
{
perror("malloc fail!");
return ;
}
newnode->next = newnode;
newnode->prev = newnode;
newnode->val = x;
return newnode;
}这里需要注意的是:跟实现单链表的节点，大体相同。但是需要前驱指针，后继指针都指向自己设计为一个闭环，在插入中这样子的设计有很好的优势
2.4 双向循环链表的插入节点
2.4.1 双向循环链表的尾插
void SLTPushBack(SLNode* head, LTDataType x)
{
assert(head);
SLNode* newnode = CreatNewNode(x);
SLNode* tail = head->prev;//尾插，需要找到尾
tail->next = newnode;
newnode->prev = tail;
head->prev = newnode;
newnode->next = head;
}
这里需要注意的是:由于一开始哨兵位就是循环体，一开始创建指向尾的指针，也是指向自己，这种结构具有很好的优势，维持闭环的状态，在进行插入或删除操作时，提供了便利。当进行尾插时，需要找到尾，再进行尾插操作。
2.4.2 双向循环链表的头插
void SLTPushFront(SLNode* head, LTDataType x)//双向循环链表无空指针
{
assert(head);
if (head->next==head)
{
SLTPushBack(head, x);
}
else
{
SLNode* newnode = CreatNewNode(x);
SLNode* tail = head->prev;
head->next = newnode;
newnode->prev = head;
newnode->next = tail;
tail->prev = newnode;
}
}
这里需要注意的是 : 头插是值第一个有效数据节点前面插入，不是在哨兵位前面进行插入。当只有哨兵位存在时，这里跟尾插操作是一样的，剩下跟单链表的任意位置插入差不多，主要是改变指针的指向
2.5 双向循环链表的删除节点
2.5.1 双向循环链表的尾删
void SLTPopBack(SLNode* head)//哨兵位不删
{
assert(head);
assert(head->next!=head);
SLNode* tail = head->prev;
SLNode* tailprev = tail->prev;
tailprev->next = head;
head->prev = tailprev;
free(tail);
tail = NULL;
}
这里需要注意的是:哨兵位不参与对节点进行操作时，对此不对哨兵位进行删除操作。由于循环体虽然没有空指针，但是可能会出现野指针现象。可以不置空free(tail)，不对tail指向空间进行访问。
2.5.2 双向循环链表的头删
void SLTPopFront(SLNode* head)
{
assert(head);
SLNode* cur = head->next;
SLNode* curnext = cur->next;
if (head->next == head)
{
return 1;
}
else
{
head->next = curnext;
curnext->prev = head;
free(cur);
cur = NULL;
}
}
这里需要注意的是:哨兵位不参与对节点进行操作时，对此不对哨兵位进行删除操作。双向循环的优势在此体现出来了，只需在cur和curnext位置上处理。
2.6 双向循环链表的查找
SLNode* SLFind(SLNode* head, LTDataType x)
{
assert(head);
SLNode* cur = head->next;
while (cur!=head)
{
if (cur->val == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}这里需要注意的是:当cur==head时，说明cur遍历完了链表。如果没有符合的值，则表示不存在；反之返回该位置的指针。
2.7 实现双向循环链表任意位置的插入和删除
2.7.1 任意位置插入
void SLInsert(SLNode* head, SLNode* pos,LTDataType x)//之前插入
{
assert(head);
SLNode* posprve = pos->prev;
if (head->next == head)
{
SLTPushBack(head,x);
}
else
{
SLNode* newnode = CreateLTNode(x);
posprve->next = newnode;
newnode->prev = posprve;
pos->prev = newnode;
newnode->next = pos;
}
}这里需要注意的是:当不存在有效数据时，默认是尾插操作。具体实现逻辑，知道pos和posprev的地址，再通过改变指针完成链接
2.7.2 任意位置删除
void SLEmpty(SLNode* head, SLNode* pos, LTDataType x)
{
assert(pos != head);
assert(head);
SLNode* posprve = pos->prev;
SLNode* frist = posprve->prev;
if (cur->next == head)
{
SLTPopBack(head);
}
else
{
frist->next = pos;
pos->prev = frist;
free(posprve);
}
}
这里需要注意的是:哨兵位不参与对节点进行操作时，对此不对哨兵位进行删除操作。只存在一个有效数据时，只进行尾删操作即可。对于三个指针的位置关系，满足pos在两个指针之间
以上就是双向循环链表的核心接口，接下来实现一些实用小接口，丰富我们的双向循环链表
2.8 双向循环链表的打印
void SLTPrint(SLNode* head)
{
assert(head);
printf("哨兵位<->");
SLNode* cur = head->next;
while (cur != head )
{
printf("%d<->", cur->val);
cur = cur->next;
}
}2.9 双向循环链表的销毁
void SLDestroy(SLNode* head)
{
assert(head);
SLNode* cur = head->next;
//结束条件是什么，这里是无死角的-->先销毁哨兵位之外的空间
while (cur!=head)
{
SLNode* curnext = cur->next;
free(cur);
cur = curnext;
}
free(head);
}这里需要注意的是:先将除哨兵位之外的空间释放，最后在释放哨兵位
三、双向循环链表的好处
在实现过程中，我们清晰地知道，如果需要快速搭建一个链表，实现双向循环链表中任意插入、删除是很快的，这里利用到了结构特点。
以上就是本篇文章的所有内容，在此感谢大家的观看！这里是店小二初阶数据结构笔记，希望对你在学习初阶数据结构中有所帮助！
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
