Getting the Five-Hundredth Element Out of Each

A thousand elements in each list, and one element asked for by position, in a loop.

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 it cannot answer the question it is being asked.