# 7. ArrayList 的 `remove` 方法是如何实现的？为什么删除操作性能较差？

# 标准答案

ArrayList 的 remove(int index) 方法在删除元素时，会调用 System.arraycopy 将后续元素向前移动，以保持数组的索引连续性，导致时间复杂度为 O(n)。如果删除的是靠前的元素，需要移动更多的元素，性能最差。因此，在频繁删除的场景下，应避免使用 ArrayList，或者采用批量删除、倒序删除等优化策略，甚至直接使用 LinkedList 以降低删除成本。

# 答案解析

# 1. `ArrayList.remove(int index)` 方法的底层实现

ArrayList 底层是动态数组（Object[] elementData），删除元素时必须保持数组的连续性，因此后续元素必须前移，从而导致 O(n) 复杂度。

# JDK 18 源码解析

public E remove(int index) {
    Objects.checkIndex(index, size); // 校验索引合法性
    final Object[] es = elementData;
    @SuppressWarnings("unchecked") E oldValue = (E) es[index]; // 记录被删除的元素
    fastRemove(es, index);
    return oldValue;
}

1
2
3
4
5
6
7

核心方法 fastRemove：

private void fastRemove(Object[] es, int index) {
    final int newSize;
    if ((newSize = size - 1) > index) { // 若删除的不是最后一个元素，则进行移动
        System.arraycopy(es, index + 1, es, index, newSize - index);
    }
    es[size = newSize] = null; // 将最后一个元素置空，避免内存泄漏
}

1
2
3
4
5
6
7

拆解分析：

检查索引合法性，防止 IndexOutOfBoundsException。
记录被删除的元素，以便返回。
调用 System.arraycopy：
- 若删除的不是最后一个元素，后续元素需要整体前移。
- 移动范围 = newSize - index，即删除点之后的所有元素前移。
置空最后一个元素，防止内存泄漏（避免引用对象无法被 GC 回收）。

# 示例

List<Integer> list = new ArrayList<>(List.of(1, 2, 3, 4, 5));
list.remove(2); // 删除索引 2 位置的元素

1
2

移位过程：

原始： [1, 2, 3, 4, 5]
删除3：
       [1, 2, 4, 5]

1
2
3

移动元素数量 = size - index - 1，即 O(n) 复杂度。

# 2. 为什么 `ArrayList` 删除操作性能较差？

# （1）删除元素后，后续元素必须前移

时间复杂度 O(n)，删除位置越靠前，移动的元素越多，开销越大。
若数据量过大，删除操作会影响整体性能。

# （2）`System.arraycopy` 的开销

System.arraycopy 采用 memcpy 级别的内存拷贝，适用于批量复制，但对于大量随机删除操作仍然是瓶颈。
大数据量下，频繁删除会导致 CPU 缓存失效，影响 Cache Line 命中率，从而降低性能。

# （3）删除后不会自动缩容

ArrayList 不会自动缩小 elementData 的数组容量，即使删除了很多元素，内存仍然被占用。
可以手动调用 trimToSize() 释放多余空间：

list.trimToSize();

# 3. 如何优化 `ArrayList` 删除操作？

# （1）倒序删除，减少 `System.arraycopy` 调用

顺序删除会导致后续所有元素不断前移，如果倒序删除，则不会影响未删除的元素。

for (int i = list.size() - 1; i >= 0; i--) {
    list.remove(i);
}

1
2
3

# （2）批量删除，避免重复拷贝

使用 removeIf 方法，一次性删除多个元素，避免 System.arraycopy 反复调用：

list.removeIf(e -> e % 2 == 0); // 删除所有偶数元素

# （3）切换数据结构

ArrayList 适合 “查询多，删除少” 的场景。
如果频繁删除，推荐使用 LinkedList，因为删除仅需修改前后指针，时间复杂度 O(1)。

# 4. 适用场景

场景	ArrayList（推荐）	LinkedList
查询多，删除少	✅ 快（O(1)）	❌ 慢（O(n)）
频繁插入/删除	❌ 慢（O(n)）	✅ 快（O(1)）
顺序遍历	✅ CPU 预取优化	❌ CPU 预取差
删除大量元素	❌ 删除成本高	✅ 快
队列、栈结构	❌ 不适合	✅ 适合

# 深入追问

# 1. 为什么 `ArrayList` 适合查询多、删除少的场景？

查询 O(1)：数组支持随机访问，时间复杂度 O(1)。
删除 O(n)：删除后需要移动元素，数据量大时代价很高。

# 2. 为什么 `ArrayList` 不会自动缩容？

ArrayList 采用预分配策略，避免频繁扩缩容影响性能。
若需要手动缩容，调用 trimToSize() 释放空间：

list.trimToSize();

# 3. `remove(int index)` 和 `remove(Object o)` 有什么区别？

remove(int index): 按照索引删除，需要移动元素（O(n)）。
remove(Object o): 先查找对象索引（O(n)），再调用 remove(index)，比索引删除更慢。

# 4. 如何减少 `System.arraycopy` 影响？

批量删除，减少数组拷贝的次数。
倒序删除，避免元素前移。
切换数据结构，如 LinkedList 或 ConcurrentLinkedQueue。

# 相关面试题

为什么 ArrayList 删除操作比 LinkedList 慢？
如何减少 ArrayList 删除的性能开销？
为什么 ArrayList 适合查询多、删除少的场景？
remove(int index) 和 remove(Object o) 的区别？
为什么 ArrayList 不自动缩容？如何优化？

← 6. ArrayList和LinkedList在遍历时的性能有什么区别？适用于哪些场景？ 8. 为什么LinkedList的get(index)方法时间复杂度是O(n)？ →

# 7. ArrayList 的 remove 方法是如何实现的？为什么删除操作性能较差？