Почему вставка элемента в начало в LinkedList быстрее, чем в ArrayList?

Почему вставка элемента в начало в LinkedList быстрее, чем в ArrayList

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

Структура ArrayList

ArrayList использует динамический массив под капотом:

public class ArrayList<E> extends AbstractList<E> {
    private static final int DEFAULT_CAPACITY = 10;
    private Object[] elementData;  // Внутренний массив
    private int size;
}

Визуально это выглядит так:

Внутренний массив (index по памяти):
┌─────┬─────┬─────┬─────┬─────┬─────┐
│ A │ B │ C │ D │ null│ null│
└──┬──┴──┬──┴──┬──┴──┬──┴─────┴─────┘
   0    1    2    3    4

Добавляем X в позицию 0:
┌─────┬─────┬─────┬─────┬─────┬─────┐
│ X │ A │ B │ C │ D │ null│
└─────┴─────┴─────┴─────┴─────┴─────┘
  0    1    2    3    4    5

Что происходит при вставке в ArrayList

Программа должна:

1. Сдвинуть ВСЕ элементы на одну позицию вправо
2. Вставить новый элемент

public void add(int index, E element) {
    if (index < 0 || index > size)
        throw new IndexOutOfBoundsException();
    
    // Шаг 1: Если нет место, расширить массив
    if (size == elementData.length)
        grow();  // Создать новый массив, скопировать данные
    
    // Шаг 2: Сдвинуть элементы
    System.arraycopy(elementData, index, 
                     elementData, index + 1, 
                     size - index);
    
    // Шаг 3: Вставить элемент
    elementData[index] = element;
    size++;
}

Сложность для вставки в начало (index = 0):

• O(n) — нужно скопировать ВСЕ n элементов

add(0, X)  на ArrayList из 1000 элементов
= 1000 операций копирования

Структура LinkedList

LinkedList использует двусвязный список:

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;
    }
}

Визуально:

Первый элемент:
┌──────┐
│ Node │ ← first
│ data:A │
│ prev:null│
│ next:───┐
└──────┘ │
         ↓
        ┌──────┐
        │ Node │
        │ data:B │
        │ prev:◄──┐
        │ next:───┤
        └──────┘ │
                 ↓
                ┌──────┐
                │ Node │ ← last
                │ data:C │
                │ prev:◄──┐
                │ next:null│
                └──────┘

Вставка в LinkedList

public void addFirst(E e) {
    linkFirst(e);
}

private void linkFirst(E e) {
    final Node<E> f = first;     // Сохранить старый первый
    final Node<E> newNode = new Node<>(null, e, f);  // Создать новый
    first = newNode;             // Новый становится первым
    if (f == null)               // Если список был пустой
        last = newNode;
    else
        f.prev = newNode;        // Обновить prev старого первого
    size++;
}

Сложность для вставки в начало:

• O(1) — всего 3-4 операции присваивания!

addFirst(X)  на LinkedList из 1000 элементов
= 4 операции (создание Node, обновление ссылок)

Визуальное сравнение

ArrayList

До добавления:
[A][B][C][D][E]

Добавляем X в позицию 0:

1. Сдвигаем:
   [A][B][C][D][E] → [?][A][B][C][D][E]
   
2. Копируем:
   System.arraycopy(5 элементов)
   
3. Вставляем:
   [X][A][B][C][D][E]
   
Время: O(n) ~ 5 операций для 5 элементов

LinkedList

До добавления:
first → [A]←→[B]←→[C]←→[D]←→[E] ← last

Добавляем X в начало:

1. Создаём Node(data=X)
2. first.prev = newNode
3. newNode.next = first
4. first = newNode

После:
first → [X]←→[A]←→[B]←→[C]←→[D]←→[E] ← last

Время: O(1) ~ 4 операции всегда

Практический тест

ArrayList<Integer> arrayList = new ArrayList<>();
LinkedList<Integer> linkedList = new LinkedList<>();

// Заполнить обе на 10,000 элементов
for (int i = 0; i < 10_000; i++) {
    arrayList.add(i);
    linkedList.add(i);
}

// Вставка в начало для ArrayList
long start = System.nanoTime();
for (int i = 0; i < 1000; i++) {
    arrayList.add(0, -1);  // O(n) каждый раз!
}
long arrayTime = System.nanoTime() - start;
System.out.println("ArrayList: " + arrayTime + " ns");
// Результат: ~500,000,000 ns (500 ms)

// Вставка в начало для LinkedList
start = System.nanoTime();
for (int i = 0; i < 1000; i++) {
    linkedList.addFirst(-1);  // O(1) каждый раз!
}
long linkedTime = System.nanoTime() - start;
System.out.println("LinkedList: " + linkedTime + " ns");
// Результат: ~1,000,000 ns (1 ms)

// Разница: ~500x раз!
System.out.println("Ratio: " + (arrayTime / linkedTime));

Математическое обоснование

Для ArrayList:

Вставка в начало = скопировать n элементов
Вставка на позицию i = скопировать (n-i) элементов
Вставка в конец = O(1) amortized

Вставка в начало (i=0): O(n)

Для LinkedList:

Вставка в начало = найти позицию + обновить ссылки
Нахождение первого = O(1) (first pointer)
Обновление ссылок = O(1) (4 присваивания)

Вставка в начало: O(1)

Но есть подвох!

Доступ к элементу в LinkedList

int x = linkedList.get(9999);  // O(n) - нужно пройти список!
int y = arrayList.get(9999);   // O(1) - прямой доступ по индексу

Кэш процессора

ArrayList использует последовательную память:

Внутренний массив в памяти:
Address: 1000 1008 1016 1024 1032
         [A]  [B]  [C]  [D]  [E]
                           ↑ CPU кэш подгружает соседние

LinkedList разбросан по памяти:

Node A   at 2000 → next at 3500
Node B   at 3500 → next at 1200
Node C   at 1200 → next at 4800
Node D   at 4800 → next at 2300

Кэш miss! Cache miss! Cache miss!

Выводы

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

ArrayList:

• Частый доступ по индексу
• Добавление в конец
• Стабильный размер
• Приоритет: скорость чтения

LinkedList:

• Частое добавление/удаление из начала/конца
• Очередь (Queue) или стек (Deque)
• Размер постоянно меняется
• Приоритет: скорость вставки

Резюме

LinkedList быстрее при вставке в начало из-за O(1) временной сложности против O(n) у ArrayList. LinkedList просто обновляет несколько ссылок, в то время как ArrayList должен скопировать все элементы в памяти. Это фундаментальное различие в архитектуре данных.