🟢 Junior Level

Правило: НЕ удаляйте через list.remove() в цикле!

// ❌ ConcurrentModificationException!
for (String s : list) {
    list.remove(s);
}

// ✅ Iterator.remove()
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (condition(it.next())) {
        it.remove();  // Безопасно!
    }
}

// ✅ removeIf (Java 8+) — лучший способ!
list.removeIf(e -> condition(e));

---

🟡 Middle Level

Сравнение подходов

Способ	ArrayList	LinkedList	Безопасно?
for-each + remove	❌ CME	❌ CME	Нет
Iterator.remove()	O(n²)	O(n)	✅ Да
removeIf()	O(n)	O(n)	✅ Да
Обратный цикл	O(n²)	O(n²)	✅ Да
Stream + filter	O(n) + память	O(n) + память	✅ Да

removeIf — победитель

// O(n) для ArrayList:
// 1. Находит первый элемент для удаления
// 2. Сдвигает оставшиеся ОДИН раз
list.removeIf(e -> e.startsWith("A"));

Iterator.remove() для ArrayList каждый вызов сдвигает все элементы после удалённого (System.arraycopy). При удалении N элементов = N сдвигов = O(n^2). removeIf() делает один проход с одним сдвигом = O(n).

LinkedList + Iterator

// После next() итератор уже на узле
// remove() = O(1) — перевешивание ссылок
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (condition(it.next())) {
        it.remove();  // O(1) для LinkedList!
    }
}
// Итого: O(n)

---

🔴 Senior Level

ArrayList.removeIf под капотом

// Java 9+ оптимизация:
// 1. Находит первый элемент для удаления
// 2. До него — НЕ трогает массив
// 3. После — сдвигает в O(n) один раз
// → Минимальные записи в память!

В Java 8 removeIf для ArrayList также O(n), но без оптимизации «минимальных записей» — он может делать лишние копирования. В Java 9+ алгоритм улучшен: сначала помечает удаляемые, потом один сдвиг.

Многопоточность

// CopyOnWriteArrayList:
// Можно удалять в for-each (итератор = snapshot)
// НО: каждое удаление = копия массива!

// ConcurrentHashMap:
// iterator.remove() безопасно
// Weakly consistent → не падает

Production Experience

Реальный сценарий: O(n²) убил производительность

// 1 млн элементов, удаление 50%
// Iterator.remove(): 10 минут!
// removeIf(): 50 мс

// Причина: Iterator.remove() = System.arraycopy КАЖДЫЙ раз

Best Practices

1. removeIf — по умолчанию (Java 8+)
2. Iterator.remove() — если нужна доп. логика
3. Не удаляйте в for-each для обычных коллекций (ArrayList, LinkedList, HashSet) — получите CME. Исключение: CopyOnWriteArrayList — for-each безопасен, но итератор не увидит удаления (snapshot).
4. LinkedList → Iterator идеален
5. Stream + filter → новый список, не мутация
6. Обратный цикл → работает, но O(n²)

Резюме для Senior

• removeIf = O(n), лучший выбор
• Iterator.remove() = O(n²) для ArrayList, O(n) для LinkedList
• for-each + remove = CME
• ArrayList.removeIf → минимальные записи
• Stream → новый список, иммутабельный подход

---

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

Обязательно знать:

• for-each + list.remove() = гарантированный ConcurrentModificationException
• removeIf() (Java 8+) — лучший способ: O(n) для ArrayList, один System.arraycopy
• Iterator.remove() для ArrayList = O(n^2) (System.arraycopy каждый раз), для LinkedList = O(n)
• Обратный цикл for (int i = size-1; i >= 0; i--) — работает, но O(n^2) для ArrayList
• Stream + filter создаёт новый список, не мутирует оригинал (иммутабельный подход)
• CopyOnWriteArrayList позволяет удалять в for-each (snapshot), но каждое удаление = копия массива
• Java 9+ оптимизация removeIf: сначала помечает, потом один сдвиг — минимальные записи

Частые уточняющие вопросы:

• Почему Iterator.remove() = O(n^2) для ArrayList? — Каждый вызов делает System.arraycopy для сдвига элементов; N удалений = N сдвигов.
• Почему removeIf() быстрее Iterator.remove() для ArrayList? — Один проход, один System.arraycopy вместо N отдельных сдвигов.
• Можно ли удалять элементы в for-each цикле? — Только для CopyOnWriteArrayList (snapshot-итератор), но это дорого по памяти.
• Какой подход для удаления 50% из 1 млн элементов? — removeIf(): 50 мс вместо 10 минут у Iterator.remove().

Красные флаги (НЕ говорить):

• «Можно удалять через list.remove() внутри for-each» — нет, это гарантированный CME
• «Iterator.remove() так же эффективен, как removeIf() для ArrayList» — нет, O(n^2) против O(n)
• «CopyOnWriteArrayList — лучший способ удаления во время итерации» — нет, каждая модификация копирует весь массив
• «Stream.filter мутирует оригинальную коллекцию» — нет, создаёт новый список

Связанные темы:

• [[27. Что такое ConcurrentModificationException]]
• [[26. Что такое fail-fast и fail-safe итераторы]]
• [[31. Какие операции поддерживает интерфейс Collection]]