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

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

双向循环链表像一群人手拉手围成圈：每个人既记得左边是谁、也记得右边是谁，从任意一人出发都能绕完一整圈，加人走人只需改两根手指。

核心思想

单链表最大的痛是找前驱 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结束。

关键操作实现

创建节点 LTbuynode

LTNode*LTbuynode(LTDataType x){LTNode*node=(LTNode*)malloc(sizeof(LTNode));if(node==NULL){perror("malloc fail!");exit(1);}node->data=x;node->next=node->prev=node;// 新节点自环：next 和 prev 都指向自己returnnode;}

逐行解释：新节点初始时next = prev = self（自环）。这是双向循环链表的「空状态」原子结构——一个自环节点本身就是一条合法的空环。后续插入时只需把它接到链里，不用单独初始化指针。

初始化 LTInit

LTNode*LTInit(){LTNode*phead=LTbuynode(-1);// 哨兵位，-1 是占位数据（永不读取）returnphead;}

逐行解释：初始化就是建一个自环哨兵节点。返回值赋给调用者的头指针。哨兵的data用-1占位，约定永不读取哨兵的 data，所以放什么都行。

打印 LTprint

voidLTprint(LTNode*phead){LTNode*pcur=phead->next;// 从第一个有效节点开始while(pcur!=phead)// 转一圈回到哨兵就结束{printf("%d->",pcur->data);pcur=pcur->next;}printf("\n");}

逐行解释：从phead->next出发，顺着next走，直到再次回到phead。这就是循环链表遍历的终止条件——不是NULL，而是「回到起点」。

尾插 LTPushBack

voidLTPushBack(LTNode*phead,LTDataType x){assert(phead);LTNode*newnode=LTbuynode(x);// phead phead->prev(原尾) newnodenewnode->prev=phead->prev;// 新节点的前驱 = 原尾newnode->next=phead;// 新节点的后继 = 哨兵（成环）phead->prev->next=newnode;// 原尾的后继 = 新节点phead->prev=newnode;// 哨兵的前驱 = 新节点（更新尾）}

逐行解释：尾插 O(1)，因为哨兵的prev直接给出原尾节点。要改 4 个指针：newnode->prev、newnode->next、原尾->next、phead->prev。

修改顺序的核心原则：先改新节点的两个指针（它还没接入，随便改不影响别人），再改旧节点的指针。具体说：

1. newnode->prev = phead->prev—— 此时phead->prev还指向原尾，安全。
2. newnode->next = phead。
3. phead->prev->next = newnode—— 让原尾指向新节点。必须在这步之前还没动phead->prev，否则原尾就找不到了。所以这步在phead->prev = newnode之前。
4. phead->prev = newnode—— 最后更新哨兵的前驱为新尾。

陷阱：如果先执行phead->prev = newnode，那phead->prev->next（第3步）就变成了newnode->next，原尾节点彻底丢失。所以「先改新、后改旧」「先连原尾、再更新哨兵」是铁律。

头插 LTPushFront

voidLTPushFront(LTNode*phead,LTDataType x){assert(phead);// phead newnode phead->next(原首节点)LTNode*newnode=LTbuynode(x);newnode->prev=phead;// 新节点前驱 = 哨兵newnode->next=phead->next;// 新节点后继 = 原首节点phead->next->prev=newnode;// 原首节点的前驱 = 新节点phead->next=newnode;// 哨兵的后继 = 新节点（更新头）}

逐行解释：头插 O(1)，哨兵的next直接给原首节点。同样 4 个指针，同样「先改新节点、再改旧节点」「先连原首、再更新哨兵」。

尾删 LTPopBack / 头删 LTPopFront

voidLTPopBack(LTNode*phead){assert(phead&&phead->next!=phead);// 不能删空表，也不能删哨兵LTNode*del=phead->prev;// 待删的尾节点// phead del->prev(新尾) deldel->prev->next=phead;// 新尾的后继 = 哨兵phead->prev=del->prev;// 哨兵的前驱 = 新尾free(del);del=NULL;}voidLTPopFront(LTNode*phead){assert(phead&&phead->next!=phead);LTNode*del=phead->next;// 待删的首节点// phead del del->next(新首)del->next->prev=phead;// 新首的前驱 = 哨兵phead->next=del->next;// 哨兵的后继 = 新首free(del);del=NULL;}

逐行解释：删除也是 O(1)。assert(phead->next != phead)保证不删空表（空表时哨兵自环，next==phead，删了等于删哨兵，链表结构就毁了）。删的过程：让待删节点的前驱和后继直接相连（跨过del），再free(del)。

先连后断原则：先让del的邻居互连（del->prev->next = del->next等），再free(del)。如果先free，就读不到del->prev和del->next了。

查找 LTFind

LTNode*LTFind(LTNode*phead,LTDataType x){LTNode*pcur=phead->next;while(pcur!=phead)// 转一圈{if(pcur->data==x)returnpcur;pcur=pcur->next;}returnNULL;}

逐行解释：遍历有效节点比较，找到返回节点指针（供LTInsert/LTErase用），找不到返回 NULL。

在 pos 之后插入 LTInsert

voidLTInsert(LTNode*pos,LTDataType x){assert(pos);LTNode*newnode=LTbuynode(x);// pos newnode pos->next(原后继)newnode->prev=pos;// 新节点前驱 = posnewnode->next=pos->next;// 新节点后继 = 原后继pos->next=newnode;// pos 的后继 = 新节点newnode->next->prev=newnode;// 原后继的前驱 = 新节点}

逐行解释：在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 节点 LTErase

voidLTErase(LTNode*pos){assert(pos);// pos->prev pos pos->nextpos->next->prev=pos->prev;// 后继的前驱 = pos 的前驱pos->prev->next=pos->next;// 前驱的后继 = pos 的后继free(pos);// 邻居互连后再删pos=NULL;// 只置空形参（见下）}

逐行解释：删除 O(1)。让pos的前驱和后继直接互连（跨过pos），再free(pos)。先连后断：两步互连必须都在free之前。

重要约定：pos不能是哨兵phead，否则删了哨兵整个链表结构就废了。调用者必须保证不传哨兵。函数内pos = NULL只置空形参，外部持有的指针仍悬空，需调用者自行置空。

销毁 LTDestroy

voidLTDestroy(LTNode*phead){assert(phead);LTNode*pcur=phead->next;while(pcur!=phead)// 遍历有效节点{LTNode*next=pcur->next;// 先存下一个free(pcur);pcur=next;}free(phead);// 最后释放哨兵本身phead=NULL;// ⚠️ 只置空形参}

逐行解释：遍历释放所有有效节点，最后释放哨兵phead。同样「先存 next 再 free」防 UAF。

陷阱：phead = NULL只改了形参，调用者手里的头指针仍指向已释放的哨兵内存（悬空指针）。和LTErase一样，调用者必须自己plist = NULL。这是「传一级指针无法改外部指针」的老问题——如果要彻底解决，LTDestroy应改成传二级指针LTNode**。

复杂度分析

操作	时间复杂度	说明
头插 / 尾插	O(1)	哨兵 prev/next 直接给位置
头删 / 尾删	O(1)	同上
在 pos 处插入 / 删除 pos	O(1)	双向，前驱后继都在手
按值查找	O(n)	仍需遍历
销毁	O(n)	逐个释放

对比单链表：单链表尾插尾删 O(n)（找前驱），双向循环链表全 O(1)。代价是每个节点多 8 字节（一个prev指针）。

常见陷阱清单

1. 4 个指针修改顺序错→ 断链，最常见也最难调。口诀：「先改新节点两指针，再连旧邻居，最后更新哨兵」。
2. 先free后连邻居→ UAF，读不到前驱后继。
3. LTErase传了哨兵phead→ 删了哨兵，结构崩塌。
4. LTDestroy/LTErase后不置空外部指针→ 悬空指针。
5. 空表判断写错→ 应是phead->next == phead，写成phead == NULL（哨兵永不为空，永远判非空）。
6. 哨兵 data 被误读→ 占位值无意义，遍历应跳过哨兵。

我的实现 vs 教科书实现

• 设计正确：哨兵 + 双向 + 循环，结构标准，头尾插删全 O(1)。
• 代码复用不足：LTPushBack/LTPushFront完全可以调用LTInsert(phead, x)/LTInsert(phead->prev... )复用，当前各写一遍，有重复。
• LTDestroy置空无效：传一级指针无法改外部头指针，应改二级指针或要求调用者手动置空。
• 缺接口：没有LTSize、LTEmpty（判空）、LTClear（清空不销毁）。
• vsstd::list：C++ 标准库的list就是这种结构，额外提供迭代器、splice（O(1) 拼接）、size维护。

拓展知识点

变体与进阶

• Linux 内核链表：反向设计——把链表节点（struct list_head）嵌入到业务结构体里，而非把业务数据放进链表节点。这样一套链表代码能挂任意类型，极致复用。
• LRU Cache：HashMap + 双向链表，O(1) 访问 + O(1) 淘汰。访问一个节点就移到链表头，满了删尾。
• 不带头双向链表：去掉哨兵，但头插删要特判空表，代码稍繁。

常见考点

• 双向链表插入/删除 4 个指针的顺序（口诀见上）。
• 哨兵位的作用：统一边界，免特判。
• 为何循环 + 哨兵能让头尾操作 O(1)：哨兵 prev/next 直接定位首尾。

与其他结构的关系

双向链表是单链表的升级版（加prev），常用来实现队列、栈、LRU、调度队列。std::deque（双端队列）底层用分块的双向链表/数组组合。和单链表、顺序表同属线性表家族。

一句话记忆法

双向循环链表：哨兵是圆心，首尾在隔壁，插删都 O(1)，改 4 指针先新后旧、先连后断，空表看 next==phead。