高 基础
ArrayList与LinkedList对比#
一句话答案#
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 对象，缓存友好，性能更好。”
面试回答（2分钟版）
ArrayList 底层是动态数组，LinkedList 底层是双向链表，核心区别在数据结构特性上。ArrayList 支持 O(1) 的随机访问，通过下标直接定位元素，但在中间或头部插入删除需要移动后续所有元素，时间复杂度 O(n)，尾部插入均摊 O(1)。当容量不够时按 1.5 倍扩容并通过 Arrays.copyOf 复制数组。LinkedList 在已知节点位置的情况下增删是 O(1)，但随机访问需要从头遍历是 O(n)，而且每个节点有 prev 和 next 两个指针的额外内存开销。实际开发中绝大多数场景应该选 ArrayList，原因是现代 CPU 对连续内存的缓存行非常友好，ArrayList 的数组元素在内存中连续存放，即使中间插入需要移位，实际的内存复制速度也往往快于 LinkedList 追踪指针时频繁的 cache miss。如果需要队列或栈的功能，推荐用 ArrayDeque 而不是 LinkedList，同样是因为缓存友好性和无需创建 Node 对象。
追问与易错
追问方向：
- “ArrayList 扩容机制是什么？”→ 默认容量 10，每次扩容为原来的 1.5 倍（oldCap + oldCap >> 1），通过 Arrays.copyOf 复制旧数组到新数组
- “LinkedList 真的增删快吗？”→ 只有在已知节点位置时增删才是 O(1)，实际使用中定位节点仍需从头/尾遍历 O(n)，整体性能不一定优于 ArrayList
- “什么场景用 ArrayList 什么场景用 LinkedList？”→ 绝大多数场景用 ArrayList（CPU 缓存友好、随机访问快）；LinkedList 适合需要频繁头部插删或当作 Deque 使用的场景，但实际中 ArrayDeque 是更优选择
易错点：
- ❌ “LinkedList 增删一定比 ArrayList 快”——需要先定位到节点，整体性能不一定好
- ❌ 忽略 ArrayList 尾部增删也是 O(1)