第 5 讲：序列 ADT——数组、动态数组与链表

一、序列 ADT

序列（sequence） 关心元素的外在顺序——由使用者决定谁排第几，而不是由元素的值决定。（由值决定顺序的是集合/字典 ADT，见第 7 讲与第 15 讲。）

操作	语义
`Get(i)` / `Set(i, x)`	按位置读写
`InsertAt(i, x)` / `DeleteAt(i)`	在位置 i 插入 / 删除
`InsertFirst` / `InsertLast`	头插 / 尾插
`DeleteFirst` / `DeleteLast`	头删 / 尾删
`Len()`	元素个数

⭐ 本讲的核心结论只有一句：没有一种实现在所有操作上都最优，选型取决于你的操作混合比例。

二、静态数组

一块连续内存，第 i 个元素的地址 = base + i × 元素大小。

索引:    0     1     2     3     4     5
       ┌─────┬─────┬─────┬─────┬─────┬─────┐
       │  31 │  41 │  59 │  26 │  53 │  58 │
       └─────┴─────┴─────┴─────┴─────┴─────┘
地址:  1000  1008  1016  1024  1032  1040   （int64）

操作	代价	原因
`Get(i)` / `Set(i, x)`	Θ(1)	一次地址计算
`InsertAt(i, x)`	Θ(n)	要把 i 之后所有元素右移
`DeleteAt(i)`	Θ(n)	左移
尾部插入	—	静态数组做不到（容量固定）

这里的取舍非常干净：连续存储换来了 O(1) 随机访问，代价是任何改变长度的操作都要搬数据。

三、动态数组

核心思想：容量满时新开一块几何增长的内存，把数据搬过去。第 4 讲已证明：倍增策略下，尾部追加的摊还代价是 Θ(1)；线性增长则退化成 Θ(n)。

Go 的 slice 就是内建的动态数组，它的三元组是「指针 + 长度 + 容量」：

type Vector struct {
    data []int
}

func (v *Vector) Len() int      { return len(v.data) }
func (v *Vector) Get(i int) int { return v.data[i] } // Θ(1)

func (v *Vector) Append(x int) { // 摊还 Θ(1)
    v.data = append(v.data, x)
}

func (v *Vector) InsertAt(i, x int) { // Θ(n)
    v.data = append(v.data, 0)   // 先扩一格
    copy(v.data[i+1:], v.data[i:]) // 右移 [i, n) 段
    v.data[i] = x
}

func (v *Vector) DeleteAt(i int) { // Θ(n)
    copy(v.data[i:], v.data[i+1:]) // 左移
    v.data = v.data[:len(v.data)-1]
}

⚠️ Go 特有的两个坑

（1）删除引用类型元素会造成内存泄漏。 上面的 DeleteAt 缩短了长度，但底层数组最后一格仍持有旧引用，GC 无法回收它指向的对象。正确写法要显式清零：

func (s *Stack[T]) Pop() T {
    var zero T
    n := len(s.data) - 1
    x := s.data[n]
    s.data[n] = zero // 关键：断开引用，否则底层数组一直持有它
    s.data = s.data[:n]
    return x
}

（2）切片共享底层数组。 b := a[2:5] 不拷贝数据，对 b 的写入会改到 a。要独立副本必须显式 copy 或用三索引切片 a[2:5:5] 限制容量，让后续 append 触发复制。

预分配的价值

buf := make([]int, 0, n) // 已知规模时一次分配到位

这不改变渐近复杂度（本来就是 Θ(n)），但省掉全部 log n 次拷贝与内存分配。在热路径上这经常是 2–3 倍的实测差距——渐近分析看不见它，profiler 看得见。

四、链表

元素分散在堆上，用指针串起来。

单链表：
 head
  │
  ▼
┌────┬───┐   ┌────┬───┐   ┌────┬───┐
│ 31 │ ●─┼──▶│ 41 │ ●─┼──▶│ 59 │nil│
└────┴───┘   └────┴───┘   └────┴───┘

双链表（带头尾哨兵）：
        ┌───────┐     ┌───────┐     ┌───────┐     ┌───────┐
 ┌─────▶│ 哨兵头 │◀───▶│  31   │◀───▶│  41   │◀───▶│ 哨兵尾 │◀─────┐
 └──────└───────┘     └───────┘     └───────┘     └───────┘──────┘

type Node[T any] struct {
    val        T
    prev, next *Node[T]
}

type List[T any] struct {
    head, tail *Node[T] // 哨兵节点，不存数据
    size       int
}

func NewList[T any]() *List[T] {
    h, t := &Node[T]{}, &Node[T]{}
    h.next, t.prev = t, h
    return &List[T]{head: h, tail: t}
}

// 在节点 p 之后插入 x，Θ(1)——不需要任何判空分支
func (l *List[T]) InsertAfter(p *Node[T], x T) *Node[T] {
    n := &Node[T]{val: x, prev: p, next: p.next}
    p.next.prev = n
    p.next = n
    l.size++
    return n
}

// 删除节点 p，Θ(1)——已经拿到节点指针时无需查找
func (l *List[T]) Remove(p *Node[T]) T {
    p.prev.next = p.next
    p.next.prev = p.prev
    p.prev, p.next = nil, nil // 帮 GC
    l.size--
    return p.val
}

func (l *List[T]) PushFront(x T) *Node[T] { return l.InsertAfter(l.head, x) }
func (l *List[T]) PushBack(x T) *Node[T]  { return l.InsertAfter(l.tail.prev, x) }

⭐ 哨兵节点（sentinel）

