面试题：Java ArrayList删除操作的性能优化

优化删除操作性能的方法

倒序遍历删除：在Java中，ArrayList删除元素时会导致后续元素向前移动。如果正序遍历删除，每次删除都会使后续元素的索引发生变化，可能导致漏删元素。倒序遍历可以避免这个问题，并且减少元素移动的次数。例如：

import java.util.ArrayList;
import java.util.List;

public class ArrayListDeletion {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            list.add(i);
        }
        for (int i = list.size() - 1; i >= 0; i--) {
            if (list.get(i) % 2 == 0) {
                list.remove(i);
            }
        }
        System.out.println(list);
    }
}

使用Iterator：Iterator提供了一个安全的删除方式，它内部维护了当前遍历的位置，调用remove方法时能正确处理元素的删除和索引的调整。例如：

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class ArrayListDeletionWithIterator {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            list.add(i);
        }
        Iterator<Integer> iterator = list.iterator();
        while (iterator.hasNext()) {
            int num = iterator.next();
            if (num % 2 == 0) {
                iterator.remove();
            }
        }
        System.out.println(list);
    }
}

System.arraycopy方法在删除操作中的作用
- System.arraycopy是一个本地方法，用于将一个数组的内容复制到另一个数组或同一数组的不同位置。在ArrayList删除元素时，ArrayList内部通过System.arraycopy方法将删除元素位置之后的元素向前移动，以填补删除元素造成的空缺。它的效率较高，因为它是由底层的C或C++代码实现的，减少了Java层面的开销。

结合示例代码说明如何使用它来减少数据移动的开销

以下是模拟ArrayList删除元素时使用System.arraycopy的简化示例：

public class ManualArrayListDeletion {
    private int[] elements;
    private int size;

    public ManualArrayListDeletion(int initialCapacity) {
        elements = new int[initialCapacity];
        size = 0;
    }

    public void add(int element) {
        if (size == elements.length) {
            resize();
        }
        elements[size++] = element;
    }

    private void resize() {
        int newCapacity = elements.length * 2;
        int[] newElements = new int[newCapacity];
        System.arraycopy(elements, 0, newElements, 0, size);
        elements = newElements;
    }

    public void remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        System.arraycopy(elements, index + 1, elements, index, size - index - 1);
        size--;
    }

    public int get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        return elements[index];
    }

    public int size() {
        return size;
    }

    public static void main(String[] args) {
        ManualArrayListDeletion list = new ManualArrayListDeletion(5);
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.remove(2);
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }
    }
}

在上述代码的remove方法中，使用System.arraycopy将index + 1位置开始的元素向前移动一个位置，覆盖掉要删除的元素位置，从而实现删除操作，减少了数据移动的开销。同时，size减1表示实际元素数量减少。

星途面试题库

面试题：Java ArrayList删除操作的性能优化

知识考点

面试题答案