2.2 链表
前置：数组，约 45 分钟。本节把“链表插入是常数时间”补全为一份包含位置句柄、前驱、尾指针和所有权的准确合同。
从节点和链接开始
链表用链接维持顺序，不用连续槽位维持下标。这项选择换来了局部改链的低成本，也放弃了按整数下标直接定位。
链表由链接定义
单链表的逻辑结构是：
head
│
▼
[1 | next] → [2 | next] → [3 | None]实现通常为每个节点单独分配空间，因此节点可能不相邻。不过，“一定散落在内存各处”也说得太满。内存池、区域分配器或紧凑运行时可以把节点放得很近。链表的抽象合同只要求 next 建立顺序。
最小 Python 节点可以这样写：
class ListNode:
def __init__(self, value, next_node=None):
self.value = value
self.next = next_node
head = ListNode(1, ListNode(2, ListNode(3)))参数名用 next_node，避免遮蔽 Python 内置函数 next()。
按索引查找：先声明下标规则
本章使用从 0 开始的索引。k = 0 返回头节点，负数不接受：
def get_kth(head, k):
if k < 0:
raise IndexError("index out of range")
current = head
for _ in range(k):
if current is None:
raise IndexError("index out of range")
current = current.next
if current is None:
raise IndexError("index out of range")
return current到第 k 个节点要走 k 条链接，时间是 Θ(k + 1)；当 k 与表长 n 同阶时，最坏为 Θ(n)。链表没有从 head 直接算出第 k 个节点地址的公式。
插入和删除：常数操作的前提
已知前驱时插入
def insert_after(previous, value):
if previous is None:
raise ValueError("previous node is required")
node = ListNode(value, previous.next)
previous.next = node
return node创建节点并写两条链接，操作数不随 n 增长，所以是 Θ(1)。前提是调用者已经持有属于这条链的 previous。
若调用者只给“在下标 i 后插入”，实现要先走到第 i 个节点，定位 Θ(i + 1)，改链接 Θ(1)，总时间为 Θ(i + 1)，最坏 Θ(n)。
单链表删除需要前驱
def delete_after(previous):
if previous is None or previous.next is None:
raise IndexError("no successor to delete")
removed = previous.next
previous.next = removed.next
removed.next = None
return removed已知前驱时为 Θ(1)。只持有目标节点通常不足以删除单链表尾节点；找目标的前驱仍可能花 Θ(n)。
有一道面试技巧会把目标节点的后继值复制进目标，再删除后继。它改变了节点身份语义，对尾节点无效，也可能破坏外部持有的节点引用。不能把它当作通用删除合同。
哨兵与尾指针解决不同问题
哨兵放在第一个业务节点之前，不保存业务值：
sentinel → first → ... → tail → None它让空表与删除头节点都能写成“修改某个前驱的 next”。尾指针则让追加不用每次从头找尾部。
| 状态 | 不变量 |
|---|---|
| 空表 | sentinel.next is None，tail is sentinel，size == 0 |
| 非空 | sentinel.next 是头，tail.next is None |
| 每次插删后 | 从头可达节点数等于 size，尾指向最后一个节点 |
哨兵减少分支，但不会自动维护这些不变量。漏改尾指针仍会让下一次追加接到错误位置。
一份可运行的单链表
下面的 Python 3.10+ 实现为每个节点记录 _owner，用常数时间拒绝其他链表的节点和已经删除的节点。insert_after 与 delete_after 都要求前驱属于当前表。调用者可以持有返回的节点，但不能绕过容器直接改写链接或 _owner；生产接口通常封装这些字段。
这里把分配一个固定大小节点算作常数成本。真实分配器、垃圾回收以及元素本身的构造和析构成本，需要另行考虑。
# linked_list_demo.py
class ListNode:
def __init__(self, value: object, next_node: "ListNode | None" = None) -> None:
self.value = value
self.next = next_node
self._owner = None
class SinglyLinkedList:
def __init__(self) -> None:
self._sentinel = ListNode(None)
self._sentinel._owner = self
self._tail = self._sentinel
self._size = 0
@property
def size(self) -> int:
return self._size
def append(self, value: object) -> ListNode:
node = ListNode(value)
node._owner = self
self._tail.next = node
self._tail = node
self._size += 1
return node
def insert_after(self, previous: ListNode | None, value: object) -> ListNode:
if previous is None or previous._owner is not self:
raise ValueError("previous node does not belong to this list")
node = ListNode(value, previous.next)
node._owner = self
previous.next = node
if self._tail is previous:
self._tail = node
self._size += 1
return node
def delete_after(self, previous: ListNode | None) -> object:
if previous is None or previous._owner is not self:
raise ValueError("previous node does not belong to this list")
if previous.next is None:
raise IndexError("no node exists after previous")
removed = previous.next
previous.next = removed.next
if self._tail is removed:
self._tail = previous
removed.next = None
removed._owner = None
self._size -= 1
return removed.value
def get_kth(self, index: int) -> ListNode:
if index < 0:
raise IndexError("index out of range")
current = self._sentinel.next
for _ in range(index):
if current is None:
raise IndexError("index out of range")
current = current.next
if current is None:
raise IndexError("index out of range")
return current
def middle_node(self) -> ListNode:
slow = self._sentinel.next
fast = self._sentinel.next
if slow is None:
raise IndexError("empty list has no middle node")
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
assert slow is not None
return slow
def reverse(self) -> None:
old_head = self._sentinel.next
previous = None
current = old_head
while current is not None:
next_node = current.next
current.next = previous
previous = current
current = next_node
self._sentinel.next = previous
self._tail = old_head if old_head is not None else self._sentinel
def to_list(self) -> list[object]:
result: list[object] = []
current = self._sentinel.next
for _ in range(self._size):
assert current is not None
result.append(current.value)
current = current.next
assert current is None
return result
def main() -> None:
linked = SinglyLinkedList()
linked.append(1)
second = linked.append(2)
linked.append(3)
linked.append(4)
initial = linked.to_list()
inserted = linked.insert_after(second, 9)
after_insert = linked.to_list()
removed = linked.delete_after(inserted)
middle = linked.middle_node().value
linked.reverse()
assert initial == [1, 2, 3, 4]
assert after_insert == [1, 2, 9, 3, 4]
assert removed == 3
assert middle == 9
assert linked.to_list() == [4, 9, 2, 1]
assert linked.size == 4
print(f"初始：{initial}")
print(f"插入后：{after_insert}")
print(f"删除：{removed}")
print(f"中点：{middle}")
print(f"反转：{linked.to_list()}")
print("链表检查通过")
if __name__ == "__main__":
main()运行：
python3 linked_list_demo.py输出：
初始：[1, 2, 3, 4]
插入后：[1, 2, 9, 3, 4]
删除：3
中点：9
反转：[4, 9, 2, 1]
链表检查通过长度为偶数时，本章的快慢指针返回两个中点中的第二个。因此 [1, 2, 9, 4] 返回值为 9。接口若需要第一个中点，应改变快指针的初始位置或循环条件，并把约定写进测试。
单链表操作表
| 操作 | 已有条件 | 时间 | 需要留意 |
|---|---|---|---|
读取第 k 个节点 | 只有头节点 | Θ(k + 1) | 越界和负数规则 |
| 头部插入 | 有哨兵/头句柄 | Θ(1) | 更新头链接 |
| 尾部追加 | 维护尾句柄 | Θ(1) | 空表与尾不变量 |
| 尾部追加 | 只有头节点 | Θ(n) | 先找尾部 |
| 前驱后插入 | 已知前驱 | Θ(1) | 前驱必须属于本表 |
| 删除后继 | 已知前驱 | Θ(1) | 可能需要更新尾 |
| 按值删除 | 只有头节点 | 最坏 Θ(n) | 查找前驱占主导 |
| 删除尾节点 | 只有头和尾 | Θ(n) | 单链表还要找前驱 |
| 完整遍历 | 有头节点 | Θ(n) | 可能有环时先定策略 |
表里的“句柄”可以是节点引用、受控迭代器或容器提供的位置对象。只给整数下标时，链表需要遍历。
双链表
双链表节点同时保存前驱和后继：
None ← [1] ⇄ [2] ⇄ [3] → Noneclass DoublyNode:
def __init__(self, value, previous=None, next_node=None):
self.value = value
self.previous = previous
self.next = next_node
def unlink(node, head, tail):
if node.previous is None:
head = node.next
else:
node.previous.next = node.next
if node.next is None:
tail = node.previous
else:
node.next.previous = node.previous
node.previous = None
node.next = None
return head, tailunlink 要求 node 是当前无环双链表中仍然有效的节点，且 head、tail 对应同一条链；重复删除不在这个函数的合同内。已知节点时，删除只改固定数量的链接，时间 Θ(1)。双向遍历也不必反复从头开始。代价是每个节点多一条链接、插删多几次写操作，以及更复杂的不变量。节点总内存不一定恰好翻倍，因为对象头、对齐和负载值仍占空间。
循环链表
循环链表让尾节点指回头节点：
head → [A] → [B] → [C]
▲ │
└───────────┘它适合成员会增删的轮询路线。遍历时不能再等 None：
def circular_values(head):
if head is None:
return []
result = [head.value]
current = head.next
while current is not head:
result.append(current.value)
current = current.next
return result这段遍历要求非空输入构成一个经过 head 的完整环。若链在别处进入环，循环不会回到 head；若中途断链，则会访问 None。循环终止依赖节点身份 is，不是值相等，节点值可以重复。访问 n 个节点需 Θ(n) 时间，返回的列表占 Θ(n) 输出空间。
环形缓冲区（ring buffer）通常由固定数组和首尾索引实现，不是循环链表的同义词。二者都能表达循环使用位置，但布局和复杂度合同不同。
三个基础算法
原地反转
每次保存后继，再把当前链接反向：
def reverse(head):
previous = None
current = head
while current is not None:
next_node = current.next
current.next = previous
previous = current
current = next_node
return previous每个节点处理一次，时间 Θ(n)；只保存三个节点引用，辅助空间 Θ(1)。
找中点
def middle_node(head):
if head is None:
raise IndexError("empty list")
slow = head
fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
return slow快指针每轮走两条链接，慢指针走一条。快指针到尾部时，慢指针走了约一半。时间 Θ(n)，辅助空间 Θ(1)。当前写法对偶数长度返回第二中点。
Floyd 判环
def has_cycle(head):
slow = head
fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False无环时，快指针到达 None。有环时，两个指针最终在环内相遇。设入环前有 μ 个节点，环长为 λ。两指针都进入环后，每轮相对距离增加 1（模 λ），最多再走 λ 轮就会重合。因此时间为 Θ(μ + λ)，也就是按可达不同节点数计的 Θ(n)，辅助空间 Θ(1)。比较的是节点身份，不是节点值。
语言里的链表与位置句柄
Python
标准库没有通用 LinkedList 类型。队列或双端队列通常使用 collections.deque，它不是本章手写的节点链。手写节点适合学习算法或表达确实需要稳定节点身份的领域结构。
Python 垃圾回收可以处理普通引用环，但文件、锁等外部资源仍应显式管理。不要把资源关闭依赖在链表节点何时回收。
Java 17+
LinkedList<E> 是双链表，同时实现 List 与 Deque。一般索引访问可能遍历，但 addFirst、addLast、removeFirst、removeLast 直接操作两端。
LinkedList.add(0, value) 在首端操作，不需要遍历整个链表；中间索引仍需定位。用作普通队列或栈时，ArrayDeque 通常是更直接的候选；它不接受 null，也不是线程安全容器。
C++
std::forward_list 是单链表，std::list 是双链表。标准 list 在持有有效迭代器时支持单个元素的常数时间插入和删除；批量操作还需按处理的元素数计费。插入保留已有元素的引用和迭代器；删除只使被删元素的引用和迭代器失效。
节点和元素析构遵循 C++ 所有权规则。教学用裸指针实现需要写析构、复制/移动策略和异常安全；业务代码通常先考虑标准容器或智能指针。
链表与缓存
链表遍历包含依赖加载：读到当前节点后，才能知道下一节点地址。单独分配的节点还带来分配元数据、指针和对齐开销。数组顺序扫描更容易利用相邻槽位。
这些因素不会改变两者遍历都为 Θ(n) 的事实，却会改变常数。差距没有通用倍数；节点池、元素大小、访问模式、运行时与处理器都会影响结果。需要选型时，用真实操作组合做基准，而不是引用固定“快 10 倍”结论。
常见错误怎么定位
| 症状 | 先检查什么 |
|---|---|
访问第 0 个空表却返回 None | 接口应返回空值还是抛 IndexError？写进合同 |
| 插入后新节点不可达 | 两条链接的赋值顺序是否覆盖了原后继 |
| 删除尾部后追加丢失 | 删除时是否更新了 tail |
| 反转后只有一个节点 | 改链接前是否保存 next_node |
| 遍历永不结束 | 输入是否有环，循环终止条件是否仍等 None |
| 双链表反向断裂 | 是否同时更新两侧的 previous 与 next |
| 已删除节点仍连着链 | 是否按接口需要清空其链接，外部是否仍持有句柄 |
动手维护链接不变量
- 给示例类增加
prepend(value)，验证空表和非空表都维持尾指针不变量。 - 合并两个互不共享节点的无环有序单链表，不创建新业务节点；写明输入链会被重连。
- 把
middle_node改为偶数长度返回第一个中点，并为长度 0、1、2、4 写断言。 - 实现
cycle_entry(head)，返回环入口而不只返回布尔值。 - 设计一个双哨兵双链表，验证空表时
head_sentinel.next is tail_sentinel。
先说清调用者手里有什么
分别实现“已知前驱后插入”和“按下标插入”。前者只改常数条链接，后者还要从 head 走到目标位置。给空表、单节点、删除尾节点和越界位置写断言，并始终核对 head、tail 与 size 不变量。
再对反转、中点和 Floyd 判环分别写出时间与辅助空间。若输入可能有环，任何以 None 为唯一终止条件的遍历都需要重新审查。
下一页把数组与链表放进同一张表。比较时不只看“插入”两个字，还要写明定位方式、移动量、缓存和迭代器合同。