一句话答案

ArrayList 基于数组，随机访问 O(1) 但增删慢；LinkedList 基于双向链表，增删 O(1) 但随机访问 O(n)。

核心要点

维度	ArrayList	LinkedList
底层结构	动态数组（Object[]）	双向链表（Node）
随机访问（get(i)）	O(1)	O(n)（需从头遍历）
头部插入/删除	O(n)（需整体移位）	O(1)
尾部插入	O(1)（均摊，偶尔扩容）	O(1)
中间插入/删除	O(n)（移位）	O(n)（查找） + O(1)（操作）
内存占用	紧凑，仅数组	每个节点有 prev/next 指针，额外开销大
CPU 缓存友好性	好（数组连续内存）	差（链表节点散布内存）
实现接口	List	List, Deque, Queue

场景选择：

• 绝大多数场景用 ArrayList：现代 CPU 缓存行对连续内存友好，即使中间插入，ArrayList 的实际性能也往往优于 LinkedList（因为内存复制比指针追踪的 cache miss 代价小）
• LinkedList 适合：需要频繁在头部插删且不需要随机访问时；或需要把它当作双端队列（Deque）使用（推荐用 ArrayDeque 代替）

面试官追问："实际上 LinkedList 很少用，在 Java 中队列/栈首选 ArrayDeque，因为无需 Node 对象，缓存友好，性能更好。"

追问与易错

追问方向：

• ArrayList 扩容机制是什么？（1.5 倍扩容，Arrays.copyOf 复制）
• LinkedList 真的增删快吗？（只有在已知节点位置时 O(1)，查找节点仍需 O(n)）
• 什么场景用 ArrayList 什么场景用 LinkedList？

易错点：

• ❌ "LinkedList 增删一定比 ArrayList 快"——需要先定位到节点，整体性能不一定好
• ❌ 忽略 ArrayList 尾部增删也是 O(1)

💡 记忆锚点

ArrayList是书架，按编号直接抽书O(1)，插中间要整排挪位；LinkedList是火车车厢，摘挂方便但找第n节要从头数。实际中书架赢面大——CPU缓存爱连续内存，挪书比追指针快。