Java LinkedList indexed loops: a hidden quadratic traversal

This complete Java 8 program has a checked output. Compile it as the named public class, then run it without additional libraries.

Iteration keeps a moving cursor

Both loops in the fixture produce the same receipt sequence. The first calls get for each position; each call can start a new traversal from the head or tail. The second advances one iterator, so the total traversal is linear.

A tiny list will not reveal this difference in a wall-clock test. The cost follows from the operation contract and traversal pattern; do not publish a fabricated speedup percentage. If random indexing is the requirement, ArrayList better matches the access pattern.

Keep mutation under the iterator

The program only reads. When removing items during traversal, use the iterator's remove method and respect its state rules. Repeated external removals also change positions and can invalidate an iterator. The cursor lesson covers local edits.

Working program

import java.util.LinkedList;
public class ReceiptScanCost {
    public static void main(String[] args) {
        LinkedList<String> receipts = new LinkedList<>();
        receipts.add("R-71"); receipts.add("R-72"); receipts.add("R-73");
        StringBuilder indexed = new StringBuilder();
        for (int position = 0; position < receipts.size(); position++) indexed.append(receipts.get(position)).append(' ');
        StringBuilder iterated = new StringBuilder();
        for (String receipt : receipts) iterated.append(receipt).append(' ');
        System.out.println(indexed.toString().trim());
        System.out.println(iterated.toString().trim());
    }
}

Output

R-71 R-72 R-73
R-71 R-72 R-73

Costs and boundaries

An indexed full scan is O(n²) in the worst and aggregate sense; a single iterator traversal is O(n). Both hold only a constant amount of traversal state apart from output storage.

Common Mistakes

• Do not assume List.get has the same cost for every implementation.
• Do not claim timing from a three-item fixture.
• Do not repeatedly obtain listIterator(index) inside a traversal loop.

Read next

Java LinkedList: operations, internals and failure cases, Java ArrayList and indexed access, Java LinkedList ListIterator: edit at a cursor without repeated searches.

Continue with the new boundary checks

Continue with Java LinkedList binarySearch: comparisons are not the whole cost.