ArrayList 与 LinkedList 区别与选型

更新时间：2026-09-18。这是集合框架最经典的选型题，但答案和很多人的直觉相反：现实里几乎总是 ArrayList 赢。

一、底层结构

维度	ArrayList	LinkedList
底层	动态数组（连续内存）	双向链表（Node 节点分散在堆）
随机访问 get(i)	O(1) 直接索引	O(n) 要从头/尾顺着走
尾部追加	均摊 O(1)（扩容时 O(n) 拷贝）	O(1)
中间插入/删除	O(n)（要搬移后续元素）	定位 O(n) + 改指针 O(1)
头部插入	O(n)（整体搬移）	O(1)
内存额外开销	数组尾部少量预留空间	每个节点多两个指针 + 对象头
CPU 缓存友好	好（连续内存，预取命中）	差（节点离散，cache miss 多）

二、为什么「中间插入 LinkedList 快」常常是错觉

教科书说链表中间插删 O(1)，但那是已经拿到节点的前提下。实际 list.add(i, x) / list.remove(i) 还要先沿链表走到第 i 个节点，这是 O(n)；而 ArrayList 的数组搬移由 System.arraycopy 这类底层批量内存操作完成，远比逐个走指针快。再加上链表节点离散、缓存不友好，实测多数「中间插入」场景 ArrayList 仍更快。

三、选型结论

• 默认用 ArrayList：遍历、查找、绝大多数增删（尤其在尾部）都更优，缓存友好。
• LinkedList 真正适合：频繁在头部增删、或作为队列/双端队列（实现了 Deque）使用，且操作主要通过 addFirst/removeLast/peek 等不依赖随机下标的方法。
• 作为队列更推荐 ArrayDeque（数组实现的双端队列），通常比 LinkedList 更省更快。

四、常见坑

1. 循环中直接 remove 元素：fori 删除会因下标位移漏元素，for-each 删除触发 ConcurrentModificationException；正确做法：

   Iterator<String> it = list.iterator();
   while (it.hasNext()) { if (it.next().equals("x")) it.remove(); }
   // 或 Java8：list.removeIf(s -> s.equals("x"));

2. 不预设容量：ArrayList 扩容按 1.5 倍增长并拷贝，已知大小用 new ArrayList<>(expectedSize)。
3. 用 LinkedList 还调 get(i)：把 O(n) 访问放循环里，退化成 O(n²)。
4. 以为 LinkedList 省内存：每个 Node 有 prev/next 指针和对象头，元素少时比数组费得多。

总结

ArrayList 是连续动态数组，随机访问 O(1)、缓存友好、尾部追加均摊 O(1)，代价是中间插入要搬移元素和扩容时数组拷贝；LinkedList 是双向链表，头尾增删和作为 Deque 是 O(1)，但按下标访问要沿指针走 O(n)、每节点还有指针和对象头开销、内存离散缓存不友好；所谓“链表中间插删快”在还需定位节点时并不成立，因此除频繁头插或纯队列场景（更推荐 ArrayDeque）外几乎都应选 ArrayList，遍历时删除要用 Iterator.remove 或 removeIf，使用 ArrayList 时预估容量避免扩容。