一、链表长什么样：值加一根绳子

[10, 20, 30, 40] 这根链表，是由四个节点串起来的。 每个节点装两样东西：自己的值，和下一家在哪儿。 最后一个节点的绳子指向空（Python 里是 None），表示到头了。 顺着绳子走一遍：10 到 20 到 30 到 40 到空。走法只有这一种——从头开始，一路往下。

关键的一点：链表里没有「第几个」这个属性。节点不知道自己排第几，只知道自己后面是谁。 所以「取第 3 个」这件事，链表得从头数两回。这也是 3.1 里那 3718 倍的来源。

二、插一个进去：改两根绳子

在 20 和 30 之间插 25。 数组的做法是把 30 和 40 全往后挪一格，链表一根手指都不用动，只改两根绳子。 第一步：新节点的绳子指向 30。第二步：20 的绳子改指向新节点。 顺序不能反。 要是先把 20 的绳子改成指向新节点，30 在哪儿就再也没人知道了——那串 30、40 从此找不回来。

这就是链表操作最典型的坑：先接上新的，再断开旧的。3.3 后面的删除也是同一条原则。 两行代码，两条赋值语句。代价从「挪一片」变成「改两根」，这就是链表存在的理由。

三、双向链表：多一根回头的绳子

单向链表只能往后走。想从 30 找回到 20，没门——只能从头再走一遍。 双向链表给每个节点再加一根绳子，指向前一个。 于是 a.next = b 的同时还有 b.prev = a，两根绳子互为反向。 好处很实在：能往前也能往后。浏览器的前进后退、编辑器的撤销重做，都要这个本事。

代价也很实在：插入时要改四根绳子，不是两根。而且四根里忘改一根，链子就从那儿断了。 所以双向链表的手写 bug 率明显更高。工程上的做法通常是：能不自己写就不自己写，用标准库给的。

四、删除：先接上，再断开

删掉 20。做法是让 10 的绳子直接搭到 30，然后丢掉 20 这个节点。 结果变成 10 到 30 到 40。20 不在链子上了。 顺序又是关键：先让前一个指向后一个，再丢掉被删节点的引用。反过来做，节点就再也找不回来了。

在 C 这类要手动管内存的语言里，这直接就是内存泄漏：那块内存还在，但没有任何变量指着它， 谁也回收不了。 Python 有垃圾回收，丢了引用会自动收走——但「先接上再断开」这个顺序仍然要守。因为顺序错了， 你连「被删的是哪个」都不知道了。

五、链表不是升级版数组

看完这一节容易有个错觉：链表又能插又能删，是不是比数组强？ 不是。 链表每取一次数都要走一遍，而且每个节点多存一根（双向是两根）指针， 内存占用比数组高，缓存也不友好——节点散在各处，不像数组那样连号。 所以真实项目里数组用得远多于链表。链表出场的地方很明确：插删频繁、而且不需要按下标随机取。

这句话和第 3.1 那条结论是同一句：没有最快，只有最配。

六、动手 Demo：建一条链表，插一个、删一个，再看看双向的

先手写一个节点类，把四个数串成一条单向链表，顺着走一遍。 再在中间插一个 25，只改两根绳子，看结果。 最后建一条双向链表，验证前后两个方向都能走。

class Node:
    def __init__(self, v, nxt=None, prv=None):
        self.v, self.nxt, self.prv = v, nxt, prv

head = None
for v in (40, 30, 20, 10):
    head = Node(v, head)

def walk(p):
    out = []
    while p:
        out.append(p.v)
        p = p.nxt
    return out
print(walk(head))

# 在 20 后面插 25
p = head
while p.v != 20:
    p = p.nxt
p.nxt = Node(25, p.nxt)
print(walk(head))

# 双向：两个方向各走一遍
a, b = Node(10), Node(20)
a.nxt, b.prv = b, a
print(a.next if hasattr(a, 'next') else a.nxt.v, b.prv.v)

实跑输出：

--------------------------------------------------------------------
链表：单向能往下走，双向能回头
--------------------------------------------------------------------


  ① 先看看链表长什么样
  --------------------------------------------------------------------
  建一条链表：[10, 20, 30, 40]
  顺着绳子走一遍：10 -> 20 -> 30 -> 40 -> None
  链表里没有「第几个」这个概念，只有「下一个是谁」。所以想取第 3 个，只能从头数两回。

  ② 插一个进去，改几根绳子
  --------------------------------------------------------------------
  在 20 和 30 之间插 25：
    1. 新节点的绳子指向 30
    2. 20 的绳子改指向新节点
  两根绳子，两行代码。数组要做的是把 30、40 全往后挪一格。

  ③ 双向链表多一根回头的绳子
  --------------------------------------------------------------------
  a.next = b，b.prev = a
  从 b 能回到 a：b.prev.v = 10
  从 a 能走到 b：a.next.v = 20

| 对比项 | 单向链表 | 双向链表 |
|---|---|---|
| 能往哪走 | 只能往后 | 前后都行 |
| 插入要改几根 | 2 根 | 4 根 |
| 每个节点多占 | 1 个指针 | 2 个指针 |
| 典型用途 | 队列、栈的底层 | 浏览器历史、撤销重做 |

  多一根绳子的代价是每次插入要改四处，忘了改一处就断链。所以双向链表的手写 bug 率明显更高。

  ④ 删除也一样：先接上，再断开
  --------------------------------------------------------------------
  删掉 20：让 10 的绳子直接搭到 30
  结果：10 -> 30 -> 40 -> None
  注意顺序：先让前一个指向后一个，再丢掉被删节点的引用。反过来做，节点就找不回来了——这叫内存泄漏。

①建链表那段是倒着插的：40 先进，最后 10 进，结果头是 10。因为每次都是「新节点挂到当前头前面」。 ②插入只写了一行 p.nxt = Node(25, p.nxt)。 这一行同时做了两件事：新节点指向原来的下一个，前一个指向新节点。顺序天然是对的。 ③最后一行两个值都是下一家的号码：从 a 往后看是 20，从 b 往回看是 10。双向链表就是这两根绳子。 ④注意 while p.v != 20 这个找法：链表没有下标，只能一个个比。这就是「取第几个很慢」的具体样子。

30 秒实验

1. 在链表里删掉 20（让 10 直接指向 30），打印结果，确认 20 不见了。
2. 把插入改成「插在 30 前面」，看要改哪两根绳子。
3. 测一下：从链表取第 15000 个，和 arr[15000] 比，差多少倍。

常见误区

1. 「链表是数组的升级版。」取数是数组赢，插删是链表赢，还多占内存。
2. 「插入随便改哪根先都行。」先改前一个的绳子，后面那串就丢了。必须新节点先接上。
3. 「Python 有垃圾回收，删除顺序无所谓。」顺序错了会找不到被删的节点，回收也救不回来。

链表和数组各占一半长处，那实际选的时候看什么？ 下一节把三条判据摆成一张表，再补一个「格子固定却能一直收数据」的环形缓冲区。

• ☐ （本篇完，下一篇 3.4 数组、链表与环形缓冲区）

相关笔记

• 堆栈与队列
• 数组、链表与环形缓冲区
• 17 编程原理 · 索引
• 🧮 写给大家看的算法书 · 索引