先还原一个很短的事故。同事给后台的「操作记录」加了一个撤销栈,每条记录放在一个节点里,节点记住上一条记录,栈顶用变量 head 指过去。做展示的时候他顺手写了一个反转函数,想把最近的操作排在最前面。结果页面上只剩一条记录,剩下的全没了。
他以为是数据没写进去,加日志一看,节点都还在,只是从一个节点开始往后走,第一步就走到了空。问题出在反转函数里一句很普通的赋值:先把当前节点的 next 改成前一个节点,再执行 cur = cur.next 想继续往后走。可这时候 cur.next 已经不是原来的后继,而是刚刚接上的前驱。指针被自己亲手改掉了,后面半条链表就此失联。
链表的所有坑,几乎都能归到同一件事:你手里只有「当前节点」和它记住的指针,一旦这个指针被改写,原来的路就没了。这篇先把单链表、双链表和环形链表的结构讲清楚,再解释为什么快慢指针能判环、能找入口、能找中点,最后把链表真正的代价摆出来。链表不是「比数组高级」的结构,它只是一种用指针换掉连续内存的取舍。
现场:反转之后只剩一个节点
先看错误版本的写法。为了让现象可复现,节点用最普通的对象表示,值放在 v,后继放在 next;打印函数遇到重复节点会停下来,避免死循环把终端刷满。
function reverseLost(head) {
let prev = null, cur = head;
while (cur) {
cur.next = prev; // 第一步:把当前节点指向前一个
prev = cur; // 第二步:前一个变成当前
cur = cur.next; // 第三步:想往后走,但 next 已经被改成了 prev
}
return prev;
}
用 1 2 3 4 5 跑一遍,输出只有 1。原因不是循环没执行,而是循环只执行了一次:处理节点 1 时,1.next 被改成 null,随后 cur = cur.next 取到的就是 null,循环结束。正确的顺序必须在改指针之前,把原来的后继存到一个临时变量里。
function reverseOk(head) {
let prev = null, cur = head;
while (cur) {
const next = cur.next; // 先记住原来的路
cur.next = prev; // 再改指针
prev = cur; // 前一个前移
cur = next; // 用存下来的后继继续走
}
return prev;
}
还有一种更隐蔽的写法,递归反转时忘了把原头节点的 next 置空。代码看起来很短,效果却是把链表首尾接成了一个环,打印时永远不会结束。本机跑出来的序列是 5 4 3 2 1,接着又回到 2,一直循环。很多「页面转圈」「日志刷屏」的线上问题,根子就在这种自己接出来的环上。
这三步的顺序不是风格问题,而是正确性问题。只要「保存后继」放到改指针之后,后半条链表就丢了;只要最后没有把新的尾节点指向空,链表就成环。写完反转函数,别急着看返回值,先用三条记录和一条记录分别跑一遍,再看五条记录,三个边界过了才算过。
单链表到底长什么样
单链表(single linked list)是最简单的形式:每个节点存一个值,再存一个指向下一个节点的引用。整条链表只暴露一个入口,通常叫 head。没有下标,没有长度,想知道第几个元素,只能从头一个一个数。
因为只有向后的指针,单链表的操作成本要分情况记,不能笼统说「插入是 O(1)」。已经拿到某个节点、要在它后面插入一个新节点,改两次指针就行,这一步确实是常数时间;但要在某个值前面插入,得先从头找到它的前驱,这段查找是线性的。删除也一样:拿到要删的节点,单链表没法直接找到它的前驱,还是得从头找。
头插和头删是单链表最便宜的操作,改一个 head 就行,所以它很适合做栈:新记录压在最前面,撤销时取最前面。尾部插入则要先走到最后一个节点,除非额外维护一个 tail 指针。很多手写链表性能不如预期,就是因为每次 append 都在从头遍历,明明说是 O(1),实际是 O(n)。
工程实现里常加一个「哨兵节点」(sentinel),也就是一个不存业务数据的假头节点,让空链表和非空链表的操作走同一套代码。没有哨兵时,删除第一个节点要单独改 head,插入第一个节点也要单独处理,边界分支多了就容易漏。哨兵用一点内存换掉这些分支,代价是遍历时要记得从 sentinel.next 开始。
双链表:多一个指针换掉一次查找
双链表(doubly linked list)的节点多存一个 prev,指向前一个节点。多出来的这个指针,解决的是单链表最难受的一件事:拿到一个节点,却删不掉它,因为找不到前驱。
单链表删除
知道节点 x 要删,还得从头找到 x 的前驱,把前驱的 next 跨过 x。查找是 O(n),删除本身是 O(1),合起来还是 O(n)。
双链表删除
知道节点 x 要删,直接改 x.prev.next 和 x.next.prev,两步指针操作,O(1)。代价是每个节点多一个指针,插入删除要维护两套链接。
这个差别在缓存淘汰里非常具体。LRU(最近最少使用)缓存要求「命中一个 key 就把它挪到最前面,满了就删掉最后面」。如果链表节点同时被哈希表索引,双链表拿到节点后能在常数时间内摘除并重新挂到头部;换成单链表,摘除时还得再找前驱,整个缓存的时间复杂度就退化了。所以几乎所有手写 LRU 都用「哈希表加双链表」,不是偏好,而是单链表做不到。
双链表的代价也很实在。每个节点多一个指针,内存占用上升;每次插入删除要改四个方向的引用,漏一个就出现「往前走正常、往后走断掉」的半坏状态。常见事故是删除节点时只改了 prev.next,忘了改 next.prev,从尾部反向遍历时就会访问到已经删掉的节点。调试这类问题,最有效的办法不是盯代码,而是写一个双向遍历的检查函数,从前往后走一遍、从后往前走一遍,看节点数和顺序是否一致。
环形双链表加一个哨兵,是很多语言标准库里链表实现的形态:哨兵自己既是头也是尾,空链表时它的 next 和 prev 都指向自己。这样插入和删除永远不用判空,代码短,边界少。代价是遍历时要判断「是不是又回到了哨兵」,不能再用 null 当终止条件。
环形链表与快慢指针
环形链表(cyclic linked list)不是一种特殊节点,而是链表的某个 next 指回了前面的节点,导致从 head 出发永远走不到空。它可能是业务故意做的环形缓冲,也可能是 bug 接出来的环。判断有没有环,最直接的做法是边走边记「访问过哪些节点」,但这样要额外存一整套节点引用;快慢指针用两个变量就能做到。
快慢指针(fast and slow pointers)的思路是:慢指针每次走一步,快指针每次走两步。如果链表没有环,快指针会先走到空;如果有环,两个指针最终都会进入环里,而快指针每轮比慢指针多走一步,二者在环内的距离每轮缩小一,最多绕一圈就会相遇。这里的关键不是「快指针追上慢指针」这句话,而是「相对速度是一,所以不会跳过」这个论证。
function hasCycle(head) {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}
找环的入口用的是同一套指针,但要多推一步。设头到入口的距离是 a,入口到相遇点的距离是 b,环长是 L。相遇时慢指针走了 a + b,快指针走了 a + b + kL,而快指针走的是慢指针的两倍,所以 a + b = kL,也就是 a = kL - b。换成实际含义:从头出发走 a 步,和从相遇点出发走 L - b 步,会同时到达入口。于是把其中一个指针放回头部,两个指针都改成每次一步,再次相遇的位置就是入口。
function cycleEntry(head) {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) break;
}
if (!fast || !fast.next) return null;
slow = head;
while (slow !== fast) { slow = slow.next; fast = fast.next; }
return slow;
}
本机拿 1 2 3 4 5 6 建了一条链,把尾节点接回 4 号节点,hasCycle 返回 true,cycleEntry 返回的值是 4。找中点也是同一套走法,只是不需要判相遇:快指针走到头时,慢指针正好在一半的位置。六个节点的中点是 4 号,五个节点的中点是 3 号,这个差异来自「偶数个节点时中点取哪一个」的定义,写代码前要先定清楚。
fast 和 fast.next,因为循环体里要读 fast.next.next。只有一个节点的自环、空链表、两个节点的环,这三种情况要单独跑一遍,不要只拿长链表验证。现象、原因与第一步排查
下面这些现象在链表代码里出现频率很高。看到类似症状,先按表里的「第一步」定位,不要一上来就重写整个函数。
| 现象 | 真实原因 | 第一步查什么 |
|---|---|---|
| 反转后只打印出一个节点 | 先改 cur.next 再读它,后继指针已经丢了 | 循环里是否先把 next 存进临时变量 |
| 打印链表时停不下来 | 递归反转没把原头节点的 next 置空,首尾成环 | 反转结束后尾节点的 next 是否为 null |
| 删除后正向遍历正常,反向遍历报错 | 双链表删除只改了一个方向,next.prev 还指着已删节点 | 删除时是否同时改了 prev.next 与 next.prev |
| 追加 10 万条记录越来越慢 | 每次 append 都从头找尾,实际是 O(n²) | 是否维护了 tail 指针,或者用了哨兵 |
| 按序号取第 k 条很慢 | 链表没有下标,随机访问必须从头走 | 调用方是否把链表当数组用 |
| 快慢指针偶尔报空指针 | 循环条件只判了 fast,没判 fast.next | 循环体是否访问了 fast.next.next |
| 环检测一直返回 false | 比较的是节点值而不是节点引用,或者环根本没接上 | 用同一对象引用比较,并打印环入口 |
| 多线程下遍历时节点消失 | 另一个线程正在删除节点,链表没有并发保护 | 是否需要在遍历前加锁或改用不可变结构 |
这张表里最容易误判的是第一行和第三行。第一行看起来像「数据丢了」,其实是「路断了」,节点对象还在内存里,只是没有任何指针能走到它;第三行看起来像「反向遍历的代码写错了」,实际是正向删除时留下的悬挂指针。判断链表问题,先问「哪个指针应该指向谁,现在指向了谁」,再问「谁还能走到这个节点」。
边界与代价:链表不是免费的
链表用指针换来了「不用连续内存」和「已知位置插入删除便宜」,代价则集中在访问和局部性上。数组的元素挨在一起,CPU 一次读一整条缓存行,后面的元素大概率已经在缓存里;链表的节点是单独分配的,地址可能散落在堆的各处,每走一步都可能是一次缓存未命中。数据量小的时候感觉不出来,数据量大、遍历频繁的时候差距会非常明显。
本机做过一组很粗糙的对照:同样 10 万个元素,随机访问第 99999 个 100 次,数组耗时约 0.0003 毫秒,链表耗时约 14.9 毫秒。这个数字不能当成通用结论,因为 JavaScript 的对象有额外开销,JIT 也会影响结果;但它足以说明方向:随机访问是链表的绝对短板,差几个数量级不是算法常数的问题,而是「必须走 10 万步」和「一次寻址」的区别。
再看这组数字背后的机制。数组的 10 万个整数在一块连续内存里,按下标访问是一次基址加偏移的计算,不需要经过任何节点;链表的节点是 10 万个独立对象,每个对象里有值和指针,从 head 走到第 99999 个节点必须经过前面所有节点,每一步都要读一次对象里的 next。这不是「链表慢一点」,而是「一个用公式算地址,一个用脚一步步走」。
另一项代价是分配。每个节点都要单独申请内存,节点越多,分配器和垃圾回收的压力越大。数组扩容虽然要搬一次数据,但均摊下来每次追加仍然很便宜;链表每次插入都是一次真实的对象创建,没有「摊薄」这回事。在 GC 敏感的服务里,大量小节点会让停顿变多,这不是理论问题,是监控里能看到的。
所以链表的适用范围要说清楚:需要频繁在已知位置插入删除、元素数量增长不可预测、不需要按下标随机访问、遍历时能接受指针跳转,这些场景适合链表。典型例子是 LRU 缓存、撤销栈、稀疏图的邻接表、流式数据的缓冲。反过来,需要排序、二分、频繁按下标访问、批量遍历且在意缓存命中率的场景,数组几乎总是更好的选择。链表不是「更高级的数组」,它只是另一种取舍。
当天能做的练习
- 把本文的错误反转函数原样敲进编辑器,用 1、3、5 个节点各跑一次,打印结果并解释每一步
cur和prev指向哪个节点。 - 实现正确的迭代反转,再实现递归反转,分别测试空链表、单节点、双节点、五节点。递归版本故意不置空尾节点,观察打印函数怎样检测到环。
- 写一个双链表,实现
insertAfter、remove、moveToHead,再用「从前往后」和「从后往前」两个方向遍历,检查节点数量和顺序是否一致。 - 用快慢指针找中点,分别测试 4、5、6、7 个节点,记录返回值,并说明偶数长度时你选择的是偏左还是偏右的中点。
- 构造一条带环的链表,先打印
hasCycle与cycleEntry的结果,再把环拆掉,确认两个函数都返回正确值。记录你第一次跑空链表时发生的报错。
小结与下一篇
三句话收一下:链表的所有操作都围绕「谁能走到谁」,改指针前先保存原来的路;单链表便宜在头插头删,双链表多一个指针换来 O(1) 删除;快慢指针靠相对速度为一保证相遇,再用距离关系推出环入口。
下一篇比较数组和链表。今天已经看到链表随机访问的代价,但「链表插入一定比数组快」这句话也有前提:数组在尾部追加是均摊常数,在中间插入才需要搬移;链表在已知位置插入是常数,但找到那个位置往往要线性时间。下一篇会把两边每一种操作的完整成本列出来,并用本机测量说明为什么小数据量下数组经常全面胜出。