数据结构 - 链表详解（二）—— 带头双向循环链表

 链表的介绍

链表的结构一共有八种：带头单向循环链表、带头单向非循环链表、带头双向循环链表、带头双向非循环链表、无头单向循环链表、无头单向非循环链表、无头双向循环链表、无头双向非循环链表。

今天我们来详解带头双向循环链表

带头双向循环链表是一种数据结构，它通过在双向链表的基础上增加循环的特性，并通过一个头结点（带头）来简化操作。这种结构在实际应用中有其独特的优缺点：

优点

1. 双向遍历：链表可以从两个方向遍历，即可以向前或向后移动。这使得许多操作，如反转遍历、双端操作等，更为方便和高效。
2. 循环特性：由于是循环链表，表尾与表头直接相连。这一特性使得从链表的一端到另一端的访问时间缩短，特别是在需要频繁执行环形遍历的场合（如轮转调度算法）。
3. 统一操作：带头结点的链表简化了插入和删除节点的操作，因为不需要单独处理空链表的情况。头结点的存在使得链表始终非空，减少了边界条件的检查。
4. 易于管理：头结点提供了一个固定的起点，无论链表是否为空，这使得链表的管理更为统一和方便。

缺点

1. 额外的空间消耗：头结点本身不存储有效数据，占用一定的空间。对于内存使用极为严格的应用场景，这种额外消耗可能是一个缺点。
2. 实现复杂度：相比单向链表，双向循环链表的实现更复杂。正确管理前驱和后继指针需要更多的注意和精确控制，增加了编程的难度。
3. 性能开销：每次插入或删除操作都需要更新两个指针（前驱和后继），这比单向链表的操作稍显复杂，可能会略微增加时间开销。
4. 循环错误：如果不正确管理节点的连接和断开，循环链表容易产生逻辑错误，如死循环或访问已删除的节点，这可能导致程序出错或崩溃。

链表详解

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);//申请一个结点，数据域赋值为value
	ListNode* Front = phead->next;//记录头结点的后一个结点位置
	//建立新结点与头结点之间的双向关系
	phead->next = newNode;
	newNode->front = phead;
	//建立新结点与front结点之间的双向关系
	newNode->next = Front; //这时候不能用phead了，因为phead
	Front->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);//申请一个结点，数据域赋值为x
	ListNode* 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;//返回元素个数
}