Java 开发者必看！ArrayList 和 LinkedList 的性能厮杀：选错一次，代码慢成蜗牛

就算业务逻辑写得再溜，也可能把应用搞成蜗牛速度。

坑不在算法本身，而在你选的 “容器” 上。

选不对 List，每次循环都像绕远路散步；

选对了，同样的代码能立马精神起来。

ArrayList 和 LinkedList 表面看像双胞胎，

骨子里却像两个物种。

就是这种 “货不对板”，悄悄决定了性能是翻车还是封神。

读完这篇，你就能掌握一个简单法则，不用跑分也能选对。

01

两个 List 的暗战

ArrayList 是个可扩容的数组，内存里是一整块连续空间，支持直接索引。

LinkedList 是串节点，每个节点存着值和两个指针（.prev 和.next）。

一张图胜过千次微基准测试：

ArrayList（连续内存）

Index:   0     1     2     3     4
Data:   [A]   [B]   [C]   [D]   [E]

Access: direct by index → O(1)

LinkedList（双向链表）

 +-----+----+       +-----+----+       +-----+----+
   |  A  | ↔  |  <->  |  B  | ↔  |  <->  |  C  | ↔  |
   +-----+----+       +-----+----+       +-----+----+

Each node has:
- the value
- a pointer to previous
- a pointer to next
Access: must follow links → O(n)

每个节点包含：

• 实际值
• 指向前一个节点的指针
• 指向后一个节点的指针

访问：必须顺着链条找 → O (n)

内存布局几乎决定了所有性能差异。

02

为啥一个飞似闪电，一个爬如蜗牛

随机访问：

• ArrayList：O (1)（唰一下就到）。
• LinkedList：O (n)（得一个个节点挪过去）。

尾部追加：

• ArrayList：平均 O (1)（偶尔扩容，但总体很快）。
• LinkedList：O (1)（有尾指针的话，直接挂上去）。

头部插入 / 删除：

• ArrayList：O (n)（后面所有元素都得挪位置）。
• LinkedList：O (1)（改两个指针就行，快得很）。

中间插入 / 删除：

除非手里握着迭代器定位到了目标位置，否则俩都得先 “找” 到位置。

如果用 ListIterator 定位好了，LinkedList 实际插入只要 O (1)；ArrayList 还是得挪一堆元素。

内存开销：

ArrayList 只存元素本身。

LinkedList 每个元素要带俩指针。数据量到百万级，内存能差出一大截。

所以结论很简单：

多数时候是按索引读，或者往末尾加东西 → 选 ArrayList。

边迭代边修改，或者频繁在头部增删 → 可以瞅瞅 LinkedList。

03

代码揭露真面目

随机访问：ArrayList 飞，LinkedList 爬。

var a = new ArrayList<Integer>(1000000);
for (int i = 0; i < 1000000; i++) {
    a.add(i);
}

var l = new LinkedList<Integer>();
for (int i = 0; i < 1000000; i++) {
    l.add(i);
}

// 同样操作，成本天差地别
int x = a.get(700000); // O(1) 直接定位
int y = l.get(700000); // O(n) 慢慢爬吧

LinkedList 的秘密：在 “当前位置” 修改才快。

var list = new LinkedList<String>();
list.add("A");
list.add("B");
list.add("D");
// 用迭代器遍历并插入
var it = list.listIterator();
while (it.hasNext()) {
    if (it.next().equals("B")) {
        it.add("C"); // 直接插在B后面
        break;
    }
}

ArrayList 的舒适区：批量追加后快速读取。

var emails = new ArrayList<String>(users.size());
// 把所有邮箱拷进去
for (User u : users) {
    emails.add(u.email());
}
// 取第三个邮箱
String third = emails.get(2); // 直接定位，快得很

04

代码评审时常见的坑

• 用 LinkedList 还写索引循环

如果你写for (int i = 0; i < n; i++) list.get(i)，LinkedList 能慢到让你怀疑人生。

换成 ArrayList，或者用迭代器遍历吧。

• 迷信 “插入快”

LinkedList 只有在 “已经站在目标位置” 时才快。

多数时候，找位置的成本早就抵消了插入的优势。

• 忽略缓存 locality

ArrayList 的数据在内存里是一整块，CPU 缓存友好得很；

LinkedList 的节点散落在内存各处，访问起来自然慢。

• 用 LinkedList 实现队列

要做队列，用 ArrayDeque！

它更快、更省空间，就是为这场景设计的。

05

靠谱的简单法则

1. 先从 ArrayList 开始

多数情况它都是最佳选择：内存占用小，读操作飞快，用起来还简单。

1. LinkedList 只在特殊场景用

只有两种情况考虑它：一是边迭代边频繁修改（比如遍历的时候就地增删），二是必须频繁在头部增删。

1. 队列和栈首选 ArrayDeque

别用 LinkedList 搞这个，ArrayDeque 专门优化了队列和栈操作，快得多。

1. 改之前先实测

别瞎猜！先 profiling 看看代码到底慢在哪。很多时候瓶颈根本不在 List 本身。

这几条能搞定 Java 里大部分 List 性能问题。

06

选错 List 让 get (i) 变龟速的真实案例

有个同事用 LinkedList 存用户 ID，觉得它 “更灵活”。

后来他写了个循环，反复调用list.get(i)检查每个 ID。

在 LinkedList 上，每次 get (i) 都得从头爬一遍。

用户多到几千时，程序慢得像卡住了。

我们换成 ArrayList，get (i) 变成常数时间，

同样的代码瞬间变快，其他啥都没改。

就因为换了个 List 而已。

07

最终判决：默认选手 vs 专精选手

ArrayList 是日常主力，

LinkedList 是那种 “只租一个周末干活” 的专用工具。

如果你的访问模式是频繁按索引读，或者往末尾加元素，ArrayList 完胜。

如果你的修改操作集中在当前位置，而且用迭代器操作，LinkedList 能超常发挥。

摸清自己的使用模式，按内存布局选，别被传言忽悠。