ArrayList 和 LinkedList 的区别？

2025年阅读约 7 分钟面试指南 · Java面试

Java 面试集合

深入解析ArrayList和LinkedList的区别，从底层数据结构到性能对比，分初级、中级、高级三个层次全面讲解。

一句话总结

ArrayList 底层是动态数组（内存连续，O(1) 随机访问，尾部插入 O(1) 均摊）→ LinkedList 底层是双向链表（O(1) 头尾插入，随机访问 O(n)）。LinkedList 中间插入实际也是 O(n)（需先遍历到位置）。ArrayList 有 fail-fast 机制（modCount），遍历时结构性修改抛 ConcurrentModificationException。

初级理解

ArrayList 底层是动态数组，内存连续，支持快速随机访问（O(1)），但插入删除需要移动元素（O(n)）。

LinkedList 底层是双向链表，内存不连续，插入删除只需修改指针（O(1)），但随机访问需要遍历（O(n)）。

对比维度	ArrayList	LinkedList
底层结构	动态数组	双向链表
随机访问	O(1)，支持索引	O(n)，需遍历
头部插入	O(n)，需移动所有元素	O(1)
尾部插入	O(1) 均摊	O(1)
中间插入	O(n)	O(n)，先遍历到位置
内存占用	只存数据	存数据+前后指针
实现接口	List	List + Deque

中级深入

ArrayList 的扩容机制：默认初始容量 10，每次扩容为原来的 1.5 倍（oldCapacity + oldCapacity >> 1）。扩容时通过 Arrays.copyOf() 复制到新数组，有性能开销。

LinkedList 的双向链表结构：每个节点（Node）包含 item（数据）、prev（前驱指针）、next（后继指针）。LinkedList 同时实现了 List 和 Deque 接口，可以作为队列、栈使用。

// LinkedList 作为队列和栈 LinkedList<String> list = new LinkedList<>(); list.offer("A"); // 入队 list.poll(); // 出队 list.push("B"); // 入栈 list.pop(); // 出栈

遍历性能对比：ArrayList 用 for-i 遍历最快（直接内存访问），LinkedList 用 foreach/Iterator 遍历最快（避免每次 get(i) 的 O(n) 开销）。

高级拓展

为什么说"LinkedList 中间插入是 O(1)"是误导？虽然链表修改指针是 O(1)，但找到插入位置需要 O(n) 遍历。所以实际中间插入也是 O(n)。只有在已持有节点引用时才是真正的 O(1)。

ArrayList 的 modCount 和 fail-fast 机制：ArrayList 内部有一个 modCount 字段，每次结构性修改（add/remove）都会递增。迭代器在创建时记录 expectedModCount，每次操作前检查两者是否一致，不一致则抛出 ConcurrentModificationException。

// fail-fast 示例 List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C")); for (String s : list) { if ("B".equals(s)) { list.remove(s); // 抛出 ConcurrentModificationException } } // 正确做法：使用 Iterator.remove() Iterator<String> it = list.iterator(); while (it.hasNext()) { if ("B".equals(it.next())) { it.remove(); // 安全删除 } }

选型建议：频繁随机访问 → ArrayList；频繁头部增删 → LinkedList；大多数场景 ArrayList 更优（内存连续，CPU 缓存友好）。

面试加分项：能说出 fail-fast 机制和 LinkedList 中间插入的实际复杂度，说明你对集合源码有研究。

实战场景

场景：遍历时删除元素的正确姿势

// 反例：for-each 中直接 remove → ConcurrentModificationException List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C")); for (String s : list) { if ("B".equals(s)) list.remove(s); // 抛异常！ } // 正例1：Iterator.remove() Iterator<String> it = list.iterator(); while (it.hasNext()) { if ("B".equals(it.next())) it.remove(); } // 正例2：removeIf（JDK 8+） list.removeIf(s -> "B".equals(s)); // 正例3：倒序遍历（ArrayList 专用） for (int i = list.size() - 1; i >= 0; i--) { if ("B".equals(list.get(i))) list.remove(i); }

面试模拟

Q：ArrayList 和 LinkedList 怎么选？

A：大多数场景选 ArrayList。内存连续对 CPU 缓存友好，for-i 遍历极快。只有频繁在头部增删时才考虑 LinkedList（如实现队列/栈），但此时用 ArrayDeque 更优（循环数组，无链表节点开销）。

Q：为什么说 LinkedList 中间插入是 O(1) 是误导？

A：虽然链表修改指针是 O(1)，但找到插入位置需要 O(n) 遍历。只有已持有节点引用（如 ListIterator）时才是真正的 O(1)。面试时主动指出这一点是加分项。