¿Por qué la iteración sobre una colección ArrayList con un millón de elementos es más rápida que sobre otras estructuras de datos?

Итерация по коллекции ArrayList с миллионом элементов выполняется быстрее, чем по другим структурам данных, потому что ArrayList основан на массиве с непрерывным блоком памяти. Это обеспечивает:

• Быстрый доступ по индексу (O(1)) благодаря прямой адресации элементов.
• Высокую локальность данных, что улучшает кэширование процессора и снижает количество промахов кэша.

В отличие от связных списков или других структур, где элементы разбросаны по памяти и для доступа к следующему элементу нужно переходить по ссылкам, ArrayList позволяет проходить элементы последовательно и эффективно.

Пример:

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);
}

Такой проход по массиву будет быстрее, чем, например, итерация по LinkedList, где каждый вызов next() требует перехода по указателю.