结论先行
绝大多数业务场景优先使用 ArrayList。它的随机访问是 O(1)，连续内存带来更好的 CPU 缓存局部性。LinkedList 只有在已经持有节点位置并频繁在该位置插入、删除时才可能占优。
ArrayList 的结构与扩容
ArrayList 底层是动态数组。添加元素超过容量后会创建更大的数组并复制旧元素。常见 JDK 实现按原容量约 1.5 倍扩容，但不应把具体倍数当成 Java API 契约。
List<Integer> values = new ArrayList<>(10_000);
for (int i = 0; i < 10_000; i++) values.add(i);
已知数据规模时设置初始容量，可以减少扩容和数组复制。size 是元素数量，capacity 是内部数组容量，两者不是一回事。
LinkedList 的结构
LinkedList 是双向链表，每个节点保存元素以及前驱、后继引用。访问第 n 个元素需要从头或尾逐个移动，因此随机访问为 O(n)。此外，每个节点都是额外对象，内存开销和 GC 压力通常更大。
操作复杂度
| 操作 | ArrayList | LinkedList |
|---|---|---|
| 按下标读取 | O(1) | O(n) |
| 尾部追加 | 均摊 O(1) | O(1) |
| 头部插入 | O(n) | O(1) |
| 按下标插入 | 查找 O(1) + 移动 O(n) | 查找 O(n) + 链接 O(1) |
| 迭代 | 缓存友好 | 需要追逐节点引用 |
“LinkedList 插入一定快”并不准确。若先调用 get(index) 或 add(index, value) 定位节点，查找本身仍是 O(n)。
删除元素的陷阱
List<Integer> 同时存在 remove(int index) 和 remove(Object value)。传入基本类型会删除指定下标，想按值删除需要显式装箱：
list.remove(Integer.valueOf(1));
遍历时直接调用集合的 remove 可能触发 ConcurrentModificationException，应使用迭代器的 remove，或使用 removeIf。
并发与 fail-fast
二者都不是线程安全集合。迭代期间检测到结构性修改时通常会快速失败，但 fail-fast 只是尽力检测的错误提示机制，不能当作并发安全保证。读多写少可评估 CopyOnWriteArrayList，高并发写入则应重新考虑数据结构和同步策略。
选择建议
- 普通查询、批量遍历、尾部追加：选择
ArrayList。 - 队列或双端队列：通常选择
ArrayDeque，而不是LinkedList。 - 大量头部操作：优先评估
ArrayDeque。 - 只有确实需要链表节点操作，并通过基准测试证明收益时，才选择
LinkedList。
核心考点清单
- ArrayList 随机访问 O(1)，尾部添加均摊 O(1)，中间插入需要移动元素。
- LinkedList 按下标访问 O(n)，节点对象带来额外内存和较差缓存局部性。
- “链表插入 O(1)”仅在已经持有节点位置时成立。
- 双端队列场景通常优先 ArrayDeque，而不是 LinkedList。
高频追问与参考回答
追问：ArrayList 扩容为什么是均摊 O(1)？
单次扩容要复制 O(n) 个元素，但容量按比例增长，连续多次追加的总复制成本可摊到每次操作上。
追问：CopyOnWriteArrayList 适合什么场景？
适合读远多于写、集合较小且允许读取短暂快照的场景；每次写都会复制数组，不适合频繁写入或大集合。
机制全景图
下面把「ArrayList 与 LinkedList 应该怎么选？」从输入到结果压缩成一条可复述的主链路。面试时先用图建立全局坐标，再进入局部实现，能避免只背零散结论。
flowchart LR
A["接收访问模式"]
A --> B["选择连续数组或链节点"]
B --> C["定位目标元素"]
C --> D["执行读写或插入"]
D --> E["扩容回收并返回"]
完整链路：从输入到结果
沿着「接收访问模式 → 选择连续数组或链节点 → 定位目标元素 → 执行读写或插入 → 扩容回收并返回」观察输入、状态与输出，下面每个阶段都对应一个可以在源码、日志或系统表中验证的位置。
1. 接收访问模式
先确认主要操作是随机访问、尾部追加还是中间插入，不能只依据 Big-O 口号选择。
2. 选择连续数组或链节点
ArrayList 用连续引用数组获得局部性，LinkedList 为每个元素额外保存前后节点指针。
3. 定位目标元素
数组可按下标 O(1) 定位，链表必须从头尾遍历；现代 CPU 缓存使实际差距通常比复杂度表更明显。
4. 执行读写或插入
ArrayList 中间插入要移动元素，LinkedList 在已持有节点时改指针很快，但通过下标找节点仍是 O(n)。
5. 扩容回收并返回
ArrayList 扩容会复制数组并短暂占用两份空间，链表则持续承担节点对象与 GC 成本。
源码与实现定位
| 入口 | 阅读重点 |
|---|---|
| java.util.ArrayList | grow、fastRemove 与数组移动 |
| java.util.LinkedList | Node、node(index) 从头尾查找 |
源码或系统表应按上表顺序追踪：先确认入口实际走到哪条路径，再用运行时数据验证，而不是仅凭类名或配置推测。
参数配置与可复现实验
var list = new ArrayList<Order>(100_000);
for (Order order : source) list.add(order);
用 JMH 分别测试随机 get、中间插入、尾部追加和增强 for；数据量固定 1k/100k/1m，配合 JFR 记录 Node 分配。
验证步骤与预期结果
1. 固定输入和基线
先在没有故障注入的环境执行上述配置，固定数据规模、并发度、运行时版本和预热时间。以「10 万次随机 get」为主基线，记录值应满足「ArrayList 应明显更快」；同时保存 集合尺寸分布、扩容与数组复制次数，使后续变化能够回到同一时间轴比较。
2. 从实现入口确认路径
在「java.util.ArrayList」确认请求确实进入「grow、fastRemove 与数组移动」对应的实现，再沿「java.util.LinkedList」观察「Node、node(index) 从头尾查找」。如果入口路径都未命中，就不应继续调整下游参数，而应先检查调用条件、版本或路由是否与假设一致。
3. 注入本文特有的失败模式
优先复现「在 LinkedList 上按索引循环」，并把单一变量逐级放大，直到「10 万次随机 get」越过「LinkedList 呈 O(n²)」。随后再分别验证「ArrayList 未预估容量导致反复扩容」和「迭代时结构修改引发并发修改异常」，三类故障分开执行，避免多个变量同时变化而无法归因。
4. 执行止损和根因修复
第一轮只应用「把索引循环改为迭代器」，确认它能控制影响范围；第二轮应用「普通队列改用 ArrayDeque」，验证核心链路恢复；最后落实「批量装载前按可知规模预分配」，消除同类问题再次出现的条件。每一步都保留变更前后数据，不用“感觉变快了”替代测量。
5. 通过退出条件
实验只有同时满足三项才算通过：「10 万次随机 get」回到「ArrayList 应明显更快」、「每元素额外对象」回到「ArrayList 仅引用槽」、「扩容次数」回到「预估容量后接近 0」，并且业务结果差异为零。若性能恢复但结果不一致，仍应视为失败；若指标恢复后很快再次越线，则说明只完成了临时止损，没有消除根因。
量化基线
| 指标 | 样例基线/口径 | 风险线 | 结论 |
|---|---|---|---|
| 10 万次随机 get | ArrayList 应明显更快 | LinkedList 呈 O(n²) | 禁止按索引遍历链表 |
| 每元素额外对象 | ArrayList 仅引用槽 | LinkedList Node 数=元素数 | 评估堆与 GC |
| 扩容次数 | 预估容量后接近 0 | 多次复制大数组 | 传入合理 initialCapacity |
这些数值是实验口径或示例告警线，不是可复制到所有系统的固定答案；上线阈值应由本系统稳态、峰值和故障演练共同确定。
事故复盘：十万条分页结果处理变慢
代码认为链表插入快，把数据库结果装入 LinkedList 后反复 get(i) 遍历，实际退化为 O(n²)。改为增强 for 顺序遍历已经改善，但由于主要是追加与扫描，最终使用预估容量的 ArrayList 获得更低内存和更好的缓存局部性。
| 失败模式 | 首要证据 | 第一处置动作 |
|---|---|---|
| 在 LinkedList 上按索引循环 | 集合尺寸分布 | 把索引循环改为迭代器 |
| ArrayList 未预估容量导致反复扩容 | 扩容与数组复制次数 | 普通队列改用 ArrayDeque |
| 迭代时结构修改引发并发修改异常 | 对象分配率 | 批量装载前按可知规模预分配 |
发布与回滚检查点
- 发布前：确认「java.util.ArrayList」对应实现和上述配置在目标版本仍然有效，并保存「10 万次随机 get」基线。
- 灰度中：同时观察 集合尺寸分布、扩容与数组复制次数、对象分配率；任一指标越过表中风险线，就停止继续扩量。
- 回滚时：先执行「把索引循环改为迭代器」控制影响，再回退代码或参数；涉及持久状态时必须额外核对结果差异。
- 发布后：至少覆盖一个完整峰值周期，确认「在 LinkedList 上按索引循环」没有再次出现，才关闭变更观察窗口。
方案对比与选型
| 方案 | 更适合的场景 | 主要收益 | 代价与边界 |
|---|---|---|---|
| ArrayList | 随机访问、尾部追加和批量遍历 | 内存紧凑、CPU 缓存友好 | 中间移动与扩容复制 |
| LinkedList | 频繁操作两端且直接持有迭代位置 | 双端增删语义直接 | 节点开销高、随机访问慢 |
| ArrayDeque | 队列、栈和双端操作 | 连续数组、性能稳定 | 不支持 null，按下标访问不是主要能力 |
选型至少带上 元素数量、读写比例、遍历方式、并发度和内存预算，并用上面的量化基线验证；未知数据应明确为待测假设。
设计边界与工程取舍
复杂度是上界模型，不包含缓存局部性、对象头和 GC；除非确有链表语义，ArrayList 或 ArrayDeque 通常是更稳妥的默认选择。
工程落地遵循：先保证数据结构语义正确，再依据访问模式选择实现。回答时直接引用「java.util.ArrayList」、配置实验和事故数据，比复述固定模板更有说服力。