Что произойдет под капотом у ArrayList при удалении всех элементов?

Что происходит под капотом ArrayList при удалении элементов

Когда мы удаляем элементы из ArrayList, происходит сложный процесс переупорядочивания памяти. Понимание этого механизма критично для оптимизации производительности.

Структура ArrayList

// Внутренняя структура ArrayList
public class ArrayList<E> extends AbstractList<E> {
    private Object[] elementData;  // Массив с элементами
    private int size;              // Текущее количество элементов
    private static final int DEFAULT_CAPACITY = 10;
}

// Пример состояния
ArrayList<Integer> list = new ArrayList<>();
list.add(10);
list.add(20);
list.add(30);
list.add(40);

// Внутри:
// elementData = [10, 20, 30, 40, null, null, null, ...]
// size = 4
// capacity = 10

Удаление по индексу (remove(index))

public E remove(int index) {
    // 1. Проверка диапазона
    rangeCheck(index);
    
    // 2. Получение старого значения
    E oldValue = elementData(index);
    
    // 3. КРИТИЧЕСКИЙ МОМЕНТ: сдвиг элементов
    int numMoved = size - index - 1;  // Сколько элементов после удаляемого?
    if (numMoved > 0) {
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);
        // Копирует элементы: сдвигает влево на 1 позицию
    }
    
    // 4. Уменьшение размера
    elementData[--size] = null;  // Помощь GC
    
    return oldValue;
}

Пример удаления с визуализацией

ArrayList<Integer> list = new ArrayList<>();
list.add(10);
list.add(20);
list.add(30);
list.add(40);
list.add(50);

// До удаления:
// elementData: [10, 20, 30, 40, 50, null, null, null, null, null]
// size: 5
// capacity: 10

list.remove(1);  // Удаляем 20

// После удаления:
// elementData: [10, 30, 40, 50, null, null, null, null, null, null]
//              ^   ^  ^  ^
//              |   |  |  смещены влево на 1
// size: 4
//
// Что произошло:
// System.arraycopy(elementData, 2, elementData, 1, 3)
// Скопировали 3 элемента (30, 40, 50) с позиции 2 на позицию 1

Удаление элемента по значению (remove(Object))

public boolean remove(Object o) {
    // 1. Ищет элемент в массиве
    for (int index = 0; index < size; index++) {
        if (o.equals(elementData[index])) {
            // 2. Удаляет при нахождении
            fastRemove(index);
            return true;
        }
    }
    return false;
}

private void fastRemove(int index) {
    // Похоже на remove(int), но без проверок
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);
    elementData[--size] = null;
}

Удаление всех элементов (clear())

public void clear() {
    // 1. Зачищает все ссылки
    for (int i = 0; i < size; i++)
        elementData[i] = null;  // Помощь GC
    
    // 2. Сбрасывает счётчик
    size = 0;
    
    // 3. elementData (capacity) НЕ меняется!
    // Массив остаётся того же размера
}

// Пример:
ArrayList<String> list = new ArrayList<>();
for (int i = 0; i < 1000; i++) {
    list.add("item" + i);
}

list.clear();
// Пока что:
// size = 0
// Но внутренний массив ВСЕ ЕЩЁ занимает 1000+ слотов памяти!
// Это может быть проблемой для долгоживущего листа

Проблема памяти при многократном удалении

// НЕОПТИМАЛЬНО: утечка памяти
public class MemoryLeak {
    private ArrayList<String> cache = new ArrayList<>();
    
    public void process() {
        // Добавляем 10 млн элементов
        for (int i = 0; i < 10_000_000; i++) {
            cache.add(new String("data" + i));
        }
        
        // Удаляем все
        cache.clear();
        // Но массив size 10 млн ОСТАЁТСЯ в памяти!
        // Объекты удалены, но массив-контейнер нет
    }
}

// ОПТИМАЛЬНО: переинициализация
public class NoMemoryLeak {
    private ArrayList<String> cache = new ArrayList<>();
    
