数据结构-双向循环链表

双向循环链表（哨兵位）踩坑全复盘：从运行崩溃到接口统一

写在前面

在学习完单链表之后，我继续实现了带哨兵位的双向循环链表。相比单链表，双向链表的每个节点多了一个prev指针，可以同时向前、向后访问；再配合固定存在的哨兵头结点，头插、尾插、头删、尾删时能够减少很多边界判断。

不过真正自己动手写之后才发现，双向链表并不是简单地“多维护一个prev”。一次插入或删除通常需要同时改变多个指针，只要其中一个关系写错，问题可能不会立即出现，而是在后面的遍历、删除甚至销毁过程中突然崩溃。

这次代码是我先按照自己的理解完成基础实现，然后在测试过程中一边运行、一边报错、一边修改。期间先后遇到了打印无输出、一级与二级指针混用、删除节点时改错指针、误操作哨兵节点、销毁时空指针访问等问题。把这些问题基本解决之后，我感觉自己的实现虽然已经能够正常完成各项功能，但在变量命名、接口风格和测试结构上还不够规范，于是又借助 AI 对代码进行了整理和优化。

所以这篇文章的重点并不是展示一份“标准答案”，而是记录我自己的代码是怎样在一次次踩坑中逐渐修改正确的。最后的 AI 优化版本主要作为对照和补充。

本文代码已经上传至 Gitee：Code_2026：双链表 List 完整代码

一、我的初始实现思路

本文实现的是一个带哨兵位的双向循环链表。哨兵节点phead本身不保存有效数据，真正的第一个数据节点是phead->next，最后一个数据节点是phead->prev；首节点的prev指向哨兵，尾节点的next同样指回哨兵。

假设链表中存放：1、2、3

整体关系可以理解成：phead ⇄ 1 ⇄ 2 ⇄ 3 ⇄ phead

空链表也不是NULL，而是：phead->next == phead、phead->prev == phead

因此我在申请节点时直接让next和prev默认指向自己，这样创建哨兵节点时可以直接复用LTBuyNode。初始化函数则直接返回创建好的哨兵指针，后续大部分操作都接收一级指针LTNode*，因为插入和删除修改的是节点之间的连接关系，并不需要改变调用者保存的phead本身。

1.1 初始头文件 List.h

#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int LTDataType; // 双向链表节点结构 typedef struct ListNode { LTDataType data; struct ListNode* next; struct ListNode* prev; }LTNode; // 初始化与销毁 LTNode* LTInit(); void LTDesTroy(LTNode* phead); // 打印 void LTPrint(LTNode* phead); // 头尾插删 void LTPushBack(LTNode* phead, LTDataType x); void LTPushFront(LTNode* phead, LTDataType x); void LTDelBack(LTNode* phead); void LTDelFront(LTNode* phead); // 查找 LTNode* LTFind(LTNode* phead, LTDataType x); // 指定位置插入 void LTPushAft(LTNode* pos, LTDataType x); void LTPushBef(LTNode* pos, LTDataType x); // 指定位置删除 void LTDelPos(LTNode* pos); void LTDelAft(LTNode* pos); void LTDelBef(LTNode* pos);

1.2 初始功能实现 List.c

