# 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
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
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
2
移位过程:
原始: [1, 2, 3, 4, 5]
删除3:
[1, 2, 4, 5]
1
2
3
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
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
影响?
- 批量删除,减少数组拷贝的次数。
- 倒序删除,避免元素前移。
- 切换数据结构,如
LinkedList
或ConcurrentLinkedQueue
。
# 相关面试题
- 为什么
ArrayList
删除操作比LinkedList
慢? - 如何减少
ArrayList
删除的性能开销? - 为什么
ArrayList
适合查询多、删除少的场景? remove(int index)
和remove(Object o)
的区别?- 为什么
ArrayList
不自动缩容?如何优化?