C语言带头双向循环链表实现指南
在学习C语言数据结构时，带头双向循环链表因其结构的复杂性往往让初学者感到困惑，但其强大的扩展性和对称性使其成为许多底层容器（如PHP Hash表、Redis列表）的基础。本文将通过分步代码解析与图示，带你从零构建一个完整的带头双向循环链表，重点攻克节点指针悬挂与内存管理难点。
为什么选择带头双向循环链表
在常见的链表结构中，无头单向非循环链表结构简单但缺乏双向遍历能力，通常仅作为其他数据结构的子组件；而带头双向循环链表虽然设计最为复杂，却具备诸多优势：首尾访问效率高、插入删除操作时间复杂度稳定为O(1)（已知节点位置时）、且通过哨兵位（Dummy Head）简化了边界条件的判断逻辑。了解其实现原理，对深入理解STL中的list或std::deque等容器大有裨益。
第1步：定义节点结构体
首先定义链表的节点。为了代码的可维护性，使用 typedef 对数据类型进行重命名。每个节点包含指向前驱节点的 prev、指向后继节点的 next 以及存储数据的 val。
typedef int LNDataType;
typedef struct ListNode
{
struct ListNode* prev; // 前驱指针
struct ListNode* next; // 后继指针
LNDataType val; // 数据域
}LN;第2步：封装节点申请函数
创建新节点时应封装独立函数 BuynewNode。必须检查 malloc 是否成功，防止因内存不足导致程序崩溃。新节点初始状态为空，需显式将指针置为NULL。
// 申请一个新节点并初始化
LN* BuynewNode(LNDataType x)
{
LN* newNode = (LN*)malloc(sizeof(LN));
if (newNode == NULL)
{
printf("malloc fail\n");
exit(-1); // 终止进程
}
newNode->next = NULL;
newNode->prev = NULL;
newNode->val = x;
return newNode;
}第3步：创建哨兵位节点（初始化）
链表初始化即创建哨兵位。注意，因为要修改外部传入的指针 plist 本身的指向，所以函数参数需要传递二级指针 LN** pphead。哨兵位本身不存有效业务数据，但其 next 和 prev 均指向自身，形成闭环。
// 初始化节点
void ListNodeInit(LN** pphead)
{
LN* newNode = BuynewNode(0);
*pphead = newNode;
(*pphead)->next = *pphead;
(*pphead)->prev = *pphead;
}
调用示例：
// test.c
LN* plist = NULL;
ListNodeInit(&plist); 第4步：实现尾插操作
尾插即在最后一个有效数据和哨兵位之间插入新节点。由于只需修改节点内部字段而不改变链表头指针，故传一级指针即可。使用 assert(phead) 确保链表存在。插入过程涉及四个指针关系的调整：
- 找到当前尾部节点
tail = phead->prev。 - 将旧尾部的
next指向新节点。 - 将新节点的
prev指向旧尾部。 - 将新节点的
next指向哨兵位，并将哨兵位的prev指向新节点。
// 尾插
void ListNodePushBack(LN* phead, LNDataType x)
{
assert(phead);
LN* newNode = BuynewNode(x);
LN* tail = phead->prev;
// 连接旧尾部与新节点
tail->next = newNode;
newNode->prev = tail;
// 连接新节点与哨兵位
newNode->next = phead;
phead->prev = newNode;
}第5步：打印链表数据
遍历时应从第二个节点（phead->next）开始，直到回到哨兵位为止，避免打印哨兵位的伪数据。
// 打印链表
void ListNodePrint(LN* phead)
{
assert(phead);
LN* cur = phead->next;
while (cur != phead)
{
printf("%d ", cur->val);
cur = cur->next;
}
printf("\n");
}第6步：实现尾删操作
尾删即将最后一个有效节点移除。关键点是：绝对不要free掉哨兵位。因此必须断言链表不止有哨兵位一个节点（phead->next != phead）。删除步骤：
- 定位尾部节点
tail及其前驱tailPrev。 - 断开尾部节点的链接：将哨兵位的
prev指向tailPrev，将tailPrev的next指向哨兵位。 - 释放
tail内存并置空。
// 尾删
void ListNodePopBack(LN* phead)
{
assert(phead);
assert(phead->next != phead); // 防止删掉头结点
LN* tail = phead->prev;
LN* tailPrev = tail->prev;
// 重新建立连接
phead->prev = tailPrev;
tailPrev->next = phead;
free(tail);
tail = NULL;
}第7步：实现头插操作
头插在哨兵位和第一个有效节点之间插入新节点。同样只需修改局部指针指向：
// 头插
void ListNodePushFront(LN* phead, LNDataType x)
{
assert(phead);
LN* newNode = BuynewNode(x);
LN* next = phead->next; // 暂存原第一个节点
// 哨兵位与新节点连接
phead->next = newNode;
newNode->prev = phead;
// 新节点与原第一个节点连接
newNode->next = next;
next->prev = newNode;
}第8步：在指定位置前插入节点
该函数通用性极强，既可用于中间插入，也可用于头插。逻辑是找到 pos 的前驱，将新节点夹在它们中间。
// 在 pos 前面插入节点
void ListNodeInsert(LN* pos, LNDataType x)
{
if (pos == NULL)
{
printf("没有找到这个数\n");
return;
}
LN* newNode = BuynewNode(x);
LN* tailPrev = pos->prev;
// 连接前驱与新节点
tailPrev->next = newNode;
newNode->prev = tailPrev;
// 连接新节点与pos
newNode->next = pos;
pos->prev = newNode;
}第9步：删除指定位置节点
删除 pos 节点时，需确保 pos 不是哨兵位，否则会导致破坏链表基础结构。操作逻辑为跨越 pos，将其前后节点直接相连，然后释放 pos。
// 删除指定位置节点
void ListNodeErease(LN* phead, LN* pos)
{
if (pos == phead || pos == NULL)
{
printf("pos指向头，或为空\n");
return;
}
LN* posPrev = pos->prev;
LN* posNext = pos->next;
// 跨越删除
posPrev->next = posNext;
posNext->prev = posPrev;
free(pos);
pos = NULL;
}第10步：销毁整个链表
程序结束时必须释放所有节点以防止内存泄漏。遍历所有节点进行 free 操作。注意：最后还需手动 free 哨兵位。形参指针置空无法影响外部实参，这是C语言值传递的特性。
// 销毁链表
void ListNodeDestroy(LN* phead)
{
assert(phead);
LN* cur = phead->next;
while (cur != phead)
{
LN* next = cur->next;
free(cur);
cur = next;
}
// 别忘了释放哨兵位
free(phead);
// phead = NULL; // 此处无法改变外部变量
}以上就是C语言实现带头双向循环链表的详细内容，更多关于C语言数据结构链表实战的资料请关注本站其它相关文章！
本站声明
本文内容仅供参考，不代表本站观点。转载或引用请注明出处。如发现内容问题，请通过联系我们页面反馈。
