ArrayList vs LinkedList при итерации по миллиону элементов — что быстрее?

При итерации по миллиону элементов ArrayList обычно будет работать быстрее, чем LinkedList.

Причина в том, что ArrayList хранит элементы в одном непрерывном массиве, что обеспечивает хорошую локальность данных и эффективный доступ по индексу. Итерация происходит последовательно по массиву, что хорошо кэшируется процессором.

LinkedList же представляет собой двусвязный список, где каждый элемент содержит ссылки на соседние. При итерации происходит переход по ссылкам, что приводит к частым переходам по памяти и плохой кэшируемости.

Пример:

List<Integer> arrayList = new ArrayList<>();
List<Integer> linkedList = new LinkedList<>();
// заполнение списков
for (int i = 0; i < 1_000_000; i++) {
    arrayList.add(i);
    linkedList.add(i);
}

// Итерация по ArrayList
for (Integer num : arrayList) {
    // обработка num
}

// Итерация по LinkedList
for (Integer num : linkedList) {
    // обработка num
}

В этом примере итерация по ArrayList будет быстрее за счет лучшей локальности данных и меньших накладных расходов на переходы по ссылкам.

Если же доступ к элементам происходит случайным образом, то ArrayList также выигрывает, так как доступ по индексу у LinkedList — O(n).