数据结构-双向循环链表

双向循环链表哨兵位踩坑全复盘从运行崩溃到接口统一写在前面在学习完单链表之后我继续实现了带哨兵位的双向循环链表。相比单链表双向链表的每个节点多了一个prev指针可以同时向前、向后访问再配合固定存在的哨兵头结点头插、尾插、头删、尾删时能够减少很多边界判断。不过真正自己动手写之后才发现双向链表并不是简单地“多维护一个prev”。一次插入或删除通常需要同时改变多个指针只要其中一个关系写错问题可能不会立即出现而是在后面的遍历、删除甚至销毁过程中突然崩溃。这次代码是我先按照自己的理解完成基础实现然后在测试过程中一边运行、一边报错、一边修改。期间先后遇到了打印无输出、一级与二级指针混用、删除节点时改错指针、误操作哨兵节点、销毁时空指针访问等问题。把这些问题基本解决之后我感觉自己的实现虽然已经能够正常完成各项功能但在变量命名、接口风格和测试结构上还不够规范于是又借助 AI 对代码进行了整理和优化。所以这篇文章的重点并不是展示一份“标准答案”而是记录我自己的代码是怎样在一次次踩坑中逐渐修改正确的。最后的 AI 优化版本主要作为对照和补充。本文代码已经上传至 GiteeCode_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 #includestdio.h #includestdlib.h #includeassert.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#includeList.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 初始测试代码#includeList.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