ArrayList 这个知识点，我前后在面试里被人问了不下三次，每次都能问出新东西来。很多人的复习还停留在“动态数组、默认容量10、扩容1.5倍”这三句话上，可真到了手写扩容逻辑或者排查线上问题时，这三句话根本兜不住。我建议你把 ArrayList 当成一个“会在特定场景下踩坑的数据结构”来看，而不是一个背完就扔的集合类。这篇文章我尽量把底层原理、时间复杂度的成立条件、迭代器的坑、和 LinkedList 的对比逻辑一次讲透，适合准备校招复习、跳槽面试或者单纯想补源码知识的开发者。

1. 先看底层：ArrayList 不是一个“有长度的数组”

1.1 elementData 与 size 的本质区别

很多教材会把 ArrayList 简单描述成“可变长数组”，这话没错，但容易让人忽略一个关键事实：ArrayList 底层确实是一个数组，但这个数组的长度和“你往里面放了几个元素”是完全两回事。

源码里其实就两个核心成员：

transient Object[] elementData; private int size;

elementData是真正存储元素的数组，size是已经使用的元素个数。你往 ArrayList 里 add 一个元素，size加 1，但elementData.length不一定变化。只有当size即将超过elementData.length时，它才会触发扩容，去申请一块更大的数组。

这个区分为什么重要？因为很多人在手写一个简易版 ArrayList 时会犯一个错误：直接用数组的 length 当作元素个数。比如数组初始化长度是 10，你只放了 3 个元素，length 仍然是 10。如果你用 length 去做遍历，那返回的可能是null占位符，而不是真正的数据。我在给某位同学看他的模拟实现时，他遍历出来一堆 null，问题就出在这——size 必须在 add 和 remove 时被精细维护，它才是逻辑上“列表到底有多长”的唯一依据。

1.2 三个构造方法的入口差异

ArrayList 的构造函数看着简单，新手容易忽略细节：

• 无参构造：elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA，这是一个空数组，第一次 add 时才会扩容到默认容量 10。
• 指定初始容量构造：如果传入的initialCapacity > 0，直接 new 一个对应长度的数组；等于 0 时用EMPTY_ELEMENTDATA；小于 0 会抛IllegalArgumentException。
• 接收 Collection 的构造：先转成数组，再决定是否需要Arrays.copyOf成精确长度的数组。

这里有一个很值得关注的点：无参构造的第一轮扩容。add方法里有一个ensureCapacityInternal(size + 1)，它先判断elementData是不是那个空的默认数组，如果是，就取DEFAULT_CAPACITY(10) 和minCapacity中较大的一个。所以第一次 add 之后，底层数组长度就是 10。

很多人不知道的是，如果你提前知道数组会装很多元素，却还是用无参构造，那么前几次 add 会连续触发扩容，产生不必要的数组复制。我建议你对“容量”有概念，但别一开始就陷入“我到底要设置多少初始容量”的焦虑里，先搞清楚数量级就行。比如你要装 500 个元素，直接new ArrayList<>(500)就比无参构造一路扩上来干净很多。

2. 扩容机制：为什么说“扩容才是 ArrayList 性能的真正分水岭”

2.1 grow 方法的核心逻辑

扩容是 ArrayList 里最值得手推一遍的源码逻辑，它远比“扩容 1.5 倍”这六个字复杂。真正的逻辑在grow(int minCapacity)方法里，关键步骤是这样：

int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) { newCapacity = minCapacity; } if (newCapacity - MAX_ARRAY_SIZE > 0) { newCapacity = hugeCapacity(minCapacity); } elementData = Arrays.copyOf(elementData, newCapacity);

oldCapacity + (oldCapacity >> 1)就是 1.5 倍的位运算实现方式。为什么用右移而不是oldCapacity * 3 / 2？因为位运算的写法更直观地表达“在原来基础上再加一半”，而且在 Java 里整数运算本身不会有性能差异，主要是语义上更贴合容量估算的意图。

第二层判断很容易被忽略：如果minCapacity比 1.5 倍之后的结果还大，那说明调用方一次性要加入的数据量特别大，比如addAll一个几百个元素的集合，此时就要直接以minCapacity为准。第三层判断涉及MAX_ARRAY_SIZE，也就是Integer.MAX_VALUE - 8，这是 JVM 对数组长度的一个安全限制，超出后会走hugeCapacity，看是否溢出Integer.MAX_VALUE。

2.2 扩容带来的连锁影响

扩容的本质是“申请新数组 + 复制旧数据 + 丢弃旧数组”。这里有三层成本被打包在一起：

