Java Academy · 课时

LinkedList 与 ArrayList 的权衡

Q: 「LinkedList 与 ArrayList 的权衡」这节课中我会学到什么？

比较插入、删除和随机访问的性能，以选择合适的列表类型 你通过在浏览器中直接运行的动手代码来练习 Java Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

比较插入、删除和随机访问的性能，以选择合适的列表类型

LinkedList 与 ArrayList 的权衡 是 CoddyKit 上的免费 Java Academy 课时。这是第 3 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 Java Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Java Academy 课程共包含 4 节课。

核心问题

ArrayList 和 LinkedList 都实现了 List，因此共享相同的 API。区别在于它们的内部数据结构，以及各自能够高效执行的操作。

ArrayList 内部原理

ArrayList 将元素存储在连续数组中。当数组填满时，会用一个大 1.5 倍的新数组替换它，并复制所有元素。

import java.util.ArrayList;

ArrayList<String> list = new ArrayList<>(4); // initial capacity 4
list.add("A"); list.add("B"); list.add("C"); list.add("D");
list.add("E"); // triggers resize: new array of capacity 6

System.out.println(list.get(3)); // O(1) — direct index access

重新认识 LinkedList 内部原理

每个元素都存放在自己的 Node 对象中，该对象包含 prev/next 指针。不存在连续内存——节点可以位于堆中的任意位置。

import java.util.LinkedList;

LinkedList<String> list = new LinkedList<>();
list.add("A"); list.add("B"); list.add("C");

// get(index) must traverse from head or tail
System.out.println(list.get(1)); // O(n) — traverses 1 step from head

随机访问：ArrayList 更具优势

ArrayList.get(i) 的时间复杂度为 O(1)——直接通过数组索引访问。LinkedList.get(i) 的时间复杂度为 O(n)——最多需要遍历 n/2 个节点。

ArrayList<Integer> al = new ArrayList<>();
LinkedList<Integer> ll = new LinkedList<>();
for (int i = 0; i < 100_000; i++) { al.add(i); ll.add(i); }

// Fast:
System.out.println(al.get(99_999)); // O(1)

// Slow — avoid this pattern with LinkedList:
System.out.println(ll.get(99_999)); // O(n)

头部插入：LinkedList 更具优势

在 ArrayList 的索引 0 处添加元素需要移动所有元素——时间复杂度为 O(n)。LinkedList 只需更新两个指针——时间复杂度为 O(1)。

// ArrayList: O(n) — shifts all elements right
ArrayList<String> al = new ArrayList<>(List.of("B","C","D"));
al.add(0, "A"); // shifts B, C, D

// LinkedList: O(1)
LinkedList<String> ll = new LinkedList<>(List.of("B","C","D"));
ll.addFirst("A"); // updates head pointer only

尾部插入：大致相当

ArrayList 和 LinkedList 在尾部追加元素的摊销时间复杂度都为 O(1)。ArrayList 偶尔会触发扩容复制，但摊销后仍为 O(1)。LinkedList 会分配一个新节点，无需扩容。

ArrayList<Integer> al = new ArrayList<>();
LinkedList<Integer> ll = new LinkedList<>();

for (int i = 0; i < 1_000_000; i++) {
    al.add(i); // amortized O(1)
    ll.add(i); // O(1)
}

内存使用

ArrayList：每个元素约 8 字节（数组中的一个引用）。LinkedList：每个元素约 48 字节（包含数据、prev、next 以及对象头的 Node 对象）。对于大型数据集，ArrayList 占用的内存明显更少。

迭代性能

对于两者，顺序迭代（增强 for 循环或迭代器）的时间复杂度都是 O(n)。但 ArrayList 可以受益于 CPU 缓存预取——元素在内存中连续存储。LinkedList 的节点分散在堆中，会导致缓存未命中。

// Both O(n), but ArrayList is faster in practice due to cache locality
for (String s : arrayList) { process(s); }
for (String s : linkedList) { process(s); } // more cache misses

中间插入和删除

两者都需要 O(n) 才能找到位置。找到位置后，ArrayList 需要以 O(n) 移动元素；LinkedList 只需以 O(1) 解除节点链接。因此，当您已经持有迭代器并且需要频繁修改中间元素时，LinkedList 更具优势；否则两者差别不大。

LinkedList<Integer> ll = new LinkedList<>(List.of(1,2,3,4,5));
ListIterator<Integer> it = ll.listIterator();
while (it.hasNext()) {
    int val = it.next();
    if (val == 3) it.remove(); // O(1) unlink via iterator
}
System.out.println(ll); // [1, 2, 4, 5]

选择指南

请根据主要操作进行选择：

ArrayList：随机访问、迭代、尾部追加——可覆盖 90% 的使用场景
LinkedList：频繁在头部或尾部插入和删除，实现队列、双端队列或栈
ArrayDeque：需要纯队列或栈时使用（优于 LinkedList）

基准测试总结

关于性能的思维模型：

get(i)：ArrayList 为 O(1)，LinkedList 为 O(n)
add(0,x)：ArrayList 为 O(n)，LinkedList 为 O(1)
add(x)：两者的摊销时间复杂度都为 O(1)
迭代器删除：定位后两者都是 O(1)
每个元素的内存占用：ArrayList 约 8B，LinkedList 约 48B

快速检查

您正在构建一个任务队列：任务从队尾添加，并以每秒数百万次的频率从队首移除。哪种数据结构最合适？

回顾：LinkedList 与 ArrayList

要点：

ArrayList 在随机访问（O(1)）和对缓存友好的遍历方面表现出色
LinkedList 擅长 O(1) 的头部和尾部操作
内存：ArrayList 每个元素约占 8B；LinkedList 每个元素约占 48B
对于队列和栈，请优先使用 ArrayDeque，而不是 LinkedList
在大多数场景下，ArrayList 是合适的默认选择

常见问题解答

「LinkedList 与 ArrayList 的权衡」课时是免费的吗？

是的 — 「LinkedList 与 ArrayList 的权衡」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Java Academy 课程的其余内容，请升级到 CoddyKit PRO。 Java Academy 课程共包含 4 节课。

「LinkedList 与 ArrayList 的权衡」这节课中我会学到什么？

比较插入、删除和随机访问的性能，以选择合适的列表类型你通过在浏览器中直接运行的动手代码来练习 Java Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 Java Academy 需要有经验吗？

无需任何先前经验。CoddyKit 上的 Java Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。这是第 3 节课，共 4 节。

「LinkedList 与 ArrayList 的权衡」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 Java Academy 课中编写并运行代码吗？

能。每节 Java Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

← 返回 Java Academy