数组与链表

数组与链表是两个最基本的线性结构，几乎所有高级结构都由它们（或它们的变体）构成。它们代表两种内存组织哲学：连续内存与指针链。本章讲两者的取舍，以及它们如何与缓存层次（→ 存储层次与缓存）互动。

数组：连续内存

数组把元素连续存放，第 $i$ 个元素的地址是首地址加 $i \times \text{size}$——一次乘法一次加法，随机访问 $O(1)$。

操作	数组	动态数组	链表
按索引访问	$O(1)$	$O(1)$	$O(n)$
头部插入/删除	—	$O(n)$	$O(1)$
尾部插入	—	均摊 $O(1)$	$O(1)$（有尾指针）
已知位置插入/删除	$O(n)$	$O(n)$	$O(1)$（已持有节点）
缓存友好性	最好	好	差

动态数组（C++ vector、Python list、Java ArrayList）在满时分配更大的新数组（通常 1.5–2 倍）并整体拷贝。尾部追加的均摊成本 $O(1)$（证明见均摊分析），倍增因子在"扩容次数"与"空间浪费"之间折中。

数组的核心优势是缓存友好：顺序遍历就是把缓存行完整利用（→ 存储层次与缓存）。现代工程里，即使需要频繁中间插入，"数组 + 移位"也常常快过链表，因为移位的连续内存成本远低于指针追逐的缓存未命中。

链表：指针链

链表把元素分散存放，每个节点带指向后继（双向链表还有前驱）的指针：

• 插入/删除 $O(1)$——但前提是已持有该位置的节点指针；找到那个位置本身是 $O(n)$；
• 随机访问 $O(n)$：只能从头追逐指针；
• 缓存不友好：节点散布在堆上，每次跳转都可能未命中。

链表真正的用武之地：需要 $O(1)$ 拼接与摘除的场景（LRU 缓存的双向链表 + 哈希表、无锁队列）、元素地址稳定的场景（其他容器持有指向节点的指针）、以及外部排序与流式合并（归并排序在链表上无需额外空间）。

变体速览

• 环形缓冲区（ring buffer）：数组 + 首尾索引回绕，固定空间、无分配，是队列（内核网络包、音频、无锁队列）的标准实现。
• 双端队列（deque）：两端都能 $O(1)$ 增删，通常用分块数组实现，兼得数组的局部性。
• 跳表（skip list）：多级指针链，以概率实现 $O(\log n)$ 查找，是 Redis 有序集合与 LevelDB 的选择（→ 索引与 B+ 树）。

如何选择

判断顺序基本可以机械化：

1. 需要按索引访问？→ 数组类；
2. 增删集中在两端？→ 动态数组 / deque / 环形缓冲；
3. 需要 $O(1)$ 拼接摘除或地址稳定？→ 链表；
4. 其他情况默认动态数组——它的局部性优势在现代硬件上几乎是决定性的。

本章要点

• 数组随机访问 $O(1)$ 靠连续内存；动态数组尾部追加均摊 $O(1)$ 靠倍增
• 链表插入/删除 $O(1)$ 的前提是已持有节点指针；查找本身 $O(n)$
• 数组的缓存友好性在现代硬件上常是决定性优势；"数组+移位"常快过链表
• 链表的真正用武之地：$O(1)$ 拼接摘除、地址稳定、无锁结构