Course contentsShow
← Java
Lesson 1044 of 2,87024. List ImplementationsFree lesson

Iteration Performance: Sequential Access Patterns

ArrayList iterator very fast; LinkedList iterator acceptable but slower due to pointer chasing.

Iteration Performance: Sequential Access Patterns

What you'll learn: You'll understand why iterating through an ArrayList is blazingly fast while iterating through a LinkedList is noticeably slower, even though both support iteration.

The Core Difference

When you use an iterator or enhanced for-loop to traverse a collection sequentially (visiting each element once, front to back), both ArrayList and LinkedList work correctly — but their performance differs significantly.

ArrayList's Iterator: Because ArrayList stores elements in a contiguous array, its iterator simply increments an index to move from element to element. Each next() call is an O(1) array access. The elements sit right next to each other in memory, which leverages cache locality (as you learned previously). Iterating through 10,000 elements means 10,000 lightning-fast array lookups with excellent CPU cache hits.

LinkedList's Iterator: LinkedList must follow node references (pointers) to traverse from one element to the next. Each next() call dereferences a pointer to find the next node object, which might be scattered anywhere in memory. While still O(1) per step, this "pointer chasing" is slower than array indexing, and the poor cache locality means more CPU cache misses.

The Practical Impact

Think of it like reading a book: ArrayList iteration is like reading consecutive pages (flip, flip, flip — fast and smooth). LinkedList iteration is like following footnotes that send you jumping to random pages throughout the book (flip to page 237, now 89, now 412 — more work per step).

For sequential traversal, ArrayList typically performs several times faster than LinkedList, even though both operations are technically O(n).

Key Takeaway: ArrayList's iterator is very fast due to contiguous memory and cache efficiency; LinkedList's iterator is acceptable but slower because it must chase pointers through scattered memory.