#include"List.h" // 申请节点：默认自环 LTNode* LTBuyNode(LTDataType x) { LTNode* node = (LTNode*)malloc(sizeof(LTNode)); if (node == NULL) { perror("malloc fall!"); exit(1); } node->data = x; node->next = node->prev = node; return node; } // 初始化：返回哨兵指针 LTNode* LTInit() { LTNode* phead = LTBuyNode(-1); return phead; } // 销毁链表 void LTDesTroy(LTNode* phead) { assert(phead); LTNode* pcur = phead->next; while (pcur != phead) { LTNode* next = pcur->next; free(pcur); pcur = NULL; } free(phead); phead = NULL; } // 尾插 void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = LTBuyNode(x); newnode->next = phead; newnode->prev = phead->prev; phead->prev->next = newnode; phead->prev = newnode; } // 头插 void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = LTBuyNode(x); newnode->next = phead->next; newnode->prev = phead; phead->next->prev = newnode; phead->next = newnode; } // 打印 void LTPrint(LTNode* phead) { assert(phead); LTNode* newnode = phead; while (newnode != phead) { printf("%d->",newnode->data); newnode = newnode->next; } printf("NULL"); printf("\n"); } // 尾删 void LTDelBack(LTNode* phead) { assert(phead && phead->next != phead); LTNode* Tarnode = phead->prev; Tarnode->prev->next = phead; phead->prev = Tarnode->prev; free(Tarnode); Tarnode = NULL; } // 头删 void LTDelFront(LTNode* phead) { assert(phead && phead->next != phead); LTNode* Tarnode = phead->next; Tarnode->next->prev = phead; phead->next = Tarnode->next; free(Tarnode); Tarnode = NULL; } // 查找 LTNode* LTFind(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = phead->next; while (newnode != phead) { if (newnode->data == x) { printf("Found it!\n"); return newnode; } newnode = newnode->next; } printf("No Found!\n"); return NULL; } // pos之后插入 void LTPushAft(LTNode* pos, LTDataType x) { assert(pos); LTNode* newnode = LTBuyNode(x); newnode->next = pos->next; newnode->prev = pos; pos->next->prev = newnode; pos->next = newnode; } // pos之前插入 void LTPushBef(LTNode* pos, LTDataType x) { assert(pos); LTNode* newnode = LTBuyNode(x); newnode->next = pos; newnode->prev = pos->prev; pos->prev->next = newnode; pos->prev = newnode; } // 删除pos本身 void LTDelPos(LTNode* pos) { assert(pos && (!(pos->next == pos && pos->prev == pos))); pos->prev->next = pos->next; pos->next->prev = pos->prev; free(pos); pos = NULL; } // 删除pos之后的节点 void LTDelAft(LTNode* pos) { assert(pos && pos->next != pos); LTNode* Tarnode = pos->next; Tarnode->next->prev = pos; Tarnode = Tarnode->next; free(Tarnode); Tarnode = NULL; } // 删除pos之前的节点 void LTDelBef(LTNode* pos) { assert(pos && pos->prev != pos); LTNode* Tarnode = pos->prev; Tarnode->prev->next = pos; pos->prev = Tarnode->prev; free(Tarnode); Tarnode = NULL; }

1.3 初始测试代码

#include"List.h" void ListTest01() { LTNode* Plist = LTInit(); LTPushBack(&Plist, 1); LTPrint(Plist); LTPushBack(Plist, 2); LTPrint(Plist); LTPushFront(Plist, 3); LTPrint(Plist); LTPushFront(Plist, 4); LTPrint(Plist); LTDelBack(Plist); LTPrint(Plist); LTDelFront(Plist); LTPrint(Plist); // 指定位置插入 LTNode* Find = LTFind(Plist, 1); if (Find != NULL) { LTPushAft(Find, 5); LTPrint(Plist); LTPushBef(Find, 6); LTPrint(Plist); } LTNode* Find2 = LTFind(Plist, 3); if (Find2 != NULL) { LTPushAft(Find2, 4); LTPrint(Plist); LTPushBef(Find2, 5); LTPrint(Plist); } // 指定位置删除 LTNode* Find3 = LTFind(Plist, 1); if (Find3 != NULL) { LTDelAft(Find3); LTPrint(Plist); LTDelBef(Find3); LTPrint(Plist); LTDelPos(Plist); Find3 = NULL; LTPrint(Plist); LTDesTroy(Plist); Plist = NULL; } } int main() { ListTest01(); return 0; }

这就是我最开始写出来的一套代码。接口基本都有了，但真正开始测试之后，问题也一个接一个出现。后面的代码并不是重新推翻重写，而是在这套实现上根据运行结果逐步修改。

二、第一次踩坑：链表打印不出来

最开始运行时，插入之后调用LTPrint，却发现控制台没有正常输出链表内容。检查之后才发现，问题并不在插入，而是打印函数自己的遍历起点错了。

原来的代码是：

