ArrayList 与 LinkedList：底层结构、扩容与选型

普通列表场景通常优先 ArrayList。LinkedList 的“插入删除快”有前提：先定位节点可能仍需线性遍历，不能只比较真正修改指针的那一步。

底层结构与复杂度#

操作	ArrayList	LinkedList
按下标访问	数组定位，O(1)	从较近的一端遍历，O(n)
尾部添加	均摊 O(1)，扩容时 O(n)	O(1)
按下标在中间插入/删除	需要移动元素，O(n)	定位通常 O(n)，修改链接 O(1)
通过已定位的链表迭代器增删	不适用相同的节点模型	修改链接 O(1)
内存与局部性	保存连续的引用，局部性通常较好	节点额外保存前后链接，开销较大

ArrayList 的连续存储指内部数组槽位连续，不代表槽位引用的所有对象也连续分配。LinkedList 即使不用移动元素，也有节点分配和缓存局部性方面的成本。

ArrayList 怎样扩容？#

以 OpenJDK 8 常见实现为例，无参构造时使用空数组，第一次添加元素通常分配容量 10；容量不够时通常按旧容量的 1.5 倍计算新容量，再考虑最低需求和数组上限，复制旧元素。

1
添加元素 → 容量是否足够？
2
           ├─ 足够：写入并更新 size
3
           └─ 不够：分配更大的数组 → 复制 → 写入

size 表示已有元素数量，capacity 表示内部数组可容纳数量。扩容比例属于实现细节，不是 List 接口保证。知道大致元素数量时，可以通过初始容量减少重复扩容；预分配过大也会浪费内存。

为什么不能并发 add？#

普通 ArrayList 不保证线程安全，多个线程同时修改 size 和数组内容可能导致丢失更新、状态不一致等。仅仅提前分配足够容量也不能让并发写入变安全。

根据场景选择外部加锁、同步包装或 CopyOnWriteArrayList。后者写入时复制数组，更适合读多写少、可接受快照可见性的场景，不适合频繁修改大列表。

队列一定用 LinkedList 吗？#

不一定。普通非并发队列、栈或双端队列通常可以考虑 ArrayDeque，它基于可扩容数组，没有每个链表节点的额外分配成本，不允许 null。需要阻塞或并发访问时，选择对应的并发队列，而不是把普通 LinkedList 直接共享给多个线程。

面试回答模板#

ArrayList 基于动态数组，随机访问 O(1)，尾部追加均摊 O(1)，中间增删要移动元素；LinkedList 基于双向链表，定位节点通常 O(n)，已定位后的链接修改是 O(1)。普通列表多数优先 ArrayList，队列可考虑 ArrayDeque。ArrayList 容量不足时扩容并复制数组，已知规模时可以合理预分配，普通 ArrayList 不能直接并发修改。

自测#

LinkedList.add(index, value) 一定是 O(1) 吗？不是，要算定位成本。
ArrayList 每次 add 都是 O(1) 吗？不是，扩容那一次可能 O(n)，尾部追加是均摊 O(1)。
已预分配的 ArrayList 能安全并发写吗？不能。