ArrayList 和 LinkedList 有什么区别？

简化版

ArrayList 是动态数组，随机访问 O(1)、中间增删要搬元素；LinkedList 是双向链表，头尾增删改指针 O(1)、但随机访问要从头遍历 O(n)。实战里 99% 场景用 ArrayList——即使是频繁增删，ArrayList 靠连续内存和 CPU 缓存往往还是更快。

详细版

维度	ArrayList	LinkedList
底层结构	可扩容数组 `Object[]`	双向链表 `Node`（前后指针）
随机访问 `get(i)`	O(1)，下标寻址	O(n)，从头/尾遍历
中间增删	O(n)，搬移后续元素	定位 O(n) + 改指针 O(1)
头部增删	O(n)	O(1)
内存开销	小，只存元素 + 少量空槽	大，每个节点多存两个指针
缓存友好度	高（连续内存）	低（节点散落堆各处）

关键洞察在「中间增删」这行：很多人以为「链表增删快」，但 LinkedList 在任意位置增删，得先遍历找到那个位置（O(n)），改指针本身才是 O(1)。所以除非你手里已经握着那个节点的迭代器，否则链表的「增删快」根本兑现不了。

完整版教学

一、为什么「链表增删快」是个误导

这是这道题最大的陷阱。教科书说「链表增删 O(1)」，但那有个前提：你已经站在要操作的位置上。现实中你通常只知道「删第 500 个」或「删值为 x 的」，LinkedList 得先花 O(n) 走到那里。

于是对比就变成了：

中间插入：ArrayList = 定位 O(1) + 搬移 O(n)；LinkedList = 定位 O(n) + 改指针 O(1)。两者都是 O(n)。
而 ArrayList 的「搬移」是一段连续内存的批量拷贝（System.arraycopy，底层高度优化），LinkedList 的「遍历」是不断跳指针、每跳一次都可能 cache miss。

结果往往是 ArrayList 反而更快。这就是为什么实践中几乎总选 ArrayList。

二、为什么缓存局部性这么重要

ArrayList 的元素挤在一块连续内存里，CPU 一次加载一个缓存行就能带进来好几个元素，遍历飞快。LinkedList 的节点是一个个 new 出来的，散落在堆的各个角落，遍历时每访问一个节点几乎都要重新从内存加载（cache miss），加上每个节点还多存两个指针（内存占用大约是 ArrayList 的数倍）。

记忆点：现代 CPU 下，「连续内存」这个优势常常压倒算法复杂度上的理论差异。这也是为什么 Java 之父之一 Josh Bloch 都说自己几乎不用 LinkedList。

三、那 LinkedList 什么时候有用

真正适合 LinkedList 的场景其实很窄：频繁在两端增删、且很少随机访问——但这种需求 ArrayDeque（基于循环数组的双端队列）做得更好，既满足头尾 O(1) 操作，又有连续内存的缓存优势。

所以结论很干脆：

需要 List、随机访问 → ArrayList；
需要队列/栈/双端队列 → ArrayDeque；
LinkedList → 基本没有非它不可的场景。

四、ArrayList 的补充细节

默认初始容量 10（首次 add 时才真正分配），扩容 1.5 倍。
能预估数据量就 new ArrayList<>(n)，省掉多次扩容拷贝。
非线程安全，并发场景用 CopyOnWriteArrayList 或 Collections.synchronizedList。

五、用具体操作量比较，而不只背复杂度

假设容器有 10 万个元素，要在索引 50,000 插入：ArrayList 能 O(1) 定位，然后用一次连续内存搬移约 5 万个引用；LinkedList 要先逐节点走约 5 万步，再改 4 个相邻指针。两者都是 O(n)，但前者的批量复制通常更符合 CPU 缓存和预取机制。

ArrayList: 直接到 index 50000 → 连续搬移 [50000..99999]
LinkedList: node0 → node1 → ... → node50000 → 修改前后链接

真实需求	更合适的选择	原因
大量按索引读取、顺序遍历	`ArrayList`	随机访问与局部性好
已知规模后批量装载	`ArrayList(n)`	可预分配，内存紧凑
FIFO 队列、栈、双端队列	`ArrayDeque`	两端均摊 O(1)，无节点开销
已持有 `ListIterator` 并在当前位置频繁增删	`LinkedList`	免去重新定位，改链接 O(1)
读多写少的并发快照	`CopyOnWriteArrayList`	读无锁，但写复制

复杂度只描述增长趋势，不包含对象头、指针、GC、缓存未命中和底层数组拷贝的常数。选型应以操作分布和基准测试为依据，不能看到“增删”两个字就条件反射选择链表。

六、常见误区与追问

误区：LinkedList 任意位置插入都是 O(1)。 只有已经持有目标节点或迭代器位置时，修改链接才是 O(1)。
误区：ArrayList 每次尾部添加都会扩容。 只有容量用尽才扩容，普通追加直接写入空槽。
误区：LinkedList 做队列一定优于数组。 ArrayDeque 通常有更低内存开销和更好的缓存局部性。
追问：两者是否都允许 null 和重复元素？ 允许，它们都实现 List 语义，差别主要在存储结构和性能。
追问：LinkedList 的 get(i) 会总从头走吗？ 它会比较索引与 size/2，从更近的一端开始，但复杂度仍是 O(n)。
追问：为什么节点内存开销大？ 每个节点除元素引用外还保存前驱、后继引用及对象头，并增加 GC 追踪对象数量。

易错点：链表“改链接快”不等于“按位置增删快”；先定位再修改，必须把两段成本一起算。

内存账也可以做粗略推演。假设使用 64 位 JVM 且开启压缩普通对象指针，一个 LinkedList 节点至少要保存元素、前驱、后继三个引用，再叠加对象头和对齐；10 万个元素就多出 10 万个节点对象。ArrayList 主要是一块引用数组，哪怕预留 25% 空槽，通常仍比这些节点紧凑。

ArrayList：1 个列表对象 + 1 个引用数组 + 少量空槽
LinkedList：1 个列表对象 + N 个 Node 对象 + 2N 个额外前后指针

具体字节数会随 JVM 指针压缩、对象对齐和版本变化，不能背成固定答案。真正应记的是对象数量与间接寻址：节点越多，分配、GC 扫描和缓存未命中的机会越多。

此外，ArrayList 的 subList 返回共享底层结构的视图，而不是独立数组；原列表发生未协调结构修改后，子视图操作可能抛 CME。需要独立结果时应显式 new ArrayList<>(list.subList(...))。最后还要区分“随机删除”和“按迭代器当前位置删除”。若算法本来就在顺序扫描并持续调用 ListIterator.remove()，LinkedList 能避免数组搬移；但如果删除比例不高，ArrayList 的 removeIf 可在内部批量压紧元素，仍可能更快。结论应由真实数据分布验证。可用 JMH 分别构造随机读取、头部插入、已持有迭代器插入和顺序遍历四组基准；测试前固定数据规模并预热 JVM，才能避免用单一操作代表所有业务负载。

基准结论只对“该数据规模 + 该操作比例 + 该 JVM 环境”有效。

七、加强记忆

ArrayList 用连续数组换来 O(1) 随机访问、紧凑内存和高效遍历，代价是扩容复制与中间搬移；LinkedList 用独立双向节点换来已知位置上的 O(1) 链接修改，代价是 O(n) 定位、更多内存和较差局部性。一般 List 优先 ArrayList，双端队列优先 ArrayDeque，只有确实持有迭代位置并频繁局部增删时才认真考虑 LinkedList。

简化版

详细版