🟢 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]]