Software Systems Atlas

深色模式

第2章：数组与链表 ​

Vol 2：算法森林探险 · 第2站：数据结构起点站

你在哪 ​

沿着森林小径走了一小段，你面前突然出现了两条岔路——一条笔直开阔（数组），一条弯弯曲曲但随时可以改道（链表）。你该走哪条？

你站在后山山脊上。右边是连成一片的整片树林——树挨着树，整齐得像列队等检阅的士兵。那是数组。

左边是散落在山坡上的一个个小棚屋——各有各的位置，靠一条小径串联，要找到第 100 个棚屋你得从第 1 个开始数。那是链表。

两片"森林"都不复杂。但选错一个，你的算法从起飞到坠毁只在一念之间。

你的任务 ​

本章分层

  • 必读：数组和链表的内存布局对比（连续 vs 离散）；数组访问/插入/删除时间复杂度表；单链表节点的定义和基本操作（插入、删除）——重点是"为什么定点操作是 O(1)"
  • 选读：双链表与循环链表的应用场景；哨兵节点（dummy node）简化边界处理
  • 深水区：缓存局部性（cache locality）的硬件原理——简要了解，详细在 Vol 3 计算机体系结构中展开

本章不会要求你掌握

  • 快慢指针（Floyd 判环算法）的各种变形——作为一个算法技巧在后面的挑战区了解即可
  • 跳表（Skip List）的完整实现
  • CPU 缓存层级（L1/L2/L3）的具体延迟数字

学完本章，你能够：

  1. 区分静态数组和动态数组，理解底层内存布局
  2. 手写单链表、双链表和循环链表的基本操作
  3. 用复杂度表回答"什么时候用数组、什么时候用链表"
  4. 了解缓存友好性（cache locality）——数组为什么在实际运行中比链表快得多，详细原理链接到 Vol 3

遭遇战：林间驿站的两条岔路 ​

你走在算法森林的小径上，面前出现了两条岔路，路边立着两块木牌。

木牌 A： 左边是一条笔直开阔的大路，路边整齐排列着 30 个树洞驿站。每个驿站的门牌号固定刻在石板上——想找 17 号驿站？直接走过去就行。

木牌 B： 右边是一条弯弯曲曲的小路，路边散落着一个个小棚屋，靠一条细绳串在一起。林间的驿站随时在变动——今天开了个新棚屋，明天有个老棚屋塌了。路线每天都在变。

你在冒险者笔记里模拟了一下：

  • 数组路（A）：查第 k 站 → 直接走过去，O(1)。但中间新增驿站 → 后面的门牌号全要重刻，O(n)。
  • 链表路（B）：查第 k 站 → 得从第 1 个棚屋开始一个一个数到 k，O(n)。但新增一个棚屋 → 只需解开细绳再系上，O(1)。

没有完美的路，只有合适的场景。

常见陷阱：数组 ​

静态数组 ​

内存里是一段连续的块。像一排电影院座位，座位号就是下标。

python
# Python 没有"纯静态数组"——list 是动态的
# 但我们可以用 array 模块模拟静态数组的行为
from array import array

# 创建一个 int 类型的静态数组
static_arr = array('i', [10, 20, 30, 40, 50])

# 随机访问：已知每个元素是 4 字节
# 要取第 3 个（下标 2）→ 内存地址 = 基地址 + 2 × 4
print(static_arr[2])  # 30
# 输出: 30

为什么随机访问是 O(1)？ 因为 arr[k] = 基地址 + k × 元素大小。这是一个乘法 + 一个加法的机器指令，与 n 无关——所以 O(1)。

动态数组 ​

Python 的 list、Java 的 ArrayList、C++ 的 std::vector——它们底层还是连续数组，但容量不够时自动扩容。

python
# Python list 扩容机制
arr = []
for i in range(10):
    arr.append(i)
    print(f"len={len(arr)}, capacity≈{len(arr)}", end="")

如果仔细追踪 Python list 的 sys.getsizeof，你会发现它每次扩容约 1.125 倍（不同版本细节有差异）。每次扩容须分配新内存 + 拷贝所有旧元素 → O(n)。但均摊下来，单次 append 是 O(1)。

