Как правильно удалять элементы во время итерации

Самый лаконичный, безопасный и быстрый способ:

🟢 Junior Level

1. Главное правило удаления элементов

[!CAUTION] Никогда не вызывайте метод collection.remove() внутри цикла for-each! Это гарантированно приведет к выбросу ConcurrentModificationException.

List<String> names = new ArrayList<>(List.of("Анна", "Иван", "Петр", "Иван"));

// ❌ ТАК ДЕЛАТЬ НЕЛЬЗЯ (Аварийное завершение программы):
for (String name : names) {
    if (name.equals("Иван")) {
        names.remove(name); // Выбросит ConcurrentModificationException!
    }
}

2. Два правильных способа в современном коде

Вариант 1: `Collection.removeIf()` (Стандарт Java 8+)

Самый лаконичный, безопасный и быстрый способ:

// ✅ ЛУЧШИЙ СПОСОБ:
names.removeIf(name -> name.equals("Иван"));

Вариант 2: Явный вызов `Iterator.remove()`

Классический подход для ситуаций, когда перед удалением требуется сложная процедурная логика или логирование:

// ✅ КЛАССИЧЕСКИЙ БЕЗОПАСНЫЙ СПОСОБ:
Iterator<String> it = names.iterator();
while (it.hasNext()) {
    String name = it.next();
    if (name.equals("Иван")) {
        it.remove(); // Безопасно: итератор сам удаляет элемент и обновляет счетчики
    }
}

🟡 Middle Level

1. Сравнительный анализ стратегий удаления

Стратегия	`ArrayList`	`LinkedList`	Потокобезопасность	Сложность по памяти	Примечание
`removeIf(Predicate)`	$O(N)$	$O(N)$	❌ Нет	$O(1)$	Промышленный стандарт
`Iterator.remove()`	$O(N^2)$	$O(N)$	❌ Нет	$O(1)$	$O(N^2)$ в `ArrayList` из-за сдвигов
Обратный цикл `for (i--)`	$O(N^2)$	$O(N^2)$	❌ Нет	$O(1)$	Не вызывает CME, но медленный
Stream API `.filter()`	$O(N)$	$O(N)$	❌ Нет	$O(N)$	Создает новый список в Heap
Вспомогательный список	$O(N^2)$	$O(N)$	❌ Нет	$O(N)$	`removeAll(toRemove)`

2. Почему `Iterator.remove()` деградирует до $O(N^2)$ в `ArrayList`

Внутри ArrayList.remove() (и Itr.remove()) при удалении любого элемента вызывается низкоуровневая операция копирования памяти:

System.arraycopy(elementData, index + 1, elementData, index, numMoved);

Все элементы правее удаленного сдвигаются на одну позицию влево.

Если из списка в $1\,000\,000$ элементов удалить 500 000 записей через Iterator.remove():

500 000 раз вызовется System.arraycopy.
Каждое копирование перемещает сотни килобайт памяти.
Суммарная сложность составляет $O(K \cdot N) \approx O(N^2)$. В реальных тестах такая операция занимает десятки секунд или минуты!

В LinkedList ситуация обратная: Iterator.remove() работает за строгое константное время $O(1)$, поскольку итератор уже держит прямую ссылку на текущий узел Node и просто перенаправляет ссылки prev и next у соседей. Суммарная сложность удаления для LinkedList — честные $O(N)$.

🔴 Senior Level

1. Архитектурное превосходство `ArrayList.removeIf()` под капотом

В классе ArrayList метод removeIf полностью переопределен для обеспечения максимальной производительности процессора и бережного отношения к памяти:

Фаза поиска первой мутации: Алгоритм сканирует массив elementData предикатом. Если ни один элемент не подошел под удаление, метод завершается за $O(N)$ без единой записи в память!

Фаза компактификации (Two-Pointer Compaction): При нахождении первого удаляемого элемента алгоритм переходит в режим фильтрации:

// Псевдокод логики компактификации ArrayList:
int to = i; // Индекс ячейки назначения
for (int from = i + 1; from < size; from++) {
    if (!filter.test((E) elementData[from])) {
        elementData[to++] = elementData[from]; // Сдвиг элементов на месте за один проход!
    }
}