void LTPrint(LTNode* phead) { assert(phead); LTNode* newnode = phead; // 遍历起点直接设为哨兵 while (newnode != phead) // 循环条件一开始就不成立 { printf("%d->",newnode->data); newnode = newnode->next; } }

newnode一开始就被赋值成phead，下一句却马上判断newnode != phead，第一次判断就已经为假，所以整个循环一次都不会进入。

这时候我才真正把“哨兵节点”和普通数据节点区分开。哨兵本身不应该参与有效数据的打印，真正的第一个节点应该是phead->next；因为这是循环链表，结尾也不是NULL，而是遍历指针重新回到phead。

于是修改成：

void LTPrint(LTNode* phead) { assert(phead); LTNode* cur = phead->next; // 从第一个数据节点开始 while (cur != phead) // 回到哨兵就结束 { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }

这个问题本身不复杂，但让我建立了后面一直在使用的遍历规则：

带哨兵的双向循环链表，从phead->next开始，以重新遇到phead作为结束条件。

三、第二次踩坑：尾插直接读取访问权限冲突

解决打印问题之后继续测试，第一次执行尾插又直接崩溃，调试时phead->prev已经变成了明显异常的地址。

问题实际上出现在测试代码：

LTNode* Plist = LTInit(); LTPushBack(&Plist, 1); // 错误传参

而我的函数声明是：void LTPushBack(LTNode* phead, LTDataType x);

Plist本身的类型已经是LTNode*，保存的就是哨兵节点地址；写成&Plist之后，传进去的却变成了LTNode**，也就是“保存哨兵地址的指针变量本身的地址”。

函数内部仍然把这个地址当作一个真正的LTNode节点，再执行phead->prev，自然就会去访问错误的内存位置。

正确调用应该是：

LTPushBack(Plist, 1); // 正确：一级指针接口直接传指针

这个 Bug 也让我重新理解了一级和二级指针的使用。不能简单认为“链表函数就应该传&head”，而应该看函数到底需要改变什么。如果只是通过phead修改节点内部的next和prev，一级指针就够了；只有函数需要改变调用者保存的那个指针变量本身时，才需要考虑二级指针。

四、第三次踩坑：删除之后链表开始错乱

插入部分逐渐正常之后，我继续测试指定位置删除，结果执行LTDelAft后开始出现乱码，后续操作甚至直接崩溃。

原代码是：

void LTDelAft(LTNode* pos) { assert(pos && pos->next != pos); LTNode* Tarnode = pos->next; Tarnode->next->prev = pos; Tarnode = Tarnode->next; // 致命错误：改错了变量 free(Tarnode); Tarnode = NULL; }

假设当前局部结构是：pos ⇄ del ⇄ next

想删除del，最后应该恢复成：pos ⇄ next

因此真正需要改变的是：pos->next，以及：next->prev

但是我原来的代码保存完待删除节点之后，却写成了：Tarnode = Tarnode->next

这只是把临时变量移动到了下一个节点，并没有让pos跳过原来的待删除节点。更严重的是，紧接着free(Tarnode)释放的已经不是一开始保存的目标节点，而是后面的节点，导致整个链表的连接关系被破坏。

后来修改为：

void LTDelAft(LTNode* pos) { assert(pos && pos->next != pos); LTNode* del = pos->next; pos->next = del->next; // pos跳过被删节点 del->next->prev = pos; // 后继节点回连 free(del); }

这次问题让我觉得，写双向链表删除时，与其去背next、prev的具体代码，不如先在脑中画清楚局部关系。删除：prev ⇄ del ⇄ next

本质上就是重新连接：prev ⇄ next

只要先确定操作之后谁应该指向谁，再翻译成代码，出错的概率会低很多。

五、第四次踩坑：删除时传错节点，以及free后的指针问题

继续测试时，我又在指定位置删除这里写了：

LTDelPos(Plist); // 错误：传入了哨兵头结点

但这里真正想删除的其实是前面LTFind找到的Find3。于是经过调试：

我发现Plist是整个链表的哨兵节点，phead->next和phead->prev都依靠它维持整个循环结构，如果把哨兵当作普通数据节点释放，后面的链表入口和首尾连接都会出问题。

正确调用应该是：

LTDelPos(Find3); // 传入数据节点指针 Find3 = NULL; // 外部手动置空，杜绝野指针

这里还有一个之前理解得不够准确的地方。最开始的LTDelPos中，在free(pos)后又写了：

pos = NULL；

但pos只是调用函数时传进来的一份指针副本。即使函数内部把它改成NULL，外面的Find3仍然保存原来的地址，只不过这块内存已经被释放了。

所以这一步真正让我理解的是：free释放的是内存，不会自动改变其他保存该地址的指针；函数内部修改一级指针形参，也不会同步修改外部的指针变量。

这也是为什么测试代码中删除完成以后，我会再手动：Find3 = NULL，避免后面误用这个已经失效的地址。

六、第五次踩坑：链表都写完了，却在销毁时崩溃

最后一个比较明显的问题出现在销毁函数。当时的写法是：

void LTDesTroy(LTNode* phead) { assert(phead); LTNode* pcur = phead->next; while (pcur != phead) { LTNode* next = pcur->next; free(pcur); pcur = NULL; // 错误：循环内把指针置空 } free(phead); }

在释放当前节点之前先用next保存下一个节点，这一步其实已经想对了。因为pcur一旦被free，就不能再通过它去访问pcur->next。

真正的问题是后面应该：pcur = next，继续释放下一个节点，我却直接写成了：pcur = NULL；

下一轮循环时NULL != phead仍然可能成立，程序继续进入循环，再访问pcur->next就成了典型的空指针解引用。

所以销毁链表应该按照：保存后继 → 释放当前节点 → 移动到后继

这个顺序进行：

void LTDesTroy(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { LTNode* next = cur->next; free(cur); cur = next; // 指针后移，不是置空 } free(phead); }

同时我最开始还把销毁函数写在了if (Find3 != NULL)里面，这样如果前面的查找失败，整个链表就不会执行销毁。后来也把这一部分调整到了所有测试结束之后，让链表的生命周期变得更明确：初始化 → 插入 / 删除 / 查找 → 销毁。

七、从“能正常运行”到“代码更规范”：再借助 AI 做一次优化

前面的几个问题并不是最后一次性让 AI 帮我重写代码，而是在我自己的实现基础上，随着测试逐渐发现并修改的。到这里之后，链表的主要功能已经能够正常完成，我对各个接口的指针关系也基本理解清楚了。

不过重新看自己的代码时，我感觉还有一些地方“不够正式”，例如变量名中同时出现newnode、Tarnode、pcur等不同风格，销毁函数命名也存在大小写不统一的问题；测试代码虽然能完成验证，但执行顺序和输出提示还可以整理得更加清楚。

所以在自己的代码已经完成和调通之后，我又让 AI 作为辅助，对整套代码做了一次规范化整理。主要变化包括：

• 将待删除节点统一使用del等更直观的变量名；

• 将销毁函数名称统一为LTDestroy；

• 去掉部分没有实际意义的局部指针置空操作；

• 将测试过程按初始化、插入、删除、指定位置操作和销毁重新分组；

• 保持原有链表结构和接口逻辑不变的基础上，让代码整体更清晰。

这一步和前面的踩坑过程对我来说是两个不同阶段：前面主要是在解决“代码为什么会错”，后面则是在已经正确的基础上考虑“怎样写得更规范”。

AI 在这里更像一个代码检查和整理工具，而不是替代我完成双向链表。从学习角度来说，我觉得先自己写、自己运行、自己遇到问题，再带着具体代码和报错去分析，比一开始直接拿到一份完整正确代码更有意义。

最终整理后的优化版本没有再全文重复放在文章里，避免与前面的实现代码占用太多篇幅，可以直接在 Gitee 仓库查看：Code_2026 / 双链表 List 优化版完整代码

八、这次真正学到的几个点

这次双向循环链表虽然踩了不少坑，但回头看下来，很多错误其实都围绕几个最核心的问题。

首先是哨兵节点改变了链表的边界规则。它让空链表仍然拥有完整的前后连接关系，很多头尾操作因此不需要单独判断特殊情况；与此同时，遍历也不能再使用普通单链表的NULL结束条件，而要从phead->next出发，重新回到phead时结束。

其次是要区分临时指针的移动和链表结构的修改。像：cur = cur->next只是让一个局部变量向后移动，并不会改变链表；而：pos->next = del->next才是真正修改了节点之间的连接关系。之前LTDelAft出错，本质上就是把这两件事混在了一起。

最后是对动态内存和函数传参理解得更具体了。free只负责释放对应的内存，不会自动把其他指针改成NULL；一级指针传参本质上仍然是值传递，函数内部把pos设为空，也不会影响外部变量。同样，是否使用一级或二级指针，也不能机械判断，而应该看函数到底需不需要改变调用者保存的指针本身。

写在最后

相比之前写单链表，这次双向循环链表让我更加明显地感觉到：数据结构代码能够编译通过，并不代表指针关系一定正确。

打印没有输出、读取访问权限冲突、删除之后链表错乱、程序最后在销毁阶段崩溃，这些问题看起来发生在完全不同的位置，但本质上都和“当前指针到底指向谁、修改之后节点应该怎样重新连接”有关。

这次代码也是在这样的过程中一点点完善的。我先按照自己的理解把接口写出来，再通过测试暴露问题，继续修改和理解；等到功能已经正常之后，才借助 AI 对代码风格和测试结构做进一步整理。

相比直接得到一份标准代码，我觉得这种过程对我更有价值。因为最后留下来的不仅是一份能够运行的双向循环链表，更重要的是，当以后再看到类似的野指针、空指针或者链表断裂问题时，我开始知道应该从哪里检查，而不是只盯着报错位置反复试代码。

先理解自己为什么写错，再知道正确代码为什么这样写，应该才是这次踩坑真正留下来的东西。

完整代码仓库：Code_2026 / 双链表 List