双向循环链表：单向的进化，插入删除的终极形态

双向循环链表：单向的进化，插入删除的终极形态

1. 灵魂拷问：单向链表不够用了吗？

上一篇我们手撕了单向链表，头插、尾插、查找、删除，每个操作都剖析得明明白白。但在实际动手写代码时，我踩到了几个痛到刻骨铭心的坑：

• 尾插必须从头跑到尾：每次想在末尾加个元素，都要 while(cur->next) 遍历整条链表，时间复杂度 O(n)。
• 找不到前驱，删除太痛苦：要删除某个节点，必须先找到它的前一个节点，否则链表就断了。为此我还专门写了个 FindBefore 函数。
• 无法回头：单向链表只能一路走到黑。想返回上一个节点？对不起，要么重头再来，要么提前存好指针。

这些痛点，都是因为单向链表只有一根 next 指针。如果每个节点除了知道"下一个是谁"，还知道"上一个是谁"，那么尾插不用遍历、删除不用找前驱、遍历可以双向走——所有问题迎刃而解。

如果再进一步，让尾节点的 next 指向头节点，头节点的 prev 指向尾节点，链表形成一个闭环，那么尾节点可以通过 head->prev 直接定位，连尾指针都不用单独维护。这就是我们今天要实现的无头双向循环链表，真正打破单向链表的性能瓶颈。

2. 结构设计：多一根指针，少无数麻烦

2.1 节点结构体

typedef struct _DDLinkListNode {
DataType data; // 数据域
struct _DDLinkListNode* next; // 后继指针
struct _DDLinkListNode* prev; // 前驱指针 ← 这就是解决所有痛点的关键
} DDLinkListNode;

对比单向链表，只是多了一个 prev 成员。但在算法设计上，一个 prev 换来了插入、删除操作性能的全面提升。

2.2 管理结构体：为什么我不加 tail？

typedef struct _DDLinkList {
DDLinkListNode* head; // 头节点指针
int size; // 节点总数
} DDLinkList;

细心的你可能会问：“既然要优化尾插，为什么不学单向链表那样，维护一个 tail 指针呢？”

答案就在循环二字上。循环链表中，尾节点的 next 指向头节点，头节点的 prev 指向尾节点。因此，头节点的前驱 head->prev 就是尾节点。用 head->prev 访问尾节点的时间复杂度同样是 O(1)，我何必再多维护一个 tail，徒增出错的风险呢？

这就是用结构设计换取代码简化的经典案例。

3. 所有插入操作的基石：InsertBefore

单向链表中，我设计了 InsertAfter 作为核心；而双向循环链表里，InsertBefore（在某个节点前插入）才是真正的万能函数。头插、尾插、指定位置前插、后插，全部通过它实现，一套四步指针操作吃遍天。

3.1 代码实现

static void InsertBefore(DDLinkList* list, DDLinkListNode* pos,
DDLinkListNode* node) {
assert(list && node);

if (list->head == NULL) { // 空链表：自成闭环
node->next = node;
node->prev = node;
list->head = node;
} else {
// 四步指针操作，顺序极为重要
node->prev = pos->prev; // ① 新节点记住前驱
node->next = pos; // ② 新节点记住后继
pos->prev->next = node; // ③ 前驱改为指向新节点
pos->prev = node; // ④ 后继（pos）的前驱改为新节点
}
list->size++;
}

3.2 图解指针重排（重点！）

假设原链表为 … ⇄ A ⇄ B ⇄ …，现要在 B 之前插入 New。操作前状态：

A ⟷ B (A->next = B, B->prev = A)

执行四步操作：

完成后：

A ⇄ New ⇄ B

为什么顺序不能乱？

• 必须先执行 ①②，让新节点先"记住"自己的邻居。
• 如果先执行 ③④，比如先改了 A->next，那 pos->prev 指向的 A 已经发生了变化，步骤 ① 再去找 pos->prev 拿到的就不是原来的 A 了，指针立刻乱套。

原则总结：插入时，先处理新节点的两条指针，再修改邻居的指针。删除时则相反，先处理邻居指针，再释放节点。