    public void process() {
        for (int i = 0; i < 10_000_000; i++) {
            cache.add(new String("data" + i));
        }
        
        cache = new ArrayList<>();  // Создаём новый список
        // Старый массив будет собран GC
    }
}

Производительность удаления

public class RemovalPerformance {
    
    // МЕДЛЕННО: O(n) в худшем случае
    public void slowRemoval(ArrayList<Integer> list) {
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i) % 2 == 0) {
                list.remove(i);  // Каждое удаление сдвигает элементы
                // Сложность: O(n) для каждого remove
                // Общая: O(n^2)
            }
        }
    }
    
    // БЫСТРО: O(n)
    public void fastRemoval(ArrayList<Integer> list) {
        list.removeIf(x -> x % 2 == 0);
        // Внутри использует эффективный алгоритм сдвига
    }
    
    // ЕЩЁ БЫСТРЕЕ для множественного удаления
    public void efficientRemoval(ArrayList<Integer> list) {
        // Используем Iterator
        Iterator<Integer> it = list.iterator();
        while (it.hasNext()) {
            if (it.next() % 2 == 0) {
                it.remove();  // Эффективнее
            }
        }
    }
}

Система.arraycopy() — ключевой метод

// System.arraycopy — это нативный метод на C++
// Он очень быстрый, но всё равно O(n)

public static native void arraycopy(
    Object src,      // Исходный массив
    int srcPos,      // Начальная позиция в src
    Object dest,     // Целевой массив
    int destPos,     // Начальная позиция в dest
    int length       // Сколько элементов копировать
);

// Пример при remove(1)
ArrayList<String> list = new ArrayList<>(5);
list.add("A");  // [A, null, null, null, null]
list.add("B");  // [A, B, null, null, null]
list.add("C");  // [A, B, C, null, null]
list.add("D");  // [A, B, C, D, null]

list.remove(1);  // Удаляем "B"
// System.arraycopy(elementData, 2, elementData, 1, 2)
// Копирует 2 элемента с позиции 2 на позицию 1
// Результат: [A, C, D, null, null]

Trimming для экономии памяти

public void trimToSize() {
    // После удаления большого количества элементов
    // Можем уменьшить capacity до size
    
    ArrayList<String> list = new ArrayList<>();
    for (int i = 0; i < 1000; i++) {
        list.add("item");
    }
    
    // Удалим 900 элементов
    for (int i = 0; i < 900; i++) {
        list.remove(0);  // Очень медленно! O(n^2)
    }
    
    // Теперь size = 100, но capacity = 1000
    // Вызовем trimToSize()
    list.trimToSize();  // Теперь capacity = 100
    // Создаёт новый массив меньшего размера и копирует данные
}

Практические рекомендации

// 1. Избегай удаления в начале/конце в цикле
for (int i = 0; i < list.size(); i++) {
    list.remove(0);  // O(n^2) ! ПЛОХО
}

// 2. Используй removeIf для фильтрации
list.removeIf(item -> shouldRemove(item));  // O(n)

// 3. Используй Iterator для удаления во время итерации
for (Iterator<Item> it = list.iterator(); it.hasNext(); ) {
    if (shouldRemove(it.next())) {
        it.remove();  // Безопасно
    }
}

// 4. Для частых удалений используй LinkedList вместо ArrayList
LinkedList<Item> list = new LinkedList<>();  // O(1) для удаления

// 5. После больших очисток вызови trimToSize()
list.clear();
list.trimToSize();

Заключение

При удалении из ArrayList происходит:

1. System.arraycopy() — сдвиг элементов влево (O(n))
2. Обнуление ссылки — помощь garbage collector
3. Уменьшение size — но capacity остаётся неизменным
4. Потеря памяти возможна — если часто удалять большие объёмы

Критичное правило: никогда не удаляй в цикле по индексу — это даёт O(n^2). Используй removeIf(), Iterator или LinkedList для частых удалений.