Как меняется размер ArrayList при удалении элемента

# Как меняется размер ArrayList при удалении элемента

Вопрос о том, как изменяется внутреннее состояние ArrayList при удалении элемента, открывает интересную особенность этой коллекции.

Быстрый ответ

Размер (size) уменьшается на 1, но вместимость (capacity) остаётся прежней.

ArrayList имеет две важные характеристики:

• size - количество элементов
• capacity - длина внутреннего массива

Структура ArrayList

Внутри ArrayList используется обычный Java массив:

public class ArrayList<E> extends AbstractList<E> implements List<E> {
    // Внутренний массив для хранения элементов
    private Object[] elementData;
    
    // Актуальное количество элементов
    private int size = 0;
}

Пример: Удаление элемента

ArrayList<String> list = new ArrayList<>();

// Добавляем элементы
list.add("A");  // size = 1, capacity = 10 (default)
list.add("B");  // size = 2, capacity = 10
list.add("C");  // size = 3, capacity = 10

System.out.println("До удаления:");
System.out.println("Size: " + list.size());  // 3
System.out.println("Capacity: 10 (скрыто)");

// Удаляем элемент
list.remove("B");  // Удаляем "B"

System.out.println("\nПосле удаления:");
System.out.println("Size: " + list.size());     // 2 (уменьшилось!)
System.out.println("Capacity: 10 (не изменилось!)");

Что происходит при удалении

1. Поиск элемента - ArrayList ищет индекс удаляемого элемента
2. Сдвиг элементов - все элементы после удаляемого сдвигаются на одну позицию влево
3. Уменьшение size - поле size уменьшается на 1
4. Последний элемент обнуляется - null присваивается для помощи сборщику мусора

Код метода remove()

public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++) {
            if (elementData[index] == null) {
                fastRemove(index);  // Быстрое удаление
                return true;
            }
        }
    } else {
        for (int index = 0; index < size; index++) {
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
        }
    }
    return false;
}

private void fastRemove(int index) {
    modCount++;  // Увеличиваем версию структуры
    
    // Сдвигаем элементы
    int numMoved = size - index - 1;
    if (numMoved > 0) {
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);
    }
    
    // Уменьшаем размер и обнуляем последний элемент
    elementData[--size] = null;
}

Визуализация процесса

Исходное состояние (size = 4):
┌───┬───┬───┬───┬───┬───┐
│ A │ B │ C │ D │   │   │  (capacity = 6)
└───┴───┴───┴───┴───┴───┘
  0   1   2   3   4   5

Удаляем "B" (index = 1):

Шаг 1: Найти индекс
  index = 1

Шаг 2: Сдвинуть элементы [2, 3] на позицию [1, 2]
┌───┬───┬───┬───┬───┬───┐
│ A │ C │ D │ D │   │   │  (промежуточное состояние)
└───┴───┴───┴───┴───┴───┘

Шаг 3: Обнулить последний элемент и уменьшить size
┌───┬───┬───┬───┬───┬───┐
│ A │ C │ D │   │   │   │  (size = 3, capacity = 6)
└───┴───┴───┴───┴───┴───┘
  0   1   2   3   4   5

Вместимость (capacity) НЕ уменьшается

Это важная особенность! Capacity остаётся прежним:

ArrayList<Integer> list = new ArrayList<>();

// Добавляем много элементов
for (int i = 0; i < 100; i++) {
    list.add(i);
}
// После 100 добавлений capacity автоматически вырос (1.5x)
// list.size() = 100, capacity примерно 150

// Удаляем 99 элементов
for (int i = 0; i < 99; i++) {
    list.remove(0);
}
// list.size() = 1, но capacity всё ещё 150!
// Это означает 149 позиций памяти впустую

Когда это проблема?

Сценарий: Утечка памяти

public class Cache {
    private ArrayList<CacheEntry> entries = new ArrayList<>();
    
    public void clear() {
        entries.clear();  // size = 0, но capacity остаётся!
    }
    
    // Если было 1 миллион entries, после clear() 
    // память всё равно занята!
}

Решение: Использовать trimToSize()

public class Cache {
    private ArrayList<CacheEntry> entries = new ArrayList<>();
    
    public void clear() {
        entries.clear();           // size = 0
        entries.trimToSize();      // Уменьшает capacity до size
    }
}

// trimToSize() создаёт новый массив размером size и копирует элементы

Это относится ко всем методам удаления

ArrayList<String> list = new ArrayList<>(Arrays.asList("A", "B", "C", "D"));

// remove(int index)
list.remove(0);  // Удаляет по индексу - size уменьшается, capacity нет

// remove(Object o)
list.remove("B");  // Удаляет по значению - size уменьшается, capacity нет

// clear()
list.clear();  // Удаляет все - size = 0, capacity не меняется

// removeAll(Collection)
list.removeAll(Arrays.asList("A", "B"));  // size уменьшается, capacity нет

Цена операции удаления

Удаление из ArrayList может быть дорогой операцией:

// O(1) - Удаление с конца
list.remove(list.size() - 1);  // Только уменьшить size

// O(n) - Удаление с начала или середины
list.remove(0);  // Нужно сдвинуть все элементы
list.remove(list.size() / 2);  // Нужно сдвинуть половину элементов

Рекомендации для оптимизации

Не удаляйте много элементов в цикле

// ❌ Плохо - O(n²) сложность
ArrayList<Integer> list = new ArrayList<>(1000000);
for (Integer item : list) {
    if (item % 2 == 0) {
        list.remove(item);  // Каждое удаление O(n)
    }
}

// ✅ Хорошо - O(n) сложность
list.removeIf(item -> item % 2 == 0);
// или
list = list.stream()
    .filter(item -> item % 2 != 0)
    .collect(Collectors.toCollection(ArrayList::new));

Если часто удаляете элементы - используйте LinkedList

// LinkedList удаление из начала/середины - O(n) поиск + O(1) удаление
// ArrayList удаление из начала/середины - O(n) сдвиг
// Но LinkedList имеет другие проблемы с памятью

// Лучший выбор зависит от сценария использования
LinkedList<Integer> linkedList = new LinkedList<>();  // O(1) remove в начале
ArrayList<Integer> arrayList = new ArrayList<>();      // O(1) remove в конце

Заключение

Когда вы удаляете элемент из ArrayList:

1. size уменьшается на 1 - это видимое изменение
2. Capacity остаётся прежним - внутренний массив не сжимается
3. Элементы сдвигаются - если удаляли не последний элемент
4. Последняя позиция обнуляется - для помощи GC

Это означает, что ArrayList оптимизирован для добавления и удаления с конца, но удаление с начала или середины дорогое. Если вам часто нужны такие операции, рассмотрите LinkedList или другие структуры данных.