4. 头插与尾插：一行代码，O(1) 完成

有了 InsertBefore，头插和尾插变得极其简单，代码复用达到极致。

4.1 头插

ErrorCode DDLinkListPushFront(DDLinkList* plist, DataType val) {
// 校验与创建节点省略…
InsertBefore(plist, plist->head, node);
plist->head = node; // ★ 唯一额外操作：更新头指针
return SUCCESS;
}

头插 = 在当前 head 节点前插入新节点，然后将 head 指向新节点。InsertBefore 已经完成了所有指针连接，只需再挪一下 head 即可。

4.2 尾插

ErrorCode DDLinkListPushBack(DDLinkList* plist, DataType val) {
// 校验与创建节点省略…
InsertBefore(plist, plist->head, node);
// ★ 注意：这里不更新 head！
return SUCCESS;
}

尾插 = 在 head 节点前插入新节点，但**不移动 ****head**。神奇之处：由于链表是循环的，head 的前一个位置恰好就是尾节点之后。新节点插入到 head 之前，就成了新的尾节点，而 head 的位置不变，整个结构保持循环。不需要遍历，时间复杂度 O(1)。

补充说明：当链表为空时（head == NULL），InsertBefore 会走空链表分支，将新节点的 next 和 prev 都指向自身，并将 head 设置为新节点。此时新节点既是头节点也是尾节点，head 被正确初始化，无需额外处理。

单向链表的尾插 O(n) 之痛，至此彻底解决。

5. 指定位置插入：前后都能插，逻辑统一

5.1 在 pos 前面插入

ErrorCode DDLinkListInsertFront(DDLinkList* plist, DDLinkListNode* pos,
DataType val) {
// 校验与创建节点省略…
InsertBefore(plist, pos, node);
return SUCCESS;
}

直接调用 InsertBefore。由于 pos 本身在链表中，操作后 head 仍然有效，无需额外处理。

5.2 在 pos 后面插入

ErrorCode DDLinkListInsertBack(DDLinkList* plist, DDLinkListNode* pos,
DataType val) {
// 校验与创建节点省略…
InsertBefore(plist, pos->next, node); // ← 核心转换
return SUCCESS;
}

在 pos 后面插入，等价于在 pos->next 前面插入。因为循环链表中 pos->next 永远有效（即使 pos 是尾节点，pos->next 也指向 head），所以这个转换不需要任何边界判断。双向循环链表的设计之美，在这一刻体现得淋漓尽致。

6. 查找与获取头尾

6.1 查找节点

DDLinkListNode* DDLinkListFind(const DDLinkList* plist, DataType val) {
// 空链表检查省略…
DDLinkListNode* cur = plist->head;
do {
if (cur->data == val) return cur;
cur = cur->next;
} while (cur != plist->head); // 循环一圈后退出
return NULL;
}

循环链表的遍历必须使用 do-while，因为一开始 cur 就等于 head，如果使用 while 会直接跳过循环体。

6.2 获取头部和尾部数据

ErrorCode DDLinkListFront(const DDLinkList* plist, DataType* val) {
*val = plist->head->data;
return SUCCESS;
}

ErrorCode DDLinkListBack(const DDLinkList* plist, DataType* val) {
*val = plist->head->prev->data; // ★ 循环链表的尾节点就是 head->prev
return SUCCESS;
}

head->prev 直接拿到尾节点，时间复杂度 O(1)。单向链表需要从头跑到尾 O(n)，差距明显。

7. 删除操作：通用摘除公式

7.1 删除指定节点 Erase

ErrorCode DDLinkListErase(DDLinkList* plist, DDLinkListNode* pos) {
// 校验省略…

if (pos->next == pos) { // 仅剩一个节点
plist->head = NULL;
} else {
if (pos == plist->head) { // 删除的是头节点
plist->head = pos->next; // 先转移 head，再摘除 pos
}
// 通用摘除操作：让前驱和后继互连，绕过 pos
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
}
plist->size—; // 先减少计数
free(pos); // 再释放节点内存
return SUCCESS;
}