上面的 InsertAfter 和 Remove 没有一个 if。这是因为哨兵头尾节点保证了"每个真实节点都有前驱和后继"，把"插到表头"“删掉最后一个元素"这些边界情形变成了普通情形。

没有哨兵的版本要写四个分支（空表 / 头部 / 尾部 / 中间），而链表 bug 的绝大多数正好出在这四个分支上。

这是一条通用的数据结构设计原则：用一点空间消灭边界情形。 红黑树的 nil 哨兵（第 17 讲）、跳表的头节点（第 19 讲）用的是同一个技巧。

五、代价矩阵

操作	静态数组	动态数组	单链表	双链表（带尾指针）
`Get(i)`	Θ(1)	Θ(1)	Θ(n)	Θ(n)
`InsertFirst`	Θ(n)	Θ(n)	Θ(1)	Θ(1)
`DeleteFirst`	Θ(n)	Θ(n)	Θ(1)	Θ(1)
`InsertLast`	—	Θ(1) 摊还	Θ(1)	Θ(1)
`DeleteLast`	Θ(1)	Θ(1)	Θ(n)	Θ(1)
`InsertAt(i)`（已知位置 i）	Θ(n)	Θ(n)	Θ(n) 找 + Θ(1) 改	Θ(n) 找 + Θ(1) 改
已持有节点指针时删除	Θ(n)	Θ(n)	Θ(n)	Θ(1)
空间开销	0	≤ n（未用容量）	n 个指针	2n 个指针
缓存局部性	优	优	差	差

⭐ 表里最重要的一行是倒数第三行：“已持有节点指针时的 Θ(1) 删除"是双链表唯一无可替代的能力。LRU 缓存正是靠它：散列表存 key → 节点指针，双链表维护访问顺序，两者结合得到 O(1) 的 get 与 put。

六、缓存局部性：渐近分析看不见的事

两段代码都是 Θ(n)：

sum := 0
for _, x := range arr { sum += x }        // 数组遍历

sum := 0
for p := head; p != nil; p = p.next { sum += p.val }  // 链表遍历

实测差距通常在 5–10 倍。 原因在内存层级：

CPU 从内存取数据时，一次搬一整条缓存行（通常 64 字节）

数组：  [x0][x1][x2][x3][x4][x5][x6][x7] ← 一次缓存未命中，带回 8 个 int64
        └────────── 一条缓存行 ──────────┘
        之后 7 次访问全部命中

链表：  节点散落在堆的各处
        [节点A] ....... [节点C] ... [节点B] .....
        每次 p = p.next 都可能是一次缓存未命中（~100 ns）
        而且指针追逐（pointer chasing）无法被预取器预测

结论：在现代硬件上，遍历密集的场景下动态数组几乎总是赢，即使中间插入是 Θ(n)。C++ 社区有个著名的经验结论：vector 的 O(n) 插入在 n 小于几千时仍快于 list 的 O(1) 插入，因为 memmove 是顺序访问，而链表插入前必须先指针追逐找到位置。

Go 里这一点更明显：[]T 是值的连续存储（如果 T 不是指针），而链表节点每个都是独立的堆分配，还给 GC 增加扫描负担。

那链表什么时候真的该用

场景	为什么
LRU 缓存 / 侵入式链表	已持有节点指针的 O(1) 摘除，且不能有拷贝
需要稳定指针（迭代器不失效）	数组扩容会让所有指针失效，链表不会
无锁队列、内核调度队列	单个节点的原子指针操作
元素巨大且频繁移动	移动一个指针 vs 移动一个 4KB 结构体
需要 O(1) 拼接两个序列	改两个指针即可

Go 标准库的 container/list 就是双链表，但在实践中直接用 slice 的场合远多于它。

七、其他序列变体

结构	特点	代价
循环数组（ring buffer）	头尾都 O(1)，见第 6 讲	两端 Θ(1)，中间 Θ(n)
分块链表（unrolled list）	每个节点存 √n 个元素的数组	插入/删除/访问都 Θ(√n)，缓存友好
跳表	概率式多级索引，见第 19 讲	期望 Θ(log n) 各操作
平衡树序列（rope）	按子树大小定位，见第 20 讲	全部 Θ(log n)，文本编辑器用

⭐ 值得注意的是最后一行：如果你同时需要 O(log n) 的随机访问和 O(log n) 的任意位置插入，答案不是链表也不是数组，而是增强过的平衡树——这是第 20 讲的主题。

随堂自测

为什么动态数组必须几何增长？增长因子 2 与 1.5 各有什么工程理由？
Go 中 s = append(s[:i], s[i+1:]...) 删除元素时，如果 s 的元素是指针类型，会有什么问题？怎么修？
双链表相对单链表多花一倍指针空间，换来了哪两个能力？
用哨兵节点重写一个"删除链表中所有值为 x 的节点"的函数，说明哨兵消灭了哪些分支。
两个都是 Θ(n) 的遍历为什么实测差 5–10 倍？请用缓存行解释。
设计一个 LRU 缓存，说明为什么必须是"散列表 + 双链表”，单用其中之一为什么不行。
如果一个序列要频繁在中间位置插入，且需要按下标访问，数组和链表都不好，应该用什么？

一、序列 ADT#

二、静态数组#

三、动态数组#

⚠️ Go 特有的两个坑#

预分配的价值#

四、链表#

⭐ 哨兵节点（sentinel）#

五、代价矩阵#

六、缓存局部性：渐近分析看不见的事#

那链表什么时候真的该用#

七、其他序列变体#

随堂自测#