💛 前情提要💛

本章节是数据结构的带头+双向+循环链表的相关知识~

接下来我们即将进入一个全新的空间，对代码有一个全新的视角~

以下的内容一定会让你对数据结构有一个颠覆性的认识哦！！！

❗以下内容以C语言的方式实现，对于数据结构来说最重要的是思想哦❗

以下内容干货满满，跟上步伐吧~

---

作者介绍：

🎓 作者： 热爱编程不起眼的小人物🐐
🔎作者的Gitee：代码仓库
📌系列文章&专栏推荐：

1. 🐶《刷题特辑》—实现由小白至入门者的学习记录_专栏

2. 😺C语言学习【小白->入门】_全过程_专栏

3. 【数据结构】顺序表（增、删、查、改）的实现 [初阶篇_ 复习专用]

4. 【数据结构】单链表（增、删、查、改）的实现 [初阶篇_ 复习专用]

📒我和大家一样都是初次踏入这个美妙的“元”宇宙🌏 希望在输出知识的同时，也能与大家共同进步、无限进步🌟

---

📌导航小助手📌

• 💡本章重点
• 🍞一.链表的概念
• • 🥐Ⅰ.什么是链表
  • 🥯Ⅱ.总结
• 🍞二.带头+双向+循环链表
• • 🥐Ⅰ.结构
  • 🥐Ⅱ.优势
  • 🥐Ⅲ.实现
• 🍞三.链表插口实现
• • 🥐Ⅰ.链表初始化
  • 🥐Ⅱ.创建新结点
  • 🥐Ⅲ.尾插链表
  • 🥐Ⅳ.头插链表
  • 🥐Ⅴ.尾删链表
  • 🥐Ⅵ.头删链表
  • 🥐Ⅶ.查找链表结点
  • 🥐Ⅷ.任意位置删除元素
  • • 🧇1.【复用】头删函数
    • 🧇2.【复用】尾删函数
  • 🥐Ⅸ.任意位置前插入结点
  • • 🧇1.【复用】头插函数
    • 🧇2.【复用】尾插函数
  • 🥐Ⅹ.判断链表是否为NULL
  • 🥐Ⅺ.统计链表有效结点个数
  • 🥐Ⅻ.打印链表
  • 🥐XIII.销毁链表
  • 🥯XIV.总结
• 🫓总结

---

💡本章重点

• 链表的概念

• 带头+双向+循环链表的结构

• 带头+双向+循环链表的优势

• 带头+双向+循环链表的实现

---

🍞一.链表的概念

🥐Ⅰ.什么是链表

• 链表是一种物理存储结构上非连续、非顺序的存储结构

• 数据元素的逻辑顺序是通过链表中的指针链接次序实现的

❗综上：

• 链表也符合我们在顺序表中提及的线性表，即链表也是线性表的一种

🥯Ⅱ.总结

✨综上：就是链表的概念啦~

➡️简单来说：链表是逻辑结构上类似于顺序表的连续的结构，但实际物理结构是不一定连续存储的

🔍以上内容可考古上篇：【数据结构】单链表（增、删、查、改）的实现 [初阶篇_ 复习专用]

---

但今天，我们终点来看看链表的终极形态：带头+双向+循环链表

---

🍞二.带头+双向+循环链表

🥐Ⅰ.结构

逻辑结构

🥐Ⅱ.优势

💡通过上图，我们可知： 双向带头循环链表

• 1️⃣带头：带有头结点（哨兵位），头结点一般不存储值，只存指向下一个（上一个）结点的地址

• 2️⃣双向：每一个结点既有前驱指针（Prev）又有后驱指针（Next）

• 3️⃣循环：链表的逻辑结构整体上是循环的

➡️简单来说

带头双向循环链表较单链表的优势在于：

🔴单向与双向

• 单链表仅仅仅仅只能通过访问后驱指针（Next）从一个方向【由头到尾】去访问每个结点，难以从某个结点去访问回上一个结点

• 而双向链表因为同时具有前、后驱指针，便可以很灵活地访问任意结点的上一个结点

🟢带头与不带头

• 若不带头结点，每次对链表执行操作时，都通过第一个结点开始操作，很容易误判链表一&二级指针接收的问题【即是否需要改头指针指向的问题】

• 若带上头结点，就没有上述的问题出现了，因为头指针永远是指向头结点，头指针的指向不会发生改变，就无需担心上述问题了

关于一级指针or二级指针接收相关问题详解，可点击跳转

🟡循环

• 链表的循环结构是由双向【前、后驱指针】这个特点形成的

👉综上：

• 因为带有双向+循环结构，此时的头结点也是可以看作最后一个结点的，因为最后一个结点的next指向的就是head

✨有了以上对链表的概念后，我们便可以实现它啦~

🥐Ⅲ.实现

💡结点： 我们所创建的结点都是从堆区上申请空间的

➡️简单来说： 使用动态开辟在堆区上开辟一个结点的空间

Tips: 关于动态开辟不熟悉的同学可以跳转去🔍【C语言】动态内存管理 [进阶篇_ 复习专用]查看呀

