跳到主要内容
约 8 分钟3 张卡

ArrayList

ArrayList 用连续的引用数组保存元素，支持按下标读取和动态增删。本文先区分元素数量与数组容量，再解释随机访问、扩容和中间搬移的成本。最后说明子列表共享数据带来的修改与内存保留问题。实现细节以 OpenJDK 21 为准。

1. 面试核心​

先记住这几条，再读正文
  • 按下标访问。 ArrayList 的 get、set 按下标访问，成本为 O(1)。
  • 扩容策略。 OpenJDK 21 的 ArrayList 扩容时首选增加旧容量的一半，并满足本次操作所需的最小容量。卡 · size 与 capacity
  • 摊销与单次成本。 ArrayList 尾部追加的摊销成本为 O(1)，触发扩容时的单次复制成本为 O(n)。卡 · size 与 capacity
  • 中间增删。 ArrayList 在中间插入和删除元素时需要搬移后续引用，最坏成本为 O(n)。卡 · 随机访问
  • 子列表视图。 subList 与原列表共享数据，复制子列表可以隔离后续的结构变化。卡 · 子列表的内存保留

2. size 与 capacity​

必会卡 · ArrayList 怎样扩容，指定初始容量有什么作用

创建列表时，要区分元素数量和数组容量。size 是已经放入列表的元素数量，capacity 是内部数组的长度。下面的代码只预留存储空间：

List<String> values = new ArrayList<>(100);
System.out.println(values.size()); // 0

构造参数 100 预留 100 个引用槽，size 仍是 0。此时调用 get(0) 会抛出 IndexOutOfBoundsException。

数组中连续排列的是对象引用，也就是用于找到对象的值。元素对象位于各自的堆位置，所以引用连续并不表示对象本身也连续。

3. 随机访问​

必会卡 · ArrayList 与 LinkedList 应该怎样选择

读取第 i 个元素时，ArrayList 先检查 0 <= i < size，再读取内部数组对应位置：

User user = users.get(i);

下标可以直接定位数组槽，所以 get 和 set 的成本都是 O(1)。顺序遍历会连续读取相邻引用，有利于 CPU 缓存和预取。缓存保存近期访问的数据，预取则提前加载即将使用的数据。相比沿链表访问分散的节点，这种布局减少了跳转带来的开销。

复杂度描述的是操作成本随数据量增长的趋势。即使同为 O(n)，连续复制数组与逐个访问链表节点的实际耗时也会不同。因此，比较性能时还要固定数据规模和访问方式。

4. 尾部追加与扩容​

必会卡 · ArrayList 怎样扩容，指定初始容量有什么作用

只要内部数组还有空位，尾部 add 就把引用写到 elementData[size]，再增加 size：

users.add(user);

容量不足时，OpenJDK 21 会通过分配与复制扩大存储空间：

  1. 根据最小需要容量计算新容量。
  2. 首选增加旧容量的一半，并满足最小所需容量。
  3. 申请新的引用数组。
  4. 复制现有元素引用。
  5. 把内部字段指向新数组。

首选增加一半，也就是按旧容量约 1.5 倍增长。一次需要加入更多元素时，新容量还要满足最小所需容量。这个比例属于 OpenJDK 的实现细节，API 保证的是尾部追加具有摊销常数时间。

4.1 摊销复杂度​

摊销复杂度把一段操作的总成本分摊到每次操作上。连续追加时，多数操作只写入一个数组槽，少数操作才需要分配数组并复制引用。容量按比例增长后，前几次复制的数组都比最后一次小。累计复制量随追加数量线性增长，所以每次追加的摊销成本是 O(1)。

摊销成本描述整段追加的平均开销，单次扩容仍需 O(n) 的复制。大数组恰好在请求处理中扩容时，这次调用就会变慢。因此，延迟敏感的代码可以提前预留容量。

5. 初始容量​

必会卡 · ArrayList 怎样扩容，指定初始容量有什么作用

