关于Java ArrayList与LinkedList性能的理解是否正确？

我知道这是一个反复出现的老生常谈的问题，但我对这两者确实感到困惑。以下是我对它们的理解：

理论层面：

• LinkedList在两端添加元素时速度更快（因为无需偶尔进行扩容和列表复制，能保证无特殊情况的O(1)时间复杂度）
• 向列表中间添加单个元素时，两者的时间复杂度均为O(n)，但ArrayList仍更快，因为其遍历速度远高于LinkedList
• 若已持有中间Node的引用，LinkedList向中间添加多个元素的时间复杂度为O(1)

实践层面：

• LinkedList在末尾添加/删除元素时比ArrayList慢（我猜测是因为ArrayList占用的内存更少）

这让我产生一个想法：实际上LinkedList仅在以下场景更具优势——从头部添加/删除元素，以及持有中间Node引用时向中间添加元素。不过如果我们不关心随机访问，可以用ArrayDeque替代LinkedList来解决头部增删的问题。如此一来，LinkedList就只剩一个优势：持有中间节点引用时向中间添加元素。除此之外的场景，我基本都不应使用LinkedList。我的这个想法是否正确？

你的判断基本正确，再补充几个关键细节帮你更清晰地把握：

1. 头尾操作的最优选择 #

你提到用ArrayDeque替代LinkedList处理头尾增删完全正确。ArrayDeque底层基于数组实现，没有LinkedList每个节点的额外内存开销，缓存命中率更高，实际运行速度普遍比LinkedList更快，且同样支持O(1)的头尾操作。如果只需要队列/双端队列的功能，ArrayDeque是首选。

2. LinkedList的核心不可替代场景 #

你指出的「持有中间Node引用时的中间插入/删除」确实是LinkedList几乎唯一的核心优势。此时无需遍历定位，直接修改节点指针就能完成操作，时间复杂度O(1)；而哪怕你知道索引，ArrayList插入中间元素也需要移动后续所有元素，时间复杂度始终是O(n)。

另外，如果你用ListIterator遍历LinkedList并在当前位置频繁插入/删除，效率也会远高于ArrayList——因为LinkedList的ListIterator是基于节点实现的，移动和修改都是O(1)，而ArrayList的ListIterator插入时仍需移动元素。

3. 实践中LinkedList性能劣势的深层原因 #

你观察到LinkedList尾部操作比ArrayList慢，除了内存占用，还有两个关键因素：

• 缓存友好性：ArrayList的元素是连续内存块，CPU缓存命中率远高于LinkedList的分散节点，遍历和尾插时的缓存效率差距会带来显著性能差异；
• 对象开销：LinkedList每次新增元素都要创建Node对象，额外的对象分配和GC开销会拖慢速度。

此外，LinkedList的随机访问（get(index)）性能极差，时间复杂度O(n)，而ArrayList是O(1)，这也是绝大多数场景优先选ArrayList的核心原因。

总结 #

日常开发中，除非你明确需要持有中间节点/迭代器位置进行高效中间修改，否则优先选择ArrayList；如果只需要头尾操作，用ArrayDeque替代LinkedList是更优的方案。

内容的提问来源于stack exchange，提问作者sebkaminski16