双向链表删除的精髓就在这两行：

pos->prev->next = pos->next; // 前驱跳过 pos，连到后继
pos->next->prev = pos->prev; // 后继跳过 pos，连到前驱

无论 pos 是头节点、尾节点还是中间节点，这两行代码都能正确摘除。需要特殊处理的只有两种情况：

回想单向链表删除的烦恼：必须先找到前驱节点。而这里，pos->prev 直接就是前驱，O(1) 一步到位。

为什么先 size– 再 free？在调试时，如果先释放节点再减少计数，而此时程序因其他原因崩溃，打印 size 会得到错误的值（仍包含已释放的节点）。先减计数再释放，能让调试日志在任何时刻都反映链表的真实状态。

7.2 按值删除 Remove

ErrorCode DDLinkListRemove(DDLinkList* plist, DataType val) {
DDLinkListNode* node = DDLinkListFind(plist, val);
if (node) return DDLinkListErase(plist, node);
return ERR_DATA_NOT_EXISTS;
}

Find + Erase 组合，简洁明了。

7.3 删除所有指定值 RemoveAll

这个函数的设计稍微复杂一些，需要格外小心循环控制。

ErrorCode DDLinkListRemoveAll(DDLinkList* plist, DataType val) {
if (plist == NULL) {
LOG("参数错误");
return ERR_INVALID_PARAM;
}
if (plist->head == NULL) {
LOG("链表为空，无数据可删除");
return ERR_DATA_NOT_EXISTS;
}

DDLinkListNode* cur = plist->head->next; // 从第二个节点开始
do {
if (cur->data == val) {
DDLinkListNode* toDel = cur;
cur = cur->next; // ① 先移动 cur
DDLinkListErase(plist, toDel); // ② 再删除节点
continue; // ★ 跳过末尾的 cur = cur->next
}
cur = cur->next;
} while (cur != plist->head); // 循环至头节点前停止

// 单独判断头节点
if (plist->head && plist->head->data == val) {
DDLinkListErase(plist, plist->head);
}
return SUCCESS;
}

为什么头节点要最后单独处理？

如果头节点在循环中被删了，plist->head 会更新为下一个节点，那么 while (cur != plist->head) 这个终止条件就不稳定了——head 变了，cur 也可能因此无法正确回到起点。把有可能改变 head 的操作放在最后单独处理，是最稳妥的工程实践。

删除后为什么用 **continue**？

因为 cur 在删除前已经向前移动了一步（cur = cur->next），如果让循环末尾的 cur = cur->next 再执行一次，就会跳过一个节点。所以用 continue 跳过尾部移动，保证遍历不会漏节点。

8. 销毁链表

ErrorCode DDLinkListDestroy(DDLinkList* plist) {
if (plist == NULL) return ERR_INVALID_PARAM;
while (plist->head) {
DDLinkListErase(plist, plist->head); // 反复删除头节点
}
return SUCCESS;
}

每次删除头节点，Erase 内部会自动更新 head（如果只剩一个节点则置为 NULL，否则指向下一个节点）。当 head 变为 NULL 时，循环结束，链表安全销毁。

9. 设计决策速查表

10. 学习体会

写完双向循环链表，我最大的感受是：好的数据结构设计，不是功能的堆砌，而是用最少的代码，覆盖最多的场景。

InsertBefore 一个函数，撑起了四种插入操作。pos->prev->next = pos->next; pos->next->prev = pos->prev; 两行代码，覆盖了所有情况下的节点摘除。回想单向链表里那些冗长的特殊判断和遍历查找，双向链表用一根额外的 prev 指针，换来了代码的极大简洁和执行效率的显著提升。

这就是数据结构设计的魅力：在时间和空间之间做出权衡，用精巧的结构让算法自然变快、变简单。下一次当你觉得某个操作实现起来很别扭时，不妨回头审视一下：是不是数据结构本身选得不对？换成双向链表，也许问题就消失了。

从单向到双向，从线性到循环，我们一步一步把链表这个最基础的数据结构吃透。下一篇，我们将学习泛型双向链表。敬请期待吧！