• 空间成本：扩容后旧数组如果没有被 GC 回收，短时间内可能存在两份数组引用。
• 时间成本：System.arraycopy是 native 方法，复制大数组很快，但终究是 O(n) 操作。
• 引用成本：扩容后所有元素的数组下标位置变了，如果你在其他地方保存过“这个元素在数组里的索引”，那索引本身不受影响，但如果是通过subList或toArray返回的引用，它们引用的仍是旧数组？不，toArray是新建数组，但subList是视图，视图底层仍然引用原elementData。一旦扩容后又被修改，视图和原列表的 modCount 就会同步变化，这个细节我后面讲迭代器时会再提。

从摊还分析的角度看，扩容虽然单次是 O(n)，但是因为扩容次数是 log(n) 量级，均摊到每次 add 上仍然是 O(1)。这个结论在面试里经常被追问，你应该能自己推出来：假设从容量 1 一路扩，每次扩容的复制总开销其实不超过 2n，所以 n 次 add 的总复杂度约 O(n)。

我在实测中发现一个很反直觉的点：如果你用无参构造，在容量 10 附近反复 add 和 remove，导致size刚好在 10 上下震荡，那么每次 add 都可能触发扩容，此时摊还分析的前提“扩容频率很低”就不成立了，性能会肉眼可见地下降。所以某些场景下，预先指定容量不只是优化，而是规避边界振荡的必要手段。

3. add/remove 的时间复杂度：教科书上的结论在什么条件下才成立

3.1 添加：尾部、指定位置、批量添加

“ArrayList 在尾部添加是 O(1)，在中间添加是 O(n)”这句话，可以说人人都会背，但我想让你注意“在尾部添加是 O(1)”成立的条件——它隐含的前提是“未发生扩容”。一旦扩容发生，单次 add 其实是 O(n) 的复制成本，只不过摊还后是 O(1)。

真正容易忽视的复杂度陷阱是addAll。很多代码里这样做：

List<String> list = new ArrayList<>(); list.addAll(hugeCollection); // 假设有 10000 个元素

如果不指定初始容量，addAll的第一次调用就会触发扩容。grow方法里对比的是minCapacity，这时minCapacity = size + 10000，所以一次性扩容直接到 10000，而不是 15。这个行为看起来“一步到位”，实际上它可能导致一次性申请超大数组，内存瞬时占用飙升。如果你知道要加 1 万个元素，最好先new ArrayList<>(10000)，让底层数组一开始就有足够空间，省去大数组复制的峰值消耗。

在列表中间插入指定位置的复杂度是System.arraycopy带来的 O(n - index) 移动成本。这里有一个很实际的用法：如果你要在一个 Arraylist 里频繁往头部插入元素，代码会非常难看：

list.add(0, value);

每次都要把所有已有元素整体右移一位，n 次操作的复杂度是 O(n^2)。这种情况我通常会先反问自己：是不是数据结构选错了？如果确实需要头部插入，并在某些场景下兼顾索引访问，可以用ArrayDeque或者用LinkedList结合具体访问模式来判断。甚至更简单的办法是反过来维护一个“倒序列表”，最后再Collections.reverse。

3.2 删除：把“移动元素”这件事算清楚

删除也有一个很容易被忽略的边界 case。remove(int index)和remove(Object o)是两条路线，前者按索引删，后者先indexOf找到第一个匹配元素，再按索引删。

按索引删除的逻辑：

int numMoved = size - index - 1; if (numMoved > 0) { System.arraycopy(elementData, index + 1, elementData, index, numMoved); } elementData[--size] = null;

两件事值得注意：第一，移动成本取决于被删元素的位置，删最后一个元素是 O(1)，删第一个元素是 O(n)；第二，最后那个elementData[--size] = null不是可有可无的细节。如果不把已经不用的 tail 位置置为 null，那么当 ArrayList 里存的是对象引用时，这个位置的旧对象会一直存活在数组里，造成“非典型内存泄漏”。在集合层面表现为：元素删了，但你无法通过 ArrayList 访问它，可它仍被数组强引用着，GC 永远回收不了。

还有一种批量删除的方式，比如removeIf和removeAll。它们底层会走batchRemove逻辑，用双指针“覆盖移动”而不是逐个删除。对一个 10 万元素的列表执行removeIf删除其中一半，用时比“遍历再逐个 remove”快得多。原因很简单，逐删涉及到频繁的数组段移动，而batchRemove只做一次覆盖，最后统一清理尾部空位。复习到删除这一块，强烈建议你把removeIf的实现翻出来看一遍，能完全理解“维护读写双指针”的意义，比背任何复杂度结论都有用。

4. 遍历、迭代器与 fail-fast：面试里最容易翻车的角落

