链表

链表通过分别分配的节点之间的引用保存序列顺序，而不是把元素放在连续槽位中。

from dataclasses import dataclass


@dataclass
class Node:
    value: int
    next: "Node | None" = None

变体与不变量

• 单链节点指向后继；尾节点指向 None。
• 双链节点同时指向前驱和后继；更新时必须保持两个方向一致。
• 循环链表把尾节点重新连到某个端点，遍历时需要明确的终止规则。

维护头、尾和大小字段可以改善部分操作，却也引入了更多必须在每次修改时保持的不变量。

成本模型

操作	单链表
按位置或值访问/搜索	$O(n)$
在已知节点后插入	$O(1)$
在已知前驱后删除	$O(1)$
维护尾指针时追加	$O(1)$
删除尾节点	$O(n)$

所谓常数时间插入/删除，并不包括寻找节点的成本。双链表同时知道前驱，因此可以在 $O(1)$ 时间内删除已知节点。

权衡

链表提供稳定的节点身份和廉价的局部拼接，但需要承担引用、内存分配、指针追逐和较弱缓存局部性的成本。它适合侵入式链表、哈希表链等结构内部；作为一般序列，动态数组通常是更好的默认选择。

拼接时保留后续节点

单链表的实现通过改链接完成操作，不必移动后面的值。使用上面的 Node：

head = Node(10, Node(30))
pred = head
pred.next = Node(20, pred.next)
assert head.next.value == 20
assert head.next.next.value == 30

removed = pred.next
if removed is None:
    raise IndexError("no successor to remove")
pred.next = removed.next
removed.next = None
assert head.next.value == 30

必须先让新节点保存原来的后继，再修改前驱的链接，否则可能再也无法从头节点找到后半段。删除时绕过目标节点；清空目标的链接只是把它拆开，不会销毁其他地方对它的引用。

这个小例子只保留头指针。完整容器还必须在旧尾节点后插入、或删除最后一个节点时更新尾指针，并且只增减一次大小。空表的头尾均为 None，大小为零；删除唯一元素后必须恢复此状态。头插没有前驱，可用 head = Node(value, head)。也可以用不存放业务元素的哨兵节点，让这个边界与普通拼接类似。

成本表计算常数次链接操作，并假设处理单个元素的成本固定；内存分配和回收没有通用的延迟保证。“已知节点”还必须属于当前链表。让两个链表共用一个已链接节点，或意外把节点连回自身，会破坏所有权或遍历的终止条件，即使每次赋值都只需常数时间。

来源

• Open Data Structures：链表

我的阅读 · 打开过的笔记会记在当前浏览器里。