Why is iterating a LinkedList with a for-i index loop a performance trap, and what's the correct way to traverse it?
answer
- LinkedList get(i) = O(n) traversal
- Index loop over LinkedList = O(n^2) trap
- for-each / Iterator = O(n) single pass (cursor + next())
- for-each is the safe default for any List
- Iterator.remove() / removeIf for in-place deletion (O(1) relink on LinkedList)
basics
~20 sIn a LinkedList, get(i) has to walk from the start each time, so a loop calling get(0), get(1), get(2)... re-walks the chain repeatedly and becomes very slow (O(n^2)). Use an enhanced for-loop or iterator instead, which walks the chain just once.
solid answer
~50 sBecause LinkedList has no direct index access, each get(i) traverses from the nearest end to position i in O(n) time. A classic index loop — for (int i = 0; i < list.size(); i++) list.get(i) — therefore re-traverses the list on every iteration, giving overall O(n^2) behavior that grinds to a halt on large lists. The correct way is to use the Iterator, which the enhanced for-each loop uses under the hood: it keeps a cursor on the current node and steps to next in O(1), so the whole traversal is O(n). On an ArrayList the same index loop is perfectly fine because get(i) is O(1). This is a concrete example of why you should program against the List interface but stay aware of the concrete implementation's access cost, and why for-each is the safe default for any List. For in-place removal during traversal, use Iterator.remove() (or removeIf), which is also where LinkedList's O(1) relink shines.
go deeper
Knows to use a for-each loop on lists and that LinkedList get(i) is slow.
Explains that an index loop over LinkedList is O(n^2) because each get re-traverses, and that for-each/iterator is O(n).
Derives the 1+2+...+n = O(n^2) cost, explains the iterator cursor mechanism, handles in-place removal with Iterator.remove/removeIf, and ties it to programming-to-interface-but-knowing-the-cost-model.
Sets coding standards (for-each default, beware index loops on non-random-access lists), reasons about how the same interface code yields different complexity by implementation, and considers RandomAccess marker interface for generic algorithms.
## The setup A `LinkedList` stores elements as a chain of nodes; there is **no formula** to jump to position `i`. To answer `get(i)`, it must **traverse** the chain step by step from the head (or tail, whichever is nearer) until it reaches index `i`. That single call is O(n) in the worst case. ## The trap: an index loop Consider the very common pattern: ``` for (int i = 0; i < list.size(); i++) { process(list.get(i)); } ``` On an **ArrayList** this is fine: `get(i)` is O(1), so the whole loop is O(n). On a **LinkedList** it's a disaster. Each `get(i)` re-walks the chain from an end: - `get(0)` walks 0 steps, `get(1)` walks 1, `get(2)` walks 2, ... `get(n-1)` walks ~n. - Total work = 1 + 2 + ... + n = **O(n^2)**. For a list of 100,000 elements that's ~10 billion pointer hops — seconds or minutes instead of milliseconds. (Java's implementation halves the constant by starting from whichever end is closer, but the complexity is still quadratic.) ## The fix: iterate with the Iterator / for-each The **enhanced for-loop** (`for (E e : list)`) compiles to use the list's `Iterator`. The iterator keeps a **cursor** on the current node and advances via `next()`, which simply follows the node's `next` pointer in **O(1)**. So the entire traversal is **O(n)** — linear, the way it should be: ``` for (E e : list) { process(e); } ``` This works correctly and efficiently for **any** List, which is why for-each is the safe default. ## Removing during traversal If you need to delete elements while iterating, don't modify the list directly inside a for-each (that throws `ConcurrentModificationException`). Use the iterator's own `remove()`: ``` Iterator<E> it = list.iterator(); while (it.hasNext()) { if (shouldRemove(it.next())) it.remove(); } ``` or the higher-level `list.removeIf(predicate)`. For a **LinkedList**, `Iterator.remove()` is O(1) per removal (just relink neighbors) — this is exactly the niche where LinkedList beats ArrayList, whose removal must shift elements. ## The broader lesson Program to the `List` **interface** for flexibility, but remember the **concrete implementation's cost model**. The same code can be O(n) or O(n^2) depending on the runtime type. for-each abstracts this away safely: it's O(n) for both ArrayList and LinkedList. Reserve index loops for when you genuinely need the index (and ideally an O(1)-access list like ArrayList).
- Why doesn't the same index loop hurt an ArrayList?ArrayList's get(i) is O(1) (direct array addressing), so an index loop over it is O(n) overall — no re-traversal occurs.
- What exception can you hit if you call list.remove(x) inside a for-each loop, and how do you avoid it?ConcurrentModificationException, thrown by the iterator's fail-fast check when the list is structurally modified outside the iterator. Avoid it by using Iterator.remove() or list.removeIf(predicate).
saying these in an interview costs you the question
- Using for-i get(i) loops on a LinkedList
- Thinking for-each and index loops are equivalent in cost for all lists
- Modifying a list inside a for-each (ConcurrentModificationException)
- Assuming get(i) is O(1) for every List
- Removing in a loop with list.remove(i) instead of Iterator.remove()/removeIf