Why is iteration over an ArrayList collection with a million elements faster than over other data structures?

Iterating over an ArrayList collection with a million elements is faster than over other data structures because ArrayList is based on a contiguous memory array. This provides:

• Fast index-based access (O(1)) due to direct element addressing.
• High data locality, which improves CPU caching and reduces cache misses.

Unlike linked lists or other structures where elements are scattered in memory and accessing the next element requires following links, ArrayList allows sequential and efficient traversal of elements.

Example:

ArrayList<Integer> list = new ArrayList<>(1_000_000);
for (int i = 0; i < 1_000_000; i++) {
    list.add(i);
}

long sum = 0;
for (int i = 0; i < list.size(); i++) {
    sum += list.get(i);
}

This array traversal will be faster than, for example, iterating over a LinkedList, where each call to next() requires following a pointer.