ExampleDifficulty: Intermediate1 min

ArrayList vs LinkedList Example: Reading by Position in a Loop

The same loop does a thousand steps on one list and half a million on the other.

Reading an element by position, get(i), is constant time on an ArrayList and a walk along the nodes on a LinkedList. Inside a loop over every position, that difference turns a linear loop into a quadratic one.

A thousand elements in each list, and every element read by position:

java

List<Integer> array = new ArrayList<>(numbers);
List<Integer> linked = new LinkedList<>(numbers);

for (int i = 0; i < numbers.size(); i++) {
    total += array.get(i);
}

for (int i = 0; i < numbers.size(); i++) {
    total += linked.get(i);
}

The first loop does a thousand pieces of arithmetic. get(i) on an array list works out where element i sits from the start of the block and reads it, the same amount of work whether i is 3 or 900.

The second loop walks. get(i) on a linked list starts at the nearer end and follows pointers until it has counted to i, so the loop as a whole does about half a million steps rather than a thousand.

Cost of one get, and of a loop over n elements
Compared on	One `get(i)`	A loop with `get(i)`
`ArrayList`	Constant	Proportional to n
`LinkedList`	Proportional to n	Proportional to n squared

The second loop is not written badly: it is the same loop, and it is quadratic because the list underneath cannot answer the question it is asked cheaply. Walking with an enhanced for instead would be linear on both.

← → move through sections and cards