外观
03 - 数组与链表没有谁更高级:从 CPU Cache 到随机访问
前置阅读:01 - 时间复杂度如何决定系统上限、A - 算法正确性、测试与基准方法。
后续阅读:05 - 栈与队列的解题模型。
摘要
“频繁插入就用链表”省略了一个关键条件:插入前是否已经找到位置?本文先解释数组与链表如何存储和访问元素,再比较定位、搬移和内存访问的成本,最后通过反转和删除节点理解引用更新的顺序。
1. 场景:频繁插入就该用 LinkedList 吗
数组把元素放在连续的槽位中,下标表示槽位的位置。因为每个槽位大小相同,可以直接根据起始位置和下标定位元素,不必经过前面的元素,所以按下标访问是 O(1)。这里的“随机访问”指可以直接读取任意下标,并不是随机选择元素。
单链表则把数据放在一个个节点中:每个节点保存值和指向下一个节点的引用 next,head 指向第一个节点,末尾节点的 next 为 null。Java 中的引用用于找到对象,本文所说的“指针操作”就是修改这些引用。
例如 1 -> 2 -> 3 表示三个节点按 next 相连。要找到第三个节点,必须从头依次沿引用前进;如果每次插入前都要从头走到第 k 个位置,定位成本随 k 增长,最坏是 O(n),其中 n 为元素数量。单链表在某节点之后插入,只需修改少量引用,改链本身是 O(1);删除时通常还需要持有待删除节点的前驱,即指向它的上一个节点。
数组在中间插入时,为保持顺序,需要把插入位置之后的元素右移。固定长度数组没有自动扩容能力;ArrayList 这类动态数组会维护“已用元素数”和“容量”,空间不足时申请更大的数组并复制旧内容。
动态数组尾部追加通常是均摊 O(1):单次扩容可能复制 n 个元素,成本为 O(n),但扩容后留下的空位可以支持多次追加。以第 6 节的倍增策略为例,连续追加过程中复制的元素总数与追加次数同阶,把总成本分摊到每次追加仍是常数级。均摊并不保证每次追加都没有延迟尖峰。
2. 内存布局影响实际速度
CPU Cache(CPU 缓存)保存近期使用的内存数据,减少处理器等待主内存的时间。数据通常按 Cache Line(缓存行)成块读取:访问一个位置时,附近的数据也可能一起进入缓存。CPU 预取则尝试提前读取接下来可能用到的数据。
顺序遍历数组时,下一个槽位紧邻当前槽位,因此更容易利用已经读入的数据和预取。链表节点通常分散在堆中,访问下一个节点要先读取当前节点的 next,再按引用找到对象,这叫间接寻址;它形成了前后依赖,也未必能利用同一缓存行中的邻近数据。这就是内存局部性:一次访问后,后续访问能否继续利用附近或刚用过的数据。
在 Java 中还要区分“值连续”和“引用连续”:int[] 的槽位直接保存整数;ArrayList<Integer> 的底层数组连续保存对象引用,读取整数仍需访问引用指向的 Integer 对象。不能据此推断所有整数对象也连续存放。链表还要保存节点及其连接引用,具体内存开销取决于对象布局。
两者顺序遍历都是 O(n),只说明访问次数随元素数线性增长,并没有说明每次访问要等待多久。数组布局通常更利于缓存,这是机制层面的分析;实际吞吐,也就是单位时间完成的操作数,仍需在相同负载下测量。
3. 单链表反转
反转要把 1 -> 2 -> 3 变成 3 -> 2 -> 1,节点和值不变,只改变 next 的方向。下面的 ReverseList 是类定义,没有 main 入口;第 6 节提供完整演示。算法假设输入是有限、无环的单链表,并会原地修改它,调用方应使用返回值作为新的头节点。
先把链表分为“已反转”和“未处理”两部分:previous 指向已反转部分的头,初始为 null;current 指向未处理部分的头,初始为 head。每轮把当前节点从后一部分移到前一部分。
java
/**
* 可运行示例:数组与链表没有谁更高级:从 CPU Cache 到随机访问。
* 重点观察核心状态如何更新,以及边界输入如何处理。
*/
public class ReverseList {
static class Node {
int value;
Node next;
Node(int value) {
this.value = value;
}
}
static Node reverse(Node head) {
// previous 指向已反转部分,current 指向尚未处理部分。
Node previous = null;
Node current = head;
while (current != null) {
Node next = current.next; // 先保存后继,避免断链
// 反转当前这一条边,再同步推进两个边界指针。
current.next = previous;
previous = current;
current = next;
}
return previous;
}
}循环不变量是每轮开始时都成立的状态约定:previous 指向已反转部分,current 指向尚未处理的第一个节点,两部分合起来包含原链表的全部节点。
更新顺序不能颠倒:先用 next 保存剩余链表的入口,再把 current.next 改为 previous,最后推进两部分的头引用。如果先改写 current.next,再从它读取后继,读到的就是已反转部分,原来的后继便无法通过这个引用找回。结束时 current 为 null,全部节点都已处理,previous 就是新的头。
4. 哨兵节点减少分支
删除一个节点,需要让它的前驱绕过它,直接指向它的后继。头节点没有前驱,通常要单独更新 head。dummy node(哨兵节点)是在真正的头节点之前临时增加的辅助节点,这样头节点也有了前驱,可以使用同一套删除逻辑。哨兵不属于业务数据,它的值不参与匹配。
下面是局部方法片段,可放入上面的 ReverseList 类中,复用其 Node 定义;它删除所有值等于 target 的节点,同样假设输入有限且无环。
java
static Node remove(Node head, int target) {
Node dummy = new Node(0);
dummy.next = head;
Node current = dummy;
while (current.next != null) {
if (current.next.value == target) {
current.next = current.next.next;
} else {
current = current.next;
}
}
return dummy.next;
}这里 current 始终是待检查节点的前驱。若 current.next 命中,就让它绕过该节点,且暂不推进 current,因为新的后继也可能命中;否则才向后移动。比如删除 2 -> 2 -> 3 中的 2,哨兵会连续绕过两个节点,最后指向 3。返回 dummy.next 才能得到删除后的真实头节点;若全部删除,返回 null。每个节点检查一次,时间为 O(n),额外空间为 O(1)。
5. 选型建议
| 访问模式 | 优先考虑 |
|---|---|
| 随机读取、批量遍历 | 数组或 ArrayList |
| 已持有节点位置,频繁插入删除 | 链式结构 |
| 队列两端操作 | ArrayDeque |
| 需要紧凑存储与序列化 | 数组 |
Java LinkedList 同时实现 List(列表)与 Deque(双端队列,可在两端插入和删除),但对象开销和局部性通常不占优势;具体性能应在目标负载下测量。表中的 ArrayDeque 是数组实现的双端队列,这里推荐的是队列两端操作场景,并不表示它提供 List 式的下标访问。
选择结构时应把完整操作链算进去。例如“在第 k 个位置插入”在一般中间位置的最坏情况成本是(这里的数组指维护连续顺序的数组结构):
text
数组:定位 O(1) + 搬移 O(n)
链表:定位 O(n) + 改链 O(1)若位置靠近端点,定位或搬移的成本可能更低,不能把上述最坏情况当作每次操作的固定成本。链式结构要发挥常数时间改链的优势,调用方必须已经持有操作所需的节点或迭代器位置。迭代器是保存遍历位置、用于逐步访问集合的对象;如果每次操作都重新按下标寻找位置,定位成本仍然存在。Java LinkedList 的公开 API 不暴露可长期持有的内部节点引用,因此不能直接把自定义链表的节点操作方式套到业务代码上。
6. 完整可运行示例:动态数组与单链表
下面的类对应文件名 LinearStructureDemo.java,包含 main 入口。示例展示容量管理、插入搬移和链表反转,不是标准容器的完整实现;它未处理并发访问,也未专门保护极大容量下的整数溢出或分配失败。
size 是已存入的元素数,data.length 是容量。插入允许下标落在 [0, size],因为 size 位置代表尾部追加;读取只允许 [0, size),因为那里才有已存入的元素。
java
import java.util.Arrays;
/**
* 可运行示例:数组与链表没有谁更高级:从 CPU Cache 到随机访问。
* 重点观察核心状态如何更新,以及边界输入如何处理。
*/
public class LinearStructureDemo {
static class IntArrayList {
private int[] data = new int[2];
private int size;
void add(int value) {
// 尾部写入前确保容量;扩容不是每次 add 都发生。
ensureCapacity(size + 1);
data[size++] = value;
}
void add(int index, int value) {
rangeForAdd(index);
ensureCapacity(size + 1);
// 把 [index, size) 整体右移一格,为新元素腾位置。
System.arraycopy(data, index, data, index + 1, size - index);
data[index] = value;
size++;
}
int get(int index) {
if (index < 0 || index >= size) throw new IndexOutOfBoundsException(
index
);
return data[index];
}
private void ensureCapacity(int required) {
if (required <= data.length) return;
// 倍增扩容使连续尾部追加保持均摊 O(1)。
data = Arrays.copyOf(data, Math.max(required, data.length * 2));
}
private void rangeForAdd(int index) {
if (index < 0 || index > size) throw new IndexOutOfBoundsException(index);
}
@Override
public String toString() {
return Arrays.toString(Arrays.copyOf(data, size));
}
}
static class Node {
int value;
Node next;
Node(int value) {
this.value = value;
}
}
static Node reverse(Node head) {
Node previous = null;
while (head != null) {
// 必须先保存 next;否则改写 head.next 后会丢失剩余链表。
Node next = head.next;
head.next = previous;
previous = head;
head = next;
}
return previous;
}
static void print(Node head) {
for (Node node = head; node != null; node = node.next) {
System.out.print(node.value + (node.next == null ? "\n" : " -> "));
}
}
// 运行入口:使用一组包含典型边界的数据验证主要算法。
public static void main(String[] args) {
IntArrayList list = new IntArrayList();
list.add(10);
list.add(30);
list.add(1, 20);
System.out.println(list + ", index 1 = " + list.get(1));
Node head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
print(reverse(head));
}
}手工推演:1 -> 2 -> 3
| 轮次 | 已反转部分 | 尚未处理部分 |
|---|---|---|
| 初始 | null | 1 -> 2 -> 3 |
| 1 | 1 | 2 -> 3 |
| 2 | 2 -> 1 | 3 |
| 3 | 3 -> 2 -> 1 | null |
这个表展示了第 3 节的不变量如何保持:每轮仅改变一个节点的连接方向,随后把它归入已反转部分。在有限无环的前提下,每个节点只处理一次,因此时间复杂度为 O(n);只使用少量引用变量,额外空间为 O(1)。
动态数组部分先追加 10 和 30,占满初始的两个槽位;在下标 1 插入 20 时容量扩为 4,再把 30 右移一格。按代码手工推演,main 的预期输出为:
text
[10, 20, 30], index 1 = 20
3 -> 2 -> 1这是预期输出。
建议测试的边界
反转应覆盖空链表、单节点、两个节点和重复值链表;删除应覆盖头部命中、连续命中、全部命中和没有命中,并检查返回的头节点。动态数组应覆盖恰好触发扩容时的头部、中间和尾部插入,以及非法下标。完整示例的 main 只有一组数组插入和三节点反转,不能代表这些边界已经测试通过。
如何验证“数组遍历通常更快”
不要用一次循环耗时证明 Cache 结论。JMH 是 Java 微基准测试工具,可用于测量小段操作的性能。可以分别测试 int[]、ArrayList<Integer> 和 LinkedList<Integer> 的顺序求和,并至少记录:
- 集合大小和元素类型;
- 是否发生装箱,即把
int等基本类型转换为Integer等包装对象,以及装箱发生在构建还是测量阶段; - JDK、堆大小和 GC(垃圾回收器及回收情况);
- 吞吐、分配率与硬件信息;
- 顺序遍历、随机读取和中间插入三种不同负载。
还应记录预热、重复次数与结果波动,并让计算结果被使用,避免编译器把无用计算消除。三种容器的元素表示不同,结果可能同时包含装箱、对象访问和容器布局的影响,不能全部归因于 Cache。随机读取与中间插入要分别测量;插入还应说明定位是否计入、位置分布以及是否触发扩容。
这些是建议的实验方法。具体速度倍数必须由目标机器和对象布局上的基准给出。
7. 排障与工程证据
当容器操作导致延迟或内存问题时,先区分:
- 是否因
LinkedList.get(i)等访问模式产生隐藏的平方复杂度; - 是否因动态数组反复扩容产生瞬时复制和分配峰值;
- 是否因链表节点、装箱对象和引用增加堆占用;
- 是否出现意外成环,导致遍历无法终止;
- 是否真正需要中间插入,还是可以批量构建后一次排序。
例如,对 LinkedList 用 get(i) 从 0 循环到 n - 1,每次读取都可能重新沿节点定位,累计成本可能达到 O(n²);沿迭代器顺序遍历则可以避免反复定位。
JFR(Java Flight Recorder)用于记录 JVM 运行事件;Profiler(性能分析工具)用于观察程序在哪些方法上消耗时间或分配对象。可结合分配热点、CPU 调用栈和 GC 指标检查上述假设,不应仅凭容器名称判断原因。批量构建后排序也只适用于业务允许改变处理顺序的情况。
8. 容易踩的坑
- 反转时未保存
next,导致后续链表丢失。 - 删除或反转后忘记接收返回的头节点,调用方仍持有旧入口。
- 链表成环后普通遍历无法终止。
- 用
LinkedList.get(i)写索引循环,可能退化成O(n²)。 - 数组扩容瞬时复制影响低延迟,应预估容量。
9. 总结
数据结构的复杂度必须连同“如何定位元素”和硬件访问特征一起分析。
- 链表
O(1)插入的前提是已经拿到插入位置。 - 数组可以直接按下标定位,连续槽位也通常有利于遍历;对象引用数组仍需考虑对象访问成本。
- 指针算法应先定义不变量,再修改引用,避免断链或成环。
横向对比:Hash 表原理与工程应用。继续学习:栈与队列的解题模型。