🟢 Junior Level

Rule: Do NOT remove via list.remove() in a loop!

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

// ✅ Iterator.remove()
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (condition(it.next())) {
        it.remove();  // Safe!
    }
}

// ✅ removeIf (Java 8+) — the best way!
list.removeIf(e -> condition(e));

---

🟡 Middle Level

Comparison of approaches

Method	ArrayList	LinkedList	Safe?
for-each + remove	❌ CME	❌ CME	No
Iterator.remove()	O(n²)	O(n)	✅ Yes
removeIf()	O(n)	O(n)	✅ Yes
Reverse loop	O(n²)	O(n²)	✅ Yes
Stream + filter	O(n) + memory	O(n) + memory	✅ Yes

removeIf — the winner

// O(n) for ArrayList:
// 1. Finds the first element to remove
// 2. Shifts the rest ONCE
list.removeIf(e -> e.startsWith("A"));

Iterator.remove() for ArrayList shifts all elements after the removed one on each call (System.arraycopy). Removing N elements = N shifts = O(n^2). removeIf() does one pass with one shift = O(n).

LinkedList + Iterator

// After next(), the iterator is already at the node
// remove() = O(1) — relinking references
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (condition(it.next())) {
        it.remove();  // O(1) for LinkedList!
    }
}
// Total: O(n)

---

🔴 Senior Level

ArrayList.removeIf under the hood

// Java 9+ optimization:
// 1. Finds the first element to remove
// 2. Before it — does NOT touch the array
// 3. After — shifts in O(n) once
// → Minimal memory writes!

In Java 8, removeIf for ArrayList is also O(n), but without the “minimal writes” optimization — it may perform extra copying. In Java 9+, the algorithm is improved: it first marks elements for removal, then performs a single shift.

Multi-threading

// CopyOnWriteArrayList:
// Can remove in for-each (iterator = snapshot)
// BUT: each removal = array copy!

// ConcurrentHashMap:
// iterator.remove() is safe
// Weakly consistent → does not crash

Production Experience

Real scenario: O(n²) killed performance

// 1 million elements, removing 50%
// Iterator.remove(): 10 minutes!
// removeIf(): 50 ms

// Reason: Iterator.remove() = System.arraycopy EVERY time

Best Practices

1. removeIf — by default (Java 8+)
2. Iterator.remove() — if additional logic is needed
3. Do not remove in for-each for regular collections (ArrayList, LinkedList, HashSet) — you’ll get CME. Exception: CopyOnWriteArrayList — for-each is safe, but the iterator won’t see removals (snapshot).
4. LinkedList → Iterator is ideal
5. Stream + filter → new list, not mutation
6. Reverse loop → works, but O(n²)

Summary for Senior

• removeIf = O(n), best choice
• Iterator.remove() = O(n²) for ArrayList, O(n) for LinkedList
• for-each + remove = CME
• ArrayList.removeIf → minimal writes
• Stream → new list, immutable approach

---

🎯 Interview Cheat Sheet

Must know:

• for-each + list.remove() = guaranteed ConcurrentModificationException
• removeIf() (Java 8+) — the best approach: O(n) for ArrayList, a single System.arraycopy
• Iterator.remove() for ArrayList = O(n^2) (System.arraycopy each time), for LinkedList = O(n)
• Reverse loop for (int i = size-1; i >= 0; i--) — works, but O(n^2) for ArrayList
• Stream + filter creates a new list, does not mutate the original (immutable approach)
• CopyOnWriteArrayList allows removal in for-each (snapshot iterator), but each removal = array copy
• Java 9+ removeIf optimization: first marks, then single shift — minimal writes

Frequent follow-up questions:

• Why is Iterator.remove() = O(n^2) for ArrayList? — Each call performs a System.arraycopy to shift elements; N removals = N shifts.
• Why is removeIf() faster than Iterator.remove() for ArrayList? — Single pass, single System.arraycopy instead of N separate shifts.
• Can you remove elements in a for-each loop? — Only for CopyOnWriteArrayList (snapshot iterator), but it’s expensive in memory.
• Which approach for removing 50% of 1 million elements? — removeIf(): 50 ms instead of 10 minutes for Iterator.remove().

Red flags (DO NOT say):

• “You can remove via list.remove() inside for-each” — no, that’s a guaranteed CME
• “Iterator.remove() is as efficient as removeIf() for ArrayList” — no, O(n^2) vs O(n)
• “CopyOnWriteArrayList is the best way to remove during iteration” — no, each modification copies the entire array
• “Stream.filter mutates the original collection” — no, it creates a new list

Related topics:

• [[27. What is ConcurrentModificationException]]
• [[26. What are fail-fast and fail-safe iterators]]
• [[31. What operations does the Collection interface support]]