ArrayList vs LinkedList when iterating over a million elements — which is faster?

When iterating over a million elements, ArrayList is usually faster than LinkedList.

The reason is that ArrayList stores elements in a contiguous array, which provides good data locality and efficient index-based access. Iteration occurs sequentially over the array, which is well cached by the processor.

LinkedList, on the other hand, is a doubly linked list where each element contains references to its neighbors. During iteration, it involves following links, leading to frequent memory jumps and poor cache performance.

Example:

List<Integer> arrayList = new ArrayList<>();
List<Integer> linkedList = new LinkedList<>();
// filling the lists
for (int i = 0; i < 1_000_000; i++) {
    arrayList.add(i);
    linkedList.add(i);
}

// Iterating over ArrayList
for (Integer num : arrayList) {
    // process num
}

// Iterating over LinkedList
for (Integer num : linkedList) {
    // process num
}

In this example, iteration over ArrayList will be faster due to better data locality and lower overhead for link jumps.

If random access to elements is required, ArrayList also wins because index access in LinkedList is O(n).