Почему ArrayList перебирает элементы эффективнее чем LinkedList?

Почему ArrayList эффективнее при переборе, чем LinkedList

Это фундаментальный вопрос о структурах данных в Java. ArrayList быстрее при переборе благодаря способу хранения элементов в памяти — это вопрос архитектуры данных, а не какого-то магического оптимизирования.

Внутренняя структура

ArrayList — массив на основе

ArrayList хранит элементы в динамическом массиве:

Мемория:
┌─────┬─────┬─────┬─────┬─────┐
│ e1  │ e2  │ e3  │ e4  │ e5  │  (непрерывный блок памяти)
└─────┴─────┴─────┴─────┴─────┘
↑
index=0

Доступ: O(1) — просто прибавь offset к базовому адресу

public class ArrayList<E> extends AbstractList<E> {
    private static final int DEFAULT_CAPACITY = 10;
    
    // Основное хранилище — обычный массив
    Object[] elementData;
    
    // Размер
    int size;
    
    // Доступ к элементу за O(1)
    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }
}

LinkedList — связанный список

LinkedList хранит элементы в узлах с указателями:

Мемория:
[Node1] → [Node2] → [Node3] → [Node4] → [Node5]
  data     data      data      data      data
  next     next      next      next      null

Эти узлы могут быть разбросаны по памяти!

Доступ: O(n) — нужно пройти через все предыдущие узлы

public class LinkedList<E> extends AbstractSequentialList<E> {
    // Размер
    int size;
    
    // Ссылка на первый узел
    Node<E> first;
    
    // Ссылка на последний узел
    Node<E> last;
    
    // Внутренний класс узла
    private static class Node<E> {
        E item;
        Node<E> next;    // Ссылка на следующий
        Node<E> prev;    // Ссылка на предыдущий (двусвязный)
        
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
}

Проблема: Cache Locality

ArrayList: Cache-friendly (кеш-дружественный)

Процессор кеширует блоки памяти. ArrayList хранит элементы непрерывно:

Когда достаём элемент index[0]:

1. Процессор загружает в кеш блок памяти с e1
2. Заодно загружаются e2, e3, e4, e5 (они рядом!)
3. Доступ к e1-e5: быстрый (из кеша)
4. Cache hit rate высокий!

Процессор: "Вот e1... вот e2... вот e3... — всё в кеше!"

LinkedList: Cache-unfriendly (кеш-враждебный)

Узлы разбросаны по памяти, кеш не помогает:

Когда достаём node1 → переходим к node2:

1. Загружаем node1 в кеш
2. Считываем next → 0x7F3A2B4C0 (совсем другой адрес!)
3. Загружаем node2 из памяти (CACHE MISS!)
4. Снова cache miss для node3
5. Снова cache miss для node4

Процессор: "Где он теперь?... Там?... Cache miss!"

Бенчмарк: реальные числа

Перебор 1 миллиона элементов

import java.util.*;

public class ListIterationBenchmark {
    public static void main(String[] args) {
        int size = 1_000_000;
        
        // Создание ArrayList
        List<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            arrayList.add(i);
        }
        
        // Создание LinkedList
        List<Integer> linkedList = new LinkedList<>(arrayList);
        
        // Тест 1: for loop (БЫСТРО для ArrayList)
        long start = System.nanoTime();
        long sum = 0;
        for (int i = 0; i < arrayList.size(); i++) {
            sum += arrayList.get(i);
        }
        long arrayListForLoop = System.nanoTime() - start;
        System.out.println("ArrayList for loop: " + arrayListForLoop + " ns");
        
        // Тест 2: for loop для LinkedList (МЕДЛЕННО!)
        start = System.nanoTime();
        sum = 0;
        for (int i = 0; i < linkedList.size(); i++) {
            sum += linkedList.get(i);  // O(n) на каждую итерацию!
        }
        long linkedListForLoop = System.nanoTime() - start;
        System.out.println("LinkedList for loop: " + linkedListForLoop + " ns");
        
        // Тест 3: Iterator (хороша для обеих)
        start = System.nanoTime();
        sum = 0;
        for (Integer value : arrayList) {
            sum += value;
        }
        long arrayListIterator = System.nanoTime() - start;
        System.out.println("ArrayList iterator: " + arrayListIterator + " ns");
        