typedef int LTDataType;typedef struct ListNode{struct ListNode* next;struct ListNode* prev;LTDataType data;}ListNode;

👉由上述我们可知：

结点本质是结构体类型，结构体内包含了数据域、前驱指针、后驱指针域

• LTDataType data;用来存储数据

• struct ListNode* next;是用来指向下一个结点

• struct ListNode* prev;是用来指向上一个结点

✨综上：

• 链表可以根据存储的数据多少实现随时创建结点【动态开辟】进行链接，不会存在空间的浪费

• 所以下面我们实现链表的接口

❗此处我们实现的是基础的带头双向循环链表

---

🍞三.链表插口实现

对于数据结构的接口实现，一般围绕增、删、查、改的内容

💡如下的实现围绕此原码进行：

//创建头结点//头指针指向头结点ListNode* plist = ListInit();

🥐Ⅰ.链表初始化

❗特别注意：

• 与单链表不同，因为带头双向循环链表的头指针指向的是头结点（哨兵位）而非第一个结点，所以需要对头指针进行初始化

• 但单链表是不需要初始化的，头指针是直接指向第一个结点，即直接指向新创建的结点

1️⃣链表初始化的函数声明：

ListNode* ListInit();

2️⃣链表初始化函数的实现：

ListNode* ListInit() {ListNode* phead = BuyListNode(0);phead->next = NULL;phead->prev = NULL;return phead;}

🥐Ⅱ.创建新结点

1️⃣创建新结点的函数声明：

ListNode* BuyListNode(LTDataType x)

2️⃣创建新结点函数的实现：

ListNode* BuyListNode(LTDataType x){ListNode* node = (ListNode*)malloc(sizeof(ListNode));node->next = NULL;node->prev = NULL;node->data = x;return node;}

🥐Ⅲ.尾插链表

👉简单来说： 对链表尾部链接一个新的结点

➡️实现： 因为结构的优势，可以直接通过访问头结点（pHead）的Prev找到最后一个结点【就不需要像单链表找尾需要遍历】，将此最后一个结点的next指向新的结点

❗特别注意： 当链表为NULL（空表）的时候，尾插即是在头插

✊图例：

1️⃣尾插的函数声明：

void ListPushBack(ListNode* phead, LTDataType x);

2️⃣尾插函数的实现：