已知大致元素数量时，可以预留容量：

List<OrderLine> lines = new ArrayList<>(expectedLineCount);

预留容量可以减少扩容带来的三类开销：

  • 分配新数组的次数减少。
  • 已有元素引用被复制的次数减少。
  • 新旧数组同时占用内存的峰值降低，因为旧数组还要等待垃圾回收（GC）。

预留容量应参考实际的元素数量分布。大量小列表都预留大数组时，空槽会长期占用内存，甚至超过减少扩容带来的收益。

已有列表需要追加大量元素时，可以先调用 ensureCapacity。元素减少后，trimToSize 可以将数组缩小到当前元素数量。缩容也要分配和复制，所以适合长期保留且大小已稳定的列表，频繁调用反而增加开销。

6. 中间插入与删除​

必会卡 · ArrayList 与 LinkedList 应该怎样选择

在索引位置插入元素时，后面的引用需要整体向右移动：

users.add(0, user);

删除后，后续引用向左移动。最后一个旧位置置为 null，释放多余引用。对象的其他引用也消失后，GC 才能回收它。

根据是否需要查找和搬移，可以区分以下三类操作成本：

  • 尾部追加直接利用空槽，摊销成本为 O(1)。
  • 中间插入和删除需要搬移后续引用，最坏成本为 O(n)。
  • 按值删除需要先线性查找目标，再搬移后续引用。

批量删除时，倒序按索引删除可以避免索引错位，但仍会反复搬移引用。OpenJDK 21 的 removeIf 会集中压缩保留元素，减少重复搬移。也可以一次筛选出需要保留的元素，再组成结果列表。

后续阅读：subList 视图

7. subList 视图​

subList 可以查看原列表的一段范围，返回的是共享数据的视图。例如，下面的 page 对应从 from 到 to 之前的元素：

List<User> page = users.subList(from, to);

通过视图替换或增删元素，会影响原列表。原列表如果绕过视图增删元素，就发生了视图未跟踪的结构修改。此时继续使用视图的语义未定义。OpenJDK 会通过修改计数尽力检测这类错误，并抛出 ConcurrentModificationException。

需要保存独立的列表结构时，可以显式复制：

List<User> page = new ArrayList<>(users.subList(from, to));

子列表还会保留根列表，内存影响见 子列表的内存保留。

8. 线程安全​

ArrayList 不提供并发修改保证。下面的复合操作不是原子的：

if (!users.contains(user)) {
    users.add(user);
}

两个线程都通过检查后，会分别追加同一个元素。要避免这类竞争，需要根据数据的共享方式选择方案：

  • 列表只由一个线程访问时，使用线程封闭，让其他线程通过任务或消息提交修改。
  • 多个线程共享可变列表时，用同一把锁保护完整的检查与追加。
  • 读者只需要固定结果时，发布安全构造的不可变快照。
  • 需要特定并发操作时，选择提供相应原子方法的并发容器。

Collections.synchronizedList 为单个方法提供同步，遍历和复合操作仍需在包装列表的同一把锁上完成。具体规则见 集合迭代器。

核心阅读到这里

检查能否解释

解释随机访问、追加、扩容和中间插入的成本，区分单次操作与摊销复杂度。

ArrayList 怎样扩容，指定初始容量有什么作用？ 查看题目与参考回答 →
下一篇：HashMap返回主题目录查看其他复习主题

9. 子列表的内存保留​

必会卡 · 只保留一个很小的 subList，为什么仍会占用大量内存？

只保留一页视图，也会让原列表的其他元素继续占用内存。原因是 OpenJDK 21 的 SubList 保存了根列表 root、父视图 parent 和偏移量。根列表仍可通过这些引用访问，所以它的底层数组及数组引用的其他元素也会继续存活。

需要长期保存一页结果时，可复制这一页：

List<String> page = new ArrayList<>(all.subList(0, 10));

