Почему итерация по 100 млн элементов в ArrayList быстрее, чем в LinkedList?

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

Ключевые причины:

1. Прямой доступ к памяти: Итератор ArrayList просто инкрементирует индекс, обращаясь к следующей ячейке массива.
2. Минимум промахов кэша: Соседние элементы уже загружены в быстрый кэш процессора.
3. Отсутствие переходов по ссылкам: В отличие от LinkedList, где каждый элемент (Node) хранится в отдельном участке памяти со ссылками на следующий и предыдущий узлы, что приводит к постоянным промахам кэша.

Пример итерации:

ArrayList<Integer> arrayList = new ArrayList<>();
// Заполнение (опущено для краткости)
for (int value : arrayList) { // Высокая скорость из-за локальности
    // Обработка value
}

Производительность:

• ArrayList: Итерация — O(n), но с очень низкой константой из-за кэш-эффективности.
• LinkedList: Итерация — O(n), но с высокой константой из-за непредсказуемых обращений к памяти и накладных расходов на объекты Node.