Очистка ссылок для GC (Prevention of Memory Loitering): Все освободившиеся ячейки в конце массива принудительно обнуляются:
```
for (int j = to; j < size; j++) {
    elementData[j] = null; // Освобождаем объекты для Garbage Collector!
}
```
Результат: Вместо сотен тысяч вызовов System.arraycopy выполняется ровно один последовательный проход по памяти с линейной сложностью $O(N)$ и нулевым выделением дополнительной памяти!

2. Удаление в конкурентных коллекциях

В многопоточной среде удаление имеет принципиальные особенности:

CopyOnWriteArrayList: Метод iterator().remove() выбрасывает UnsupportedOperationException. Если вызывать cowal.removeIf(predicate), метод отработает потокобезопасно под эксклюзивным замком, создав новый массив с отфильтрованными данными.
ConcurrentHashMap: Удаление через Iterator.remove() или keySet().removeIf(...) абсолютно безопасно. Итераторы CHM слабосогласованы (Weakly Consistent), не выбрасывают ConcurrentModificationException и отражают удаления в живой хэш-таблице через CAS и гранулярные блокировки бакетов.

🎯 Шпаргалка для интервью

30-секундный ответ (Elevator Pitch)

«Правильный и наиболее производительный способ удаления элементов при итерации в современной Java — метод Collection.removeIf(Predicate). В ArrayList он работает за $O(N)$ без выделения памяти за счёт алгоритма компактификации в один проход, обнуляя хвостовые ссылки для предотвращения утечек памяти GC. Использование Iterator.remove() также безопасно против ConcurrentModificationException, но в ArrayList деградирует до катастрофических $O(N^2)$ из-за постоянных сдвигов массива через System.arraycopy. Прямой вызов collection.remove() в цикле for-each строго запрещен».

3 каверзных вопроса на интервью с ответами

1. Почему обход с конца `for (int i = list.size() - 1; i >= 0; i--)` с вызовом `list.remove(i)` не выбрасывает `ConcurrentModificationException`?

Ответ: Цикл со счетчиком for (int i...) работает напрямую с индексами и не создает объект Iterator. Счетчик структурных изменений modCount при этом исправно инкрементируется, но проверять его некому. Удаление с конца не смещает индексы еще не проверенных элементов (все они находятся левее индекса i). Однако для ArrayList сложность все равно остается $O(N^2)$ при удалении многих элементов из середины/начала, а для LinkedList превращается в катастрофические $O(N^2)$ из-за постоянного поиска узлов по индексу.

2. В чём скрытая опасность решения «собрать элементы во временный список `toRemove` и вызвать `list.removeAll(toRemove)`»?

Ответ:

Память: Требуется выделение памяти под промежуточный список toRemove (давление на GC).
Алгоритмический коллапс: Метод ArrayList.removeAll(Collection c) для каждого своего элемента вызывает c.contains(e). Если toRemove — это ArrayList, метод contains() работает за $O(M)$. Общая сложность операции составит $O(N \cdot M) \approx O(N^2)$. Если размер коллекции велик, приложение зависнет.

3. Как `ArrayList.removeIf()` предотвращает утечки памяти (Memory Loitering)?

Ответ: При сдвиге элементов влево размер списка size уменьшается, но физический массив elementData сохраняет свой размер. Если просто уменьшить счетчик size, в ячейках от нового size до старого останутся старые ссылки на удаленные объекты. Garbage Collector будет считать эти объекты достижимыми и не сможет освободить память. В реализации removeIf() хвостовые ячейки явно затираются вызовом elementData[j] = null.

Типичные ошибки и Red Flags

❌ Удаление через list.remove() в цикле for-each: Грубейшая ошибка, приводящая к ConcurrentModificationException.
❌ Использование Iterator.remove() для массового удаления из ArrayList: Приводит к деградации производительности до $O(N^2)$.
❌ Удаление в прямом цикле со счетчиком for (int i=0; i<size; i++): При удалении элемента следующий за ним элемент смещается на позицию i и на следующей итерации i++ будет безвозвратно пропущен.
❌ Попытка удалить элемент через it.remove() в CopyOnWriteArrayList: Вызовет немедленный UnsupportedOperationException.

🟢 Junior Level

1. Главное правило удаления элементов

2. Два правильных способа в современном коде

Вариант 1: Collection.removeIf() (Стандарт Java 8+)

Вариант 2: Явный вызов Iterator.remove()