链表：指针的艺术
第四章：链表 — 指针的艺术
你有一排学生站队。数组的方式是：所有人站在一块连续的空地上，按编号排好。如果要在中间插一个人，后面所有人都得往后挪一步。链表的方式是：每个人手里拿着一张纸条，上面写着下一个人站在哪儿。要插人？只需要改两张纸条就行了。
这个比喻揭示了链表最本质的特征：逻辑顺序和物理存储位置完全解耦。节点可以散落在内存的任何角落，仅靠指针（引用）维系彼此的关系。这赋予了链表极大的灵活性，但也付出了代价——你再也不能"算出"第 k 个元素在哪儿，只能从头一个一个跟着指针走。
Level 1 · 你需要知道的
4.1 单链表：最简单的链式结构
4.1.1 节点定义
链表的基本构建块是节点（Node）。每个节点包含两部分：存储的数据和指向下一个节点的引用。
class ListNode:
"""单链表节点"""
def __init__(self, val=0, next=None):
self.val = val
self.next = next # 指向下一个节点，None 表示链表末尾
这个定义看似简单，却蕴含了一个重要的计算机科学概念：自引用数据结构（self-referential data structure）。节点的类型定义中引用了自身类型，这使得我们可以用有限的代码描述无限长的结构。
WHY — 为什么用类而不是元组/字典？ 在 Python 中，你当然可以用 (val, next_ref) 元组或字典来模拟链表。但类的好处是：(1) 属性访问 node.next 比字典查找 node['next'] 快（CPython 中属性访问走 __dict__ 哈希表或 __slots__，而且 IDE 能自动补全）；(2) 可以添加 __repr__ 方便调试；(3) LeetCode/面试中约定俗成使用类。
4.1.2 构建链表
def build_linked_list(values):
"""从列表构建链表，返回头节点"""
if not values:
return None
head = ListNode(values[0])
current = head
for val in values[1:]:
current.next = ListNode(val)
current = current.next
return head
# 示例：1 -> 2 -> 3 -> None
head = build_linked_list([1, 2, 3])
4.1.3 遍历
def traverse(head):
"""遍历链表并打印每个节点"""
current = head
while current:
print(current.val, end=" -> ")
current = current.next
print("None")
遍历的时间复杂度是 O(n)，空间复杂度是 O(1)。这是链表操作中最基本的模式——用一个指针从头走到尾。
4.1.4 插入操作
链表插入有三种情况：头部插入、尾部插入、中间插入。
def insert_at_head(head, val):
"""在链表头部插入新节点 — O(1)"""
new_node = ListNode(val)
new_node.next = head
return new_node # 新节点成为新的头
def insert_at_tail(head, val):
"""在链表尾部插入新节点 — O(n)"""
new_node = ListNode(val)
if not head:
return new_node
current = head
while current.next:
current = current.next
current.next = new_node
return head
def insert_after(node, val):
"""在指定节点后面插入 — O(1)（假设已有指向该节点的引用）"""
if not node:
return
new_node = ListNode(val)
new_node.next = node.next
node.next = new_node
关键洞察：头部插入是 O(1)，但尾部插入是 O(n)——因为你必须先遍历到末尾。这就是为什么很多实现会维护一个 tail 指针。
4.1.5 删除操作
def delete_node(head, target):
"""删除第一个值为 target 的节点"""
# 特殊情况：删除头节点
if head and head.val == target:
return head.next
current = head
while current and current.next:
if current.next.val == target:
current.next = current.next.next # 跳过目标节点
return head
current = current.next
return head # 未找到目标
删除操作的核心是：找到目标节点的前一个节点，然后让前一个节点的 next 跳过目标节点。这意味着你需要保持对前驱节点的引用。
4.1.6 搜索
def search(head, target):
"""在链表中搜索值，返回节点或 None — O(n)"""
current = head
while current:
if current.val == target:
return current
current = current.next
return None
时间复杂度总结：
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 头部插入 | O(1) | 只需修改一个指针 |
| 尾部插入 | O(n) 或 O(1) | 取决于是否维护 tail 指针 |
| 在给定节点后插入 | O(1) | 已有指向该位置的引用 |
| 删除头节点 | O(1) | 只需返回 head.next |
| 删除指定值 | O(n) | 需要先搜索 |
| 搜索 | O(n) | 必须线性遍历 |
| 随机访问第 k 个 | O(n) | 无法像数组一样索引 |
4.2 双向链表：前后自如
单链表的局限在于只能单向遍历。如果你站在某个节点上，想回到前一个节点，你做不到——除非从头再来一遍。双向链表（Doubly Linked List）通过在每个节点中增加一个 prev 指针解决了这个问题。
class DoublyListNode:
"""双向链表节点"""
def __init__(self, val=0, prev=None, next=None):
self.val = val
self.prev = prev
self.next = next
4.2.1 双向链表的插入与删除
def dll_insert_after(node, val):
"""在双向链表的 node 后面插入新节点 — O(1)"""
new_node = DoublyListNode(val)
new_node.next = node.next
new_node.prev = node
if node.next:
node.next.prev = new_node
node.next = new_node
return new_node
def dll_delete(node):
"""删除双向链表中的指定节点 — O(1)
前提：node 不是头节点且不是尾节点（或者使用哨兵节点）
"""
if node.prev:
node.prev.next = node.next
if node.next:
node.next.prev = node.prev
双向链表最大的优势：给定任意节点的引用，可以 O(1) 删除它。单链表做不到这一点——你必须找到前驱节点，而这需要从头遍历。
4.2.2 Python collections.deque 的底层
WHO — 出处：CPython 源码 Modules/_collectionsmodule.c。
Python 标准库的 collections.deque 底层并不是一个简单的双向链表，而是一个双向链表 + 定长数组块的混合结构。每个块（block）是一个固定大小 64 个元素的数组，多个块通过双向链表连接起来。
Block 0 Block 1 Block 2
[a,b,c,...,64] <-> [e,f,g,...,64] <-> [h,i,j,...,64]
WHY — 为什么不用纯双向链表？ 纯链表的问题是：每个元素都需要一个节点对象（Python 对象开销约 56 字节），内存利用率极低。分块策略让每 64 个元素共享一对 prev/next 指针，大幅降低了内存开销，同时保持了两端 O(1) 的插入/删除能力。
这种设计也叫展开链表（Unrolled Linked List），由 Shao, Bodík, Goldstein 在 1994 年正式提出（论文标题为 "Space Efficient Conservative Garbage Collection"，虽然展开链表的思想更早）。
4.3 循环链表
循环链表的末尾节点不指向 None，而是指回链表的某个节点（通常是头节点）。
def build_circular(values):
"""构建循环链表"""
if not values:
return None
head = ListNode(values[0])
current = head
for val in values[1:]:
current.next = ListNode(val)
current = current.next
current.next = head # 尾部指回头部
return head
4.3.1 约瑟夫环问题（Josephus Problem）
WHO — 出处：Flavius Josephus，公元 1 世纪犹太历史学家，在其著作《犹太战争》中描述了这个问题的原型。现代数学形式化由 W. Ahrens (1918) 完成。
问题描述：n 个人围成一圈，从第 1 个人开始报数，报到 k 的人出列，然后从下一个人重新开始报数，直到所有人出列。求出列顺序。
def josephus(n, k):
"""约瑟夫环 — 循环链表模拟解法"""
# 构建循环链表
head = ListNode(1)
current = head
for i in range(2, n + 1):
current.next = ListNode(i)
current = current.next
current.next = head # 形成环
result = []
prev = current # prev 指向当前节点的前一个
curr = head
while curr.next != curr: # 直到只剩一个人
# 报数 k-1 次（移动 k-1 步）
for _ in range(k - 1):
prev = curr
curr = curr.next
# 出列
result.append(curr.val)
prev.next = curr.next # 删除当前节点
curr = curr.next
result.append(curr.val) # 最后一个人
return result
# josephus(7, 3) => [3, 6, 2, 7, 5, 1, 4]
数学解法：约瑟夫环有一个优雅的递推公式 J(n, k) = (J(n-1, k) + k) % n，可以在 O(n) 时间内求出最后一个幸存者的编号，不需要模拟整个过程。
def josephus_survivor(n, k):
"""求最后幸存者编号（0-indexed）— O(n) 数学解"""
pos = 0
for i in range(2, n + 1):
pos = (pos + k) % i
return pos # 转为 1-indexed: pos + 1
4.4 链表 vs 数组：全面对比
| 维度 | 数组（Python list） | 链表 |
|---|---|---|
| 随机访问 | O(1) | O(n) |
| 头部插入 | O(n) | O(1) |
| 尾部插入 | 均摊 O(1) | O(n) 或 O(1)* |
| 中间插入 | O(n) | O(1)** |
| 删除 | O(n) | O(1)** |
| 内存布局 | 连续 | 分散 |
| Cache 友好度 | 极高 | 极低 |
| 额外空间 | 无（或少量预分配） | 每节点一个/两个指针 |
| 大小是否固定 | 动态扩容（有拷贝开销） | 天然动态 |
*维护 tail 指针时。**已有指向该位置的引用时。
WHY — Cache 为什么重要？ 现代 CPU 的 L1 缓存访问约 1ns，主内存访问约 100ns——差了 100 倍。数组的连续内存布局意味着 CPU 预取（prefetch）能提前把后面的数据加载到缓存；链表的节点散布在堆的各个角落，几乎每次 node.next 都会导致缓存未命中（cache miss）。
WHO — 出处：Bjarne Stroustrup（C++ 之父）在多次演讲中强调这一点，最著名的是 2012 年 GoingNative 大会的 keynote "Why you should avoid linked lists"，他用实验数据展示了即使对于频繁插入/删除的场景，由于缓存效应，std::vector 也经常比 std::list 快。
4.5 常见操作
4.5.1 反转链表
这是链表最经典的操作，也是面试最高频的题目之一（LeetCode #206）。
def reverse_list(head):
"""迭代法反转链表 — O(n) 时间, O(1) 空间"""
prev = None
curr = head
while curr:
next_temp = curr.next # 先保存下一个节点
curr.next = prev # 反转指针方向
prev = curr # prev 前进
curr = next_temp # curr 前进
return prev # prev 现在是新的头节点
图解过程：
初始： None <- 1 2 -> 3 -> None
prev curr
一步后：None <- 1 <- 2 3 -> None
prev curr
两步后：None <- 1 <- 2 <- 3
prev curr=None
递归版本：
def reverse_list_recursive(head):
"""递归法反转链表 — O(n) 时间, O(n) 空间（栈）"""
if not head or not head.next:
return head
new_head = reverse_list_recursive(head.next)
head.next.next = head # 让后继节点指向自己
head.next = None # 断开原来的指向
return new_head
4.5.2 合并两个有序链表（LeetCode #21）
def merge_two_sorted(l1, l2):
"""合并两个有序链表 — O(n+m) 时间, O(1) 空间"""
dummy = ListNode(0) # 哨兵节点
tail = dummy
while l1 and l2:
if l1.val <= l2.val:
tail.next = l1
l1 = l1.next
else:
tail.next = l2
l2 = l2.next
tail = tail.next
tail.next = l1 if l1 else l2 # 拼接剩余部分
return dummy.next
4.5.3 找链表中点（快慢指针）
def find_middle(head):
"""快慢指针找中点 — O(n) 时间, O(1) 空间
偶数长度时返回靠左的中间节点
"""
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
return slow
WHY — 为什么是快慢指针？ 如果你先遍历一遍计算长度 n，再走 n/2 步找中点，需要 1.5n 步。快慢指针只需要 n 步——快指针走完时，慢指针正好在中间。虽然都是 O(n)，但常数因子更小。更重要的是，快慢指针法不需要知道链表长度，适用于无法预知长度的流式数据。
4.5.4 删除倒数第 N 个节点（LeetCode #19）
def remove_nth_from_end(head, n):
"""删除倒数第 n 个节点 — 一次遍历法"""
dummy = ListNode(0)
dummy.next = head
fast = slow = dummy
# fast 先走 n+1 步
for _ in range(n + 1):
fast = fast.next
# fast 和 slow 同时走，直到 fast 到达末尾
while fast:
fast = fast.next
slow = slow.next
# 此时 slow 是要删除节点的前驱
slow.next = slow.next.next
return dummy.next
技巧：让快指针先走 n+1 步而不是 n 步，这样当快指针到达末尾 None 时，慢指针恰好在目标节点的前一个位置，方便执行删除。
4.6 常见错误
错误 1：忘记处理空链表
# 错误！如果 head 是 None，head.val 会崩溃
def bad_search(head, target):
if head.val == target: # ❌ NoneType has no attribute 'val'
return head
...
# 正确：先检查 head 是否为 None
def good_search(head, target):
if not head:
return None
if head.val == target:
return head
...
错误 2：丢失指针引用
# 错误！这样会断链
def bad_insert_after(node, val):
new_node = ListNode(val)
node.next = new_node # ❌ 原来 node.next 的后续节点丢了！
new_node.next = node.next # 这里 node.next 已经是 new_node 了
# 正确：先保存，或者先设置新节点的 next
def good_insert_after(node, val):
new_node = ListNode(val)
new_node.next = node.next # ✓ 先接上后面的
node.next = new_node # ✓ 再修改前面的
错误 3：遍历时修改链表结构
# 危险！在遍历中删除节点可能导致跳过元素或无限循环
current = head
while current:
if should_delete(current):
# 这里如何正确删除？你已经丢失了 prev 的引用！
pass
current = current.next
正确做法是维护 prev 指针，或使用哨兵节点。
Level 2 · 加深理解
4.7 快慢指针检测环（Floyd 判圈算法）
WHO — 出处：Robert W. Floyd，1967 年非正式提出（他本人未发表正式论文，但 Donald Knuth 在 The Art of Computer Programming 中将该算法归功于 Floyd）。也叫"龟兔赛跑算法"。
问题：给定一个链表，判断其中是否存在环。
核心思想：设置快慢两个指针，慢指针每次走一步，快指针每次走两步。如果存在环，快指针最终会追上慢指针（就像操场跑圈，快的人总会套慢的人一圈）；如果不存在环，快指针会先到达 None。
def has_cycle(head):
"""Floyd 判圈 — O(n) 时间, O(1) 空间（LeetCode #141）"""
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
WHY — 为什么一定会相遇？ 设环长为 C。当慢指针进入环时，快指针已经在环内某处。此时快指针每步比慢指针多走一步，两者的距离每步缩小 1。最多经过 C 步，距离从某个值缩小为 0，即相遇。
更正式的证明：设慢指针走了 k 步到达环入口，此时快指针已走 2k 步。快指针在环内的位置是 (2k - 进入环前的步数) % C。两者进入环后，每步距离差减 1，所以最多 C 步后相遇。总时间复杂度 O(n)。
关于环检测的更深入讨论和变体问题，参见第 23 章《双指针与滑动窗口》。
4.8 找环入口的数学推导
问题：给定一个有环的链表，找到环的入口节点（LeetCode #142）。
def detect_cycle_entry(head):
"""找到环的入口节点"""
slow = fast = head
# 第一阶段：检测环
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
else:
return None # 无环
# 第二阶段：找入口
# 将一个指针重置到 head，两个指针同步前进
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
数学推导：
设链表头到环入口的距离为 a，环入口到相遇点的距离为 b，相遇点继续走回到环入口的距离为 c。环长 C = b + c。
- 相遇时，慢指针走了
a + b步 - 快指针走了
a + b + nC步（n 为快指针多绕的圈数，n ≥ 1） - 快指针速度是慢指针的 2 倍：
2(a + b) = a + b + nC - 化简：
a + b = nC，即a = nC - b = (n-1)C + c
这意味着：从头节点走 a 步到环入口，等价于从相遇点走 (n-1) 圈再走 c 步也到环入口。所以第二阶段两个指针同步前进，相遇处就是环入口。
4.9 跳表（Skip List）简介
WHO — 出处：William Pugh，1990 年论文 "Skip Lists: A Probabilistic Alternative to Balanced Trees"，发表于 Communications of the ACM。
跳表是在有序链表的基础上，通过添加多级"快速通道"来实现 O(log n) 搜索的数据结构。
Level 3: head ---------> 6 --------------------------> None
Level 2: head ---------> 6 ---------> 25 -----------> None
Level 1: head ---> 3 --> 6 ---> 9 --> 25 ---> 30 ---> None
Level 0: head -> 1 -> 3 -> 6 -> 7 -> 9 -> 12 -> 25 -> 30 -> 42 -> None
核心思想：每个节点随机决定自己出现在几层中。插入时以概率 p（通常 p=0.5 或 p=0.25）决定是否"提升"到上一层。查找时从最高层开始，利用高层的"快速通道"跳过大量节点。
import random
class SkipNode:
def __init__(self, val, level):
self.val = val
self.forward = [None] * (level + 1) # 每层一个 next 指针
class SkipList:
MAX_LEVEL = 16
P = 0.5 # 提升概率
def __init__(self):
self.header = SkipNode(-float('inf'), self.MAX_LEVEL)
self.level = 0 # 当前最高层
def random_level(self):
"""随机决定新节点的层数"""
lvl = 0
while random.random() < self.P and lvl < self.MAX_LEVEL:
lvl += 1
return lvl
def search(self, target):
"""O(log n) 平均时间搜索"""
current = self.header
for i in range(self.level, -1, -1):
while current.forward[i] and current.forward[i].val < target:
current = current.forward[i]
current = current.forward[0]
return current and current.val == target
def insert(self, val):
"""O(log n) 平均时间插入"""
update = [None] * (self.MAX_LEVEL + 1)
current = self.header
for i in range(self.level, -1, -1):
while current.forward[i] and current.forward[i].val < val:
current = current.forward[i]
update[i] = current
new_level = self.random_level()
if new_level > self.level:
for i in range(self.level + 1, new_level + 1):
update[i] = self.header
self.level = new_level
new_node = SkipNode(val, new_level)
for i in range(new_level + 1):
new_node.forward[i] = update[i].forward[i]
update[i].forward[i] = new_node
WHY — Redis 为什么选跳表不选红黑树？
WHO — 出处：Salvatore Sanfilippo (antirez)，Redis 作者，在 Redis GitHub issue 和 2014 年的多次回复中解释了这个决定。
antirez 的原话大意是：
- 实现简单：跳表的代码量大约是红黑树的一半，更容易理解、调试和维护。
- 范围查询天然高效：跳表的底层是有序链表，范围查询只需找到起点然后顺序遍历。红黑树的范围查询需要中序遍历，实现更复杂。
- 并发友好：跳表可以更容易地实现无锁并发版本（虽然 Redis 是单线程的，但这是一般性优势）。
- 内存局部性可调：通过调整 p 值，可以在时间和空间之间权衡。Redis 使用 p=0.25，使得平均每个节点只有 1.33 个指针。
跳表的期望复杂度：
| 操作 | 平均 | 最坏 |
|---|---|---|
| 搜索 | O(log n) | O(n) |
| 插入 | O(log n) | O(n) |
| 删除 | O(log n) | O(n) |
| 空间 | O(n) | O(n log n) |
最坏情况（所有节点都在最高层）概率指数级小，在实践中可以忽略。
4.10 链表在 LRU Cache 中的应用
WHO — 出处：LRU (Least Recently Used) 缓存淘汰策略的思想可追溯到 1960 年代操作系统页面置换算法的研究。作为面试题，它是 LeetCode #146。
LRU Cache 的核心需求：
get(key)：O(1) 获取值，并将该项标记为最近使用put(key, value)：O(1) 插入，容量满时淘汰最久未使用的项
解决方案：哈希表 + 双向链表
class LRUNode:
def __init__(self, key=0, val=0):
self.key = key
self.val = val
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = {} # key -> LRUNode
# 哨兵节点：避免边界条件
self.head = LRUNode() # dummy head
self.tail = LRUNode() # dummy tail
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node):
"""从双向链表中移除一个节点 — O(1)"""
node.prev.next = node.next
node.next.prev = node.prev
def _add_to_front(self, node):
"""将节点插入到 head 后面（表示最近使用）— O(1)"""
node.next = self.head.next
node.prev = self.head
self.head.next.prev = node
self.head.next = node
def get(self, key):
if key in self.cache:
node = self.cache[key]
self._remove(node)
self._add_to_front(node)
return node.val
return -1
def put(self, key, value):
if key in self.cache:
node = self.cache[key]
node.val = value
self._remove(node)
self._add_to_front(node)
else:
if len(self.cache) >= self.capacity:
# 淘汰最久未使用的（tail 前面的节点）
lru = self.tail.prev
self._remove(lru)
del self.cache[lru.key]
node = LRUNode(key, value)
self.cache[key] = node
self._add_to_front(node)
WHY — 为什么需要双向链表？ 哈希表提供 O(1) 查找，但无法维护使用顺序。链表维护顺序，但搜索是 O(n)。两者结合：哈希表存 key→node 映射实现 O(1) 定位，双向链表维护使用顺序且支持 O(1) 移动/删除任意节点。
WHY — 为什么用双向而不是单向？ 因为 _remove(node) 需要同时修改 node 的前驱和后继。如果是单链表，你需要从头遍历找前驱，删除就变成 O(n) 了。
关于哈希表的详细讨论见第 8 章，LRU Cache 的更多变体和工业级实现见第 38 章。
4.11 递归 vs 迭代处理链表的权衡
链表的递归结构——一个节点加上"剩余的链表"——使得它天然适合递归处理。但递归并不总是最佳选择。
# 递归遍历
def recursive_traverse(head):
if not head:
return
print(head.val)
recursive_traverse(head.next)
# 递归求长度
def recursive_length(head):
if not head:
return 0
return 1 + recursive_length(head.next)
对比分析：
| 维度 | 递归 | 迭代 |
|---|---|---|
| 代码简洁度 | 通常更简洁 | 可能更长 |
| 空间复杂度 | O(n) 栈空间 | O(1) |
| 栈溢出风险 | 链表长度 > 递归深度限制时会崩 | 无此风险 |
| 尾递归优化 | Python 不支持 | 不适用 |
| 调试难度 | 较难（调用栈深） | 较易 |
WHY — Python 不支持尾递归优化：Guido van Rossum 在 2009 年的博文 "Neopythonic: Tail Recursion Elimination" 中明确表示 Python 不会实现尾递归优化，因为这会破坏 traceback 的可读性——Python 哲学认为清晰的错误报告比性能优化更重要。
实际建议：在 Python 中处理链表，几乎总是优先选择迭代。递归方案更适合教学和证明正确性。在 CPython 中，默认递归深度限制是 1000（可通过 sys.setrecursionlimit() 修改），这意味着超过 1000 个节点的链表会导致递归版本崩溃。
Level 3 · 深入底层
4.12 链表的历史
WHO — 出处：Allen Newell, Cliff Shaw, Herbert A. Simon，1955-1956 年在 RAND Corporation 和卡内基梅隆大学开发 IPL (Information Processing Language)。
链表的发明并不是为了解决某个具体的编程问题，而是为了实现人工智能。1955 年，Newell、Shaw 和 Simon 正在开发 Logic Theorist——历史上第一个 AI 程序，用于自动证明数学定理。他们需要一种灵活的数据结构来表示和操作符号表达式（逻辑公式），而当时的计算机只有固定大小的数组。
他们的解决方案是 IPL 语言，其中核心数据结构就是链表。IPL 中的每个"单元"（cell）包含一个符号值和一个指向下一个单元的地址。这个设计直接影响了 John McCarthy 在 1958 年创造的 LISP 语言——LISP 的名字就是 "LISt Processing" 的缩写，链表是整个语言的基础数据结构。
历史影响线：
IPL (1955-56, Newell/Shaw/Simon)
↓
LISP (1958, McCarthy) — cons cell 就是链表节点
↓
所有现代函数式语言的列表类型
(Haskell, ML, Erlang, Clojure...)
趣事：Newell 和 Simon 因为在 AI 领域的开创性工作获得了 1975 年的图灵奖。链表只是他们工作的副产品，但它对计算机科学的影响比 Logic Theorist 本身还要深远。
4.13 XOR 链表：用异或节省指针空间
WHO — 出处：这个技巧在 1990 年代的系统编程社区中广为人知，最早的正式描述难以追溯，但在 Knuth 的 The Art of Computer Programming Vol.1 (1968) 的习题中有提及类似思想。
普通双向链表每个节点需要两个指针（prev 和 next），XOR 链表只存一个值：prev_addr XOR next_addr。
原理：
设节点 A, B, C 的内存地址分别为 addr(A), addr(B), addr(C)
普通双向链表：
A.prev = None, A.next = addr(B)
B.prev = addr(A), B.next = addr(C)
C.prev = addr(B), C.next = None
XOR 链表：
A.link = 0 XOR addr(B) = addr(B)
B.link = addr(A) XOR addr(C)
C.link = addr(B) XOR 0 = addr(B)
遍历方法：如果你在节点 B 上，且知道来的方向是从 A 来的（即知道 addr(A)），那么：
next_addr = B.link XOR addr(A)
= (addr(A) XOR addr(C)) XOR addr(A)
= addr(C) （因为 X XOR X = 0）
Python 伪代码（Python 无法直接操作内存地址，这里用 id() 和字典模拟）：
import ctypes
class XORNode:
def __init__(self, val):
self.val = val
self.npx = 0 # XOR of prev and next addresses
def xor(a, b):
"""XOR two node addresses (using id)"""
return a ^ b
def insert_at_head(head, val):
new_node = XORNode(val)
new_node.npx = id(head) if head else 0
if head:
# head.npx = 0 XOR old_next_addr
# 新的 head.npx = id(new_node) XOR old_next_addr
head.npx = xor(id(new_node), head.npx)
return new_node
def traverse_xor(head):
"""遍历 XOR 链表"""
prev_addr = 0
current = head
while current:
print(current.val, end=" -> ")
next_addr = xor(prev_addr, current.npx)
prev_addr = id(current)
# 需要从地址恢复对象（在 C 中直接解引用指针）
current = ctypes.cast(next_addr, ctypes.py_object).value if next_addr else None
print("None")
WHY — 为什么实际中很少用？
- 可读性极差：代码难以理解和维护。
- 调试困难：不能直接在调试器中看到前驱/后继。
- 与垃圾收集器冲突：GC 需要遍历所有引用来判断可达性。XOR 编码后的"指针"对 GC 不可见，节点可能被错误回收。这使得 XOR 链表在 Java/Python/Go 等有 GC 的语言中完全不可用。
- 现代内存充裕：当年每个指针 4 字节时，节省一个指针确实有意义。现在即使 8 字节指针，内存也通常不是瓶颈。
适用场景：极端嵌入式系统（内存以 KB 计），且使用 C/C++ 手动管理内存。
4.14 内存分配器中的自由链表（Free List）
WHO — 出处：自由链表是最古老的动态内存管理技术之一，追溯到 1960 年代的 ALGOL 编译器。Doug Lea 的 dlmalloc（1987 年）和后续的 ptmalloc2（glibc 默认分配器）都大量使用了自由链表的变体。
当你调用 malloc() 分配内存时，分配器如何知道哪些内存块是空闲的？答案就是自由链表。
核心思想：将所有空闲内存块用链表串起来。分配时从链表头部取一个块；释放时将块插回链表头部。
Free List (空闲块链表):
[16B block] -> [32B block] -> [16B block] -> [64B block] -> None
malloc(16):
取出第一个 16B block，返回给用户
Free List: [32B block] -> [16B block] -> [64B block] -> None
free(ptr):
将 ptr 指向的块插回链表头部
Free List: [16B block] -> [32B block] -> [16B block] -> [64B block] -> None
精妙之处：空闲块的链表指针存在空闲块自身的内存中！因为空闲块没人在用，它的前几个字节可以用来存 next 指针。这意味着维护自由链表不需要额外的内存开销。
// 简化的 free list 实现（C 伪代码）
typedef struct free_block {
struct free_block *next; // 存在空闲块自身的内存中
} free_block_t;
free_block_t *free_list = NULL;
void *my_malloc(size_t size) {
// 在 free_list 中找到合适大小的块
free_block_t *block = free_list;
free_list = block->next;
return (void *)block;
}
void my_free(void *ptr) {
// 将释放的块插入 free_list 头部
free_block_t *block = (free_block_t *)ptr;
block->next = free_list;
free_list = block;
}
现代分配器的优化：
- 分离式自由链表（Segregated Free Lists）：按大小分类，16 字节的块有一个链表，32 字节的有另一个，以此类推。分配时直接从对应大小的链表中取，避免碎片化。
- glibc 的 fastbin：对小块（≤ 160 字节）使用 LIFO 的单链表，分配和释放都是 O(1)。
- jemalloc / tcmalloc：使用线程本地的自由链表，避免锁竞争。
4.15 Linux 内核的 list_head 侵入式链表
WHO — 出处：Linux 内核，include/linux/list.h。这个设计从 Linux 2.1 开始引入（约 1996 年），由多位内核开发者贡献。
传统链表（如我们上面实现的）是"非侵入式"的：链表节点包含数据。Linux 内核使用的是"侵入式"（intrusive）链表：数据结构中嵌入链表节点。
// Linux 内核的 list_head 定义
struct list_head {
struct list_head *next, *prev;
};
// 使用方式：将 list_head 嵌入到你的数据结构中
struct task_struct {
pid_t pid;
char comm[16];
struct list_head tasks; // 进程链表
struct list_head children; // 子进程链表
// ... 其他字段
};
关键技巧：container_of 宏。给定 list_head 的地址，如何找到包含它的外部结构体？
// container_of 宏：从成员指针反推出结构体指针
#define container_of(ptr, type, member) \
((type *)((char *)(ptr) - offsetof(type, member)))
// 遍历进程链表
struct task_struct *task;
struct list_head *pos;
list_for_each(pos, &init_task.tasks) {
task = container_of(pos, struct task_struct, tasks);
printk("PID: %d, Name: %s\n", task->pid, task->comm);
}
WHY — 为什么内核用侵入式链表？
- 零额外内存分配：不需要为每个链表节点单独
kmalloc。链表头嵌在已有结构体中，随结构体一起分配。 - 一个对象可以同时在多个链表中：比如
task_struct同时在进程链表、运行队列、等待队列中，只需嵌入多个list_head。 - 类型无关：
list_head的操作（插入、删除、遍历）不关心外部结构体是什么类型，代码高度复用。 - 缓存友好：链表节点和数据在同一块内存中，减少指针追踪和缓存未命中。
Python 中的类似思想：
class IntrusiveNode:
"""侵入式链表节点 mixin"""
def __init__(self):
self.list_prev = None
self.list_next = None
class Process(IntrusiveNode):
"""进程对象，自身就是链表节点"""
def __init__(self, pid, name):
super().__init__()
self.pid = pid
self.name = name
class IntrusiveList:
"""侵入式双向链表"""
def __init__(self):
self.head = IntrusiveNode()
self.head.list_prev = self.head
self.head.list_next = self.head # 空链表指向自己
def insert(self, node):
"""在头部插入"""
node.list_next = self.head.list_next
node.list_prev = self.head
self.head.list_next.list_prev = node
self.head.list_next = node
def remove(self, node):
"""移除指定节点"""
node.list_prev.list_next = node.list_next
node.list_next.list_prev = node.list_prev
Level 4 · 工程实践
4.16 Python 中链表很少用的原因
在实际 Python 项目中，你几乎永远不需要自己实现链表。原因如下：
1. Python list 已经足够好
Python 的 list 底层是动态数组（C 实现，PyObject ** 指针数组）。虽然头部插入是 O(n)，但：
- CPython 的
list.insert(0, x)是用memmove实现的，对于现代 CPU 来说非常快（连续内存，预取友好） - 对于 10 万以内的元素，O(n) 的
list.insert(0, x)可能比链表的 O(1) 还快，因为链表的每次node.next都是一次缓存未命中
2. collections.deque 覆盖了大部分场景
from collections import deque
d = deque()
d.appendleft(1) # O(1) 头部插入
d.append(2) # O(1) 尾部插入
d.popleft() # O(1) 头部删除
d.pop() # O(1) 尾部删除
deque 两端操作都是 O(1)，足以替代链表的大部分用途。
3. Python 对象开销巨大
每个 Python 对象至少占 56 字节（sys.getsizeof(object()) = 56）。一个 ListNode 对象：
import sys
node = ListNode(42)
print(sys.getsizeof(node)) # 48 (基本对象大小)
# 加上 __dict__: 额外 104 字节
# 总计：约 152 字节存储一个 int（本身只需要 28 字节）
相比之下，list 中存储一个 int 引用只需要 8 字节（一个指针）。链表的空间效率极差。
4. 什么时候链表仍然有用？
- LRU Cache 等需要 O(1) 删除任意元素的场景（配合哈希表）
- 需要在迭代过程中频繁插入/删除的场景（但 Python 中通常用其他方式绕过）
- 教学和面试（理解指针操作的思维训练）
- 操作系统/嵌入式等底层系统编程（但那通常不用 Python）
4.17 面试高频链表题
4.17.1 回文链表（LeetCode #234）
思路：找到中点 → 反转后半部分 → 逐一比较 → （可选）恢复链表
def is_palindrome(head):
"""O(n) 时间, O(1) 空间判断回文链表"""
if not head or not head.next:
return True
# 1. 找中点
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
# 2. 反转后半部分
second_half = reverse_list(slow.next)
# 3. 比较
p1, p2 = head, second_half
result = True
while p2:
if p1.val != p2.val:
result = False
break
p1 = p1.next
p2 = p2.next
# 4. 恢复链表（好习惯）
slow.next = reverse_list(second_half)
return result
4.17.2 相交链表（LeetCode #160）
思路：两个指针分别从两个链表头出发。当一个到达末尾时，重定向到另一个链表的头部。如果有交点，两个指针会在交点相遇。
def get_intersection_node(headA, headB):
"""O(n+m) 时间, O(1) 空间"""
if not headA or not headB:
return None
pA, pB = headA, headB
while pA != pB:
pA = pA.next if pA else headB
pB = pB.next if pB else headA
return pA # 要么是交点，要么是 None（两者同时到达末尾）
WHY — 为什么这个方法有效？ 设链表 A 长度为 a，链表 B 长度为 b，公共部分长度为 c。指针 A 走的路径：a + (b - c)；指针 B 走的路径：b + (a - c)。两者相等：a + b - c = b + a - c。所以它们一定同时到达交点（或同时到达 None）。
4.17.3 排序链表（LeetCode #148 — 归并排序）
WHY — 为什么链表排序用归并排序？ 快排需要随机访问（partition 操作），不适合链表。归并排序只需要顺序访问和合并操作，完美适配链表。而且链表的归并不需要额外 O(n) 空间（不像数组归并需要临时数组）。
def sort_list(head):
"""链表归并排序 — O(n log n) 时间, O(log n) 空间（递归栈）"""
if not head or not head.next:
return head
# 找中点并断开
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
mid = slow.next
slow.next = None # 断开前后两半
# 递归排序两半
left = sort_list(head)
right = sort_list(mid)
# 合并
return merge_two_sorted(left, right)
进阶：自底向上的迭代归并排序可以做到 O(1) 空间（不使用递归栈），但代码复杂度显著增加。
4.17.4 K 个一组翻转链表（LeetCode #25）
这是链表题中的"Hard"级别，综合考察指针操作能力。
def reverse_k_group(head, k):
"""每 k 个节点一组进行翻转"""
# 检查是否还有 k 个节点
count = 0
node = head
while node and count < k:
node = node.next
count += 1
if count < k:
return head # 不足 k 个，不翻转
# 翻转前 k 个节点
prev = None
curr = head
for _ in range(k):
next_temp = curr.next
curr.next = prev
prev = curr
curr = next_temp
# head 现在是翻转后的最后一个节点
# curr 是下一组的开始
head.next = reverse_k_group(curr, k) # 递归处理剩余部分
return prev # prev 是翻转后的新头
迭代版本（面试中更受青睐，因为不会栈溢出）：
def reverse_k_group_iterative(head, k):
"""迭代版 K 个一组翻转"""
dummy = ListNode(0)
dummy.next = head
group_prev = dummy
while True:
# 检查剩余节点是否够 k 个
kth = group_prev
for _ in range(k):
kth = kth.next
if not kth:
return dummy.next
group_next = kth.next
# 翻转 group_prev.next 到 kth 之间的节点
prev, curr = kth.next, group_prev.next
for _ in range(k):
next_temp = curr.next
curr.next = prev
prev = curr
curr = next_temp
# 更新连接
tmp = group_prev.next
group_prev.next = kth
group_prev = tmp
# 测试：reverse_k_group_iterative(build_linked_list([1,2,3,4,5]), 2)
# 结果：2 -> 1 -> 4 -> 3 -> 5
4.18 哨兵节点（Dummy Head）技巧
哨兵节点（sentinel/dummy node）是链表编程中最实用的技巧之一。
WHY — 为什么需要哨兵？ 链表操作中最烦人的是边界条件：头节点没有前驱，尾节点没有后继。插入/删除头节点需要特殊处理（因为要更新 head 引用）。哨兵节点通过在真正的头节点前面加一个假节点，统一了所有操作。
def remove_elements(head, val):
"""删除所有值为 val 的节点（LeetCode #203）
不使用哨兵 vs 使用哨兵的对比
"""
# 方法1：不使用哨兵 — 需要特殊处理头节点
while head and head.val == val:
head = head.next
current = head
while current and current.next:
if current.next.val == val:
current.next = current.next.next
else:
current = current.next
return head
# 方法2：使用哨兵 — 统一处理
dummy = ListNode(0)
dummy.next = head
current = dummy
while current.next:
if current.next.val == val:
current.next = current.next.next
else:
current = current.next
return dummy.next
使用哨兵的好处：
- 不需要单独处理"删除头节点"的情况
- 代码逻辑统一，不容易出错
- 最后返回
dummy.next，它自然就是正确的新头（可能是原来的头，也可能头被删了）
经验法则：如果你的链表操作可能修改头节点，就用哨兵。这包括：
- 删除操作（头节点可能被删）
- 合并/排序（新的头不确定是哪个）
- 插入操作（可能在头部插入）
4.19 什么时候该用链表，什么时候不该
应该用链表（或其变体）的场景：
- 需要频繁在已知位置插入/删除：例如文本编辑器的行缓冲区（但现代编辑器多用 rope 或 piece table）。
- 需要 O(1) 拼接两个序列：两个链表的合并只需要改一个指针。数组合并是 O(n)。
- 实现特殊数据结构：LRU Cache、LFU Cache、Fibonacci Heap 的内部都使用链表。
- 内存碎片化严重，无法分配连续大块：嵌入式系统中常见。
- 元素极大，移动代价高：但在 Python/Java 中对象都是引用，移动只是移动指针，这个理由不成立。
不应该用链表的场景：
- 需要随机访问：链表的
get(i)是 O(n)。 - 数据量小（小于几千个元素）：数组的缓存友好性会碾压链表的理论优势。
- 需要二分搜索：链表上无法高效二分（除非用跳表）。
- Python/Java 等有 GC 的高级语言：对象开销使链表空间效率极差。
- 并行/向量化计算：现代 CPU 的 SIMD 指令需要连续内存。
总结性决策树：
需要随机访问？
→ 是：用数组
→ 否：
需要两端操作？
→ 是：用 deque
→ 否：
需要 O(1) 删除任意已知节点？
→ 是：用链表 + 哈希表
→ 否：
数据量大且频繁中间插入？
→ 是：考虑链表或跳表
→ 否：用数组
本章小结
链表是理解指针/引用和动态数据结构的基石。尽管在现代高级语言中很少直接使用链表，但它的思想无处不在：
- 操作系统的进程调度队列（Linux
list_head） - 内存分配器的自由块管理（free list）
- 数据库和缓存系统（LRU、跳表）
- 编译器的符号表实现
- 网络协议栈的数据包队列
掌握链表，关键不在于背诵那些指针操作的代码模板，而在于理解：当逻辑顺序和物理位置解耦后，你获得了什么自由，又付出了什么代价。
下一章我们将学习栈和队列——它们是对链表和数组的"访问方式"进行限制后得到的抽象，这种"限制即力量"的设计哲学是计算机科学中反复出现的主题。