Что обеспечивает более быструю итерацию: ArrayList или LinkedList в Java?

ArrayList итерируется значительно быстрее, чем LinkedList.

Причина: Разница в организации данных в памяти и локальности ссылок.

• ArrayList использует внутренний массив (Object[]). Элементы хранятся в непрерывном блоке памяти, что идеально для предсказания переходов процессора и эффективного использования кэш-памяти (cache locality). При итерации происходит простое инкрементирование индекса.
• LinkedList реализован как двусвязный список. Каждый элемент (Node) хранится в отдельном месте памяти и содержит ссылки на предыдущий и следующий узлы. Итерация требует постоянного перехода по этим разрозненным ссылкам, что вызывает частые промахи кэша (cache misses) и замедляет работу.

Пример и сравнение:

import java.util.*;

public class IterationBenchmark {
    public static void main(String[] args) {
        List<Integer> arrayList = new ArrayList<>();
        List<Integer> linkedList = new LinkedList<>();
        int size = 1_000_000;

        // Заполнение
        for (int i = 0; i < size; i++) {
            arrayList.add(i);
            linkedList.add(i);
        }

        long start = System.nanoTime();
        for (int val : arrayList) { /* Проход по ArrayList */ }
        long arrayTime = System.nanoTime() - start;

        start = System.nanoTime();
        for (int val : linkedList) { /* Проход по LinkedList */ }
        long linkedTime = System.nanoTime() - start;

        System.out.println("ArrayList time:  " + arrayTime + " ns");
        System.out.println("LinkedList time: " + linkedTime + " ns");
        // ArrayList time будет в разы меньше
    }
}

Вывод: Для операций, требующих частого последовательного доступа (итерации), ArrayList является оптимальным выбором. LinkedList может быть полезен для частых вставок/удалений в середине списка, если эти операции выполняются через ListIterator.