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

# 标准答案

ArrayListremove(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

拆解分析

  1. 检查索引合法性,防止 IndexOutOfBoundsException
  2. 记录被删除的元素,以便返回。
  3. 调用 System.arraycopy
    • 若删除的不是最后一个元素,后续元素需要整体前移。
    • 移动范围 = newSize - index,即删除点之后的所有元素前移。
  4. 置空最后一个元素,防止内存泄漏(避免引用对象无法被 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();
1

# 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); // 删除所有偶数元素
1
# (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();
1

# 3. remove(int index)remove(Object o) 有什么区别?

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

# 4. 如何减少 System.arraycopy 影响?

  • 批量删除,减少数组拷贝的次数。
  • 倒序删除,避免元素前移。
  • 切换数据结构,如 LinkedListConcurrentLinkedQueue

# 相关面试题

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