** Java 差异：** ArrayList 默认初始容量是 10，扩容因子是 1.5 倍（newCapacity = oldCapacity + (oldCapacity >> 1)）。明确知道元素数量时，提前指定容量避免频繁扩容：new ArrayList<>(initialCapacity)。

** C++ 差异：** std::vector 默认扩容因子通常是 2 倍（具体取决于实现）。用 reserve(n) 预分配空间可以避免扩容开销。C++ 没有 GC，所有元素析构函数会在 vector 销毁时依次调用——这在非平凡的类上会有额外开销。

数组操作复杂度表 ​

操作静态数组动态数组（最好/最坏/摊销）
随机访问 arr[k]O(1)O(1)
末尾插入（不可变）O(1) / O(n) / 摊销 O(1)
中间插入O(n)
开头插入O(n)
按值查找O(n)O(n)
删除末尾O(1)
删除中间O(n)

常见陷阱：链表 ​

链表的节点是散落在内存里的。每个节点拿着下一节点的"地址"——就像披着斗篷的神秘人递给你一张纸条："下一个在 0x7ffd..."

单链表节点 ​

python
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 构建: 1 → 2 → 3
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)

查找第 k 个元素： 你没有下标的地图。只能从 head 开始，一个一个往后找。

python
def get_kth(head: ListNode, k: int) -> ListNode:
    for _ in range(k):
        if not head:
            raise IndexError("k 越界了")
        head = head.next
    return head

复杂度？O(k)。最坏 O(n)。

插入节点 ​

python
def insert_after(prev: ListNode, val: int):
    """在 prev 节点之后插入一个新节点"""
    new_node = ListNode(val)
    new_node.next = prev.next   # 新节点指向原后置节点
    prev.next = new_node        # prev 指向新节点
    # 链表插入 = 改两条线，O(1)

关键洞察：如果已经站在要插入的位置（prev 节点）上，插入本身是 O(1)。 但在数组里，"找到位置"和"插入"加起来也是 O(n)——因为你要把后面的元素逐个右移。链表的优势在于：只要你知道 '站在谁后面'，插入是常数操作。

删除节点 ​

python
def delete_after(prev: ListNode):
    """删除 prev 的后继节点"""
    if prev and prev.next:
        prev.next = prev.next.next  # 跳过要删的节点
    # 也是 O(1)，只需改一条线

双链表 ​

每个节点多了 prev 指针：

python
class DoublyListNode:
    def __init__(self, val=0, prev=None, next=None):
        self.val = val
        self.prev = prev
        self.next = next

双链表的优势：

  • 反向遍历：从尾到头也是 O(n)，单链表做不到
  • 删除时已知节点：不需要找前驱节点，因为 node.prev 直接告诉你是谁

代价：每个节点多存一个指针（内存翻倍）。

循环链表 ​

尾节点的 next 不指向 None，而是回头指向 head。

应用场景：轮询调度（Round-Robin）、约瑟夫环问题、Ring Buffer。

python
class CircularLinkedList:
    def __init__(self):
        self.head = None

    def build(self, vals):
        if not vals:
            return
        self.head = ListNode(vals[0])
        cur = self.head
        for v in vals[1:]:
            cur.next = ListNode(v)
            cur = cur.next
        cur.next = self.head  # 最后指向头 → 循环

** Java 差异：** Java 标准库没有直接的单链表实现。LinkedList<E> 是双链表，实现了 List 和 Deque 接口。add(index, element) 需要 O(n) 找到位置——不要被 list.add(0, x) 的表面简洁骗了，背后是 O(n) 的遍历。

** C++ 差异：** std::forward_list 是单链表（你猜为什么叫 forward）。std::list 是双链表。C++ 的迭代器机制很优雅——插入节点后，之前拿到的迭代器依然有效（不像 vector 的迭代器在扩容后会失效）。这是链表的"不变量"优势。

实战对比：数组 vs 链表 ​

实战永远是最真实的。试试在 10 万个元素的中间位置插入一个元素：

python
import time

# 数组（Python list）
arr = list(range(100_000))
start = time.perf_counter()
arr.insert(50_000, 999)   # 中间插入
t_list = time.perf_counter() - start
print(f"list.insert: {t_list*1000:.1f} ms")
# 输出示例: list.insert: ~0.6 ms (但实际 O(n) 移动 ~50000 个元素)