4.1 modCount 与 ConcurrentModificationException

如果你在迭代一个 ArrayList 的过程中直接list.remove(...)，大概率会碰到ConcurrentModificationException。很多新手第一反应是“多线程并发修改了”，但哪怕你的程序是单线程，也照样会抛这个异常，原因在modCount。

modCount是 ArrayList 用来统计“结构性修改次数”的字段。所谓结构性修改，就是会让数组长度或 size 发生本质变化的操作，比如 add、remove、clear。单纯设置某个位置的值，比如set(index, value)，不会修改 modCount。迭代器内部保存了一个初始时的expectedModCount，每次next()时都会检查iterator.modCount != ArrayList.this.modCount是否成立，一旦发现不等，立即抛出异常。

这个机制叫 fail-fast，意思是不保证在检测到并发修改后一定抛异常，而是“尽量能抛就抛”。为什么不是万无一失？因为modCount是 int 类型，如果多线程修改刚好让它变了两次，回到与原值相等的结果，那理论上可能检测不到，虽然概率极低，但设计者并没有承诺绝对的并发安全。这也解释了为什么官方文档会强调：ArrayList 非线程安全——fail-fast 只是错误检测，不是并发保护。

4.2 边遍历边删除的三种正确姿势

复习完迭代器必考的禁止点之后，要顺手掌握实际开发里边遍历边删除的正确姿势。我常用的三种方案：

第一种：使用Iterator.remove()。这是迭代器自带的删除方法，它会把expectedModCount同步成最新的 modCount，所以不会抛出异常。

Iterator<String> iterator = list.iterator(); while (iterator.hasNext()) { if (iterator.next().equals("特殊值")) { iterator.remove(); } }

第二种：先收集再统一删除。适合删除条件复杂或需要依赖索引的场景，先用另一个列表记录需要删除的元素，遍历结束后调用removeAll。这种方法不会触发 fail-fast，因为遍历期间没有结构性修改。

第三种：直接用removeIf。这是最省心的写法：

list.removeIf(s -> s.equals("特殊值"));

底层就是batchRemove，效率高，语义清楚。三种方案里，我实际项目中用removeIf最多，它几乎就是为“按条件批量删除”这种高频需求准备的。

还有一个衍生的问题，很多人在删除多个元素时写这样的循环：

for (int i = 0; i < list.size(); i++) { if (list.get(i) == null) { list.remove(i); } }

删完第 i 个之后，后面的元素全部左移，但 i 还在继续自增，于是你“跳过了”原来紧跟着的那个元素。正确做法要么倒序遍历，要么每次删除后把 i 减一。这种错误在真实代码里出现频率极高，值得写在复习清单上。

5. ArrayList 与 LinkedList 的选择：别再背“增删快”的口诀了

5.1 从随机访问和缓存局部性看性能差异

教科书上常写“LinkedList 增删快、ArrayList 查询快”。这句话误导性很强，因为它没有限定“增删的位置”。基于数组的 ArrayList 在头部增删确实是 O(n)，因为要搬数据；基于双向链表的 LinkedList 在头部增删确实是 O(1)。但如果是在尾部增删，ArrayList 也是均摊 O(1)，反而节点引用带来的额外对象开销让 LinkedList 更“重”。

更关键的是随机访问差异。ArrayList 的get(index)是真正的 O(1)，底层就是elementData[index]数组寻址；LinkedList 的get(index)需要从头或从尾双向遍历，是 O(n)。

缓存局部性也是很多人忽略的因素。ArrayList 的元素在一个连续的内存数组里，遍历时CPU Cache命中率高；LinkedList 的每个节点是独立对象，内存不一定连续，遍历时频繁跳转地址，缓存命中率低。即使两者的算法复杂度相同，实际耗时也往往有明显差距。我用 10 万个整数的逗留测试来看，LinkedList 的普通遍历要比 ArrayList 慢一个数量级。

5.2 我什么时候真的会选 LinkedList

基于上面的分析，我的个人结论是：在现代 JDK 项目里，LinkedList 的实际使用场景少得可怜。如果在“中间插入”场景真的非常多，我会先考虑ArrayDeque或者自定义分段结构，而不是无脑选 LinkedList。

LinkedList 的节点对象本身需要维护前后引用和 data 引用，在存储小型元素时，内存膨胀非常明显。比如你存 10 万个 Integer，ArrayList 不过是 10 万次装箱 + 一个 10 万长度的数组；LinkedList 则额外多了 10 万个 Node 对象，每个 Node 还有两个引用字段。这个内存差距在数据量大时非常扎眼。

