一.带头双向循环链表
链表的分类
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
怎么算出8种情况:每次两种情况，三次，所以是2*2*2=8。
1. 单向或者双向
2. 带头或者不带头
3. 循环或者非循环
虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：
1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结
构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表： 结构最复杂 ，一般用在单独存储数据。实际中使用的链表数据结构，都
是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带
来很多优势，实现反而简单了，后面我们代码实现了就知道了。
A.带头双向循环链表概念
带头双向循环链表（Doubly Circular Linked List with a Head）是一种链表数据结构，它具有以下特点：
- 头节点：带头双向循环链表包含一个头节点，它位于链表的起始位置，并且不存储实际数据。头节点的前驱指针指向尾节点，头节点的后继指针指向第一个实际数据节点。
- 循环连接：尾节点的后继指针指向头节点，而头节点的前驱指针指向尾节点，将链表形成一个循环连接的闭环。这样可以使链表在遍历时可以无限循环，方便实现循环操作。
- 双向连接：每个节点都有一个前驱指针和一个后继指针，使得节点可以向前和向后遍历。前驱指针指向前一个节点，后继指针指向后一个节点。
总结:带头双向循环链表可以支持在链表的任意位置进行插入和删除操作，并且可以实现正向和反向的循环遍历。通过循环连接的特性，链表可以在连续的循环中遍历所有节点，使得链表的操作更加灵活和高效。
B.带头双向循环链表的实现
1.带头双向循环链表的结构
typedef int LTDataType;//代码中将int定义为LTDataType是为了提供代码的可读性和可维护性，并增加代码的灵活性。 typedef struct ListNode { struct ListNode* next;//存储下一个节点的地址 struct ListNode* prev;//存储上一个节点的地址 LTDataType data; }LTNode;//重新命名结构体类型
通过将int定义为LTDataType，可以在代码中使用LTDataType作为数据类型，而不是直接使用int。这样做的好处有以下几点：
- 可读性：使用LTDataType作为数据类型可以使代码更具可读性。LTDataType作为一个自定义的数据类型名称，可以更好地表达代码中数据的含义和用途，提高代码的可理解性。
- 可维护性：将int定义为LTDataType可以方便地在代码中统一修改数据类型。如果将来需要将数据类型更改为其他类型，只需修改typedef语句中的定义，而不需要在整个代码中逐个修改具体的数据类型，减少了修改的工作量和出错的可能性。
- 灵活性：通过使用LTDataType，可以在代码中轻松更改数据类型，而不会对代码的其他部分产生影响。这种抽象化的方式可以使代码更具通用性，便于在不同的场景中重用。
2.动态申请节点函数
函数代码:
此函数是关于一个结点动态申请的实现，包含两个指针域，一个数据域。如果分配成功，它会返回指向该内存块起始位置的指针。你可以使用这个指针来访问和操作所分配的内存。如果分配失败，malloc会返回NULL指针，表示内存分配未成功。
LTNode* BuyLTNode(LTDataType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); //刚申请下的堆区空间有可能开辟失败，所以要进行检查 if (newnode == NULL) { perror("malloc fail"); return NULL; } //开辟好后就赋值 newnode->data = x; newnode->prev = NULL; newnode->next = NULL; return newnode; }
3.链表的初始化
链表的初始化就是要创建哨兵位的头节点,此头节点不存储有效数据，并且因一开始不知道指向谁，所以根据双向链表循环的特性，就让该结点的两个指针自己指向自己。
//初始化--因为要改动指向结构体的指针，所以要么就取地址，用二级指针接收。 //要么就像下面这样，用返回值接收。 LTNode* LTInit()// 由于形参phead是实参plist的拷贝 { LTNode* guard = BuyLTNode(-1); guard->next = guard; guard->prev = guard; return guard; } int main() { LTNode* plist = LTInit(); }
图解:
4.链表打印
打印链表就是,遍历链表的每一个结点的数据域，开始时用assert断言传过来的结点地址是否为NULL。接着cur用phead->next赋值的原因是，phead传过来的是哨兵位的头节点，它的下一位才是链表真正的头节点（有数据域），接着遍历链表，当cur指针回到哨兵位时，遍历结束。
函数代码:
void LTPrint(LTNode* phead) { assert(phead); printf("guard<==>"); LTNode* cur = phead->next; while (cur != phead) { printf("%d<==>", cur->data); cur = cur->next; } printf("\n"); }
5.链表尾部插入节点
与单链表有两个不一样的点:
情况一:
1.单链表尾插结点需要遍历全链表，当指针走到链表最后一个结点的时候，判断tail->next是否为NULL，若为NULL，则跳出遍历的循环，尾插新结点。然而带头双向循环链表不需要遍历链表，只需要对哨兵位的头节点的prev域解引用，直接找到带头双向循环链表的尾节点，尾插新节点。
情况二:
2.头指针的区别:带头双向循环链表不需要判断头指针是否指向NULL，因为哨兵位的头节点也是有它的地址的,添加新节点时只需要直接在尾节点尾插。然而单链表却需要判断头指针是否指向NULL，而且需要用到二级指针，比较棘手。
函数代码:
void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* tail = phead->prev;//通过哨兵位的头节点的prev找到链表最后一个结点，并用tail指向 LTNode* newnode = BuyLTNode(x); tail->next= newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; }
测试案例:
知识点:要改变一个变量的值，特别是传参传过去的，一定要注意是传值还是传址。如果是传值调用，那么传过去的函数(自定义的函数)参数就是形参，不会改变实参(main函数里面的就是实参)。如果传址调用，一般是取这个变量的地址，函数那边要用二级指针接收，并且函数(自定义函数)里面要有一层解引用，才能操作实参的值，给实参赋值，或者其它改变实参的操作。
malloc如果分配成功，它会返回指向该内存块起始位置的指针，意味着返回的是在堆上分配指定大小的内存块的地址，相等于取出内存块的地址，然后用一级指针接收，传一级指针过去，然后用结构体指针访问结构体成员的方式改变节点的值。
//初始化和尾插 void TestList1() { LTNode* plist = LTInit();//相等于取出内存块的地址，然后用一级指针接收，传一级指针过去，然后 用结构体指针访问结构体成员的方式改变节点的值。 LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); LTPushBack(plist, 4); LTPrint(plist); } int main() { TestList1(); }
实现思路:依旧是数字代表顺序
代码执行：
6.链表头部插入节点
请先看错误操作，请多注意！:
正确方法:
方法1：无需创建变量
图上的数字代表顺序
代码实现:
//方法一,不需要创建变量 void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = BuyLTNode(x); newnode->next = phead->next;//把头结点后面的d1的地址赋值给新结点的next phead->next->prev = newnode;//d1指向新节点 phead->next = newnode;//改变头节点的next，让它指向新结点 newnode->prev = phead;//新结点的prev指向phead头插完毕. }
方法2：创建变量first
图上的数字代表顺序
代码实现:
//方法二创建一个first变量 void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = BuyLTNode(x); LTNode* first = phead->next; phead->next = newnode; newnode->next = first; newnode->prev = phead; first->prev = newnode; }
代码执行:
