一、起源:数据结构要解决的第一个问题
一组同类型元素如何组织,是数据结构要回答的第一个问题。内存提供的原语只有两件事:按地址读写一个字节,以及按地址申请与释放一段区域。内存本身不理解「第 3 个元素」这类位置语义,位置必须由组织方式自己建立。围绕这件事,只有两种基本选择。
连续存储:把元素紧挨着放,用一个起始地址加上偏移量定位任意元素。
分散存储:把元素各自独立放置,用额外的记录保存元素之间的联系。
两种方式在「读取」与「修改」上的代价恰好相反。
| 操作 | 连续存储 | 分散存储 |
|---|---|---|
| 定位第 i 个元素 | 地址算术一次完成,与 i 无关 | 必须从起点沿联系走 i 步 |
| 在中间插入元素 | 插入点之后的元素整体搬移 | 修改插入点附近的联系 |
| 在中间删除元素 | 删除点之后的元素整体搬移 | 修改删除点附近的联系 |
| 尾部追加 | 有空间则直接写入 | 修改尾部附近的联系 |
| 存储额外开销 | 几乎没有 | 每个元素都要保存联系 |
这就构成了第一个根本矛盾:「按位置快速定位」与「在任意位置快速修改」不能由同一种布局同时满足。定位快要求元素地址可以由位置直接算出,也就是地址必须连续;修改快要求修改动作只影响局部,也就是元素不能被整体搬移。两者互斥。
矛盾无法消除,只能选择把代价放在哪一侧,因此线性表在实践中长期并存两种存储实现。栈、队列、哈希表、树、图等结构,都是在二者之上按访问模式做出的进一步组合。
从抽象数据类型(ADT)的视角看,线性表是规范层:定义数据对象、数据元素之间的关系以及允许的操作;数组与链表是存储层:为同一组操作提供代价不同的实现。同一份接口、不同的代价,是理解 ADT 与实现分离的具体入口,见 抽象数据类型(ADT)。
二、原理
1. 连续存储
1.1 地址计算与随机访问
连续存储把「第 i 个元素在哪」变成一个算术问题。
一维数组: addr(i) = base + i × sizeof(E)
二维数组(m 行 n 列,行主序):
addr(i, j) = base + (i × n + j) × sizeof(E)
地址计算是「一次乘加」,指令数与 i 无关。这就是随机访问 O(1) 的全部来源:不管访问第 0 个还是第 999999 个元素,定位开销相同,并且不需要先经过前面的元素。
「随机访问」描述的是定位方式,不是遍历:它表示下标任意、访问顺序无关。若程序本身按下标递增访问,随机访问的能力就退化为顺序遍历,叠加缓存局部性后效率更高。
需要注意 O(1) 的边界。它只覆盖「定位到槽位」这一步。若数组存放的是引用,取到引用之后访问对象的字段仍是一次内存访问,这次访问可能落到堆中任意位置并造成缓存未命中;若存放的是基本类型,取出的就是值本身。语言层面的差异见 1.4 节与第 5 节。
1.2 插入与删除的搬移代价
连续存储要维持「元素紧挨着」这一不变量,因此中间位置的插入与删除必须搬移后续元素。
// 在 index 处插入:index 及其之后的元素整体后移一个槽位
System.arraycopy(data, index, data, index + 1, size - index);
data[index] = e;
size++;
搬移量由位置决定。
| 操作位置 | 搬移的元素个数 | 复杂度 |
|---|---|---|
| 头部插入 / 删除 | n | O(n) |
| 中间插入 / 删除 | 平均 n/2 | O(n) |
| 尾部追加 | 0(容量足够时) | O(1) |
| 尾部删除 | 0 | O(1) |
搬移本身是连续内存的顺序复制,单次复制成本很低,因此在小数据量下数组的插入删除并不比链表慢。代价的真正来源是搬移量随元素数线性增长:对 n 个元素逐个做头部插入,总搬移量约为 n²/2,元素量翻倍则耗时变为四倍。
1.3 边界与越界
数组的可寻址范围是 [0, length - 1]。当引入容量概念后(见第 2 小节),物理长度往往大于有效元素个数,此时逻辑上的有效范围由长度字段而非数组长度决定。
不同语言对越界的处理差异很大。
- Java、C#:运行时插入边界检查,越界抛出
ArrayIndexOutOfBoundsException/IndexOutOfRangeException。异常在越界的那一行抛出,错误位置与失败位置一致。 - C、C++:不做检查,越界读写属于未定义行为。读取可能拿到相邻对象的脏数据;写入可能破坏相邻对象或分配器的元数据,而故障往往在后续某次
free或分配时才以不相关的位置崩溃。这类问题的特征是错误现场与根因分离。 - Python:索引越界抛
IndexError;额外支持负下标(从尾部计数)与切片,负下标由解释器转换成非负下标后寻址,底层仍是普通数组语义。
边界检查的成本是一个分支,在分支预测友好的循环中几乎不产生额外开销。这是解释性与内存安全语言用少量开销换取内存安全的典型取舍,也是「数组越界是最常见的漏洞类型之一」这一现象只在无检查语言中成立的原因。
1.4 多维数组的行主序与列主序
多维数组在内存中仍是一维的,映射方式有两种。
行主序(row-major):先排完一行再排下一行
addr(i, j) = base + (i × n + j) × sizeof(E)
使用者:C / C++ / Java / Go / Python(numpy 默认)
列主序(column-major):先排完一列再排下一列
addr(i, j) = base + (j × m + i) × sizeof(E)
使用者:Fortran / MATLAB / R / Julia
存储顺序决定了哪一种遍历顺序是缓存友好的。
int[][] a = new int[4096][4096];
long sum = 0;
// 行优先遍历:地址连续递增,局部性好
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[i].length; j++) {
sum += a[i][j];
}
}
// 列优先遍历:每次访问跨越一整行的距离
for (int j = 0; j < a[0].length; j++) {
for (int i = 0; i < a.length; i++) {
sum += a[i][j];
}
}
两段代码的元素访问次数相同,复杂度都是 O(n²),但实际耗时常有数倍差距:行优先遍历每一步都落在同一个缓存行内,列优先遍历几乎每一步都要换一条缓存行。缓存行与预取的机制见第 5 节。
语言层面还有一个易被忽略的差别:Java 的二维数组是「数组的数组」,int[][] 本身是一个引用数组,每个元素指向各自独立的一维数组,行与行之间不保证地址连续。因此行优先遍历在行内仍然连续(局部性良好),列优先遍历则每次跳到另一个一维数组,局部性更差。Python 的嵌套列表同理,而且每个元素都是独立的对象,开销进一步放大;数值计算场景应使用连续内存容器。
2. 动态数组
2.1 容量与长度的分离
定长数组有两个无法自行解决的问题:装满之后无法继续追加;数组的 length 无法区分「没有元素」与「元素值恰好等于零值」。动态数组在数组之上增加两个字段来同时解决这两点。
动态数组的内部状态
┌──────────────────────────────────────────────┐
│ data ──▶ [ e0 ][ e1 ][ e2 ][ ][ ][ ] │ 底层数组,长度即容量
│ │
│ size = 3 │ 有效元素个数
└──────────────────────────────────────────────┘
可访问下标范围 [0, size-1],而非 [0, data.length-1]
- 容量(capacity)是底层数组的物理长度,决定还能写入多少元素。
- 长度(size)是当前有效元素的个数,是对外暴露的语义长度。
追加元素 = 在 size 位置写入并自增;当 size == capacity 时先扩容再写入。删除元素 = 搬移后续元素并自减 size。长度可变与空槽位语义由此同时获得。
具体实现(底层数组字段、扩容方法的代码结构、延迟分配策略)见 Java 集合框架实现原理 中 ArrayList 的部分,本节讨论与语言无关的通用原理。
2.2 扩容策略与倍数选择
容量不足时,只有两种增长方式。
固定增量:每次扩容增加 k 个槽位(k 为常数)。
倍数增长:每次把容量扩为原来的 c 倍(c > 1 的常数)。
两者的总代价量级不同。
最终需要容纳 n 个元素。
固定增量 k:
扩容次数 ≈ n / k
累计搬移量 ≈ k + 2k + 3k + ... + n = n² / (2k)
→ 每次追加的均摊代价 O(n)
倍数增长 c:
各次扩容的搬移量之和 = n/c + n/c² + n/c³ + ...
< n × 1/(c − 1) (等比级数求和)
c = 2 → 累计搬移量 < n
c = 1.5 → 累计搬移量 < 2n
→ 每次追加的均摊代价 O(1)
固定增量失败的原因在于扩容频率不随规模下降:元素越多,扩容越频繁,每次搬移的量还越大,两项叠加得到平方量级。倍数增长让「需要搬移的量」按几何级数递减,总和被常数上界截断。
倍数取多少,则需要在三个方向之间权衡。
| 维度 | 倍数越大(如 2 倍) | 倍数越小(如 1.5 倍) |
|---|---|---|
| 扩容次数 | 少(约 log₂n 次) | 多(约 log₁.₅n 次) |
| 累计搬移量 | 小(< n) | 大(< 2n) |
| 单次扩容的内存峰值 | 高(旧 1 份 + 新 2 份 = 3 倍) | 低(旧 1 份 + 新 1.5 份 = 2.5 倍) |
| 空闲空间回收难度 | 高 | 低 |
峰值一列容易推导:扩容前容量为 c,新容量为 c×g,复制期间两者同时存在,占用合计 c × (1 + g)。g = 2 时为 3c,g = 1.5 时为 2.5c。
「空闲空间回收难度」的差别来自分配器的复用能力。以 2 倍增长为例,第 k 次扩容时申请的新块是旧块的 2 倍,而此前所有释放块的大小之和(约等于旧块大小减一)小于新块,通用分配器无法用这些空闲块拼出所需空间,只能向操作系统申请新的地址区域,长期运行会加剧地址空间碎片;1.5 倍增长时,历史释放块的累积量增长更快,更容易满足后续申请,因此部分实现选择 1.5 倍而非 2 倍。
具体实现的取值各不相同,且都属于实现细节、不是接口约定:
| 实现 | 扩容倍数 |
|---|---|
Java ArrayList | 1.5 倍(不足时直接扩到所需容量) |
C++ std::vector(libstdc++ / libc++) | 常见 2 倍 |
C++ std::vector(MSVC) | 1.5 倍 |
Go slice | 小容量翻倍,容量较大时按约 1.25 倍增长 |
2.3 扩容时的复制与内存峰值
一次扩容包含三个动作:申请一块更大的数组、把旧数组中的元素复制过去、把内部引用指向新数组(旧数组变为不可达,等待回收)。
复制是单次操作的最坏情况:它是 O(n),与后续的所有操作无关。而峰值内存是更容易被忽略的后果——复制期间旧数组与新数组同时驻留,占用约为原容量的 2.5 倍(1.5 倍增长时)。对已经占用数百 MB 的动态数组,一次追加就可能把内存需求瞬间抬高到原来的两倍以上。
这个峰值有两层影响:
- GC 层面:额外的数组分配会推动新生代填充、晋升加快,可能触发一次 Full GC,在并发回收能力不足时表现为长停顿。
- 主机层面:堆上的数组最终以页的形式映射为物理内存并计入进程 RSS,在容器内存限额下,RSS 触顶会导致进程被内核终止,而应用中可能没有任何 Java 异常。堆内存构成、页的映射方式与容器内存判定的关系见 JVM 内存结构与垃圾回收。
消除峰值的手段是让扩容不发生或少发生:已知规模时在构造时预设容量;无法精确估计时,在批量追加前用 ensureCapacity 一次性扩到足够容量,把多次扩容合并为一次;规模超出单机内存时改为分片处理或流式处理。
2.4 摊还分析与最坏情况
「追加元素是均摊 O(1)」与「追加元素是 O(1)」是两个不同的结论,前者才是准确的表述。
摊还分析的含义是:连续 n 次操作的总代价是 O(n),平均到每次是 O(1);它不约束单次操作的代价,某一特定次追加仍可能触发 O(n) 的复制。两种常用推导方式:
- 聚合分析:2 倍增长下,一次复制 n 个元素的操作,需要之前约 n/2 次「不扩容的追加」来分摊,因此平均每次追加的复制量小于 1。
- 势能法:定义势能
Φ = 2 × size − capacity,不扩容的追加使 Φ 增加 2,扩容前的势能积累恰好等于本次复制代价,总势能始终非负,由此得到摊还上界为常数。
摊还与最坏情况的区分在工程上有直接意义。对吞吐量为主的批处理,均摊值决定总耗时,单次抖动无关紧要;对延迟敏感的服务,一次 O(n) 复制可能直接超出上游超时阈值,此时需要关注的是最坏情况。降低最坏情况的手段包括预设容量、分批处理、把大数组的构建挪到请求路径之外。
同类结构都有这个性质:哈希表在冲突可控时是均摊 O(1)、最坏 O(n);均摊界通常来自「偶发的高代价操作」,而不是「每次操作都不贵」。
2.5 缩容策略
删除大量元素之后,容量可能远大于有效元素数,底层数组中大部分槽位是空的,但整块内存仍被占用。理论上可以在删除时缩容,实践中不能简单地按删除触发。
原因是缩容同样需要一次 O(n) 复制。如果在「元素数少于容量」时就缩容,那么容量会在扩容与缩容之间反复摆动:缩容到容量的一半后,再追加几个元素又触发扩容,每次摆动都付一次 O(n) 复制代价,这种抖动称为 thrashing。
通行做法是引入滞后阈值:只有当元素数降到容量的一个较低比例(常见为 1/4)时,才把容量缩减到一半。扩容阈值(元素数等于容量)与缩容阈值(元素数等于容量的 1/4)之间留出的区间,使容量变化需要跨过一段距离,消除了边界抖动。
各实现的默认行为差异较大:
| 实现 | 缩容行为 |
|---|---|
Java ArrayList | 不自动缩容,只能显式调用 trimToSize() |
C++ std::vector | shrink_to_fit() 为非强制请求,实现可以忽略 |
Python list | 删除大量元素后会自动收缩 |
Go slice | 不缩容,重新分配需显式操作 |
是否值得缩容取决于后续是否还会增长:若数据规模会再次上升,缩容省下的内存在下一次扩容时会被重新占用,还要多付一次复制代价;长期不再增长的容器才值得缩容。
3. 链式存储
3.1 节点与指针
链式存储把元素放进独立分配的节点,节点之间用引用(指针)连接。
class Node<E> {
E item; // 数据域
Node<E> next; // 指针域:指向后继节点
}
元素的「位置」不再由地址算术定义,而由指针关系定义:第 i 个元素是从头节点沿 next 走 i 步到达的节点。链表的入口是头引用 head;尾部节点的 next 为空(普通单链表),或指回头部(循环链表)。
从存储结构的角度看,链表把「关系」显式化成数据:每个节点都要额外保存指向后继的引用,关系本身既消耗存储,也消耗访问时间。换来的是插入与删除只需要修改少量指针,不必搬移元素。
3.2 头插与尾插
// 头插:O(1),且不需要任何遍历
newNode.next = head;
head = newNode;
// 尾插:维护尾引用时为 O(1)
if (tail == null) {
head = tail = newNode;
} else {
tail.next = newNode;
tail = newNode;
}
- 头插不依赖链表长度,代价恒定,但它改变了元素的相对顺序——若链表代表一个有序列,头插会得到逆序结果。
- 尾插若不维护尾引用,必须先遍历到尾部,单次代价 O(n)。
- 头尾操作都是常数时间,因此链表天然适合实现受限线性表:栈用头插头删,队列用尾插头删。
3.3 单链表、双向链表、循环链表
| 结构 | 节点字段 | 反向遍历 | 删除已知节点 | 尾部操作 | 典型用途 |
|---|---|---|---|---|---|
| 单链表 | item + next | 不支持 | 需先找前驱,O(n) | 需尾引用 | 简单链式结构、栈 |
| 双向链表 | item + next + prev | 支持 | O(1) | 头尾均 O(1) | 队列、双端队列、LRU |
| 单向循环链表 | item + next(尾指向头) | 不支持 | 需先找前驱,O(n) | 头尾互通 | 轮询调度、环形缓冲 |
| 双向循环链表 | item + next + prev(首尾相接) | 支持 | O(1) | 头尾均 O(1) | 无需判空的链表实现 |
循环链表的特点是「没有末端」:从任意节点出发都能遍历到全部节点,不需要在每步判断 null。代价是遍历必须依赖外部条件终止(计数、或「回到起点」),否则会无限循环。
3.4 带头节点(哨兵)的作用
不使用哨兵时,插入与删除都必须判断「操作位置是不是第一个节点」,因为只有删除或插入第一个节点才需要修改 head。
// 无哨兵:删除头节点需要单独处理
if (target == head) {
head = head.next;
} else {
Node prev = findPrev(target); // 需要 O(n) 查找前驱
prev.next = target.next;
}
引入一个不存放有效数据的头节点(哨兵)之后,每个节点的前驱都存在,head 引用本身不再变化,删除与插入统一为「修改前驱的 next」。
// 有哨兵:删除任意节点走同一条代码路径
Node prev = findPrev(target); // 哨兵本身也是合法前驱
prev.next = target.next;
哨兵的收益集中在三点:
- 消除头节点特判,插入与删除只有一个代码路径,出错面随之减少。
- 空表与非空表结构一致,不需要为「链表为空」单独写分支。
- 入口引用稳定,函数返回真实头节点的方式统一为
dummy.next,不必区分「是否修改了head」。
在双向链表中,常见做法是配置首尾两个哨兵并使其首尾相接形成哨兵环:空表时两个哨兵互指,插入与删除完全不需要判空。
哨兵的代价是一个额外的节点,以及一次间接访问(逻辑上的第 i 个元素是哨兵之后的第 i 个)。
3.5 查找 O(n) 的本质
数组能按下标定位,是因为地址可以由下标算出;链表不能,原因是地址信息存放在数据结构内部。
- 节点由分配器决定物理位置,彼此之间没有任何地址规律。
- 第 i 个节点的地址只存在于第 i−1 个节点的
next字段中。 - 要到达第 i 个节点,必须依次读取第 0 到第 i−1 个节点的
next。
这不是实现效率问题,而是分散存储的固有性质:定位所需的信息本身是分散的,无法用一次算术替代一次遍历。
由此得到一个在实践中极易误判的结论:链表的「插入删除 O(1)」以已经持有目标位置(节点或其前驱)为前提。通过下标执行的插入删除,定位阶段依然是 O(n),因此「按位置插入」的总代价与数组同级,且常数更差(见第 5 节)。链表真正不可替代的场景是:操作位置由遍历过程本身给出(如迭代器删除当前节点),或位置固定在两端。
4. 链表变体
4.1 双向链表的优势
- 已知节点时删除为 O(1)。单链表删除节点 x 需要 x 的前驱,只能 O(n) 查找;一个常见的替代技巧是把后继节点的数据复制到 x,再删除后继——它可以做到 O(1),但尾节点不适用,且外部持有的 x 引用在删除后仍指向一个「内容已被替换」的节点,语义上并不等价。双向链表直接用
prev换来了真正的 O(1) 删除。 - 支持反向遍历与回退。需要从当前位置向前查找的算法可以直接利用
prev,不必回到头部重新定位。典型场景是把被访问的节点移动到表头(LRU 的命中处理)、链表的插入排序、双向迭代器。 - 代价:每个节点多一个引用(64 位 JVM 开启压缩指针时 4 字节,关闭时 8 字节);插入与删除需要同时维护两个方向,是链表代码中最常见的错误来源。
4.2 静态链表与跳表
静态链表用数组模拟链表:节点存放在数组中,指针域保存的是后继节点的下标而不是地址。
下标: 0 1 2 3
item: A B C D
next: 2 3 -1 1
head = 0
从 head 出发:A(0) → C(2) → -1,访问结束
空闲块也可用同样的方式串成一条空闲链表,插入时从中取节点。
静态链表把「链接关系」从语言指针中剥离出来,变成普通数据,因此适用于:不支持指针的语言中实现链式结构;需要把链接关系持久化或跨进程传输的场景;节点集中分配因而缓存局部性优于动态链表的场景。代价是容量固定(需预留空间或实现空闲块管理),且插入删除要手工维护空闲链表。
跳表可以看作在有序链表的链接关系上增加多层索引:底层是完整的有序链表,上层是由底层节点抽样得到的稀疏索引,查找时从最上层开始向右移动,无法前进则下降一层。它把有序链表的查找从 O(n) 降到期望 O(log n)。链表无法二分的根本原因是无法按下标定位;跳表用额外的索引节点把「下一步可以跳多远」的信息外置,绕开了这个限制。有序表的查找结构(平衡树、跳表、B 树)属于后续内容,其中跳表的随机层数设计、节点表示与范围查询见 跳表,平衡二叉搜索树的结构与退化成因见 二叉树与二叉搜索树,此处只说明它与链表的派生关系。
4.3 块状链表与链式数组
块状链表(block linked list,也称 unrolled linked list)是数组与链表的混合结构:每个节点持有一个小块数组,块内元素连续存储,块之间用指针连接。
head → [ 3 7 11 19 ] → [ 25 30 44 ] → [ 51 63 88 90 ] → null
块内连续存储 块内连续存储 块内连续存储
块容量 B=4 块容量 B=3 块容量 B=4
代价分析(设元素总数 n,块容量 B):
| 操作 | 过程 | 代价 |
|---|---|---|
| 按下标定位 | 沿块链找到目标块(约 n/B 步),再在块内下标寻址(B 步) | O(n/B + B),B 取 √n 时约 O(√n) |
| 块内插入删除 | 块内数组搬移 | O(B) |
| 结构维护 | 块溢出时分裂,块过空时合并 | 均摊 O(√n) 量级 |
| 内存开销 | 块间指针 + 块内空闲槽位 | 略高于纯数组 |
与纯数组相比,中间插入从 O(n) 降到 O(√n);与纯链表相比,块内连续存储恢复了缓存局部性,遍历不再是指针追逐。代价是实现复杂度显著高于数组与链表,且块容量需要权衡:B 过大退化为数组,B 过小退化为链表。
同族结构共享同一思路——块内连续 + 块间链接:rope(用平衡树组织文本块,用于超长字符串的编辑)、分块数组(区间修改与区间查询)、B+ 树(把块状组织提升为多路平衡树)。它们都在「定位」与「搬移」之间选取折中点。
5. 内存与缓存
5.1 数组的局部性与预取
CPU 与主存之间以缓存行为单位传输数据(x86 常见为 64 字节),一次未命中会把整行载入缓存。一个缓存行可容纳 16 个 int,或 8 个 64 位引用(开启压缩指针时为 16 个引用)。
由此产生两个效果:
- 顺序遍历的平均访存次数远小于元素个数。遍历 16 个
int只需要一次内存访问,其余都命中缓存。 - 硬件预取器可以识别顺序访问流。当访问地址按固定步长递增时,预取器会提前把后续缓存行装入缓存,使遍历吞吐接近内存带宽上限。
同样的思路也出现在操作系统层:内核的预读(readahead)在检测到顺序访问时提前加载后续页,在随机访问时关闭预读以避免无效 IO。文件层顺序访问与随机访问的性能差异、预读的自适应窗口与观测手段见 linux:页缓存与 IO 性能。
结论是:数组的优势不只是 O(1) 定位,还包括「访问模式可预测」——这是编译器优化与硬件预取能够生效的前提。
5.2 链表的指针跳转与缓存不命中
链表节点的地址由分配器决定,逻辑上相邻的节点在物理内存上通常相距很远。遍历链表时每次读取 node.next 都需要先完成上一次访问(下一个地址依赖当前节点内容),无法提前预取。这种「走一步才知道下一步在哪」的访问模式称为指针追逐(pointer chasing)。
后果是每一步都可能是一次缓存未命中,节点数量大时还可能引发 TLB 未命中,代价进一步提高。因此在元素数量相同的情况下,链表的顺序遍历耗时通常是数组的数倍到数十倍(具体差距与元素大小、节点分布、缓存容量有关),而两者的复杂度记号完全相同。
5.3 节点开销
以 64 位 JVM 开启压缩指针为例(引用 4 字节、对象头 12 字节、对象大小按 8 字节对齐):
| 结构 | 每个元素的容器结构开销 | 100 万元素的结构占用 |
|---|---|---|
int[] | 4 字节 | 约 4 MB |
| 引用数组 | 4 字节(引用本身) | 约 4 MB(不含被引用对象) |
| 单链表节点 | 12(对象头)+ 4(数据引用)+ 4(next)= 20,对齐后 24 字节 | 约 24 MB |
| 双向链表节点 | 12(对象头)+ 4 + 4 + 4 = 24 字节 | 约 24 MB |
| 静态链表(数组) | 4(数据)+ 4(下标)= 8 字节 | 约 8 MB |
有两个值得留意的细节:
- 在本例这一配置下,单链表的 20 字节与双向链表的 24 字节对齐后都是 24 字节,多出的
prev指针被对齐填充「吸收」了。若数据域是基本类型、或关闭压缩指针使引用变为 8 字节,两者的差距会显现出来。 - 对象头构成、字段重排规则与指针压缩的开关条件(堆是否超过约 32GB)见 JVM 内存结构与垃圾回收 的对象内存布局部分。关闭压缩指针后每个引用占 8 字节,节点开销进一步上升。
除对象本身之外,还有分配器层面的开销:C/C++ 中每个 malloc 的块都带有分配器元数据(典型 8~16 字节)与对齐填充,逐节点分配会显著放大实际占用并加剧内存碎片;数组一次性申请大块,元数据开销可以忽略。在带 GC 的语言中,这一项转化为每个对象都需要被标记与追踪的成本。
语言差异同样明显:Python 中每个对象都是带引用计数与类型指针的 PyObject,自建链表节点的每元素开销在数十字节量级;list 内部是 PyObject* 数组,容器结构开销与数组同级。
最后,这些节点最终都要映射为物理页并计入进程 RSS,在容器内存限额下,大规模链表会更快触顶。堆内存与主机内存口径的对应关系见 JVM 内存结构与垃圾回收。
5.4 为什么复杂度相同而实测差异明显
复杂度记号统计的是「基本操作次数」,并把每一次访问视为等代价。实际代价取决于这次访问是否命中缓存、是否触发缺页、是否需要同步。三条具体差距:
- 同为 O(n):数组是连续内存的顺序扫描,链表是跨随机地址的指针追逐,常数因子相差一个数量级以上。
- 同为 O(n) 的插入删除:数组的搬移由运行时提供的批量复制原语完成,可按机器字或向量指令推进;链表是「O(n) 定位 + 两次指针赋值」。元素数量不大时,数组的搬移常常比链表的定位更快。
- 同为 O(1) 的尾部操作:动态数组的尾部追加在多数情况下只是写入并自增,仅在扩容时为 O(n);链表的尾插需要额外维护尾引用,否则退化为 O(n)。
所以复杂度分析用于判断增长趋势与可行性,不足以决定实现选择。选型需要结合访问模式、数据规模与实际测量。
6. 常见算法问题
6.1 反转链表
// 迭代:三指针,时间 O(n),额外空间 O(1)
Node reverse(Node head) {
Node prev = null;
Node curr = head;
while (curr != null) {
Node next = curr.next; // 先保存后继,避免改写后丢失
curr.next = prev; // 反向链接
prev = curr; // prev 前移
curr = next; // curr 前移
}
return prev; // 循环结束时 prev 指向新的头节点
}
- 关键顺序是「先保存
next,再改写curr.next」。颠倒顺序会丢失尚未处理的后半段。 - 递归写法(先反转
head.next得到已反转的后半段,再把head接到末尾)代码更短,但调用栈深度为 n,长链表会抛StackOverflowError。
6.2 环形检测与环入口
slow 每次前进 1 步,fast 每次前进 2 步。
若 fast 到达末尾之前与 slow 相遇,则存在环;否则无环。
相遇后判定入口:一个指针回到 head,另一个停在相遇点,
两者同速前进,再次相遇的位置即环的入口。
原理:设头到入口的距离为 a,入口到相遇点的距离为 b,相遇点到入口的距离为 c。相遇时 slow 走了 a + b,fast 走了 a + b + n(b + c),且 fast 的路程是 slow 的两倍。化简得 a = c + (n − 1)(b + c),即「从 head 出发走 a 步」与「从相遇点出发走 a 步」会同时抵达入口。
复杂度为 O(n) 时间、O(1) 额外空间。用哈希表记录访问过的节点同样可以判环并找到入口,但需要 O(n) 额外空间。
6.3 找中点
快慢指针:fast 每次两步,slow 每次一步,fast 到达末尾时 slow 位于中点,一次遍历完成,无需事先知道长度。
偶数长度存在两个「中点」(前一个与后一个),取哪一个由循环条件与初始位置决定。这是常见的 off-by-one 来源,应由具体用途确定:归并排序需要把链表切成两段时取后半段作为第二段,而判断回文时两个中点都可以作为起点。
6.4 合并两个有序链表
// 哨兵头 + 双指针:时间 O(m + n),空间 O(1)(复用原节点重新链接)
Node merge(Node a, Node b) {
Node dummy = new Node(); // 哨兵,避免「结果为空」的特判
Node tail = dummy;
while (a != null && b != null) {
if (a.value <= b.value) {
tail.next = a;
a = a.next;
} else {
tail.next = b;
b = b.next;
}
tail = tail.next;
}
tail.next = (a != null) ? a : b; // 剩余部分整段接上
return dummy.next;
}
- 哨兵消除了「结果链表为空」与「首个节点来自哪条链」的分支。
- 剩余部分可以从当前节点起整段接上,不需要逐节点复制,这是有序链表合并能做到 O(1) 额外空间的原因。
- 若不允许修改原链表,需要先复制节点,空间退化为 O(m + n)。
6.5 删除倒数第 N 个节点
// 固定间距双指针:一趟扫描,慢指针最终停在待删节点的前驱
Node dummy = new Node();
dummy.next = head; // 哨兵,覆盖「删除头节点」的情况
Node fast = dummy, slow = dummy;
for (int i = 0; i < n; i++) {
fast = fast.next; // 需保证 n 不超过链表长度
}
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next; // 删除
return dummy.next;
快慢指针之间保持固定的前驱距离,因此快指针到达末尾时慢指针恰好指向待删节点的前驱。与「先求长度再走 length − n 步」的两趟做法相比,只需一次遍历,且不需要单独处理删除头节点。
6.6 两个链表的相交判定
相交的判定标准是节点相同(引用相同),而不是节点值相同。由于每个节点只有一个 next,两条链表一旦在某个节点相交,之后的路径完全重合,整体形状必然是「Y」而不是「X」。
- 长度对齐法:分别求两条链表的长度,长链先前进长度差步,然后同步前进,首次相等的节点即交点。O(m + n) 时间,O(1) 空间。
- 双指针互换法:两个指针同时从各自头节点出发,走到末尾后切换到另一条链表的头节点继续前进,两者总步数相同(m + n),第二次相遇即为交点。代码更短,同样 O(1) 空间。
反例与边界:只比较节点值会把「值相等但属于不同节点」的情况误判为相交;两条链表长度不同且无交点时,两个指针会在走完全程后同时为空,此时返回空即可;若其中一条链表存在环,上述两种方法都不成立,需要先判环并统一环的入口。
6.7 汇总
| 问题 | 主要方法 | 时间 | 额外空间 | 易错点 |
|---|---|---|---|---|
| 反转链表 | 三指针迭代 / 递归 | O(n) | O(1) / O(n) | 先保存 next 再改写 |
| 环形检测 | 快慢指针 | O(n) | O(1) | 循环条件需同时检查 fast 与 fast.next |
| 找中点 | 快慢指针 | O(n) | O(1) | 偶数长度的中点定义 |
| 合并有序链表 | 双指针 + 哨兵 | O(m+n) | O(1)(原地)/ O(m+n)(复制) | 剩余段整段接上 |
| 删除倒数第 N 个 | 固定间距双指针 + 哨兵 | O(n) | O(1) | 头节点需要哨兵;N 的合法性 |
| 相交判定 | 长度对齐法 / 双指针互换法 | O(m+n) | O(1) | 比较节点而非值;有环时不适用 |
三、实现
1. 数组实现要点
1.1 扩容与缩容的代码结构
public class DynamicArray<E> {
private Object[] data;
private int size;
public DynamicArray(int initialCapacity) {
data = new Object[Math.max(initialCapacity, 0)];
size = 0;
}
public void add(E e) {
ensureCapacity(size + 1);
data[size++] = e;
}
public void add(int index, E e) {
rangeCheckForAdd(index);
ensureCapacity(size + 1);
System.arraycopy(data, index, data, index + 1, size - index);
data[index] = e;
size++;
}
@SuppressWarnings("unchecked")
public E remove(int index) {
rangeCheck(index);
E old = (E) data[index];
int moved = size - index - 1;
System.arraycopy(data, index + 1, data, index, moved);
data[--size] = null; // 断开引用,避免被删除的对象无法回收
shrinkIfNeeded();
return old;
}
private void ensureCapacity(int minCapacity) {
if (minCapacity > data.length) {
int newCapacity = data.length + (data.length >> 1); // 1.5 倍
if (newCapacity < minCapacity) {
newCapacity = minCapacity; // 一次追加大量元素时直接满足需求
}
data = Arrays.copyOf(data, newCapacity);
}
}
private void shrinkIfNeeded() {
int capacity = data.length;
if (capacity > 8 && size < (capacity >> 2)) { // 滞后阈值:降到 1/4 才收缩
data = Arrays.copyOf(data, capacity >> 1);
}
}
private void rangeCheck(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("index: " + index + ", size: " + size);
}
}
private void rangeCheckForAdd(int index) {
if (index < 0 || index > size) { // 插入位置允许等于 size
throw new IndexOutOfBoundsException("index: " + index + ", size: " + size);
}
}
}
几个结构性要点:
- 容量管理收敛到两个私有方法(
ensureCapacity与shrinkIfNeeded),业务方法只表达语义,不直接操作容量。 - 缩容阈值显著低于扩容阈值(1/4 对 1/1),并把容量缩减到一半,形成滞后区间,避免边界抖动。
- 删除时清空末尾槽位。引用型数组若只减小
size而不清槽位,被删除的对象仍被数组强引用,无法回收,是长期存活容器上典型的内存泄漏来源。基本类型数组没有这个问题(但仍可能残留旧值,读取未初始化槽位会得到脏数据)。 - 插入位置的合法范围比访问多一个:访问要求
index < size,插入允许index == size(等价于尾部追加)。
1.2 批量搬移的优化
- 优先使用语言提供的批量复制原语:Java 的
System.arraycopy、C++ 的std::copy/memmove、Python 的切片赋值、Go 的copy。这些原语在运行时或标准库中经过专门优化,可以按机器字或向量指令推进,也避免了逐元素循环中的下标计算与边界检查。 - 搬移方向必须避免覆盖。插入时元素要向后移动,必须从后向前逐个处理(搬移原语的源区间与目标区间重叠时由实现保证正确,手工循环则需自行控制方向);删除时元素要向前移动,必须从前向后处理。方向写反会覆盖尚未搬移的数据,这类错误不会立即崩溃,而是产生难以定位的数据错乱。
- 合并多次搬移。需要连续插入 k 个元素时,先一次性扩容到
size + k,再对后续元素做一次整体搬移,最后批量写入;逐个插入会产生 k 次整段搬移。 - 对引用数组,复制过程还需要与分代 GC 的跨代引用记录配合,运行时对此有专门处理;这一点在使用搬运原语时自动满足,手工逐元素写入则可能带来额外的写屏障开销。
1.3 越界与并发修改的防护
- 访问前统一做范围检查,让失败发生在越界处,而不是在后续某个使用错误值的位置(早失败原则)。
- 严格区分 size 与 capacity。遍历与追加必须使用有效元素个数:使用底层数组长度会读到未赋值槽位(引用型为
null,基本类型为零值),并且在扩容后长度会突然变化。 - 并发修改检测。集合类通常维护一个结构性修改计数器,迭代器在创建时记录该值并在后续操作中校验,不一致时抛出
ConcurrentModificationException。需要明确三点:它在单线程下「迭代期间修改」时同样会触发,与多线程无关;它只是尽力而为的检测,不构成并发安全保证;计数器本身通常不具备可见性保证。机制细节与常见误区见 Java 集合框架实现原理。 - 遍历中删除的正确做法:使用迭代器提供的删除方法、语言内置的过滤式删除(如
removeIf、filter),或倒序按下标删除。正向循环中按下标删除会跳过一个元素,因为删除后后续元素前移,而循环变量同时递增。
2. 链表实现要点
2.1 插入与删除的指针顺序
// 头插:先建立新节点到旧头的链接,再更新头引用
newNode.next = head;
head = newNode;
// 在 prev 之后插入:先连后断,顺序不可颠倒
newNode.next = prev.next;
prev.next = newNode;
// 删除 prev 的后继
prev.next = prev.next.next;
- 头插的顺序错误:先执行
head = newNode会丢失原链表——新节点的next仍为空,其余节点将不再可达。 - 中间插入的顺序错误:先执行
prev.next = newNode会丢失原后继链,因为原后继的地址只存在于prev.next中。 - 若代码可读性受影响,可以借助局部变量表达意图,代价不变:
Node succ = prev.next; newNode.next = succ; prev.next = newNode; - C/C++ 中删除节点:必须先保存后继再释放,
Node* nxt = p->next; free(p); p = nxt;,释放之后不得再访问p的任何字段(包括在调试输出中)。
2.2 哨兵简化边界处理
Node dummy = new Node(); // 哨兵:不承载有效数据
dummy.next = head;
// ... 所有插入删除都在 dummy 之后进行,无需判断是否操作头节点
return dummy.next; // 统一返回真实的头节点
引入哨兵后,删除、插入、合并、反转等操作的代码路径都变为唯一的一条,不需要在开始时判断「头节点是否为空」,也不需要在返回时判断「头节点是否被修改」。这是用一个不承载数据的节点换取分支消除,代价是逻辑位置与物理节点之间多一次间接。
双向链表可以进一步使用首尾相接的哨兵环:head 哨兵与 tail 哨兵互为 next / prev,空表时两者互指。此时插入与删除完全不需要判空,且不存在 null 指针。
2.3 双向链表的删除
// 已知节点 x 的删除:两条赋值互不依赖,只需保证 x 不是哨兵
x.prev.next = x.next;
x.next.prev = x.prev;
// 显式清理引用(Java 中依赖于把 x 置为不可达即可,C/C++ 中释放前必须做)
x.prev = null;
x.next = null;
- 两条赋值语句的先后顺序不影响结果,因为它们都以
x现有的指针为输入;真正需要注意的是两条都要执行——只更新一个方向会留下不一致的链,从另一端遍历时结果错误。 - 若
x是头节点或尾节点,需要同时更新head/tail引用;使用哨兵环可以完全消除这一分支。 - 与单链表的对比:单链表删除给定节点需要前驱;若只持有 x 且 x 不是尾节点,可以用「复制后继节点的数据到 x、再删除后继」的技巧做到 O(1),但它改变了节点承载的数据,且当 x 为尾节点时失效;若外部还持有 x 的引用,会观察到一个内容被替换、位置仍然存在的节点。双向链表用额外的
prev指针换取了真正 O(1) 的删除。
2.4 迭代与递归的取舍
// 迭代:O(n) 时间,O(1) 额外空间
Node cur = head;
while (cur != null) {
process(cur);
cur = cur.next;
}
// 递归:代码更短,但调用栈深度为 O(n)
void traverse(Node node) {
if (node == null) {
return;
}
process(node);
traverse(node.next);
}
- 递归的代价是调用栈:每个待处理节点占用一个栈帧,长链表会抛
StackOverflowError。Java 与 Python 都不做尾调用优化(Python 默认递归深度上限约 1000),因此递归深度直接受数据规模约束。 - 链表上使用递归的合理场景是深度为对数级的分治处理,例如链表归并排序:先用快慢指针找中点(O(n) 一次遍历),再对两半递归,递归深度为 O(log n)。
- 选择依据:深度可控、逻辑确实因递归而更清晰时使用递归;处理长度不确定的链表时优先迭代。迭代写法在链表上的可读性损失通常有限,因为链表的问题大多是线性顺序处理。
3. 复杂度对照表
| 操作 | 静态数组 | 动态数组 | 单链表 | 双向链表 |
|---|---|---|---|---|
| 按下标访问 | O(1) | O(1) | O(n) | O(n) |
| 按值查找 | O(n) | O(n) | O(n) | O(n) |
| 头部插入 | 不可行(需整体后移) | O(n) | O(1) | O(1) |
| 尾部插入 | 不可行 | 均摊 O(1) | O(1)(需尾引用) | O(1) |
| 中间插入(给定下标) | O(n) | O(n) | O(n) | O(n) |
| 中间插入(已持有前驱) | 不适用 | O(n) | O(1) | O(1) |
| 删除(给定下标) | O(n) | O(n) | O(n) | O(n) |
| 删除(已持有节点) | 不适用 | O(n) | O(n)(需前驱) | O(1) |
| 顺序遍历 | O(n),常数最小 | O(n),常数最小 | O(n),指针追逐 | O(n),指针追逐 |
| 每元素容器结构开销 | sizeof(E) | sizeof(E)(含空闲槽位) | 节点头 + 1 个引用 | 节点头 + 2 个引用 |
| 缓存友好性 | 高 | 高 | 低 | 低 |
| 空间连续性 | 连续 | 连续(可扩容) | 分散 | 分散 |
| 容量调整 | 固定 | 按倍数增长 | 逐节点分配 | 逐节点分配 |
两点补充说明:
- 链表的「中间插入 O(1)」以已经持有前驱为前提;通过下标操作时,定位阶段仍是 O(n),与数组同级。
- 动态数组的「均摊 O(1)」指的是尾部追加;单次追加仍可能触发 O(n) 的扩容复制。
4. 选型指南
4.1 按访问模式选择
| 访问模式 | 推荐结构 | 理由 |
|---|---|---|
| 按下标随机访问为主 | 数组 / 动态数组 | O(1) 定位,局部性好 |
| 只在两端增删(栈、队列) | 动态数组或双端队列 | 无节点开销与指针追逐,两端均摊 O(1) |
| 顺序遍历中频繁删除当前元素 | 链表(经迭代器操作) | 迭代器已持有前驱,删除 O(1) |
| 头部频繁插入 | 链表或双端队列 | 动态数组的头部插入为 O(n) |
| 中间位置频繁插入且规模很大 | 平衡树 / 跳表 / 块状结构 | O(log n) 或 O(√n),优于数组的 O(n) |
| 既要按下标定位又要频繁中间修改 | 块状链表 / 顺序统计树 | 在定位与搬移之间取折中 |
4.2 按数据规模与内存约束选择
- 规模小(数百个元素以内)时两者的绝对差异很小,应优先选择表达更直接、内存更省的数组。
- 内存敏感(元素多、单元素小)时选数组:链表的每元素节点开销通常是数组的数倍,且大量分散的小对象会给分配器与垃圾回收带来额外压力。
- 元素本身很大且数量多时,链表的结构开销占比下降,但指针追逐的缓存代价依然存在,需要实测比较,不能只按内存开销判断。
4.3 读多写少与写多读少
- 读多写少:选数组。随机访问 O(1) 叠加顺序遍历的高缓存命中率,使读路径的常数最小;写操作少意味着 O(n) 的插入删除代价很少被触发。
- 写多读少:先确认「写」发生在哪个位置。
- 写集中在两端:双端队列或链表。
- 写分散在中间,但位置由遍历过程给出(例如流式处理中总是删除刚刚处理的节点):链表合适。
- 写是「按下标插入」:链表的定位 O(n) 会抵消插入 O(1) 的收益,此时数组反而可能更快,因为搬移由运行时批量完成,常数更小。
- 一个常见误判是把「元素多 + 插入多」直接等同于链表。插入位置若是按下标给出的,或者插入前需要随机访问做校验,链表的整体代价通常高于动态数组。
4.4 语言内置结构的差异
| 语言 | 内置结构 | 存储方式 | 需要注意的点 |
|---|---|---|---|
| Java | ArrayList | 动态数组(1.5 倍扩容) | 中间插入 O(n),迭代快 |
| Java | LinkedList | 双向链表(同时实现 List 与 Deque) | 作为 List 使用时按下标访问为 O(n) |
| Java | ArrayDeque | 环形数组实现的双端队列 | 两端操作通常优于 LinkedList |
| Python | list | 动态数组 | 索引 O(1),头部插入 O(n) |
| Python | collections.deque | 分块的双向队列 | 两端 O(1),随机访问 O(n) |
| C++ | std::vector | 动态数组 | 扩容倍数由实现决定,标准未规定 |
| C++ | std::list | 双向链表 | 提供 splice 用于整段节点 O(1) 迁移 |
| C++ | std::deque | 分块数组 | 两端高效,中间插入代价高 |
| Go | slice | 底层数组的视图(长度与容量分离) | append 容量不足时重新分配并复制 |
| Go | container/list | 双向链表 | 非泛型(Go 1.18 前),类型断言开销 |
一个值得注意的共性:语言内置的「列表」几乎都是动态数组,链表多以独立类型(Deque、list)出现。原因是动态数组在缓存局部性与常数因子上的优势覆盖了多数访问模式,链表的价值集中在两端操作与「已持有位置时的 O(1) 修改」这两类场景。Java 中 ArrayList 与 LinkedList 的扩容机制、真实代价与选型对比,以及各类集合的复杂度总表,见 Java 集合框架实现原理。
5. 常见问题与排查
5.1 频繁中间插入导致的性能问题
现象:批量构建列表的耗时随数据量呈平方增长;单次请求耗时长且 CPU 占用高;性能分析显示大量时间消耗在内存复制上。
原因:在循环中对动态数组的头部或中间位置逐个插入,每次插入都触发一次 O(n) 的搬移,n 次插入累计 O(n²)。
排查:
- 检索循环体内的
add(0, ...)、add(i, ...)、remove(0),以及「读一批数据、逐条从头部插入」的写法。 - 用分析工具查看复制原语(
arraycopy/memmove/std::copy)的调用占比;若该占比很高,说明瓶颈在搬移。 - 观察耗时与数据量的关系:数据量翻倍而耗时变为四倍,基本可以确认是平方量级。
修复:
- 改为尾部追加,最后统一反转或排序。头部插入且顺序不重要的场景,直接使用尾部追加加一次反转,把 n 次 O(n) 变为一次 O(n)。
- 两端操作改用双端队列,其环形数组实现使两端插入都是均摊 O(1)。
- 先收集到临时容器再一次性插入,减少整段搬移次数。
- 确需大量按序插入时,改用平衡树、跳表或块状结构,把单次插入降到 O(log n) 或 O(√n)。
5.2 链表遍历中的指针丢失
现象:遍历得到的元素个数少于预期;遍历过程中抛出空指针异常;程序陷入死循环;已删除的节点仍然可达。
原因:
- 改写
next(或prev)之前没有保存受影响的指针。 - 双向链表只更新了一个方向,链表从两端遍历得到不同结果。
- 哨兵的使用不一致,某个分支漏掉了「操作头节点」或「操作尾节点」的情况。
- 并发修改导致读到中间状态。
排查与防护:
- 为遍历增加步数上限,一旦超过预期元素数就判定为成环或结构损坏,避免无限循环占满 CPU。
- 在单元测试中断言遍历长度与元素顺序,而不只断言「包含某个元素」。
- 边界用例至少覆盖:空表、单节点表、删除头节点、删除尾节点、删除唯一节点、在头部插入、在尾部插入。
修复方向:结构操作前先用局部变量保存相关指针;把所有结构修改收敛到少数几个方法中,避免在多处直接改写指针;统一使用哨兵消除头尾分支。
5.3 并发环境下的可见性与安全发布
动态数组与链表都不是线程安全的:并发追加可能丢失元素,长度计数与实际内容不一致;并发结构修改可能让链表出现环或断链,且这类损坏在事后难以复现。
安全发布。一个对象在构造完成后要安全地被其他线程看到,需要保证「外部引用可见」不早于「构造完成写入字段」。否则其他线程可能观察到「引用已可见、字段仍是默认值」的部分构造对象。手段包括:
- 把字段声明为
final。 - 用
volatile引用发布对象,或使用java.util.concurrent.atomic中的原子引用。 - 通过静态初始化(类初始化由 JVM 保证可见性)或锁发布。
共享可变状态的可见性。链表的节点字段若不是 volatile,也未通过同步访问,其他线程可能看到「节点已经链接进链表,但节点数据尚未写入」的中间状态。这与语言的内存模型直接相关:在 Java 中属于数据竞争,在 C++ 中属于未定义行为,必须按各自的内存模型处理,而不是依赖「看起来能跑」。
写时复制。读多写极少的场景(监听器列表、配置快照)可以使用写时复制容器:写操作加锁并全量复制底层数组,复制完成后一次性发布新数组,读操作完全无锁。代价是单次写为 O(n) 且内存峰值翻倍;迭代器基于创建时的快照,不会抛出并发修改异常,也看不到迭代开始之后的写入。
无锁队列。基于 CAS 的单向链表队列(如 Michael–Scott 队列)可以做到无锁出入队,但需要处理 ABA 问题与节点内存回收(危险指针、引用计数或依赖 GC 托管),实现难度与验证成本都很高。除有明确性能需求且有验证手段外,应使用语言或库提供的并发容器。
并发机制(volatile 语义、CAS、happens-before 规则、安全发布的具体写法)的完整说明见 Java 并发编程;各类集合的线程安全性与并发容器对比见 Java 集合框架实现原理。
5.4 大数组导致的内存与 GC 压力
数组是整体存活的对象。只要数组本身可达,其中的元素就不能被单独回收,即使大部分槽位为空;链表的节点则可以各自独立回收。这个差别决定了长生命周期容器中大数组与链表的内存行为不同:删除数组中的元素不会释放内存,必须缩容;删除链表中的节点会立即断开引用。
扩容峰值。扩容瞬间旧数组与新数组同时驻留,占用约为原容量的 2.5 倍(1.5 倍增长)。对大容器而言,这个峰值是比「复制耗时」更危险的后果。
大对象判定。在 G1 中,超过 Region 大小一半的对象被当作大对象(Humongous),占用若干连续的 Region,分配与回收成本高于普通对象;频繁创建大数组会推动并发标记周期提前启动甚至触发 Full GC,日志中出现 Humongous regions 数量波动。G1 的分区化布局、大对象处理与日志字段判读见 JVM 内存结构与垃圾回收。
观测手段:
- 类直方图观察数组类的实例数与占用,快速判断是否有异常大的数组。
- 堆转储按保留大小排序,从大对象向下追溯引用链,定位持有者字段与业务代码位置。
- 主机侧观察进程 RSS 与容器内存限额,确认内存需求是否已逼近限额。
手段:
- 按实际规模预设容量,而不是预留一个过大的上界——过大的数组同样会真实占用物理内存。
- 超大数据分片处理或流式处理,避免整体驻留。
- 数值密集场景使用基本类型数组,消除装箱对象与引用数组的双重开销。
- 长期不再增长的大数组主动缩容(如
trimToSize),代价是一次复制。
6. 检查清单
数组与动态数组:
- 遍历与追加使用有效元素个数,而不是底层数组的物理长度。
- 访问与插入前完成范围检查;插入位置的合法范围比访问多一个位置。
- 已知规模时预设容量;批量追加前一次性扩容,避免多次搬移。
- 删除引用型元素后清空末尾槽位的引用,避免对象无法回收。
- 大批量搬移使用语言提供的复制原语,并确认搬移方向不会覆盖未处理的数据。
- 中间位置插入频繁时,评估能否用「尾部追加 + 一次反转」替代。
- 缩容使用滞后阈值,避免容量在边界反复扩缩。
链表:
- 改写 next / prev 之前先保存受影响的指针。
- 用哨兵统一头尾的特判;空表、单节点、头尾节点的用例均有覆盖。
- 双向链表的删除同时更新两个方向。
- 遍历有明确的终止条件,循环链表明确终止依据,并为遍历增加步数上限。
- 处理长度不确定的链表时优先使用迭代而非递归。
- 删除节点后不再访问该节点(C/C++ 中尤其注意释放顺序)。
通用:
- 明确复杂度是否包含定位代价:链表的插入 O(1) 以持有位置为前提。
- 需要按下标随机访问时不使用链表;需要频繁中间修改时谨慎评估数组的搬移量。
- 容器的内存开销按「每元素结构开销 × 规模」估算,而不是只按元素本身大小估算。
- 在目标数据规模与实际访问模式下测量,而不是仅凭复杂度表选型。
- 共享结构在并发场景下使用并发容器,而不是自行加锁暴露内部结构。
- 涉及下标或节点位置的计算,专项检查边界上的 off-by-one。
四、总结
数组与链表是同一个问题的两种答案:元素在内存中是连续存放还是分散存放。连续存放换来「地址可由下标直接算出」,代价是插入删除必须搬移元素;分散存放换来「修改只涉及相邻节点的指针」,代价是定位必须逐节点前进。两种代价无法同时消除,这是两种结构长期并存、并在其上派生出其他结构的根源。从 ADT 视角看,线性表是规范,数组与链表是两种存储实现,见 抽象数据类型(ADT)。
连续存储一侧的核心事实:
- 随机访问 O(1) 来自地址算术,与下标无关;它描述的是定位方式,不含遍历语义。
- 插入删除为 O(n),代价是搬移量随元素数线性增长,而不是搬移本身的单次开销大。
- 越界检查是内存安全语言与不检查语言的分界,后者的越界属于未定义行为且故障位置常与出错位置分离。
- 多维数组的遍历顺序必须与存储顺序(行主序 / 列主序)一致,否则局部性丧失,同为 O(n²) 的代码实测差距明显。
动态数组一侧的核心事实:
- 容量与长度的分离让定长数组获得可变长度语义,同时补上了「空槽位」与「零值元素」不可区分的问题。
- 倍数增长把尾部追加的均摊代价降到 O(1);固定增量则退化为平方量级的总代价。
- 倍数取值影响三件事:扩容次数、累计搬移量、复制瞬间的内存峰值。2 倍扩容次数更少但峰值更高、空闲空间更难复用;1.5 倍更节省峰值内存。
- 摊还 O(1) 不约束单次最坏代价,延迟敏感场景应关注最坏情况。
- 缩容需要滞后阈值,否则容量会在扩缩之间抖动,每一次抖动都付一次 O(n) 复制。
链式存储一侧的核心事实:
- 位置由指针关系定义,地址信息分散在节点内部,因此按下标定位必然 O(n)。
- 哨兵节点消除头尾特判,使插入删除只有一条代码路径,是用一个空节点换取分支消除。
- 双向链表为已知节点的删除提供真正的 O(1);单链表的「复制后继数据」技巧有尾节点与引用语义两处代价。
- 「插入删除 O(1)」以持有位置为前提;按下标操作时定位仍是 O(n),与数组同级且常数更差。
性能差异的根源在缓存与开销:
- 数组的访问模式可预测,硬件预取有效,顺序遍历的平均访存次数远小于元素个数;内核的预读遵循同一原理,见 linux:页缓存与 IO 性能。
- 链表的指针追逐无法预取,每一步都可能是一次缓存未命中;节点开销是数组的数倍,其对象头、指针压缩与对齐规则见 JVM 内存结构与垃圾回收。
- 复杂度相同不代表实际耗时相同,常数因子可相差一个数量级。复杂度用于判断趋势,选型需要实测。
算法层面,三指针反转、快慢指针、固定间距双指针等技巧把链表的常见问题限制在 O(n) 时间与 O(1) 额外空间内,且这些技巧都建立在「链表只能单向逐步前进」这一约束之上。
工程选型可以归纳为三条判断:需要按下标随机访问时用数组;写操作已持有位置、且集中在两端或遍历过程中时用链表;两者都要且规模很大时,用块状结构或有序索引结构在定位与搬移之间取折中。语言内置的「列表」普遍实现为动态数组,说明在多数实际访问模式下,连续存储的综合代价更低。