ArrayList 和 LinkedList 有什么区别？为什么链表插入不一定更快？

知识点详解：用一次插入，把两种成本拆开

数组中连续摆的是引用，不是所有对象本体

假设一个列表有 A、B、C、D 四个元素。

ArrayList 的底层数组有一组按位置排列的槽位，每个槽位保存元素引用。要找下标 2，可以直接定位相应槽位，取得 C。

这里“数组连续”说的是数组槽位这一层，不是承诺 A、B、C、D 这几个对象在堆中也紧挨着。这个小区别能避免后面讲缓存、内存时把对象布局说错。

ArrayList API说明了按下标访问的常数时间成本和追加的均摊成本。

中间插入，ArrayList 需要给新元素腾位置

现在要把 X 插在 B 前面。

如果数组还有容量，就要把原来的 B、C、D 对应引用向后移动，再把 X 放进新位置。这里可能要搬动很多槽位，但不需要把 B、C、D 的对象内容重新复制一遍。

如果数组已满，还可能先分配更大的内部数组、复制原有引用，再完成插入。

所以，单次尾部追加遇到扩容时也可能变贵；“均摊 O(1)”不是保证每一次追加都同样快。扩容倍率也不要当成 List 接口永远不变的承诺。

链表少搬东西，但必须先到现场

LinkedList 中，每个节点保存前后联系。已经有指向 B 附近的迭代器时，把 X 接进去，主要是建立新节点并修改相邻链接。

但如果调用的是按下标插入，比如 add(index, value)，容器仍然要先找到 index 所在的位置。双向链表可以从更近的一端开始，但目标位于中间时，还是要走过许多节点。LinkedList API明确说明了这一点。

完整成本就是：定位位置的成本，加上修改结构的成本。

“链表插入 O(1)”通常隐含了已经定位这一前提。把这个前提省略，再和 ArrayList 的完整插入比较，就会得出误导性的结论。

数组搬移的是原来 B、C、D 的引用，A 的位置不变。链图为了看清接入过程只画 next 方向；Java LinkedList 实际还维护 prev，不是单向链表。

为什么两个都是 O(n)，实际运行还可能差很多？

大 O 描述规模扩大时的增长趋势，不会告诉我们所有常数成本。

遍历 ArrayList 时，读取一组数组槽位。遍历 LinkedList 时，要不断跟随节点引用，还要为节点中的链接和对象结构付出额外空间。新插入通常也会带来节点分配。

因此，即使都需要遍历 n 个元素，链表也不一定更快。数据规模、对象大小、分配压力和实际访问方式都会影响结果。

如果有人说“我的场景链表更快”，需要让他说明操作模式和测试条件，而不是立即否定。但测试也要用有代表性的访问序列，不能只测事先已经拿到迭代器的那一次插入，就推导所有场景。

图中横向箭头表示相邻节点可以前后访问，没有按字段所在行绘制指针；next 指向后继，prev 指向前驱。

可以怎样按操作选容器？

假设页面先批量加载数据，再按位置渲染，偶尔在尾部追加。此时，ArrayList 的访问方式比较贴合需求。

假设算法已经沿迭代器逐个访问，需要在当前位置反复局部增删，LinkedList 才有值得比较的条件。别用 get(i) 循环遍历链表，否则每次 get 都可能重新走一段，整体成本容易变成二次增长。

如果主要是栈、队列或双端入队出队，应另外看 ArrayDeque。ArrayDeque API介绍了这些用法和边界；它不接受 null，也不是线程安全队列。并发需求则要选相应并发容器或明确加锁。

面试官继续追问

需要频繁删除，直接选 LinkedList 可以吗？

先问删除位置怎样确定。按值查找后删除仍然包含遍历；如果批量筛选，数组容器也可能一次整理完成。频繁删除只是线索，不是选型结论。

ArrayList 设置了初始容量，就有那么多个元素吗？

不是。容量是能容纳的槽位数量，size 是实际元素数量。预留容量能减少部分扩容，但不会自动创建一批列表元素。

fail-fast 能证明线程安全吗？

不能。ConcurrentModificationException 是尽力而为的错误检测，不能代替同步，也不保证每种并发错误都会被检测到。

面试速记卡

• ArrayList：数组槽位存引用，随机访问方便，移动与扩容有成本。
• LinkedList：双向节点，局部改链便宜，按下标通常仍要遍历。
• 插入成本：先找位置，再修改结构，不能只比较后半步。
• 均摊：多次操作平均成本，不是单次耗时保证。
• 选型：看实际操作；两端队列还要比较 ArrayDeque。