Почему в ArrayList быстрее переберет 100 млн элементов?

ArrayList vs LinkedList: производительность при переборе

Вопрос касается производительности перебора элементов в ArrayList по сравнению с другими коллекциями (вероятно, LinkedList). Рассмотрю различия и причины.

Структура данных

ArrayList — это массив на основе динамического расширяемого массива. LinkedList — двусвязный список. При переборе 100 млн элементов разница в производительности существенна.

Временная сложность

// ArrayList: O(1) для доступа по индексу
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < list.size(); i++) {
    Integer value = list.get(i);  // Прямой доступ в O(1)
}

// LinkedList: O(n) для доступа по индексу
LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < list.size(); i++) {
    Integer value = list.get(i);  // Поиск элемента за O(n)
}

Локальность памяти (Cache Locality)

Уникальное преимущество ArrayList — элементы хранятся в непрерывной памяти. Процессор загружает данные в L1/L2 кэш целыми блоками. При линейном доступе:

// ArrayList: предсказуемый доступ
Integer[] arr = new Integer[100_000_000];
for (int i = 0; i < arr.length; i++) {
    process(arr[i]);
}

LinkedList требует следовать по цепочке указателей, вызывая cache misses.

Правильный способ итерации LinkedList

// ✅ Правильно для LinkedList: O(n) сложность
for (Integer value : linkedList) {
    process(value);
}

Выводы

1. ArrayList: непрерывная память → хорошая локальность → быстрый доступ
2. LinkedList: разреженная память → cache misses → медленный доступ
3. Для большинства сценариев ArrayList выигрывает

Для работы с 100 млн элементов выбирайте структуру по реальным требованиям.