21、链表（下）：双向链表、循环链表、链表与数组的对比

好，咱们接着聊链表。上一章我把单链表的基本操作捋了一遍，今天咱们把剩下的两种重要变体——双向链表和循环链表——讲透。最后再跟数组做个硬碰硬的对比。

说实话，我在项目中用双向链表的频率比单链表高得多。为什么？因为很多时候你需要往回走。你想想看，一个文本编辑器里的撤销操作，或者一个浏览器的前进后退，底层基本都是双向链表在撑着。

21.1 双向链表：能进能退

双向链表，说白了就是在每个节点里多存了一个指针——指向前一个节点。结构体长这样：

typedef struct DNode {
    int data;
    struct DNode *prev;  // 指向前驱
    struct DNode *next;  // 指向后继
} DNode;

嗯，这里要注意：prev 和 next 两个指针，让双向链表在插入和删除时比单链表灵活很多。你不需要再单独维护一个前驱指针了。

21.1.1 插入操作

在双向链表中插入一个节点，核心步骤是四步。我习惯先连新节点的前后指针，再动老节点的指针。顺序错了容易丢链。

// 在 p 节点之后插入新节点 s
s->prev = p;
s->next = p->next;
if (p->next != NULL) {
    p->next->prev = s;
}
p->next = s;

21.1.2 删除操作

删除就简单多了，因为你能直接拿到前驱和后继：

// 删除节点 p
p->prev->next = p->next;
if (p->next != NULL) {
    p->next->prev = p->prev;
}
free(p);

这里同样要小心——如果 p 是头节点，p->prev 是 NULL，直接访问会崩。我建议你在函数入口处加一个断言：assert(p != NULL && p->prev != NULL);

21.2 循环链表：首尾相连

循环链表，就是把最后一个节点的 next 指向头节点。如果是双向循环链表，头节点的 prev 还要指向尾节点。这样一来，整个链表就变成了一个环。

为什么需要循环链表？我举两个实际场景：

• 操作系统进程调度：时间片轮转算法，每个进程轮流执行，转一圈回来继续。用循环链表天然合适。
• 约瑟夫环问题：一群人围成一圈报数，数到 m 的人出列。这就是循环链表的经典考题。

循环链表的遍历终止条件不再是 p == NULL，而是 p == head。写循环的时候要小心死循环，我建议用 do-while 而不是 while：

DNode *p = head;
if (p != NULL) {
    do {
        printf("%d ", p->data);
        p = p->next;
    } while (p != head);
}

21.3 链表与数组的对比

这个对比，我每次面试新人都会问。说白了就是空间换时间，还是时间换空间的问题。咱们直接上表：

操作	数组	单链表	双向链表
随机访问（下标）	O(1)	O(n)	O(n)
头部插入/删除	O(n)	O(1)	O(1)
尾部插入（已知尾指针）	O(1) 均摊	O(1)	O(1)
中间插入（已知位置）	O(n)	O(1)	O(1)
内存占用	低（仅数据）	中（多一个指针）	高（多两个指针）
内存连续性	连续	不连续	不连续
缓存友好性	高	低	低

你看，数组在随机访问上碾压链表，但链表在插入删除上完胜。我个人的经验是：

• 如果数据量固定、频繁查找，用数组。
• 如果数据量动态变化、频繁插入删除，用链表。
• 如果内存碎片敏感（比如嵌入式裸机环境），慎用链表。

21.4 三种链表的对比图

下面这张 SVG 图，把单链表、双向链表、循环链表的结构画在一起，方便你对比记忆：

21.5 避坑指南

最后，我把自己踩过的坑总结一下，你写代码的时候多留个心眼：

• 指针初始化：每次创建节点，记得把 prev 和 next 都置为 NULL。野指针是链表 bug 的头号元凶。
• 头节点处理：插入或删除头节点时，要更新链表头指针。我建议用二级指针或者哑节点来避免这个问题。
• 内存泄漏：删除节点后一定要 free。我在一个长期运行的服务程序里漏了一次，内存以每天 1MB 的速度上涨，三天后 OOM 被 kill 了。
• 循环链表死循环：遍历时一定要有终止条件，别写成 while (1) 然后忘了 break。

好了，链表的内容就讲到这里。双向链表和循环链表在实际项目中非常实用，尤其是当你需要频繁地前后遍历或者实现环形缓冲的时候。数组和链表各有优劣，选型的时候多想想你的数据访问模式——是读多写少，还是写多读少？想清楚了，选择自然就出来了。

---

公众号:蓝海资料掘金营，微信deep3321