新列表仅保存这 10 个元素引用。复制后的元素仍是原对象；可变元素需要单独管理。

10. 常见问题​

10.1 默认容量与延迟分配​

OpenJDK 21 的无参构造先使用共享空数组，等到首次单元素 add 时再分配容量 10。显式指定容量 0 时，首次单元素 add 分配的容量是 1。这些数值属于实现策略，业务逻辑应通过 size 判断已有元素。

10.2 Arrays.asList 的列表类型​

10.3 Integer 列表的删除重载​

10.4 ArrayList 与数组的开销​

11 · 面试题卡片​

先想答案，再翻面先在心里答一遍，再点开卡片对照参考回答。卡片之间可以左右切换，看完会回到这里。
逐张翻看 3 张 →
size 与 capacity必会
ArrayList 怎样扩容，指定初始容量有什么作用
一嗨租车美团
考察 3 点 · 相关 §2 §4 §5
随机访问必会
ArrayList 与 LinkedList 应该怎样选择
字节跳动阿里巴巴美团
考察 3 点 · 相关 §3 §6
子列表的内存保留必会
只保留一个很小的 subList，为什么仍会占用大量内存？
本站自测
考察 1 点 · 相关 §9

11.1 ArrayList 怎样扩容，指定初始容量有什么作用​

出现公司：一嗨租车、美团

考察重点

  • 说明 size 与 capacity 分别表示什么，以及它们如何对应内部引用数组。
  • 解释扩容为什么需要复制，以及连续追加为什么具有摊销常数成本。
  • 说明预留过小和过大分别产生什么成本。

相关内容：size 与 capacity、尾部追加与扩容、初始容量。

参考回答

ArrayList 容量不足时会分配更大的数组并复制引用，预留初始容量可以减少这个过程。

容量还有空位时，追加只需写入 size 对应的槽位，再增加元素数量。OpenJDK 21 扩容时首选增加旧容量的一半，最小所需容量更大时则满足该容量。

容量按比例增长，所以连续追加的摊销成本是 O(1)，单次扩容仍为 O(n)。已知大致数量时预留容量，可以减少分配、复制和新旧数组共存的内存峰值。预留过大则让空槽长期占用内存。

返回本轮自测与下一篇

11.2 ArrayList 与 LinkedList 应该怎样选择​

出现公司：字节跳动、阿里巴巴、美团

考察重点

  • 说明随机访问、定位和节点修改的不同成本。
  • 解释连续引用数组为什么有利于缓存，以及链表节点会增加哪些内存开销。
  • 说明“插入多就用 LinkedList”为什么缺少前提。

相关内容：随机访问、中间插入与删除。

参考回答

按索引读取或尾部追加时，优先考虑 ArrayList。

它的随机访问为 O(1)，尾部追加摊销 O(1)。连续引用数组也减少了节点跳转。

LinkedList 按索引定位为 O(n)，每个元素还需要单独的节点和前后引用。已有迭代位置并频繁在该处插入删除时，局部修改为 O(1)，可以省去查找和数组搬移。因此，要结合定位方式与节点分配成本选择；单线程队列或栈可优先考虑 ArrayDeque。

11.3 只保留一个很小的 subList，为什么仍会占用大量内存？​

出现公司：暂无已核验的公开来源（本站自测）

考察重点：解释子列表如何保留根列表，以及复制结构后为何仍共享元素对象。

相关内容：子列表的内存保留。

参考回答

子列表持有根列表，所以即使视图很小，也会间接保留整个底层数组。

数组还引用着其他元素，这些元素也会继续存活。OpenJDK 21 仍采用这种实现。

用 new ArrayList<>(subList) 复制需要的范围后，新列表只保存这一段的元素引用。释放原视图和原列表的其他引用后，其余元素才有机会被回收。副本仍共享原来的元素对象，所以可变字段需要单独管理。

12. 参考资料​

本页
有对应面试题卡片