ArrayList 性能分析：什么时候 ArrayList 最快
一句话总结
ArrayList 的核心优势是随机访问 O(1)，劣势是中间增删需要移动元素。
搞清楚这个，你就知道什么时候该用它了。
性能特点一览
| 操作 | 时间复杂度 | 原因 |
|---|---|---|
随机访问 get(i) / set(i, e) | O(1) | 直接数组下标 |
尾部添加 add(e) | 均摊 O(1) | 大多数是 O(1)，扩容时 O(n) |
按索引插入 add(i, e) | O(n) | 需移动 i 之后的元素 |
按索引删除 remove(i) | O(n) | 需移动 i 之后的元素 |
按对象删除 remove(Object) | O(n) | 需先查找再移动 |
contains / indexOf | O(n) | 需遍历数组 |
clear | O(n) | 需逐个清空引用 |
随机访问：ArrayList 的杀手锏
java
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < 1000000; i++) {
list.add(i);
}
// 随机访问：O(1)，极快
int value = list.get(500000);为什么这么快？因为数组在内存中是连续存储的：
内存地址 = 数组起始地址 + index × 元素大小CPU 直接算地址，一步到位。
中间增删：ArrayList 的痛点
java
// 在中间插入：O(n)
list.add(500000, newValue); // 需要移动 50 万元素
// 在中间删除：O(n)
list.remove(500000); // 需要移动 50 万元素图示：
add(2, "X") 到 [A, B, C, D, E]：
操作前：A B C D E
↑ 插入位置
操作后：A B X C D E
↑ C D E 全部后移一位尾部操作：ArrayList 的舒适区
java
// 尾部添加：均摊 O(1)
list.add("A"); // O(1)
list.add("B"); // O(1)
list.add("C"); // O(1)
// ...大多数业务代码都是尾部追加，ArrayList 为此而生。
性能实测
java
import java.util.*;
public class ArrayListPerformanceDemo {
public static void main(String[] args) {
int size = 100_000;
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < size; i++) list.add(i);
// 1. 随机访问
long start = System.nanoTime();
for (int i = 0; i < size; i++) {
list.get(i);
}
System.out.println("随机访问: " + (System.nanoTime() - start) / 1_000_000 + " ms");
// 2. 尾部添加
start = System.nanoTime();
ArrayList<Integer> tail = new ArrayList<>();
for (int i = 0; i < size; i++) {
tail.add(i);
}
System.out.println("尾部添加: " + (System.nanoTime() - start) / 1_000_000 + " ms");
// 3. 中间插入
start = System.nanoTime();
ArrayList<Integer> mid = new ArrayList<>(size);
for (int i = 0; i < size; i++) {
mid.add(0, i); // 头部插入，O(n)
}
System.out.println("头部插入 10 万次: " + (System.nanoTime() - start) / 1_000_000 + " ms");
// 4. 遍历
start = System.nanoTime();
int sum = 0;
for (int i : list) sum += i;
System.out.println("遍历: " + (System.nanoTime() - start) / 1_000_000 + " ms");
}
}典型结果：
随机访问: ~5 ms
尾部添加: ~10 ms
头部插入 10 万次: ~3000 ms ← 非常慢！
遍历: ~8 ms结论：头部插入是 ArrayList 的性能灾难，应该用 LinkedList 或 ArrayDeque。
CPU 缓存友好：被忽视的优势
ArrayList 比 LinkedList 快，不只是因为随机访问 O(1)，还因为CPU 缓存。
现代 CPU 有多级缓存，当访问数组的一个元素时，会把附近的一大块内存都加载到缓存。
java
// ArrayList：连续内存，缓存命中率高
for (int i = 0; i < list.size(); i++) {
process(list.get(i)); // 下一个元素很可能已在缓存中
}
// LinkedList：分散内存，缓存命中率低
for (String s : linkedList) {
process(s); // 每个元素都可能触发一次内存读取
}简单说：ArrayList 遍历时，CPU 缓存预加载让访问像坐电梯；LinkedList 遍历时，每次都要去内存里找下一个节点，像爬楼梯。
迭代器：遍历的最佳方式
java
List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
// ❌ 普通 for 循环
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
// ✅ 增强 for 循环（编译后就是迭代器）
for (Integer n : list) {
System.out.println(n);
}
// ✅ JDK 8+ forEach
list.forEach(System.out::println);
// ✅ Stream
list.stream().forEach(System.out::println);这几种方式性能差别不大，但增强 for 循环和 forEach 更简洁，迭代器方式遍历时删除元素更安全。
适用场景总结
✅ ArrayList 擅长的场景
java
// 场景1：按索引随机访问
for (int i = 0; i < data.size(); i++) {
process(data.get(i));
}
// 场景2：只尾部追加
while (hasMoreData()) {
list.add(readData());
}
// 场景3：批量读取后遍历处理
List<Record> records = db.queryAll();
records.forEach(this::process);❌ ArrayList 不擅长的场景
java
// 场景1：频繁在头部/中间增删
LinkedList<Integer> better = new LinkedList<>();
better.add(0, item); // O(1)
// 场景2：频繁两端的队列操作
Deque<Integer> queue = new ArrayDeque<>(); // 比 LinkedList 快选型一句话
ArrayList = 写少读多、尾部操作多、按索引访问。LinkedList = 频繁中间增删、只用迭代器遍历。