链表的介绍
链表的结构一共有八种：带头单向循环链表、带头单向非循环链表、带头双向循环链表、带头双向非循环链表、无头单向循环链表、无头单向非循环链表、无头双向循环链表、无头双向非循环链表。
今天我们来详解带头双向循环链表
带头双向循环链表是一种数据结构，它通过在双向链表的基础上增加循环的特性，并通过一个头结点（带头）来简化操作。这种结构在实际应用中有其独特的优缺点：
优点
- 双向遍历：链表可以从两个方向遍历，即可以向前或向后移动。这使得许多操作，如反转遍历、双端操作等，更为方便和高效。
- 循环特性：由于是循环链表，表尾与表头直接相连。这一特性使得从链表的一端到另一端的访问时间缩短，特别是在需要频繁执行环形遍历的场合（如轮转调度算法）。
- 统一操作：带头结点的链表简化了插入和删除节点的操作，因为不需要单独处理空链表的情况。头结点的存在使得链表始终非空，减少了边界条件的检查。
- 易于管理：头结点提供了一个固定的起点，无论链表是否为空，这使得链表的管理更为统一和方便。
缺点
- 额外的空间消耗：头结点本身不存储有效数据，占用一定的空间。对于内存使用极为严格的应用场景，这种额外消耗可能是一个缺点。
- 实现复杂度：相比单向链表，双向循环链表的实现更复杂。正确管理前驱和后继指针需要更多的注意和精确控制，增加了编程的难度。
- 性能开销：每次插入或删除操作都需要更新两个指针（前驱和后继），这比单向链表的操作稍显复杂，可能会略微增加时间开销。
- 循环错误：如果不正确管理节点的连接和断开，循环链表容易产生逻辑错误，如死循环或访问已删除的节点，这可能导致程序出错或崩溃。
链表详解
1. 链表的定义
实现步骤：
首先，我们还是需要先定义一个结点类型，与单向链表相比，双向链表的结点类型中需要多出一个前驱指针，用于指向前面一个结点，实现双向。
typedef int LTDataType;//存储的数据类型typedef struct ListNode
{LTDataType data;//数据域struct ListNode* front;//前驱指针struct ListNode* next;//后继指针
}ListNode;
2. 链表节点的创建
实现步骤：
- 内存分配：
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));这行代码通过malloc函数为一个新的ListNode结构体分配内存。sizeof(ListNode)确保分配足够的内存以存放一个ListNode结构体。 - 内存分配校验：
if (newNode == NULL) { ... }这个条件判断用来检查malloc是否成功分配了内存。如果malloc返回NULL，表示内存分配失败，可能是因为系统内存不足。这时，函数打印错误消息并返回NULL，避免后续的空指针操作。 - 初始化节点数据：
newNode->data = value;这行代码将传入的value赋值给节点的data属性。这样新节点就存储了它应该持有的数据。 - 自引用初始化：
newNode->front = newNode;和newNode->next = newNode;这两行代码初始化节点的front和next指针，使它们指向节点自身。这种初始化方式是为了创建一个独立的循环节点，即该节点在一个循环链表中既是头节点也是尾节点。
// 创建一个新的节点
ListNode* CreateNode(LTDataType value) {ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));if (node == NULL) {printf("Memory allocation failed.\n");return NULL;}newNode->data = value;newNode->front = newNode;newNode->next = newNode;return newNode;
}3. 链表的初始化
实现步骤：
对双向链表进行初始化，在初始化的过程中，需要申请一个头结点，头结点的前驱和后继指针都指向自己，使得链表一开始便满足循环。
// 初始化带头的双向循环链表
ListNode* InitList() {ListNode* phead = CreateNode(-1); // 创建头结点，数据通常设置为-1或其他标记值if (phead != NULL) {phead->front = phead; // 将头结点的前驱指针指向自身，确保循环链表的闭环性phead->next = phead; // 将头结点的后继指针指向自身，同样确保循环链表的闭环性}return phead; // 返回头结点的指针
}4. 链表的头插
实现步骤：
- 参数验证：
assert(phead);这行代码使用assert函数确保传入的头节点指针phead不是NULL。这是一种防御性编程实践，用于避免空指针引用。 - 创建新节点：
ListNode* newNode = CreateNode(value);这行代码调用CreateNode函数创建一个新的ListNode对象，其数据域设置为传入的value。这个函数返回一个初始化好的新节点，其front和next指针指向自己，形成一个独立的小循环。 - 定位第一个节点：
ListNode* Front = phead->next;这行代码获取头节点后面的第一个节点（我们称之为Front）。这是为了之后将新节点插入头节点和Front之间。 - 连接新节点与头节点：
phead->next = newNode;将头节点的next指针指向新节点，从而把新节点作为链表的第一个节点。newNode->front = phead;将新节点的front指针指向头节点，确保从新节点向前遍历可以回到头节点。 - 连接新节点与原第一个节点：
newNode->next = Front;将新节点的next指针指向原第一个节点Front，这样新节点就正确地插入在头节点和Front之间。Front->front = newNode;更新Front的front指针指向新节点，确保从Front向前遍历也可以到达新节点。
void ListPushFront(ListNode* phead, LTDataType value)
{assert(phead);ListNode* newNode = CreateNode(value);//申请一个结点，数据域赋值为valueListNode* Front = phead->next;//记录头结点的后一个结点位置//建立新结点与头结点之间的双向关系phead->next = newNode;newNode->front = phead;//建立新结点与front结点之间的双向关系newNode->next = Front; //这时候不能用phead了，因为pheadFront->front = newNode;
}
5. 链表的头删
实现步骤：
-
参数验证：
assert(phead);使用assert函数确保传入的头节点指针phead不是NULL。这一步防止后续代码在空指针上进行操作，可能导致程序崩溃。assert(phead->next != phead);确保链表中除头节点外还有其他节点。如果头节点的next指针指向自己，说明链表为空，此时不能进行删除操作。 -
定位节点：
ListNode* Front = phead->next;这行代码定位到链表的当前前端节点，即头节点后的第一个节点。ListNode* newFront = Front->next;获取当前前端节点的下一个节点，这将成为新的前端节点。 -
重建链接：
phead->next = newFront;更新头节点的next指针，直接指向newFront，从而绕过Front节点。newFront->front = phead;更新newFront的front指针，指向头节点，确保从新的前端节点向前遍历可以回到头节点。 -
释放内存：
free(Front);释放原前端节点Front所占的内存。这一步是必须的，以避免内存泄漏。
void ListPopFront(ListNode* phead)
{assert(phead);assert(phead->next != phead);ListNode* Front = phead->next;//记录头结点的后一个结点ListNode* newFront = front->next;//记录front结点的后一个结点//建立头结点与newFront结点之间的双向关系phead->next = newFront;newFront->front = phead;free(Front);//释放Front结点
}
6. 链表的尾插
实现步骤：
-
参数验证：
assert(phead);使用assert函数确保传入的头节点指针phead不是NULL。这个检查是为了防止在空指针上执行操作，这可能会导致程序崩溃。 -
创建新节点：
ListNode* newNode = CreateNode(value);这行代码调用CreateNode函数，创建一个新的ListNode对象，并将value设置为节点的数据。CreateNode函数返回一个已经初始化的新节点，它的front和next指针指向自己，形成一个独立的小循环。 -
定位尾节点：
ListNode* tail = phead->front;获取当前的尾节点，即头节点的前一个节点。 -
连接新节点与头节点：
newNode->next = phead;将新节点的next指针指向头节点，确保新节点成为链表的最后一个节点，其后继指向头节点。phead->front = newNode;更新头节点的front指针指向新节点，从而将新节点正式连接到链表的尾部。 -
连接新节点与原尾节点：
tail->next = newNode;将原尾节点的next指针指向新节点，这样原尾节点之后就是新节点了。newNode->front = tail;将新节点的front指针指向原尾节点，确保从新节点向前遍历可以到达原尾节点。
void ListPushBack(ListNode* phead, LTDataType value)
{assert(phead);ListNode* newNode = CreateNode(value);//申请一个结点，数据域赋值为xListNode* tail = phead->front;//记录头结点的前一个结点的位置//建立新结点与头结点之间的双向关系newNode->next = phead;phead->front = newNode;//建立新结点与tail结点之间的双向关系tail->next = newNode;newNode->front = tail;
}
7. 链表的尾删
实现步骤：
- 校验传入的头节点：使用
assert(phead)确保传入的头节点指针phead是有效的。这是为了防止空指针引用，确保链表至少被初始化。使用assert(phead->next != phead)确保链表不是空的（即链表中除了头节点之外还有其他节点）。这个检查是必要的，因为空链表（只有头节点指向自己）无法进行尾部删除操作。 - 定位尾部节点和新尾部节点：使用
ListNode* Tail = phead->front;定位到当前的尾部节点（即头节点的前一个节点Tail），这是要被移除的节点。使用ListNode* newTail = Tail->front;定位到新的尾部节点，即当前尾部节点的前一个节点newTail。 - 重建头节点与新尾部节点之间的链接：设置新尾部节点的
next指针指向头节点，即newTail->next = phead;，这样从新尾部节点向后遍历即可直接到达头节点。设置头节点的front指针指向新尾部节点，即phead->front = newTail;，这样从头节点向前遍历即可直接到达新尾部节点。 - 释放原尾部节点的内存：使用
free(Tail);释放原尾部节点Tail占用的内存。这一步是必须的，以避免内存泄漏。
void ListPopBack(ListNode* phead)
{assert(phead);assert(phead->next != phead);ListNode* Tail = phead->front;//记录头结点的前一个结点ListNode* newTail = Tail->front;//记录tail结点的前一个结点//建立头结点与newtail结点之间的双向关系newTail->next = phead;phead->front = newTail;free(Tail);//释放Tail结点
}
8. 在pos位置插入节点
实现步骤：
- 校验传入的节点指针：使用
assert(pos)确保传入的节点指针pos是有效的。这一步骤防止空指针引用，保证程序的健壮性。 - 定位前驱节点：使用
ListNode* before = pos->front;获取pos节点的前一个节点before。这样做是为了接下来将新节点插入到before和pos之间。 - 创建新节点：调用
CreateNode(value)函数创建一个新的节点newNode，其中value是新节点的数据值。这个函数应该分配内存并初始化新节点的data字段和指针字段。 - 建立新节点与前驱节点的关系：设置
before节点的next指针指向新节点，即before->next = newNode;，这样before和新节点之间的链接就建立了。设置新节点的front指针指向before，即newNode->front = before;，确保新节点能正确链接到链表中。 - 建立新节点与指定位置节点的关系：设置新节点的
next指针指向pos，即newNode->next = pos;，将新节点直接链接到pos节点前面。设置pos节点的front指针指向新节点，即pos->front = newNode;，完成从pos节点到新节点的双向链接。
//在指定位置插入结点
void ListInsert(ListNode* pos, LTDataType value)
{assert(pos);ListNode* before = pos->front;//记录pos指向结点的前一个结点ListNode* newNode = CreateNode(value);//申请一个结点，数据域赋值为x//建立新结点与before结点之间的双向关系before->next = newNode;newNode->front = before;//建立新结点与pos指向结点之间的双向关系newNode->next = pos;pos->front = newNode;
}
9. 在pos位置删除节点
实现步骤：
- 检查有效性：使用
assert(pos)来确保传入的节点指针pos是有效的，即不为NULL。这是一个基本的安全检查，防止对空指针进行操作，这样的操作可能导致程序崩溃 - 定位前驱和后继节点：使用
ListNode* before = pos->front;获取pos节点的前一个节点，并将其存储在变量before中。使用ListNode* after = pos->next;获取pos节点的后一个节点，并将其存储在变量after中。 - 重建链接：将
before节点的next指针指向after节点，即before->next = after;。这步操作是断开before节点与pos节点之间的链接，并直接链接到after节点。 - 将
after节点的front指针指向before节点，即after->front = before;。这步操作是断开after节点与pos节点之间的链接，并直接链接到before节点。 - 释放内存：使用
free(pos);释放pos指针指向的节点所占用的内存。这是清理资源的重要步骤，避免内存泄漏。
//删除指定位置结点
void ListErase(ListNode* pos)
{assert(pos);ListNode* before = pos->front;//记录pos指向结点的前一个结点ListNode* after = pos->next;//记录pos指向结点的后一个结点//建立before结点与after结点之间的双向关系before->next = after;after->front = before;free(pos);//释放pos指向的结点
}
10. 链表判空
实现步骤：
- 检查头节点的后继指针：在带头的双向循环链表中，头节点（哨兵节点）不存储数据。链表为空的标准是头节点的
next指针指向自身。 - 检查头节点的前驱指针：为了确保链表完整性，也应验证头节点的
prev指针是否也指向自身。
bool isEmpty(ListNode* *phead) {return (phead->next == phead && head->front == phead);
}11. 获取链表中的元素个数
实现步骤：
- 初始化计数器: 创建一个变量来保存节点的数量。
- 遍历链表: 从链表的头节点开始，遍历每一个节点，直到链表末尾。
- 递增计数器: 每访问一个节点，计数器增加1。
- 返回结果: 遍历完整个链表后，计数器的值即为链表中的元素个数。
//获取链表中的元素个数
int ListSize(ListNode* phead)
{assert(phead);int count = 0;//初始化计数器ListNode* cur = phead->next;//从头节点的后一个结点开始遍历while (cur != phead)//当cur指向头节点时，遍历完毕，头节点不计入总元素个数{count++;cur = cur->next;}return count;//返回元素个数
}
