学会顺序表和链表的演进设计之后，真正困难的问题不再是“代码怎么写”，而是“当前场景应该选哪一个”。如果只背诵复杂度，很容易得到两个过度简化的结论：
- “需要查询就用顺序表”；
- “需要插删就用链表”。
现实中还要考虑定位是否已经完成、访问比例、CPU 缓存、内存开销、引用稳定性以及标准库是否已有更合适的容器。本节用同一套问题框架完成选择。
学习目标
完成本节后，你应该能够：
- 用“定位成本 + 修改成本”解释一次操作的总成本；
- 比较随机访问、批量移动、缓存局部性和空间利用率；
- 根据读写比例与操作位置筛选顺序表、链表和双端队列；
- 识别“理论复杂度相同，实际常数与局部性不同”的场景；
- 解释 LRU 为什么要组合哈希表与双向链表；
- 写出带前提、可检验而非绝对化的选型结论。
4.1 全方位性能对比决战矩阵
以下讨论使用三种典型实现：
- 动态顺序表：连续数组，容量不足时按倍数扩容，对应 C++ 的
std::vector； - 带哨兵单链表：每节点一个
next； - 双向循环哨兵链表：每节点一个
prev和一个next，首尾都与哨兵相连。
4.1.1 随机存取 O(1) vs 指针遍历 O(n)
| 操作 | 动态顺序表 | 单链表 | 双向循环链表 |
|---|---|---|---|
按下标读取 i | O(1) | O(n) | O(n)，可从较近一端走 |
| 按值查找 | O(n) | O(n) | O(n) |
| 头部插入/删除 | O(n) | O(1) | O(1) |
| 尾部追加 | 摊还 O(1) | 有尾指针时 O(1) | O(1) |
| 尾部删除 | O(1) | O(n) | O(1) |
按下标 i 插入/删除 | O(n) 搬移 | O(n) 定位 + O(1) 改链 | O(n) 定位 + O(1) 改链 |
| 已知节点附近插入/删除 | 仍可能 O(n) 搬移 | 已知前驱时 O(1) | 已知节点时 O(1) |
| 完整遍历 | O(n) | O(n) | O(n) |
表中最值得反复检查的是“按下标插删”与“已知节点插删”的区别。链表没有下标寻址能力，输入 i 时仍要先走到目标附近。
可以把一次操作拆成：
因此，选型前应该先问：
调用者给我的是下标、关键字，还是一个仍然有效的节点/迭代器？
例题 1：只看“写操作”会选错
某排行榜保存 1\,000\,000 条记录，业务请求中：
- 80% 是按排名读取；
- 15% 是尾部追加一批新记录；
- 5% 是每天离线重建时的批量调整。
顺序表和链表应选哪个？
查看分析
优先选择动态顺序表。
- 80% 的按排名读取需要随机访问，顺序表为
O(1)，链表为O(n)； - 尾部追加在倍增扩容下是摊还
O(1)； - 5% 的调整是离线批处理，可以集中排序或重建，没必要为低频写入牺牲全部读取的局部性与下标访问。
结论必须和比例绑定。如果调整变成高频、在线、且调用者长期持有稳定节点，答案才可能改变。
4.1.2 批量移动 O(n) vs 局部修改 O(1)
在位置 1 插入 15，两类容器的代码很像，但隐藏成本不同：
#include <iterator>
#include <list>
#include <vector>
std::vector<int> sequential{10, 20, 30};
sequential.insert(sequential.begin() + 1, 15);
// begin() + 1 是 O(1)，但 20、30 需要向后移动。
std::list<int> linked{10, 20, 30};
auto cursor = linked.begin();
++cursor; // 先定位到 20；走过的步数也属于总成本。
linked.insert(cursor, 15);
// 已知 cursor 后，只修改局部链接。对顺序表来说，定位下标快，修改区间可能慢；对链表来说，定位可能慢，定位完成后的局部修改快。
不要把迭代器当成免费出现
若 cursor 是从 begin() 临时走到第 i 个位置得到的，遍历成本必须计入本次操作。只有当业务本来就长期持有有效迭代器或节点句柄时，链表的 O(1) 局部修改才会直接兑现。
4.1.3 CPU Cache Line 命中率与内存连续性
渐近复杂度只描述规模增长，不描述处理器取得数据的方式。
顺序表元素连续存放。读取 a[i] 时，处理器通常会把包含它的一小块连续内存载入缓存；接下来访问 a[i+1]、a[i+2] 时，它们很可能已经在同一条或相邻 Cache Line 中。这叫空间局部性。
链表节点通常由多次分配得到，物理地址可能分散。读取当前节点后，处理器必须先取得 next，才能知道下一个地址；若下一个节点不在缓存中，就可能等待更慢的内存访问。这类依赖指针的跳转称为 pointer chasing。
即使二者完整遍历都是 O(n)，顺序表通常也更容易利用缓存和预取。这里的“通常”不能替换成固定倍数：实际结果还受元素大小、分配器、硬件、编译优化与访问模式影响。
例题 2：同为 O(n)，为什么耗时可能不同
顺序表和链表都保存一千万个整数，只做一次从头到尾求和。两者渐近复杂度都是 O(n)，是否意味着运行时间接近？
查看分析
不意味着。顺序表中的整数连续，单个 Cache Line 往往能带来多个后续元素；硬件也更容易预取。链表除了读取数据，还要读取链接，并可能在分散地址间跳转。
正确结论是“二者增长阶相同，但常数、缓存未命中和额外读流量可能明显不同”。若要比较具体机器上的差异，应在固定编译器、数据规模和分配策略下测量，不能把某一次微基准写成普遍定律。
4.1.4 空间利用率对比
顺序表与链表都会产生额外空间，只是浪费形态不同。
顺序表：预留容量与扩容碎片
动态顺序表通常满足 size \le capacity：
其中尚未使用的槽位约占：
扩容时还可能短暂同时存在旧缓冲区和新缓冲区。优点是所有元素共享一段紧凑存储，不需要每个元素重复保存链接。
链表：每节点链接与分配开销
- 单链表每个节点至少多一个指针；
- 双向链表每个节点至少多两个指针；
- 节点还可能因对齐、分配器元数据和内存碎片付出额外成本。
在常见 64 位环境中，一个指针通常为 8 字节，因此链接字段的典型量级是单链表 8 字节、双向链表 16 字节/节点，这只是链接本身。实际 sizeof(Node) 取决于 ABI、字段顺序、对齐和编译器，堆分配的管理开销也未必包含在 sizeof(Node) 中。
小元素更容易被指针“反客为主”
若业务元素只是一个 4 字节整数，双向节点的两个指针可能比数据本身大得多；若元素是大型对象，链接占比则会下降。比较空间时应使用真实元素类型和目标平台。
4.2 场景选型决策树
复杂度表回答“单个操作怎样增长”，决策树回答“哪类操作在当前业务中最重要”：
4.2.1 “读多写少”选型法则
以下场景通常优先动态顺序表：
- 排行榜快照：高频按排名读取，低频批量重建；
- 只读词典条目：若主要按编号读取、二分或顺序扫描，连续存储更合适；
- 频繁随机抽取：随机生成下标后可
O(1)访问； - 批处理数据：一次装载，多次遍历、排序和聚合。
“只读词典”并不意味着所有按关键字查询都应线性扫描。如果核心需求是按键精确查找，散列表或树形索引可能比两类线性表都合适。选型范围不能被题目里的“表”字限制。
下面的快照类把重建与读取分开：
#include <algorithm>
#include <cstddef>
#include <stdexcept>
#include <utility>
#include <vector>
struct Record {
int id;
int score;
};
class RankingSnapshot {
private:
std::vector<Record> rows_;
public:
void rebuild(std::vector<Record> next) {
std::sort(next.begin(), next.end(), [](const Record& left, const Record& right) {
return left.score > right.score;
});
rows_ = std::move(next);
}
const Record& at_rank(std::size_t rank) const {
if (rank >= rows_.size()) {
throw std::out_of_range("rank out of range");
}
return rows_[rank];
}
std::size_t size() const noexcept {
return rows_.size();
}
};代码讲解
rebuild接受一批新数据，集中排序后一次替换旧快照；低频写成本被隔离。at_rank直接用下标访问，单次为O(1)。- 返回
const Record&避免复制，但该引用只在下一次rebuild或可能触发重分配的修改前有效。 - 如果业务必须在更新后继续持有旧记录引用，就要改用稳定句柄、间接层或其他存储，而不是忽略引用失效。
4.2.2 “频繁头尾增删”选型法则
“两端操作多”会把候选范围缩小，但不会自动推出“手写双向链表”：
| 场景 | 常见首选 | 原因 |
|---|---|---|
| 撤销栈，只在尾部压入/弹出 | std::vector | 尾部操作摊还 O(1)，缓存友好 |
| 消息队列，头出尾进 | std::deque | 两端 O(1)，分块连续，标准库已处理边界 |
| 固定容量实时流 | 环形缓冲区 | 容量可控，无节点分配，覆盖策略明确 |
| 已持有节点，频繁删除或移动任意节点 | std::list / 双向链表 | 迭代器稳定，局部摘链与拼接为 O(1) |
| 既要按键定位，又要维护最近使用顺序 | 哈希表 + 双向链表 | 哈希负责定位，链表负责 O(1) 调序 |
例题 3：消息队列一定选链表吗
消息从尾部进入、从头部离开，最大长度未知。单链表、双向链表和 std::deque 都能做到两端操作 O(1)，应该直接手写链表吗？
查看分析
通常先选 std::deque。它直接提供头删尾插，不要求每条消息单独分配节点，常有更好的局部性，也减少了所有权和异常安全代码。
只有在业务还要求节点地址长期稳定、需要从队列中间按已知句柄取消消息，或要把节点在多个链之间 O(1) 转移时，双向链表才显出独特价值。
例题 4：播放列表中的“当前歌曲”
播放器长期保存当前歌曲的节点句柄，并频繁执行：
- 在当前歌曲后插入；
- 删除当前歌曲并跳到下一首；
- 向前或向后切换；
- 不要求按第
i首随机访问。
查看分析
双向循环链表是合理候选。
当前节点已经持有，因此插入、删除与前后移动都只需局部链接；循环哨兵还能自然处理首尾切换。顺序表删除当前歌曲可能搬移后续元素，并使旧引用或迭代器失效。
若播放列表更常见的操作其实是按编号跳转、随机播放和完整顺序扫描，顺序表仍可能更好。选型取决于主导访问模式，不取决于“播放列表”这个名字。
组合例题：LRU 为什么需要两种结构
LRU 缓存需要同时完成：
- 按键查找缓存项；
- 命中后把该项移到“最近使用”端；
- 容量满时删除“最久未使用”端。
单独的顺序表能按位置访问，却无法按键平均 O(1) 定位；单独的链表能 O(1) 调整已知节点，却仍需 O(n) 按键查找。组合结构让两者各自负责擅长的部分：
#include <cstddef>
#include <list>
#include <optional>
#include <unordered_map>
#include <utility>
class LRUCache {
private:
using Entry = std::pair<int, int>; // key, value
using Iterator = std::list<Entry>::iterator;
std::size_t capacity_;
std::list<Entry> order_; // 表头最近使用，表尾最久未使用
std::unordered_map<int, Iterator> index_;
public:
explicit LRUCache(std::size_t capacity) : capacity_(capacity) {}
std::optional<int> get(int key) {
auto found = index_.find(key);
if (found == index_.end()) {
return std::nullopt;
}
order_.splice(order_.begin(), order_, found->second);
return found->second->second;
}
void put(int key, int value) {
if (capacity_ == 0) {
return;
}
auto found = index_.find(key);
if (found != index_.end()) {
found->second->second = value;
order_.splice(order_.begin(), order_, found->second);
return;
}
if (order_.size() == capacity_) {
const int expired_key = order_.back().first;
index_.erase(expired_key);
order_.pop_back();
}
order_.emplace_front(key, value);
index_[key] = order_.begin();
}
};代码讲解
index_把键映射到链表迭代器；在散列均匀的通常假设下，定位平均为O(1)。std::list::splice把已有节点移到表头，不复制元素，并保持该节点迭代器有效。order_.back()与pop_back()在尾部淘汰最旧项，均为O(1)。- 哈希表必须在链表节点删除前移除对应键，否则会留下指向已释放节点的迭代器。
- 这里的平均
O(1)依赖散列表负载与散列质量；最坏情况不能被省略成无条件保证。
例题 5：为什么不用“哈希表 + 顺序表”
哈希表也可以把键映射到顺序表下标。为什么 LRU 更常配双向链表？
查看分析
命中后需要把任意元素移到最近使用端。顺序表删除中间元素并插到头部会搬移一段数据；移动后，大量元素下标改变，哈希表里的映射也要同步更新。
双向链表迭代器直接定位节点，摘下并拼到表头只改局部链接，其他节点句柄保持有效。
一页选型检查表
做出选择前，依次回答：
- 高频操作是什么？给出大致比例，而不是只列操作名称。
- 输入是下标、关键字，还是已经持有的节点/迭代器？
- 是否要求引用、指针或迭代器在插删后保持有效？
- 数据是否被高频顺序遍历，缓存局部性是否重要？
- 元素大小与节点指针相比如何，内存预算是否敏感？
- 操作只发生在尾部、两端，还是任意已知节点附近？
vector、deque、list、环形缓冲区或组合索引中，标准库是否已有合适实现？- 当前结论来自访问模式，还是来自“链表插删快”之类的口号？
小结与自测
顺序表和链表不是互相取代，而是交换不同成本：
- 顺序表用连续空间换取随机访问和缓存局部性，承担扩容与中间搬移；
- 链表用链接和分配开销换取稳定节点与定位后的局部修改；
- 双向循环哨兵链表优化头尾和已知节点操作，却没有消除按下标定位；
deque、环形缓冲区以及“哈希 + 链表”等组合，常比二选一更贴近真实需求。
请尝试回答：
- 为什么
std::vector::push_back通常写成“摊还O(1)”而不是永远O(1)？ - 两个容器遍历都是
O(n)，还应比较哪些硬件与内存因素？ - 消息队列为什么常优先
deque而不是手写双向链表？ - “已知节点”如何改变链表删除操作的复杂度结论？
- LRU 中哈希表与双向链表分别维护什么不变量？
查看自测答案
- 容量足够时只在尾部构造；扩容当次要申请新空间并搬移已有元素，多次追加的总成本经摊还后为
O(1)。 - 比较 Cache Line 利用、预取、指针跳转、节点分配、元素大小、对齐和内存碎片。
deque已提供两端O(1)操作，通常减少逐节点分配并降低手写所有权与边界错误。- 定位成本已经由调用者支付，双向链表只需修改有限条链接，因此局部删除为
O(1)。 - 哈希表保证键能找到对应链表节点；链表保证从最近到最久的顺序，且每个缓存项恰好出现一次。
现在可以继续阅读1.5 现实中的 List 与工程扩展，或回到第 1 章总览复盘两种实现。也可以完成 Lab 01-T-01：顺序表选择题精练 与 Lab 01-T-02：单链表选择题精练，比较两种表示在访问、插入、删除和空间开销上的适用条件。