ArrayList 与 LinkedList 有什么区别？

直接回答

ArrayList 用可增长数组保存元素引用，按下标访问快，尾部追加的摊销成本低；LinkedList 用双向链表，按下标访问要沿节点寻找。链表已定位节点后的插删成本低，但按位置插删还要先定位。因此不能简单说“查询用数组，增删用链表”，普通列表通常先考虑 ArrayList。

讲清原理

ArrayList 的 get 是 O(1)，中间插入会移动后续引用，通常 O(n)。LinkedList 的 get(i) 会从较近的一端寻找，最坏 O(n)；通过已经走到该处的 ListIterator 插删，则不必再次全程定位。

链表每个节点还需要前后引用等开销，数组也可能有未用容量。实际内存和耗时受 JVM、数据规模与操作位置影响，不宜给出脱离测量的固定倍数。

例子与易错点

在有十万项的 LinkedList 上反复调用 get(i)，会一遍遍走链，整次遍历可能退化为 O(n²)。增强 for 通过迭代器逐项前进，总体才是 O(n)。

LinkedList 还实现 Deque，能从两端操作；但只是需要普通队列或栈时，也应考虑 ArrayDeque。应根据操作位置和访问方式选择，别只凭“链表适合增删”下结论。

相关题：第 23 题、第 25 题、第 35 题、第 38 题。