C语言双向带头循环链表详解：结构、核心函数与封装逻辑

一、 为何选择双向带头循环链表

单链表在处理尾部操作（如尾插、尾删）或指定节点的前驱查找时，必须从头节点遍历至目标位置，效率较低。双向带头循环链表通过以下两个特性解决了这一痛点：

1. 双向性：每个节点拥有 prev 和 next 指针，可向前追溯父节点，无需遍历即可获取前驱信息。
2. 带头循环引入一个不存有效数据的“哨兵位”头结点，使链表首尾相连。这种结构消除了判空判断的复杂性，使得头尾操作逻辑与中间操作保持一致。

二、 核心结构定义与初始化

双向链表的节点需要存储数据以及指向前后节点的指针。为便于扩展，通常使用宏或 typedef 定义数据类型。

节点结构体定义如下：

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

第1步：节点内存申请

在进行任何插入操作前，需动态分配新节点空间。此步骤需进行内存检查，防止因堆空间不足导致程序崩溃。

LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	newnode->data = x;
	newnode->prev = newnode->next = NULL;
	return newnode;
}

第2步：链表初始化（哨兵位创建）

初始化即创建一个独立的头结点，并将其 prev 和 next 均指向自身，形成闭环。此时链表为空，但结构已存在。

LTNode* InitLT()
{
	LTNode* phead = BuyLTNode(-1);
	phead->prev = phead->next = phead;
	return phead;
}

三、 通用增删接口封装

双向带头循环链表的精髓在于将头插/尾插、头删/尾删统一为“在节点前插入”和“删除指定节点”。这要求首先实现这两个通用底层函数。

第3步：在指定节点前插入（LTInsert）

该函数的目标是在 pos 指向的节点之前插入新节点 newnode。无论 pos 是第一个有效数据节点还是头结点本身，逻辑均适用。

void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = BuyLTNode(x);
	LTNode* posPrev = pos->prev;
	
	// 链接前驱与新节点
	posPrev->next = newnode;
	newnode->prev = posPrev;
	
	// 链接新节点与后继(pos)
	newnode->next = pos;
	pos->prev = newnode;
}

第4步：删除指定节点（LTErase）

删除 pos 节点时，直接断开其与前后节点的连接，并将前后节点互相指向，最后释放 pos 内存。注意：不能对头结点调用此函数，因为头结点不应被释放。

void LTErase(LTNode* pos)
{
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;
	
	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);
}

四、 高级操作接口的复用实现

借助上述两个通用函数，原本复杂的头尾操作变得异常简洁。

第5步：头插与尾插

头插实际上就是在第二个节点（即 phead->next）之前插入；尾插则是在头结点（phead）之前插入。

// 头插：在第一个有效节点前插入
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTInsert(phead->next, x);
}

// 尾插：在头结点前插入
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTInsert(phead, x);
}

第6步：头删与尾删

头删即删除第二个节点（phead->next）；尾删即删除头结点的前驱节点（phead->prev）。需注意在执行删除前检查链表是否为空。

// 头删
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead); // 非空检查
	LTErase(phead->next);
}

// 尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead); // 非空检查
	LTErase(phead->prev);
}

第7步：查找功能

从第一个有效节点开始遍历，直到回到头结点为止。若找到目标值返回节点指针，否则返回 NULL。

LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x) return cur;
		cur = cur->next;
	}
	return NULL;
}

五、 辅助工具与资源清理

第8步：状态查询

判断链表长度和是否为空。对于带头链表，当且仅当头结点的后继指向自己时，链表为空。

bool LTEmpty(LTNode* phead)
{
	assert(phead);
	return phead->next == phead;
}

size_t LTSize(LTNode* phead)
{
	assert(phead);
	size_t size = 0;
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		++size;
		cur = cur->next;
	}
	return size;
}

第9步：打印与销毁

打印用于调试，销毁需遍历并释放所有有效节点及头结点内存，防止内存泄漏。

void LTPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	printf("head ->");
	while (cur != phead)
	{
		printf("%d -> ", cur->data);
		cur = cur->next;
	}
	printf("head\n");
}

void LTDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead); // 最后释放头结点
}

以上就是C语言双向带头循环链表的详细内容，更多关于C语言数据结构链表的资料请关注本站其它相关文章！