Java 中 ArrayList 与 LinkedList 的深度对比

1. 概述

在 Java 集合框架中，List 接口有两个最常用的实现类：ArrayList 和 LinkedList。虽然它们都实现了 List 接口，行为看似一致，但底层实现天差地别，性能表现也因此大不相同。

本文将从源码层面剖析两者的实现机制，并结合实际场景给出选型建议，帮你避免踩坑，写出更高效的代码。

2. ArrayList：基于动态数组的实现

ArrayList 的核心是 一个可动态扩容的数组。它实现了 List 接口，支持按索引快速访问，是大多数开发者默认的 List 实现选择。

2.1 添加元素（add）

创建一个空的 ArrayList 时，它会初始化一个默认容量为 10 的数组（JDK 8+）：

init cap

当数组未满时，添加元素非常简单，只需将元素放入 size 位置并递增 size：

backingArray[size] = newItem;
size++;

✅ 时间复杂度：O(1) —— 最佳和平均情况都非常快。

⚠️ 但当数组满了，就需要扩容：创建一个更大的新数组（通常是原大小的 1.5 倍），然后将所有旧元素复制过去。这一步是 O(n) 的。

虽然单次扩容代价高，但摊还分析（amortized analysis）表明：连续添加 n 个元素的总时间是 O(n)，因此 **add 操作的摊还时间复杂度为 O(1)**。

💡 小贴士：如果你能预估数据量，建议直接指定初始容量，避免频繁扩容：
List<String> events = new ArrayList<>(10_000); // 预分配空间

2.2 按索引访问（get）

这是 ArrayList 的强项。数组天然支持随机访问，直接通过索引定位：

return backingArray[index];

✅ **时间复杂度恒为 O(1)**，无论数据量多大，访问速度都一样快。

2.3 按索引删除（remove）

删除某个索引的元素后，ArrayList 必须将该位置之后的所有元素向前移动一位，以填补空缺：

remove

最佳情况（删末尾）：O(1)
平均和最坏情况（删开头或中间）：O(n)

⚠️ 删除越靠前的元素，需要移动的数据越多，性能越差。

2.4 适用场景与限制

✅ 推荐使用 ArrayList 的场景：

读多写少（频繁 get，少量 add/remove）
需要随机访问（如分页、按索引取值）
能预估数据规模，避免频繁扩容

❌ 不适合的场景：

频繁在中间插入或删除（性能差）
存储超大规模数据（数组最大长度为 Integer.MAX_VALUE，即 2^31 - 1 ≈ 21 亿）

⚠️ 注意：Java 数组索引是 int 类型，所以 ArrayList 也无法存储超过 Integer.MAX_VALUE 个元素。

3. LinkedList：基于双向链表的实现

LinkedList 的底层是一个双向链表（doubly linked list），每个节点包含数据、前驱和后继指针：

four nodes

它也实现了 Deque 接口，因此支持高效的头尾操作。

3.1 添加元素（add）

添加新节点时，只需修改尾节点的 next 指针和 last 引用：

link last
update last

✅ 时间复杂度恒为 O(1) —— 无需扩容，无需移动元素。

无论是头插、尾插还是中间插入（已知位置），都是常数时间。

3.2 按索引访问（get）

LinkedList 不支持随机访问。要获取第 i 个元素，必须从头或尾开始遍历：

如果 i < size/2，从头开始遍历
否则从尾开始遍历

✅ 最佳情况（访问头/尾）：O(1)
❌ 平均和最坏情况（访问中间）：O(n)

❌ 性能踩坑：不要在 LinkedList 上频繁调用 get(i)，尤其是大列表，性能极差。

3.3 按索引删除（remove）

删除操作分两步：

找到目标节点（O(n)）
修改前后指针，断开连接（O(1)）

因此整体时间复杂度由查找决定：

最佳：O(1)（删头/尾）
平均/最坏：O(n)

3.4 适用场景

✅ 推荐使用 LinkedList 的场景：

频繁在头部或尾部插入/删除（如队列、栈）
写操作远多于读操作
需要实现 Deque 行为（双端队列）

📌 典型用例：
假设你正在处理时间序列事件流，每秒产生大量事件，需要快速追加；然后周期性地全量消费这些事件生成统计报告。

// 高频写入 + 低频全量读取，LinkedList 更合适
LinkedList<Event> events = new LinkedList<>();
events.add(event); // O(1)
// ... 周期性遍历所有事件
for (Event e : events) { ... } // O(n)，但无法避免

💡 虽然遍历是 O(n)，但写入始终是 O(1)，而 ArrayList 在扩容时可能出现卡顿。

4. 总结

操作	ArrayList	LinkedList
`add`（尾部）	摊还 O(1) ⚠️（可能扩容）	✅ O(1)
`get`（随机）	✅ O(1)	❌ O(n)
`remove`（中间）	❌ O(n)（需移动）	❌ O(n)（需查找）
`remove`（头/尾）	❌ O(n) / O(1)	✅ O(1)
内存开销	较低（数组）	较高（每个节点额外两个指针）

✅ 选型建议：

**默认选 ArrayList**：大多数场景下性能更好，尤其是读多写少。
选 LinkedList 当：
- 频繁在头/尾增删（用作栈、队列）
- 写操作密集，且无法预估数据量
- 需要 Deque 功能

⚠️ 最后提醒：不要迷信“LinkedList 插入快”这种说法。**只有在已知节点位置时插入才是 O(1)**。如果还要先 get(i) 找位置，那整体就是 O(n) 了。

简单粗暴一句话：除非你明确需要 Deque 或高频头尾操作，否则用 ArrayList 就对了。

Persistence

REST

Security