链表呢？在 Python 里链表没有内置实现，但即使手动实现，你会发现数组的实际运行时间可能比链表更快——为什么？

缓存友好性（Cache Locality）——简要了解 ​

本节仅做概念介绍。 完整深入的缓存层次结构和性能分析在 Vol 3（计算机系统） 中专门展开。

这就是残酷的现实。

数组是连续的。当你访问 arr[0] 时，CPU 把它周围的一整块数据（一个 cache line，通常是 64 字节）都拽到 L1 缓存里了。所以 arr[1]、arr[2]……都在缓存里。访问它们几乎不要钱。

链表是离散的。访问 node.next 时，node 和 node.next 可能相隔十万八千里。每次都要重新从主存里读——主存比 L1 缓存慢 100 倍。

所以在真实机器上：

  • 遍历 100 万个数组元素：连续命中缓存 → 飞快
  • 遍历 100 万个链表节点：几乎每次都 cache miss → 慢 10-100 倍

复杂度分析告诉你 O(n) 就是 O(n)？不对。实际世界里，O(n) 连续读取和 O(n) 随机跳转的速度差了不止一个数量级。 详情请见 Vol 3 存储器层次结构章节。

** Java 差异：** Java 的数组元素是连续存储的，但 LinkedList 的节点是对象——每个节点本身有对象头开销（12-16 字节），加上 val 和 next/prev 引用。100 万个节点的 LinkedList 可能占用 40-50 MB，而等长的 int[] 只需 ~4 MB。内存访问模式是巨大的性能杀手。 另一个 Java 独有的现象是 GC 压力——每个链表节点都是独立的堆对象，创建和回收它们给垃圾回收器带来很大压力。而数组是一个连续大对象，GC 扫描起来快得多。因此在 Java 中，ArrayList 总是优于 LinkedList，除非你确实需要频繁的 Queue/Deque 操作（这时用 ArrayDeque，别用 LinkedList）。

** C++ 差异：** std::vector 在连续内存上存储元素，std::list 每个节点单独分配（new）。如果你用自定义分配器（allocator）把链表节点放在一个连续内存池里，缓存友好性会提升。但大多数人不用这个功能——所以默认链表慢。 C++ 还有一个独特的优势：std::vector 的 data() 方法让你能直接拿到底层数组指针，与 C 接口互操作。这是链表做不到的——你不能把 std::list 的节点数组传给一个 C 函数。

用哨兵节点简化链表操作 ​

链表操作中最烦人的一件事是边界处理——头节点为空怎么办？在头部插入和在中间插入能共用同一份代码吗？

哨兵节点（dummy node）就是解决这个问题的：

python
def remove_node(head, val):
    """删除链表中所有值为 val 的节点（带哨兵版）"""
    dummy = ListNode(0)  # 哨兵节点，不存实际数据
    dummy.next = head
    cur = dummy
    while cur.next:
        if cur.next.val == val:
            cur.next = cur.next.next  # 跳过待删节点
        else:
            cur = cur.next
    return dummy.next  # 跳回真正的头

为什么用哨兵？ 没有哨兵的话，你得单独写一个 if 来处理头节点的删除逻辑。哨兵让所有节点的处理方式变成一致的——没有特例了。

算法技巧挑战区：快慢指针 ​

快慢指针是一个重要的算法技巧，建议先掌握基础链表操作再回来深入。 本节属于挑战扩展。

快慢指针是链表最优雅的技巧之一。两个指针从同一位置出发，快指针每次走两步，慢指针每次走一步。

python
def middle_node(head):
    """返回链表的中间节点"""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

这个技巧的魅力在于：快指针走完时，慢指针刚好在中间。 不需要知道链表长度，不需要下标计算。

其他快慢指针的变形：

  • 判环： 快慢指针相遇说明有环（Floyd 判环算法）
  • 找倒数第 k 个： 快指针先走 k 步，然后快慢一起走
  • 链表排序： 快慢指针找中点，然后归并

现实类比： 快慢指针就像两个跑步的人，一个跑得快一个跑得慢。你在跑道上观察——如果快的一圈后追上了慢的，说明跑道是环形的。

