第9章 链表与指针操作理论
本章导读
链表是最基础的动态数据结构，通过指针将离散的内存节点连接成线性序列。本章从指针语义和内存模型角度深入分析链表的理论基础，包括链表ADT规范、指针操作的形式化语义、Floyd判圈算法的正确性证明，以及链表与数组的性能权衡分析。
学习目标
完成本章学习后，读者将能够：
- 掌握链表ADT的形式化规范与公理系统
- 理解指针操作的语义与内存模型
- 掌握Floyd判圈算法的正确性证明
- 理解链表与数组的性能权衡理论
- 掌握链表经典算法的时间复杂度分析
9.1 链表的形式化理论
9.1.1 指针的数学模型
定义 9.1（指针） 指针是一个引用值，指向内存中的某个位置。形式化地，指针类型 $Ptr(T)$ 是地址空间 $Addr$ 到类型 $T$ 的部分函数：
$$Ptr(T) \subseteq Addr \rightharpoonup T$$
定义 9.2（指针操作） 指针支持两种基本操作：
- 解引用：$*p$ 返回指针 $p$ 指向的值
- 取地址：$&x$ 返回变量 $x$ 的地址
定义 9.3（空指针） 空指针 $NULL$ 是不指向任何有效内存位置的指针：
$$*NULL = \bot \quad \text{（未定义）}$$
定理 9.1（指针安全性） 对空指针解引用是未定义行为，可能导致程序崩溃。
9.1.2 链表的数学定义
定义 9.4（链表节点） 链表节点是一个记录，包含数据域和指针域：
$$Node = {value: T, next: Ptr(Node)}$$
定义 9.5（单链表） 单链表是由节点组成的有限序列，每个节点通过 $next$ 指针指向下一个节点，最后一个节点的 $next$ 为 $NULL$。
形式化地，单链表可定义为：
$$List = \langle n_1, n_2, \ldots, n_k \rangle$$
满足：
- $n_i.next = &n_{i+1}$ 对于 $1 \leq i < k$
- $n_k.next = NULL$
定义 9.6（链表长度） 链表 $L$ 的长度 $|L|$ 定义为其中节点的数量。
9.1.3 链表ADT规范
ADT 9.1（LinkedList）
ADT LinkedList[T]
Types: LinkedList[T]
Operations:
empty: → LinkedList[T]
size: LinkedList[T] → ℕ
isEmpty: LinkedList[T] → Boolean
prepend: LinkedList[T] × T → LinkedList[T]
append: LinkedList[T] × T → LinkedList[T]
head: LinkedList[T] → T
tail: LinkedList[T] → LinkedList[T]
get: LinkedList[T] × ℕ → T
insert: LinkedList[T] × ℕ × T → LinkedList[T]
remove: LinkedList[T] × ℕ → LinkedList[T]
Axioms:
∀l: LinkedList[T], ∀x: T, ∀i: ℕ
(A1) size(empty) = 0
(A2) isEmpty(empty) = true
(A3) isEmpty(prepend(l, x)) = false
(A4) head(prepend(l, x)) = x
(A5) tail(prepend(l, x)) = l
(A6) size(prepend(l, x)) = size(l) + 1
(A7) get(prepend(l, x), 0) = x
(A8) get(prepend(l, x), i+1) = get(l, i)
(A9) head(empty) = error
(A10) tail(empty) = error定理 9.2（链表ADT一致性） 链表ADT的公理系统是一致的。
证明：构造节点序列模型。设链表为节点序列 $\langle n_1, \ldots, n_k \rangle$。
- $empty = \langle \rangle$
- $prepend(\langle n_1, \ldots, n_k \rangle, x) = \langle n_0, n_1, \ldots, n_k \rangle$，其中 $n_0.value = x$
- $head(\langle n_1, \ldots, n_k \rangle) = n_1.value$
- $tail(\langle n_1, \ldots, n_k \rangle) = \langle n_2, \ldots, n_k \rangle$
可直接验证所有公理成立。∎
9.2 单链表实现与分析
9.2.1 节点与链表结构
定理 9.3（链表空间复杂度） 存储 $n$ 个元素的单链表需要 $O(n)$ 空间，每个元素额外需要一个指针的空间开销。
证明：设数据大小为 $w$，指针大小为 $p$。每个节点需要 $w + p$ 空间。$n$ 个节点总空间为 $n(w + p) = O(n)$。相比数组的 $nw$，额外开销为 $np$。∎
from typing import TypeVar, Generic, Optional, Iterator, List
T = TypeVar('T')
class Node(Generic[T]):
"""单链表节点"""
__slots__ = ['value', 'next']
def __init__(self, value: T, next_node: Optional['Node[T]'] = None):
self.value = value
self.next = next_node
def __repr__(self) -> str:
return f"Node({self.value})"
class LinkedList(Generic[T]):
"""
单链表实现
时间复杂度：
- prepend/append: O(1)
- insert/delete at position i: O(i)
- get/find: O(n)
空间复杂度：O(n)
"""
def __init__(self):
self._head: Optional[Node[T]] = None
self._tail: Optional[Node[T]] = None
self._size: int = 0
def prepend(self, value: T) -> None:
"""头部插入 - O(1)"""
new_node = Node(value, self._head)
self._head = new_node
if self._tail is None:
self._tail = new_node
self._size += 1
def append(self, value: T) -> None:
"""尾部插入 - O(1)（有尾指针）"""
new_node = Node(value)
if self._tail:
self._tail.next = new_node
else:
self._head = new_node
self._tail = new_node
self._size += 1
def insert(self, index: int, value: T) -> None:
"""指定位置插入 - O(index)"""
if index <= 0:
self.prepend(value)
elif index >= self._size:
self.append(value)
else:
current = self._head
for _ in range(index - 1):
current = current.next
new_node = Node(value, current.next)
current.next = new_node
self._size += 1
def delete_at(self, index: int) -> Optional[T]:
"""删除指定位置 - O(index)"""
if index < 0 or index >= self._size:
return None
if index == 0:
value = self._head.value
self._head = self._head.next
if self._head is None:
self._tail = None
else:
current = self._head
for _ in range(index - 1):
current = current.next
value = current.next.value
current.next = current.next.next
if index == self._size - 1:
self._tail = current
self._size -= 1
return value
def get(self, index: int) -> Optional[T]:
"""获取指定位置元素 - O(index)"""
if index < 0 or index >= self._size:
return None
current = self._head
for _ in range(index):
current = current.next
return current.value
def find(self, value: T) -> int:
"""查找元素位置 - O(n)"""
current = self._head
index = 0
while current:
if current.value == value:
return index
current = current.next
index += 1
return -1
def reverse(self) -> None:
"""反转链表 - O(n)"""
prev = None
current = self._head
self._tail = self._head
while current:
next_node = current.next
current.next = prev
prev = current
current = next_node
self._head = prev
def __len__(self) -> int:
return self._size
def __iter__(self) -> Iterator[T]:
current = self._head
while current:
yield current.value
current = current.next
def __repr__(self) -> str:
return f"LinkedList({list(self)})"9.2.2 操作复杂度分析
定理 9.4（链表操作复杂度）
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| prepend | $O(1)$ | 头部插入 |
| append | $O(1)$ | 尾部插入（有尾指针） |
| insert(i) | $O(i)$ | 需遍历到位置 $i$ |
| delete(i) | $O(i)$ | 需遍历到位置 $i$ |
| get(i) | $O(i)$ | 需遍历到位置 $i$ |
| find(x) | $O(n)$ | 需遍历整个链表 |
定理 9.5（链表vs数组访问复杂度） 链表的随机访问时间为 $O(n)$，而数组为 $O(1)$。
证明：数组元素连续存储，可通过地址计算直接访问：$addr[i] = base + i \cdot size$。
链表节点离散存储，访问第 $i$ 个元素必须从头开始遍历 $i$ 步。∎
9.3 双链表理论
9.3.1 双链表的数学定义
定义 9.7（双链表节点） 双链表节点包含两个指针：
$$DNode = {value: T, prev: Ptr(DNode), next: Ptr(DNode)}$$
定义 9.8（双链表不变式） 对于双链表中任意相邻节点 $n_1, n_2$：
$$n_1.next = &n_2 \Leftrightarrow n_2.prev = &n_1$$
定理 9.6（双链表删除复杂度） 给定节点指针，双链表删除操作为 $O(1)$，而单链表为 $O(n)$。
证明：双链表可直接访问前驱节点，修改两个指针即可删除：
node.prev.next = node.next
node.next.prev = node.prev单链表需要从头遍历找到前驱节点，最坏 $O(n)$。∎
9.3.2 双链表实现
class DoublyNode(Generic[T]):
"""双链表节点"""
__slots__ = ['value', 'prev', 'next']
def __init__(self, value: T,
prev: Optional['DoublyNode[T]'] = None,
next_node: Optional['DoublyNode[T]'] = None):
self.value = value
self.prev = prev
self.next = next_node
def __repr__(self) -> str:
return f"DoublyNode({self.value})"
class DoublyLinkedList(Generic[T]):
"""
双链表实现
特点：
- 双向遍历
- 给定节点指针时 O(1) 删除
- 额外空间开销（每个节点两个指针）
"""
def __init__(self):
self._head: Optional[DoublyNode[T]] = None
self._tail: Optional[DoublyNode[T]] = None
self._size: int = 0
def append(self, value: T) -> None:
"""尾部插入 - O(1)"""
new_node = DoublyNode(value, self._tail)
if self._tail:
self._tail.next = new_node
else:
self._head = new_node
self._tail = new_node
self._size += 1
def prepend(self, value: T) -> None:
"""头部插入 - O(1)"""
new_node = DoublyNode(value, None, self._head)
if self._head:
self._head.prev = new_node
else:
self._tail = new_node
self._head = new_node
self._size += 1
def delete_node(self, node: DoublyNode[T]) -> None:
"""删除给定节点 - O(1)"""
if node.prev:
node.prev.next = node.next
else:
self._head = node.next
if node.next:
node.next.prev = node.prev
else:
self._tail = node.prev
self._size -= 1
def reverse(self) -> None:
"""反转双链表 - O(n)"""
current = self._head
self._head, self._tail = self._tail, self._head
while current:
current.prev, current.next = current.next, current.prev
current = current.prev
def __iter__(self) -> Iterator[T]:
current = self._head
while current:
yield current.value
current = current.next
def __reversed__(self) -> Iterator[T]:
current = self._tail
while current:
yield current.value
current = current.prev
def __len__(self) -> int:
return self._size
def __repr__(self) -> str:
return f"DoublyLinkedList({list(self)})"9.4 Floyd判圈算法理论
9.4.1 问题定义
定义 9.9（链表环） 链表存在环，当且仅当存在节点 $n_i$ 使得从 $n_i$ 出发可以回到 $n_i$。
形式化地，存在 $i, k > 0$ 使得：
$$follow(n_0, i) = follow(n_0, i + k)$$
其中 $follow(n, j)$ 表示从节点 $n$ 开始沿 $next$ 指针走 $j$ 步到达的节点。
9.4.2 Floyd算法
算法 9.1（Floyd判圈） 使用快慢两个指针，快指针每次走两步，慢指针每次走一步。若存在环，两指针必在环内某点相遇。
定理 9.7（Floyd算法正确性） 若链表存在环，快慢指针必在有限步内相遇。
证明：设环的长度为 $c$，慢指针进入环时距环入口的距离为 $d$。
此时快指针已在环内某位置。设快指针位置为 $f$，慢指针位置为 $s$。
每一步后，快慢指针的距离减少 1（因为快指针走 2 步，慢指针走 1 步）。
因此，最多经过 $c$ 步，两指针相遇。∎
定理 9.8（环入口检测） 设快慢指针第一次相遇点距环入口的距离为 $k$，则从链表头和相遇点同时出发，以相同速度前进，必在环入口相遇。
证明：设链表头到环入口距离为 $a$，环长度为 $c$，相遇点距环入口距离为 $b$。
慢指针走的距离：$a + b$
快指针走的距离：$a + b + nc$（$n$ 为环的圈数）
由于快指针速度是慢指针的两倍：
$$a + b + nc = 2(a + b)$$
因此 $a = nc - b = (n-1)c + (c - b)$
这意味着从链表头走 $a$ 步到达环入口，从相遇点走 $a$ 步（即绕环 $n-1$ 圈后再走 $c-b$ 步）也到达环入口。∎
9.4.3 Floyd算法实现
from typing import Optional, Tuple
def has_cycle(head: Optional[Node]) -> bool:
"""
Floyd判圈算法 - 检测链表是否有环
时间复杂度：O(n)
空间复杂度：O(1)
"""
if not head or not head.next:
return False
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
def detect_cycle(head: Optional[Node]) -> Optional[Node]:
"""
检测环并返回入口节点
时间复杂度：O(n)
空间复杂度：O(1)
"""
if not head or not head.next:
return None
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
break
else:
return None
slow = head
while slow is not fast:
slow = slow.next
fast = fast.next
return slow
def cycle_length(head: Optional[Node]) -> int:
"""
计算环的长度
时间复杂度：O(n)
空间复杂度：O(1)
"""
entry = detect_cycle(head)
if not entry:
return 0
length = 1
current = entry.next
while current is not entry:
length += 1
current = current.next
return length9.5 链表经典算法
9.5.1 反转链表
定理 9.9（反转链表复杂度） 反转链表的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$（迭代）或 $O(n)$（递归）。
def reverse_iterative(head: Optional[Node]) -> Optional[Node]:
"""
迭代反转链表
时间复杂度：O(n)
空间复杂度：O(1)
"""
prev = None
current = head
while current:
next_node = current.next
current.next = prev
prev = current
current = next_node
return prev
def reverse_recursive(head: Optional[Node]) -> Optional[Node]:
"""
递归反转链表
时间复杂度：O(n)
空间复杂度：O(n)（递归栈）
"""
if not head or not head.next:
return head
new_head = reverse_recursive(head.next)
head.next.next = head
head.next = None
return new_head
def reverse_k_group(head: Optional[Node], k: int) -> Optional[Node]:
"""
K个一组反转链表
时间复杂度：O(n)
空间复杂度：O(1)
"""
def reverse(head: Optional[Node], tail: Optional[Node]) -> Optional[Node]:
prev = tail
current = head
while current is not tail:
next_node = current.next
current.next = prev
prev = current
current = next_node
return prev
def get_kth(node: Optional[Node], k: int) -> Optional[Node]:
while node and k > 0:
node = node.next
k -= 1
return node
dummy = Node(0, head)
prev_group = dummy
while True:
kth = get_kth(prev_group, k)
if not kth:
break
next_group = kth.next
prev_group.next = reverse(prev_group.next, next_group)
prev_group = head
head = next_group
return dummy.next9.5.2 合并有序链表
定理 9.10（合并有序链表复杂度） 合并两个长度分别为 $m$ 和 $n$ 的有序链表，时间复杂度为 $O(m + n)$。
def merge_two_lists(l1: Optional[Node], l2: Optional[Node]) -> Optional[Node]:
"""
合并两个有序链表
时间复杂度：O(m + n)
空间复杂度：O(1)
"""
dummy = Node(0)
current = dummy
while l1 and l2:
if l1.value <= l2.value:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
current = current.next
current.next = l1 if l1 else l2
return dummy.next
def merge_k_lists(lists: List[Optional[Node]]) -> Optional[Node]:
"""
合并K个有序链表
时间复杂度：O(n log k)，n为总节点数，k为链表数
空间复杂度：O(log k)（递归栈）
"""
import heapq
if not lists:
return None
dummy = Node(0)
current = dummy
heap = []
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.value, i, node))
while heap:
_, i, node = heapq.heappop(heap)
current.next = node
current = current.next
if node.next:
heapq.heappush(heap, (node.next.value, i, node.next))
return dummy.next9.5.3 快慢指针应用
def find_middle(head: Optional[Node]) -> Optional[Node]:
"""
找链表中点
时间复杂度：O(n)
空间复杂度：O(1)
若链表长度为偶数，返回前半部分的最后一个节点
"""
if not head:
return None
slow = head
fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
return slow
def is_palindrome(head: Optional[Node]) -> bool:
"""
判断链表是否为回文
时间复杂度：O(n)
空间复杂度：O(1)
"""
if not head or not head.next:
return True
mid = find_middle(head)
second_half = reverse_iterative(mid.next)
p1, p2 = head, second_half
result = True
while p2:
if p1.value != p2.value:
result = False
break
p1 = p1.next
p2 = p2.next
mid.next = reverse_iterative(second_half)
return result
def remove_nth_from_end(head: Optional[Node], n: int) -> Optional[Node]:
"""
删除倒数第n个节点
时间复杂度：O(n)
空间复杂度：O(1)
"""
dummy = Node(0, head)
fast = dummy
slow = dummy
for _ in range(n + 1):
if not fast:
return head
fast = fast.next
while fast:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy.next9.5.4 链表排序
def sort_list(head: Optional[Node]) -> Optional[Node]:
"""
链表归并排序
时间复杂度：O(n log n)
空间复杂度：O(log n)（递归栈）
"""
if not head or not head.next:
return head
mid = find_middle(head)
right = mid.next
mid.next = None
left = sort_list(head)
right = sort_list(right)
return merge_two_lists(left, right)
def insertion_sort_list(head: Optional[Node]) -> Optional[Node]:
"""
链表插入排序
时间复杂度：O(n²)
空间复杂度：O(1)
"""
if not head or not head.next:
return head
dummy = Node(0)
current = head
while current:
prev = dummy
next_node = current.next
while prev.next and prev.next.value < current.value:
prev = prev.next
current.next = prev.next
prev.next = current
current = next_node
return dummy.next9.6 循环链表与约瑟夫问题
9.6.1 循环链表定义
定义 9.10（循环链表） 循环链表是一种特殊的链表，其尾节点的 $next$ 指向头节点，形成环。
定理 9.11（循环链表性质） 在循环链表中，从任意节点出发都可以访问到所有节点。
9.6.2 约瑟夫问题
问题 9.1（约瑟夫问题） $n$ 个人围成一圈，从第 $k$ 个人开始，每次数 $m$ 个人，被数到的人出圈，求最后剩下的人。
定理 9.12（约瑟夫问题递推公式） 设 $J(n, m)$ 表示 $n$ 个人、步长为 $m$ 时最后剩下的人的编号（从0开始），则：
$$J(n, m) = \begin{cases} 0 & \text{if } n = 1 \ (J(n-1, m) + m) \mod n & \text{if } n > 1 \end{cases}$$
证明：设 $n$ 个人时最后剩下的是第 $x$ 个人。第一轮后，第 $m \mod n$ 个人出圈，剩下 $n-1$ 个人。
对于剩下的 $n-1$ 个人，问题变为 $J(n-1, m)$。设其解为 $y$。
在原 $n$ 个人中，$y$ 对应的编号是 $(y + m) \mod n$。∎
class CircularLinkedList(Generic[T]):
"""循环链表实现"""
def __init__(self):
self._tail: Optional[Node[T]] = None
self._size: int = 0
def append(self, value: T) -> None:
"""添加元素 - O(1)"""
new_node = Node(value)
if self._tail:
new_node.next = self._tail.next
self._tail.next = new_node
else:
new_node.next = new_node
self._tail = new_node
self._size += 1
def rotate(self) -> None:
"""旋转（移动tail指针）- O(1)"""
if self._tail:
self._tail = self._tail.next
def __iter__(self) -> Iterator[T]:
if not self._tail:
return
current = self._tail.next
for _ in range(self._size):
yield current.value
current = current.next
def __len__(self) -> int:
return self._size
def __repr__(self) -> str:
return f"CircularLinkedList({list(self)})"
def josephus(n: int, m: int) -> int:
"""
约瑟夫问题 - 数学解法
时间复杂度：O(n)
空间复杂度：O(1)
返回最后剩下的人的编号（从0开始）
"""
result = 0
for i in range(2, n + 1):
result = (result + m) % i
return result
def josephus_simulation(n: int, m: int) -> List[int]:
"""
约瑟夫问题 - 模拟解法
时间复杂度：O(nm)
空间复杂度：O(n)
返回出圈顺序
"""
clist = CircularLinkedList[int]()
for i in range(n):
clist.append(i)
result = []
current = clist._tail
while clist._size > 1:
for _ in range(m - 1):
current = current.next
removed = current.next
current.next = removed.next
clist._size -= 1
result.append(removed.value)
result.append(current.value)
return result9.7 链表与数组的性能权衡
9.7.1 缓存友好性分析
定义 9.11（缓存命中率） 缓存命中率是CPU从缓存中成功获取数据的比例。
定理 9.13（数组缓存优势） 数组的连续内存布局使其缓存命中率显著高于链表。
证明：现代CPU使用缓存行（通常64字节）预取数据。
- 数组：访问 $A[i]$ 后，$A[i+1], A[i+2], \ldots$ 已被预取到缓存
- 链表：节点分散在内存中，每次访问可能导致缓存未命中
对于遍历操作，数组缓存命中率接近100%，链表可能低于50%。∎
9.7.2 选择指南
| 场景 | 推荐结构 | 原因 |
|---|---|---|
| 频繁随机访问 | 数组 | $O(1)$ 访问 |
| 频繁头部插入删除 | 链表 | $O(1)$ 操作 |
| 内存受限 | 数组 | 无指针开销 |
| 需要缓存友好 | 数组 | 连续内存 |
| 大对象存储 | 链表 | 避免大块连续内存 |
9.8 本章小结
9.8.1 核心定理总结
| 定理 | 内容 | 应用 |
|---|---|---|
| 定理 9.2 | 链表ADT一致性 | 形式化验证 |
| 定理 9.5 | 链表vs数组访问复杂度 | 数据结构选择 |
| 定理 9.6 | 双链表删除优势 | 算法设计 |
| 定理 9.7 | Floyd算法正确性 | 环检测 |
| 定理 9.12 | 约瑟夫问题递推公式 | 问题求解 |
9.8.2 时间复杂度汇总
| 操作 | 单链表 | 双链表 | 数组 |
|---|---|---|---|
| 访问第i个元素 | $O(i)$ | $O(i)$ | $O(1)$ |
| 头部插入 | $O(1)$ | $O(1)$ | $O(n)$ |
| 尾部插入 | $O(1)$* | $O(1)$ | $O(1)$ |
| 中间插入 | $O(i)$ | $O(i)$ | $O(n)$ |
| 删除（给定位置） | $O(i)$ | $O(1)$** | $O(n)$ |
| 查找 | $O(n)$ | $O(n)$ | $O(n)$ |
*有尾指针时 **给定节点指针时
9.8.3 经典技巧
# 快慢指针
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 虚拟头节点
dummy = Node(0, head)
# ... 操作 ...
return dummy.next
# 原地反转
prev, curr = None, head
while curr:
curr.next, prev, curr = prev, curr, curr.next9.9 习题
理论题
证明：Floyd算法在有限步内必能检测到环。
证明：约瑟夫问题的递推公式 $J(n, m) = (J(n-1, m) + m) \mod n$。
分析链表归并排序的时间复杂度。
证明：双链表的空间开销比单链表大一个指针大小。
设计题
设计一个支持 $O(1)$ 随机访问的链表变体。
实现一个支持并发访问的无锁链表。
实现题
实现链表的复制，包含随机指针。
实现两个链表表示的大数相加。
9.10 参考文献
Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd ed.). Addison-Wesley. Section 2.2.3: Linked Lists.
Floyd, R. W. (1967). Nondeterministic algorithms. Journal of the ACM, 14(4), 636-644.
Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley. Section 1.3: Bags, Queues, and Stacks.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.). MIT Press. Chapter 10: Elementary Data Structures.
Graham, R. L., Knuth, D. E., & Patashnik, O. (1994). Concrete Mathematics (2nd ed.). Addison-Wesley. Section 1.3: The Josephus Problem.
下一章：第10章 二叉树基础理论