2.3 数组与链表：如何选择
读完数组与链表后，用这张决策页核对位置句柄、移动量、内存布局和失效规则。它是选择容器的工作表，不是脱离前提背复杂度的捷径。
先写清比较前提
数组
编号槽位可直接定位；保持连续下标时，插删要搬动后缀。
链表
节点靠链接维持顺序；拿到位置句柄后改线很快，按下标找位置要遍历。“数组插入 O(n)，链表插入 O(1)”只写了半句话。真正的选择取决于调用者手里有什么位置、要不要按索引读取、元素怎样分配，以及修改会让哪些引用失效。
操作成本总表
令数组或链表有 n 个元素，读取下标为 0 ≤ i < n，插入位置为 0 ≤ i ≤ n。数组采用固定倍数扩容；摊还追加从空表和固定初始容量计起。
| 操作 | 动态数组 | 单链表 | 双链表 |
|---|---|---|---|
按下标读取 i | Θ(1) | Θ(i + 1) | Θ(min(i, n - 1 - i) + 1)，需头尾句柄 |
| 无序按值查找，最坏情况 | Θ(n) | Θ(n) | Θ(n) |
| 头部插入 | 移动 n 个槽位，Θ(n) | 有头/哨兵时 Θ(1) | 有头/哨兵时 Θ(1) |
| 尾部追加 | 单次最坏 Θ(n)，摊还 Θ(1) | 有尾指针 Θ(1)；否则 Θ(n) | 有尾指针 Θ(1) |
下标 i 处插入 | 不扩容为 Θ(n-i+1)；扩容为 Θ(n) | 从头定位并改线 Θ(i+1) | 从较近一端定位并改线 Θ(min(i,n-i)+1) |
| 已知前驱后插入 | 数组没有等价稳定节点句柄 | Θ(1) | Θ(1) |
| 已知节点删除 | 移动后缀，最坏 Θ(n) | 还需前驱，通常不能直接删 | Θ(1) |
| 删除尾部 | 不移动后缀，通常 Θ(1) | 找前驱 Θ(n) | 有尾指针 Θ(1) |
| 完整遍历 | Θ(n) | Θ(n) | Θ(n) |
尾部删除按不触发缩容计算；若会缩容，需另计复制。单链表按下标定位一栏从头遍历，维护尾指针的实现可以对尾部追加走常数时间的专用路径。
表中忽略了元素析构、比较、复制和分配本身可能随数据增长的成本。若元素操作不是常数，应把它乘进相应次数。
“频繁中间插入”还缺一个问题
先问位置来自哪里。
调用者只有整数下标
链表需要走到该位置；若位置在长度同阶的中段，定位成本已经是 Θ(n)。数组定位是 Θ(1)，随后移动后缀。两者渐近总成本都可能为 Θ(n)，实际差异要看位置分布、元素移动成本、分配和缓存。
调用者长期持有有效节点或迭代器
链表可以在该位置 Θ(1) 改链接。数组插入会移动后缀，还可能重分配并让已有引用失效。这才是链表定点修改的典型优势。
插入后仍要频繁按索引读取
链表的中间索引访问要遍历，靠近已知首尾的位置则可能很快。一次修改省下的移动，可能被后续大量读取抵消。应该按完整工作负载算总成本，不能只挑一个操作。
表示与内存
| 维度 | 动态数组 | 链表 |
|---|---|---|
| 顺序来源 | 槽位下标 | next / previous 链接 |
| 预留空间 | 可能保留未使用 capacity | 每个节点按需分配 |
| 每元素额外信息 | 通常无节点链接 | 单链一条链接，双链两条 |
| 分配方式 | 一块可增长缓冲区 | 常见实现逐节点分配，也可用内存池 |
| 局部性 | 相邻槽位利于顺序访问 | 指针追逐产生依赖加载 |
| 元素表示 | 可能内联，也可能存引用 | 节点负载可能内联或引用对象 |
链表“按需分配”不等于更省内存。节点链接、对象头、分配器元数据和对齐可能超过动态数组的空余 capacity。具体字节数依赖语言、实现和元素类型，不能用一个通用比例回答。
引用、指针和迭代器失效
动态数组
要区分“指向槽位”与“指向槽位里的对象”。以 C++ vector 为例，重分配使元素引用、指针和迭代器失效；没有重分配的插入也会使插入点及其后的这些句柄失效。CPython list 扩容搬的是引用，外部保存的 Python 对象引用不会因此失效；整数下标虽然仍能使用，却可能指向另一个元素。
链表
在 C++ list 这类提供稳定节点句柄的接口中，插入保留已有元素的引用和迭代器，删除只使被删元素的句柄失效。不能把这条规则套到所有链表 API：Java LinkedList 的普通迭代器在容器被外部结构性修改后可能快速失败；Python 示例中被删除的节点对象也可能仍被外部引用，只是不能再作为原链表的位置。
稳定句柄是链表的一项真实能力，但外部长期保存节点也会增加生命周期管理难度。节点属于哪个容器、删除后谁负责停止使用，都应写进接口。
缓存与测量
数组槽位相邻，顺序扫描容易利用空间局部性。链表下一步地址依赖当前节点内容，处理器很难提前完成整条加载链。节点分配还可能增加对象和分配器开销。
这不产生固定“快 10–100 倍”的结论。元素尺寸、处理器、缓存、分配器、运行时和访问模式都会改变结果。两种遍历同为 Θ(n)，复杂度说明增长相同，基准测试负责比较目标环境里的常数。
需要深入硬件原因时，转到 Vol. 3：缓存与存储器层次 和 性能工程。
常见工作负载怎么选
| 主要需求 | 先考虑 | 还要确认 |
|---|---|---|
| 高频按索引读取 | 动态数组 | 是否需要保持排序、是否频繁头插 |
| 顺序批处理 | 动态数组或紧凑数值数组 | 元素是值还是引用，布局是否真的连续 |
| 栈，末尾进出 | 动态数组 | API 是否提供稳定尾操作 |
| 队列或双端队列 | 专用 deque | 不要用数组头部反复移动，也不必手写链表 |
| 持有节点句柄并频繁定点插删 | 链表 | 节点所有权、分配成本和读取模式 |
| 需要稳定元素地址/迭代器 | 链表或其他稳定容器 | 查具体语言的失效合同 |
| 固定长度、紧凑值 | 固定数组 | 长度是否编译期/创建时已知 |
| 按下标修改为主，偶尔插删 | 动态数组 | 用代表负载测量，不因一次插入改结构 |
“不确定就用动态数组”可以当起点，因为工具链和 API 通常成熟；它不是证明。数据规模、更新方式或稳定句柄要求出现后，要重新检查。
语言容器映射
Python
| 任务 | 容器 | 说明 |
|---|---|---|
| 通用索引序列 | list | CPython 中是动态引用数组 |
| 两端进出 | collections.deque | 两端追加/弹出为设计目标 |
| 同类基本数值 | array.array | 紧凑可变序列，不是固定数组 |
| 教学节点算法 | 手写 ListNode | 标准库无通用链表类型 |
Python 官方的 list/deque 教程 明确指出，列表头部插删要移动其他元素，队列应考虑 deque。
Java 17+
| 任务 | 容器 | 说明 |
|---|---|---|
| 固定长度 | T[] | 原生数组 |
| 通用 List | ArrayList<E> | 常数索引、摊还常数追加 |
| 双端队列/栈 | ArrayDeque<E> | 不接受 null |
| 双链 List/Deque | LinkedList<E> | 两端快，中间索引需定位 |
ArrayList 不公开固定扩容因子。LinkedList 的 add(0, e) 位于已知首端，不应写成完整线性遍历；任意中间索引仍需定位。
C++
| 任务 | 容器 | 说明 |
|---|---|---|
| 固定长度 | std::array<T, N> | 长度是类型的一部分 |
| 通用连续序列 | std::vector<T> | T 非 bool 时元素连续、可增长 |
| 双端序列 | std::deque<T> | 分段存储，不保证整体连续 |
| 单链 | std::forward_list<T> | 前向迭代 |
| 双链 | std::list<T> | 持有迭代器时定点插删 |
C++ 标准草案的 vector 修改器 和 list 给出重分配、失效与定点操作条件。reserve(n) 保证后续插入在新大小不超过 capacity 时不触发重分配，不会改变 size。
决策步骤
- 写出主要操作及比例，例如 90% 索引读取、10% 末尾追加。
- 写出调用者拥有的位置：整数下标、节点句柄、迭代器，还是只有值。
- 加上元素移动、比较、分配和输出成本。
- 检查地址/迭代器稳定性和所有权要求。
- 先选语义正确且简单的容器，再用代表数据做基准。
快速纠错
| 说法 | 修正 |
|---|---|
链表插入永远 O(1) | 已知正确前驱/节点时才是 Θ(1) |
数组中间插入一律移动 n 个 | 下标 i 处移动 n-i 个 |
| 链表一定比数组省空间 | 节点链接与分配开销可能更大 |
Python array.array 是静态数组 | 它是可变长同类数值序列 |
| Python 二维列表按行连续 | 它是列表引用到多个行对象 |
| 循环链表就是 ring buffer | ring buffer 通常由数组和首尾索引实现 |
Java LinkedList.add(0, e) 是线性 | 首端已知；中间索引才需要遍历 |
两种 Θ(n) 遍历实际一样快 | 渐近阶相同，局部性和分配影响常数 |
用完整负载做一次选择
先写操作比例，例如 90% 索引读取、9% 尾部追加、1% 中间插入；再说明调用者持有整数下标、节点句柄还是迭代器。若每次插入前仍要按下标定位，链表的总成本不会因为链接修改是 Θ(1) 就自动变成常数。
然后补上元素移动、节点分配、地址或迭代器失效和缓存局部性。先选语义正确且简单的容器，再用代表性数据测量；不要把相同的 Θ(n) 当成相同的实际时间，也不要给缓存优势编一个固定倍数。
返回路线
继续学习：访问顺序成为接口
数组和链表解决“数据怎样放”。下一章的栈、队列与双端队列进一步限制“下一次能从哪里取”，让 LIFO、FIFO 和两端访问成为接口合同。