通关挑战 ​

  1. 实现一个单链表的反转函数（in-place，不创建新节点）

  2. 给你两个有序链表，将它们合并成一个有序链表

  3. 缓存陷阱题： 为什么在对一个很大的二维数组做遍历时，按行遍历比按列遍历快得多？

python
# 按行遍历
for i in range(n):
    for j in range(n):
        arr[i][j] += 1

# 按列遍历
for j in range(n):
    for i in range(n):
        arr[i][j] += 1
👆 参考答案

1. 反转单链表：

python
def reverse(head):
    prev = None
    cur = head
    while cur:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    return prev  # 新头节点

2. 合并有序链表：

python
def merge_two(l1, l2):
    dummy = ListNode(0)
    cur = dummy
    while l1 and l2:
        if l1.val < l2.val:
            cur.next, l1 = l1, l1.next
        else:
            cur.next, l2 = l2, l2.next
        cur = cur.next
    cur.next = l1 or l2
    return dummy.next

3. 行遍历更快 —— 因为 C 语言/底层中二维数组在内存中是按行连续存储的（row-major）。按行遍历：arr[0][0], arr[0][1], ... 是连续内存 → 缓存命中极好。按列遍历：arr[0][0], arr[1][0], arr[2][0], ... 跳了 n 个元素才到下一个 → 几乎每步都是 cache miss。

验收标准 ​

  • [ ] 能画图说明数组和链表在内存中的存储结构
  • [ ] 能手写单链表节点的插入和删除（O(1) 定点操作）
  • [ ] 能解释"动态数组的末尾插入是摊销 O(1)"
  • [ ] 能用人话讲清楚"缓存友好性为什么会让数组比链表快一个量级"
  • [ ] 会根据以下场景选择数据结构：
你的需求选什么
频繁按索引读取（石碑名次、驿站查询）数组
频繁在中间插入/删除（林间日志修改）链表
需要双向遍历（兽道来回追踪）双链表
需要轮询循环（进程调度）循环链表
不确定场景但没性能瓶颈动态数组（list）— 大多数场景的默认选择

常见卡点 ​

卡点真相
"链表插入 O(1) 所以比数组快"只在你已经站在插入点时成立。找插入点本身可能是 O(n)。组合起来仍然是 O(n)。
"Python 的 list 就是链表"大错！Python 的 list 底层是动态数组（连续内存 + O(1) 索引）。真链表是你自己写的 ListNode 链。
"链表不浪费空间"每个节点多存一个 next 指针（64 位机器上 8 字节）。双链表多 16 字节。加上对象头开销，链表通常比数组更吃内存。
"大 O 就是一切"缓存、内存分配、GC 压力在工程实践中的影响往往超过大 O 的预测。复杂度分析是工具，不是判决书。

现在不需要理解 ​

  • 跳表（Skip List） —— 链表 + 多层索引，后面在"高级数据结构"章节讲
  • LRU Cache —— 用哈希表 + 双链表实现，后面专门讲
  • 内存池分配器 —— 优化链表缓存友好性的高级技巧
  • CPU 缓存层级（L1/L2/L3） —— 知道"连续内存更快"就够了，具体延迟数字不是现在要背的

旅人笔记 ​

  • 数组是你口袋里最基础的工具， 几乎任何语言都能用。先学数组，再学链表。
  • 链表面试高频操作： 反转、合并、找环、找中点（快慢指针）。牢记这四个操作，能覆盖 90% 的链表题。
  • 快慢指针（Floyd 判环算法） 是链表里最有想象力的技巧——一个指针走两步，一个走一步，相遇就有环。你不会在数组里想到这种招数。
  • 实战选型决策： 95% 的场景用动态数组就够了。链表在你需要"频繁在中间插入且元素特别多"时才值得考虑。别为了"学链表"而强行用链表。

→ 下一站预告 ​

第3章：栈与队列

你现在会处理连续内存（数组）和离散内存（链表）了。下一站，我们把它们变成两种特殊的容器——栈（后进先出）和队列（先进先出）。你会看到递归的栈展开、括号匹配的经典面试题，以及用队列实现 BFS 的奥妙。

继续前进。

Built with VitePress | Software Systems Atlas

Copyright 2026 Steven Yang