那有没有真的适合 LinkedList 的场景？我认为有，但要满足两个条件：一，主要在头部/尾部做增删；二，不怎么需要按下标随机访问。比如实现一个最近访问记录，同时按访问顺序维护，按头插尾删的方式维护，这时 LinkedList 的节点增删确实是 O(1)，且不需要扩容，听起来很合适。但是，如果你连按下标访问的需求都没有，ArrayDeque可能是更好的选择，它有栈和队列的通用操作，底层也是数组，缓存局部性更好。

再说一个“反直觉”的点：即使你要大量做指定位置插入，LinkedList 的定位成本也不能忽略。想在“第 50000 个元素”后面插入一个元素，LinkedList 光找到那个节点就要遍历 50000 次，然后才是 O(1) 的节点链接操作，整体上还是 O(n)。所以“增删快”只适合“插入位置已经通过迭代器持有节点”的场景，而不是“我要找位置再插”的场景。这也是为什么我只推荐 LinkedList 在队列/栈式用法下使用。

6. 复习最后阶段：几个必须动手验证的边界情况

6.1 把容量和 size 的边界条件写出来

纸上谈兵不如动手跑一段代码。我建议你准备一个空项目，把这些边界全部打印出来：

public static void main(String[] args) { ArrayList<Integer> list = new ArrayList<>(); System.out.println("size = " + list.size()); list.add(1); // 通过反射读取 elementData.length，顺便观察扩容 System.out.println("cap = " + getCapacity(list)); } private static int getCapacity(ArrayList<?> list) { try { java.lang.reflect.Field field = ArrayList.class.getDeclaredField("elementData"); field.setAccessible(true); return ((Object[]) field.get(list)).length; } catch (Exception e) { throw new RuntimeException(e); } }

用反射读取私有字段去观察容量，虽然生产环境不推荐这么做，但复习阶段这是理解扩容最直观的手段。你会看到无参构造时，第一次 add 之后容量变成 10，后面每次跨过 10、15、22、33、49、73、109 这个序列扩容。这里每个数字都是前一个数字的 1.5 倍取整，亲手观测一遍，比你背十遍结论都牢。

考虑一个边界：初始容量为 0 的 ArrayList（new ArrayList<>(0)），第一次 add 走的是EMPTY_ELEMENTDATA分支吗？不是，因为指定容量 0 时elementData是EMPTY_ELEMENTDATA，而add里的ensureCapacityInternal会先检查elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA，由于它不相等，所以不会把容量顶到 10，而是直接取minCapacity = 1，最后grow(1)得到容量 1。换句话说，容量 0 的 ArrayList 扩容序列是 1、2、3、4、6、9、13…… 这套差异很多人没注意过，但在某些“很在意初始容量”的审查场景中，确实会被问出来。

6.2 一个内部数组泄漏的“事故现场”

复习到内存时，我建议你自己构造一个“toArray 和 get 数组地址”的对比样例。ArrayList 的toArray()会返回一个新数组，修改返回数组不影响 ArrayList 内部；但如果你用反射拿到了内部elementData并直接修改，那整个 ArrayList 就失控了。生产环境不会有人反射去改它，但subList的行为却会在不知不觉中“泄漏”底层数组的视图。

List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5)); List<Integer> sub = list.subList(1, 3); list.clear(); sub.size(); // 这里会抛出 ConcurrentModificationException

因为subList是视图，它记录了父列表的parentOffset和modCount，父列表clear()后 sub 的 modCount 对不上，访问就会抛异常。反过来，如果你拿到 sub 之后往 sub 里add，父列表也会看到变化，这就是视图的双向绑定。很多人以为subList是“新列表”，其实它只是原列表的一个窗口。在使用时，要么马上用它做完操作，要么别让父列表在窗口生存期间发生结构性修改。

最后分享一个我在实际写代码时的习惯：凡是看到new ArrayList<>(collection)这种初始化，我都会想一下 collection 是不是可能为空。空集合转 ArrayList 没问题，但如果是Collections.emptyList()转过去，会生成一个容量 0 的内部数组；后续 add 时扩容到 1，可能造成比预期更多的扩容。虽然这点开销通常无足轻重，但养成“猜测初始容量”的习惯，能让你的代码在高并发高频场景下少一些隐藏抖动。

复习 ArrayList 这件事，我一直觉得是在复习“数组在动态场景下的代价”。它帮我们理解元素移动、容量扩张、视图一致性这些概念，而这些概念在你以后看 HashMap、看各种 Queue 的实现时都会反复出现。你可以不用记住我上面写的每个字段名，但size和capacity的差异、扩容的触发条件、结构性修改和迭代器的关系，必须能从头讲清楚。把这几条打通了，ArrayList 这块基本上就真的复习到位了。