数据结构：双向循环链表的全方位解构

数据结构双链表的全方位解构双向循环链表像一群人手拉手围成圈每个人既记得左边是谁、也记得右边是谁从任意一人出发都能绕完一整圈加人走人只需改两根手指。核心思想单链表最大的痛是找前驱 O(n)。双向链表给每个节点加一个prev指针前驱后继都能 O(1) 拿到。再让链表首尾相连成环尾节点的next指回头头节点的prev指向尾并加一个不存数据的哨兵头节点phead于是空表也有结构哨兵自环不用特判空表。头插、尾插、头删、尾删全部统一为 O(1)——因为哨兵的prev就是尾节点哨兵的next就是第一个有效节点O(1) 可达。已知任意节点pos在它前后插入、删除它本身都是 O(1)。代价每个节点多一个指针空间换时间且插入/删除时要改4 个指针顺序极易写错。数据结构定义typedefstructListnode{LTDataType data;structListnode*next;// 后继structListnode*prev;// 前驱}LTNode;内存模型带哨兵头节点phead存了 3 个有效数据 1,2,3┌──────────────────────────────────────────┐ ↓ │ [phead] ⇄ [1] ⇄ [2] ⇄ [3] ⇄──────────────┘ ↑ │ └──────────────────────────────────┘ 哨兵不存数据prev 指向尾节点(3)next 指向首节点(1) 尾节点(3) 的 next 指回 phead → 形成环关键约定phead是哨兵位phead-next是第一个有效节点phead-prev是最后一个有效节点尾。空表判断phead-next phead哨兵自环没有有效节点。遍历从phead-next开始到再次遇到phead结束。关键操作实现创建节点 LTbuynodeLTNode*LTbuynode(LTDataType x){LTNode*node(LTNode*)malloc(sizeof(LTNode));if(nodeNULL){perror(malloc fail!);exit(1);}node-datax;node-nextnode-prevnode;// 新节点自环next 和 prev 都指向自己returnnode;}逐行解释新节点初始时next prev self自环。这是双向循环链表的「空状态」原子结构——一个自环节点本身就是一条合法的空环。后续插入时只需把它接到链里不用单独初始化指针。初始化 LTInitLTNode*LTInit(){LTNode*pheadLTbuynode(-1);// 哨兵位-1 是占位数据永不读取returnphead;}逐行解释初始化就是建一个自环哨兵节点。返回值赋给调用者的头指针。哨兵的data用-1占位约定永不读取哨兵的 data所以放什么都行。打印 LTprintvoidLTprint(LTNode*phead){LTNode*pcurphead-next;// 从第一个有效节点开始while(pcur!phead)// 转一圈回到哨兵就结束{printf(%d-,pcur-data);pcurpcur-next;}printf(\n);}逐行解释从phead-next出发顺着next走直到再次回到phead。这就是循环链表遍历的终止条件——不是NULL而是「回到起点」。尾插 LTPushBackvoidLTPushBack(LTNode*phead,LTDataType x){assert(phead);LTNode*newnodeLTbuynode(x);// phead phead-prev(原尾) newnodenewnode-prevphead-prev;// 新节点的前驱 原尾newnode-nextphead;// 新节点的后继 哨兵成环phead-prev-nextnewnode;// 原尾的后继 新节点phead-prevnewnode;// 哨兵的前驱 新节点更新尾}逐行解释尾插 O(1)因为哨兵的prev直接给出原尾节点。要改 4 个指针newnode-prev、newnode-next、原尾-next、phead-prev。修改顺序的核心原则先改新节点的两个指针它还没接入随便改不影响别人再改旧节点的指针。具体说newnode-prev phead-prev—— 此时phead-prev还指向原尾安全。newnode-next phead。phead-prev-next newnode—— 让原尾指向新节点。必须在这步之前还没动phead-prev否则原尾就找不到了。所以这步在phead-prev newnode之前。phead-prev newnode—— 最后更新哨兵的前驱为新尾。陷阱如果先执行phead-prev newnode那phead-prev-next第3步就变成了newnode-next原尾节点彻底丢失。所以「先改新、后改旧」「先连原尾、再更新哨兵」是铁律。头插 LTPushFrontvoidLTPushFront(LTNode*phead,LTDataType x){assert(phead);// phead newnode phead-next(原首节点)LTNode*newnodeLTbuynode(x);newnode-prevphead;// 新节点前驱 哨兵newnode-nextphead-next;// 新节点后继 原首节点phead-next-prevnewnode;// 原首节点的前驱 新节点phead-nextnewnode;// 哨兵的后继 新节点更新头}逐行解释头插 O(1)哨兵的next直接给原首节点。同样 4 个指针同样「先改新节点、再改旧节点」「先连原首、再更新哨兵」。尾删 LTPopBack / 头删 LTPopFrontvoidLTPopBack(LTNode*phead){assert(pheadphead-next!phead);// 不能删空表也不能删哨兵LTNode*delphead-prev;// 待删的尾节点// phead del-prev(新尾) deldel-prev-nextphead;// 新尾的后继 哨兵phead-prevdel-prev;// 哨兵的前驱 新尾free(del);delNULL;}voidLTPopFront(LTNode*phead){assert(pheadphead-next!phead);LTNode*delphead-next;// 待删的首节点// phead del del-next(新首)del-next-prevphead;// 新首的前驱 哨兵phead-nextdel-next;// 哨兵的后继 新首free(del);delNULL;}逐行解释删除也是 O(1)。assert(phead-next ! phead)保证不删空表空表时哨兵自环nextphead删了等于删哨兵链表结构就毁了。删的过程让待删节点的前驱和后继直接相连跨过del再free(del)。先连后断原则先让del的邻居互连del-prev-next del-next等再free(del)。如果先free就读不到del-prev和del-next了。查找 LTFindLTNode*LTFind(LTNode*phead,LTDataType x){LTNode*pcurphead-next;while(pcur!phead)// 转一圈{if(pcur-datax)returnpcur;pcurpcur-next;}returnNULL;}逐行解释遍历有效节点比较找到返回节点指针供LTInsert/LTErase用找不到返回 NULL。在 pos 之后插入 LTInsertvoidLTInsert(LTNode*pos,LTDataType x){assert(pos);LTNode*newnodeLTbuynode(x);// pos newnode pos-next(原后继)newnode-prevpos;// 新节点前驱 posnewnode-nextpos-next;// 新节点后继 原后继pos-nextnewnode;// pos 的后继 新节点newnode-next-prevnewnode;// 原后继的前驱 新节点}逐行解释在pos之后插O(1)双向链表前驱后继都在手。注意第 4 步newnode-next-prev newnode此时newnode-next已指向原后继所以这步是让原后继的prev回指新节点。顺序陷阱第3步pos-next newnode必须在第4步之后吗不——第4步用的是newnode-next已存了原后继不是pos-next所以即使第3步先改了pos-next第4步仍正确。但更稳的写法是先存pos-next到临时变量避免依赖顺序记忆。删除 pos 节点 LTErasevoidLTErase(LTNode*pos){assert(pos);// pos-prev pos pos-nextpos-next-prevpos-prev;// 后继的前驱 pos 的前驱pos-prev-nextpos-next;// 前驱的后继 pos 的后继free(pos);// 邻居互连后再删posNULL;// 只置空形参见下}逐行解释删除 O(1)。让pos的前驱和后继直接互连跨过pos再free(pos)。先连后断两步互连必须都在free之前。重要约定pos不能是哨兵phead否则删了哨兵整个链表结构就废了。调用者必须保证不传哨兵。函数内pos NULL只置空形参外部持有的指针仍悬空需调用者自行置空。销毁 LTDestroyvoidLTDestroy(LTNode*phead){assert(phead);LTNode*pcurphead-next;while(pcur!phead)// 遍历有效节点{LTNode*nextpcur-next;// 先存下一个free(pcur);pcurnext;}free(phead);// 最后释放哨兵本身pheadNULL;// ⚠️ 只置空形参}逐行解释遍历释放所有有效节点最后释放哨兵phead。同样「先存 next 再 free」防 UAF。陷阱phead NULL只改了形参调用者手里的头指针仍指向已释放的哨兵内存悬空指针。和LTErase一样调用者必须自己plist NULL。这是「传一级指针无法改外部指针」的老问题——如果要彻底解决LTDestroy应改成传二级指针LTNode**。复杂度分析操作时间复杂度说明头插 / 尾插O(1)哨兵 prev/next 直接给位置头删 / 尾删O(1)同上在 pos 处插入 / 删除 posO(1)双向前驱后继都在手按值查找O(n)仍需遍历销毁O(n)逐个释放对比单链表单链表尾插尾删 O(n)找前驱双向循环链表全 O(1)。代价是每个节点多 8 字节一个prev指针。常见陷阱清单4 个指针修改顺序错→ 断链最常见也最难调。口诀「先改新节点两指针再连旧邻居最后更新哨兵」。先free后连邻居→ UAF读不到前驱后继。LTErase传了哨兵phead→ 删了哨兵结构崩塌。LTDestroy/LTErase后不置空外部指针→ 悬空指针。空表判断写错→ 应是phead-next phead写成phead NULL哨兵永不为空永远判非空。哨兵 data 被误读→ 占位值无意义遍历应跳过哨兵。我的实现 vs 教科书实现设计正确哨兵 双向 循环结构标准头尾插删全 O(1)。代码复用不足LTPushBack/LTPushFront完全可以调用LTInsert(phead, x)/LTInsert(phead-prev... )复用当前各写一遍有重复。LTDestroy置空无效传一级指针无法改外部头指针应改二级指针或要求调用者手动置空。缺接口没有LTSize、LTEmpty判空、LTClear清空不销毁。vsstd::listC 标准库的list就是这种结构额外提供迭代器、spliceO(1) 拼接、size维护。拓展知识点变体与进阶Linux 内核链表反向设计——把链表节点struct list_head嵌入到业务结构体里而非把业务数据放进链表节点。这样一套链表代码能挂任意类型极致复用。LRU CacheHashMap 双向链表O(1) 访问 O(1) 淘汰。访问一个节点就移到链表头满了删尾。不带头双向链表去掉哨兵但头插删要特判空表代码稍繁。常见考点双向链表插入/删除 4 个指针的顺序口诀见上。哨兵位的作用统一边界免特判。为何循环 哨兵能让头尾操作 O(1)哨兵 prev/next 直接定位首尾。与其他结构的关系双向链表是单链表的升级版加prev常用来实现队列、栈、LRU、调度队列。std::deque双端队列底层用分块的双向链表/数组组合。和单链表、顺序表同属线性表家族。一句话记忆法双向循环链表哨兵是圆心首尾在隔壁插删都 O(1)改 4 指针先新后旧、先连后断空表看 nextphead。