🐸一、前言
在前面我们学习实现了单链表（无头单向不循环链表），这里我们引入带头双向循环链表
很明显这两种链表的结构截然不同，但都是作为链表最常使用链表结构
前者因其结构上的缺点而作为面试考题的常驻嘉宾，而且复杂麻烦
后者则是以结构最优著称，实现起来也是非常的简单（少了单链表头节点，尾节点，前一节点等问题的困扰），可以说是最屌的链表结构🤭
🐸二、链表的分类
🍄1. 单向或者双向链表
- 单向：节点结构中只存在下一节点的地址，所以难以从后一节点找到前一节点
- 双向：节点结构中存在前一节点和后一节点的地址，寻找前一节点和后一节点很便利
🍄2. 带头或者不带头链表
- 带头：在本来的头节点之前还有一个哨兵卫节点作为头节点，它的址域指针指向头节点，值域不做使用
- 不带头：没有哨兵卫头节点，在尾删尾插等问题中要考虑头节点的情况（局限）
🍄3. 循环或者非循环
- 循环：头节点会与尾节点相连
- 非循环：头节点不与尾节点相连
🍄4. 最常用链表
虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：
🔴无头单向非循环链表
🔴带头双向循环链表
- 🚩1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
- 🚩2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
🐸三、带头双向循环链表详解
🍎创建带头双向循环链表
🥰这里先创建三个文件：
1️⃣：List.h文件，用于函数的声明
2️⃣：List.c文件，用于函数的定义
3️⃣：Test.c文件，用于测试函数
建立三个文件的目的： 将链表作为一个项目来进行编写，方便我们的学习与观察。
⭕接口1：定义结构体（LTNode）
🥰请看代码与注释👇
//自定义类型 typedef int ListNodeDataType; //创建双向链表 typedef struct ListNode { struct ListNode* prev; //前址域 struct ListNode* next; //后址域 ListNodeDataType data; //值域 }LTNode;
⭕接口2：初始化（创建哨兵卫）（LTInit）
🥰请看代码与注释👇
//初始化（创建哨兵卫） LTNode* LTInit() { LTNode* phead = BuyLTNode(-1); //哨兵卫不存储有效值 phead->prev = phead; //初始化哨兵卫头节点址域 phead->next = phead; return phead; }
⭕接口3：打印（LTPrint）
🥰请看代码与注释👇
//打印 void LTPrint(LTNode* phead) { //断言传入指针不为NULL assert(phead); printf("guard<==>"); LTNode* cur = phead->next; while (cur != phead) { printf("%d<==>", cur->data); //打印数据 cur = cur->next; //找到下一个节点 } printf("\n"); }
⭕接口4：创建新结点（BuyLTNode）
🥰请看代码与注释👇
//创建新节点 LTNode* BuyLTNode(ListNodeDataType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { perror("malloc fail"); //失败打印错误信息并结束进程 return; } //初始化节点 newnode->data = x; newnode->prev = NULL; newnode->next = NULL; return newnode; }
⭕接口5：释放（LTDestroy）
🥰请看代码与注释👇
//释放 void LTDestroy(LTNode* phead) { //断言传入指针不为NULL assert(phead); LTNode* cur = phead->next; while (cur != phead) { LTNode* next = cur->next; //记录下一个节点地址 free(cur); //释放当前节点 cur = next; //找到下一个节点 } free(phead); }
⭕接口6：判空（LTEmpty）
🥰请看代码与注释👇
//判空 bool LTEmpty(LTNode* phead) { assert(phead); return phead->next == phead; //判断只剩哨兵卫头结点的情况 }