        // Тест 4: Iterator для LinkedList (ХОРОШО!)
        start = System.nanoTime();
        sum = 0;
        for (Integer value : linkedList) {
            sum += value;
        }
        long linkedListIterator = System.nanoTime() - start;
        System.out.println("LinkedList iterator: " + linkedListIterator + " ns");
    }
}

// Примерный результат на моём компьютере:
// ArrayList for loop:      5_000_000 ns      (5 мс)   ← БЫСТРО
// LinkedList for loop:   500_000_000_000 ns (500 с!) ← УЖАС!!!
// ArrayList iterator:      8_000_000 ns      (8 мс)
// LinkedList iterator:     20_000_000 ns     (20 мс)

Почему for loop для LinkedList так медленный?

// Это происходит в цикле:
for (int i = 0; i < linkedList.size(); i++) {
    linkedList.get(i);  // get() нужно прожать через i узлов!
}

// LinkedList.get(int index) на самом деле:
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;  // O(n)!
}

private Node<E> node(int index) {
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)  // ← Прыгаем через узлы!
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)  // ← Прыгаем с конца
            x = x.prev;
        return x;
    }
}

// Итого: цикл O(n) * get() O(n) = O(n²)!!!!

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

Способ 1: Iterator (правильно!)

// Iterator движется от узла к узлу O(1)
Iterator<Integer> it = linkedList.iterator();
while (it.hasNext()) {
    int value = it.next();  // O(1) — просто перейти к следующему узлу
}

// Или через for-each loop (использует Iterator)
for (Integer value : linkedList) {
    // O(1) за итерацию
}

Способ 2: stream() API

linkedList.stream()
    .mapToInt(Integer::intValue)
    .sum();

// Использует Iterator под капотом, поэтому O(n)

Способ 3: ListIterator (если нужна позиция)

ListIterator<Integer> it = linkedList.listIterator();
int index = 0;
while (it.hasNext()) {
    int value = it.next();
    int position = it.nextIndex();  // O(1)
    index++;
}

Сравнительная таблица

Когда использовать что

Используй ArrayList когда:

// ✓ Много чтений (get())
List<User> users = new ArrayList<>();
for (int i = 0; i < users.size(); i++) {
    User user = users.get(i);  // ← Быстро!
}

// ✓ Случайный доступ по индексу
User user = users.get(randomIndex);

// ✓ Обычный перебор
for (User user : users) { }

// ✓ Когда размер примерно известен
List<Product> products = new ArrayList<>(1000);

Используй LinkedList когда:

// ✓ Много вставок/удалений в начало
Queue<Task> queue = new LinkedList<>();
queue.addFirst(task);  // O(1)
Task task = queue.removeFirst();  // O(1)

// ✓ Нужна Deque функциональность
Deque<Integer> deque = new LinkedList<>();
deque.addFirst(1);
deque.addLast(2);
deque.removeFirst();
deque.removeLast();

// ✓ Stack поведение
Stack<Integer> stack = new LinkedList<>();  // или ArrayDeque
stack.push(value);
stack.pop();

// ✓ Queue поведение  
Queue<Integer> queue = new LinkedList<>();
queue.offer(value);
queue.poll();

Best Practice

// ✓ ХОРОШО: for-each loop с LinkedList
for (Integer value : linkedList) {
    processValue(value);
}

// ✓ ХОРОШО: Iterator
for (Iterator<Integer> it = linkedList.iterator(); it.hasNext(); ) {
    Integer value = it.next();
    processValue(value);
}

// ❌ ПЛОХО: индексный цикл с LinkedList
for (int i = 0; i < linkedList.size(); i++) {
    linkedList.get(i);  // O(n²)!
}

// ✓ ХОРОШО: индексный цикл с ArrayList
for (int i = 0; i < arrayList.size(); i++) {
    arrayList.get(i);  // O(n)
}

Заключение

ArrayList быстрее при переборе из-за:

1. Cache locality — элементы в памяти рядом
2. O(1) доступ — прямой адрес в памяти
3. CPU optimization — процессор может предсказать следующий адрес

LinkedList медленнее при переборе по индексу, потому что:

1. Нет cache locality — узлы разбросаны в памяти
2. O(n) доступ по индексу — нужно пройти через узлы
3. Cache misses — на каждый переход к следующему узлу

Используй Iterator для LinkedList, и всё будет быстро. Но для большинства случаев просто используй ArrayList.