void ListPushBack(ListNode* phead, LTDataType x){assert(phead);//找尾ListNode* tail = phead->prev;ListNode* newnode = BuyListNode(x);//插入尾部==四个指针的链接//如上图所示tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;}

🥐Ⅳ.头插链表

👉简单来说： 对链表头部链接一个结点

➡️实现： 直接插入到头结点之后

❗特别注意：

• 即使是NULL（空表），也可以实现头插

• 注意插入顺序，如果顺序反了，会丢失后面结点的地址，找不到后面结点

✊图例：

1️⃣头插的函数声明：

void ListPushFront(ListNode* phead, LTDataType x);

2️⃣头插函数的实现：

void ListPushFront(ListNode* phead, LTDataType x){assert(phead);ListNode* first = phead->next;ListNode* newnode = BuyListNode(x);以下代码通用于： 只有一个 头结点的时候，也是可以的体现了结构的优势phead->next = newnode;newnode->prev = phead;newnode->next = first;first->prev = newnode;}

🥐Ⅴ.尾删链表

👉简单来说： 对链表删除最后一个结点

➡️实现： 找到尾结点的上一个结点，并将尾结点释放掉，再将上一结点与头结点相链接

❗特别注意：

• 只有一个头结点的时候，即链表为NULL，不可以进行尾删

✊图例：

1️⃣尾删的函数声明：

void ListPopBack(ListNode* phead);

2️⃣尾删函数的实现：

void ListPopBack(ListNode* phead){assert(phead);assert(phead->next != phead);ListNode* tail = phead->prev; //找尾ListNode* tailPrev = tail->prev;free(tail);tailPrev->next = phead;phead->prev = tailPrev;}

🥐Ⅵ.头删链表

👉简单来说： 对链表删除第一个结点

➡️实现： 记住链表的第二个结点，然后释放头结点，让第二个结点链接头结点

❗特别注意：

• 只有一个头结点的时候，即链表为NULL，不可以进行头删

✊图例：

1️⃣头删的函数声明：

void ListPopFront(ListNode* phead);

2️⃣头删函数的实现：

void ListPopFront(ListNode* phead){assert(phead);assert(phead->next != NULL);ListNode* newhead = phead->next->next;ListNode* del = phead->next;free(del);del = NULL; //不置空问题也不大，因为出了这个函数 这个参数就销毁了 phead->next = newhead;newhead->prev = phead;ListErase(phead->next);}

🥐Ⅶ.查找链表结点

👉简单来说： 对链表进行查找所需的结点

➡️实现： 遍历链表表一一比较查找是否有我们想要的结点

• 没有,则返回NULL

• 有，则返回当前结点的地址

1️⃣查找链表结点的函数声明：

ListNode* ListFind(ListNode* phead, LTDataType x);

2️⃣查找链表结点函数的实现：

ListNode* ListFind(ListNode* phead, LTDataType x){//遍历一遍去找assert(phead);ListNode* cur = phead->next;while (cur != phead->prev){if (cur->data = x){return cur;}else{cur = cur->next;}}return NULL;}

🥐Ⅷ.任意位置删除元素

👉简单来说： 对链表的某个位置进行删除

➡️实现： 释放掉需要删除的结点，并将其前后结点链接在一起

💥特别注意： 删除的位置要在顺序表有效个数的范围内

1️⃣任意位置删除元素的函数声明：

void ListErase(ListNode* pos);

2️⃣任意位置删除元素函数的实现：

void ListErase(ListNode* pos){assert(pos);ListNode* prev = pos->prev;ListNode* next = pos->next;prev->next = next;next->prev = prev;free(pos);}

💡有了任意位置删除元素函数的实现，我们的头删、尾删函数便可以复用这个函数来实现了

🧇1.【复用】头删函数

👉复用任意位置删除函数的头删函数的实现：

void ListPopBack(ListNode* phead){ListErase(phead->prev);}

🧇2.【复用】尾删函数

👉复用任意位置删除函数的尾删函数的实现：

void SeqListPopBack(SeqList* pq){SeqListErase(pq, pq->size - 1);}

🥐Ⅸ.任意位置前插入结点

👉简单来说： 对链表的某个位置前进行插入

➡️实现： 找到要前插的结点位置，将新的结点插入并与前插结点和被前插结点的上个结点链接

💥特别注意： 插入的位置为链表的实际范围内

1️⃣任意位置插入元素的函数声明：

void ListInsert(ListNode* pos, LTDataType x);

2️⃣任意位置插入元素函数的实现：

void ListInsert(ListNode* pos, LTDataType x){assert(pos);ListNode* prev = pos->prev;ListNode* newnode = BuyListNode(x);prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;}

💡有了任意位置插入元素函数的实现，我们的头插、尾插函数便可以复用这个函数来实现了

🧇1.【复用】头插函数

👉复用任意位置插入函数的头插函数的实现：

void ListPushFront(ListNode* phead, LTDataType x){ListInsert(phead->next, x);}

🧇2.【复用】尾插函数

👉复用任意位置插入函数的尾插函数的实现：

❗因为头节点（pHead）的上一个结点就是尾结点，所以可以用头结点的前插，当作尾插

void ListPushBack(ListNode* phead, LTDataType x){ListInsert(phead, x);}

🥐Ⅹ.判断链表是否为NULL

👉简单来说： 判断链表是否除了头结点还有其它结点

➡️实现： 只需要直接判断头结点的下一个结点是否为其它结点即可

• 链表为空：返回true

• 链表为非空：返回false

1️⃣判断链表是否为空的函数声明：

bool ListEmpty(ListNode* phead);

2️⃣判断链表是否为空函数的实现：

bool ListEmpty(ListNode* phead){assert(phead);return phead->next == phead ? true : false;}

🥐Ⅺ.统计链表有效结点个数

👉简单来说： 判断除头结点外的结点个数

➡️实现： 遍历链表统计即可

1️⃣统计链表有效结点个数的函数声明：

int ListSize(ListNode* phead);

2️⃣统计链表有效结点个数函数的实现：

int ListSize(ListNode* phead){assert(phead);ListNode* cur = phead->next;int count = 0;while (cur != phead){count++;cur = cur->next;}return count;}

🥐Ⅻ.打印链表

👉简单来说： 对链表逐个遍历打印

➡️实现： 遍历链表一一打印即可

❗特别注意：

• 因为不像单链表的结束标记是NULL，因为是循环结构，所以这里的结束标记为返回到头结点就结束

1️⃣打印链表的函数声明：

void ListPrint(ListNode* phead);

2️⃣打印链表函数的实现：

void ListPrint(ListNode* phead){ListNode* cur = phead->next;while (cur != phead)  {printf("%d ", cur->data);cur = cur->next;}printf("\n");}

🥐XIII.销毁链表

👉简单来说： 对链表进行销毁，释放内存空间

➡️实现： 逐一遍历链表结点，然后逐个释放,最后将头结点也释放即可

1️⃣销毁链表的函数声明：

void ListDestory(ListNode* phead);

2️⃣销毁链表函数的实现：

void ListDestory(ListNode* phead){assert(phead);ListNode* cur = phead->next;while (cur != phead){ ListNode* next = cur->next;free(cur);cur = next;}free(phead);}

🥯XIV.总结

✨综上：就是带头+双向+循环链表接口实现的内容啦~

➡️相信大家对带头+双向+循环链表有不一样的看法了吧🧡

---

🫓总结

综上，我们基本了解了数据结构中的 “带头+双向+循环链表” 🍭 的知识啦~~

恭喜你的内功又双叒叕得到了提高！！！

感谢你们的阅读😆

后续还会继续更新💓，欢迎持续关注📌哟~

💫如果有错误❌，欢迎指正呀💫

✨如果觉得收获满满，可以点点赞👍支持一下哟~✨