Какая сложность вставки в конец в LinkedList?

# Сложность вставки в конец LinkedList

Краткий ответ

O(1) — вставка в конец LinkedList имеет константную временную сложность.

Подробное объяснение

Структура LinkedList

LinkedList в Java — это двусвязный список (doubly-linked list). Каждый элемент содержит:

• Данные (значение)
• Ссылку на следующий узел (next)
• Ссылку на предыдущий узел (prev)

head (сразу доступна)
  ↓
[Node1] ←→ [Node2] ←→ [Node3] ←→ tail (сразу доступна)

Почему O(1)?

Специальная оптимизация в LinkedList: контейнер всегда хранит ссылку на последний узел (tail).

public class LinkedList<E> {
    transient Node<E> first;  // указатель на начало
    transient Node<E> last;   // указатель на конец (ключевой момент!)
    transient int size;        // размер списка
    
    // Узел списка
    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;
        }
    }
}

Процесс вставки в конец

public boolean add(E e) {
    linkLast(e);
    return true;
}

void linkLast(E e) {
    final Node<E> l = last;  // O(1) - просто читаем последний узел
    final Node<E> newNode = new Node<>(l, e, null);  // O(1) - создание нового узла
    last = newNode;  // O(1) - обновляем указатель
    if (l == null)
        first = newNode;  // O(1) - если список пуст
    else
        l.next = newNode;  // O(1) - обновляем ссылку предыдущего узла
    size++;  // O(1) - увеличиваем счетчик
}

Все операции выполняются за константное время, поэтому сложность O(1).

Сравнение с ArrayList

Операция          ArrayList    LinkedList
─────────────────────────────────────────
Добавить в конец   O(1)*        O(1)
Добавить в начало  O(n)         O(1)
Добавить в середину O(n)        O(n)
Получить элемент   O(1)         O(n)
Удалить из конца   O(1)         O(1)
Удалить из начала  O(n)         O(1)

• ArrayList имеет amortized O(1) только при наличии свободного места. При необходимости расширения — O(n).

Сравнение с вставкой в начало LinkedList

Вставка в начало LinkedList также O(1), потому что хранится указатель на first:

void linkFirst(E e) {
    final Node<E> f = first;  // O(1) - получить первый узел
    final Node<E> newNode = new Node<>(null, e, f);  // O(1) - создать новый
    first = newNode;  // O(1) - обновить first
    if (f == null)
        last = newNode;  // O(1)
    else
        f.prev = newNode;  // O(1) - обновить ссылку
    size++;  // O(1)
}

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

Вставка в произвольную позицию

Вставка в произвольную позицию в LinkedList требует O(n), потому что нужно найти позицию:

public void add(int index, E element) {
    checkPositionIndex(index);
    if (index == size)
        linkLast(element);  // O(1)
    else
        linkBefore(element, node(index));  // node(index) - O(n)!
}

Node<E> node(int index) {
    // Оптимизация: если индекс близко к концу - идем с конца
    if (index < (size >> 1)) {
        Node<E> x = first;  // идем с начала
        for (int i = 0; i < index; i++)
            x = x.next;  // O(index)
        return x;
    } else {
        Node<E> x = last;  // идем с конца
        for (int i = size - 1; i > index; i--)
            x = x.prev;  // O(size - index)
        return x;
    }
}

Практические примеры

Пример 1: Вставка в конец

LinkedList<Integer> list = new LinkedList<>();
list.add(10);  // O(1)
list.add(20);  // O(1)
list.add(30);  // O(1)
// Total: O(1) * 3 = O(1)

Пример 2: Вставка в начало

LinkedList<Integer> list = new LinkedList<>();
list.addFirst(10);  // O(1)
list.addFirst(20);  // O(1)
list.addFirst(30);  // O(1)
// Total: O(1) * 3 = O(1)

Пример 3: Вставка в середину

LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < 1000; i++) {
    list.add(i);  // O(1) каждый
}
list.add(500, 999);  // O(500) - нужно найти позицию 500

Почему это важно знать

1. Выбор структуры данных зависит от того, какие операции часто используются:

   • Частые обращения по индексу → ArrayList
   • Частые вставки/удаления в начало/конец → LinkedList

2. Оптимизация кода:

   // ❌ Плохо - O(n²) итого
   LinkedList<Integer> list = new LinkedList<>();
   for (int i = 0; i < n; i++) {
       list.get(i);  // O(n) для каждого элемента
   }
   
   // ✅ Хорошо - O(n) итого
   for (Integer value : list) {  // использует iterator
       // work with value
   }
   

3. Конкурентный доступ - LinkedList не синхронизирован:

   // Если нужна синхронизация
   List<Integer> list = Collections.synchronizedList(
       new LinkedList<>()
   );
   

Важные аспекты

Память

LinkedList использует больше памяти на узел (prev + next указатели):

• ArrayList: 8 байт на элемент (в среднем)
• LinkedList: 24+ байта на элемент (в среднем)

Cache locality

ArrayList имеет лучшую cache locality - элементы находятся рядом в памяти, что дает лучшую производительность при итерации.

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

Даже несмотря на O(1) для вставки в конец, часто ArrayList более эффективен на практике благодаря cache locality и меньшей памяти:

// В 99% случаев это лучше
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 1_000_000; i++) {
    list.add(i);  // O(1) amortized, хорошая cache locality
}

Резюме

• LinkedList.add(E) (вставка в конец) имеет сложность O(1)
• Это возможно благодаря хранению ссылки на последний узел (tail)
• Вставка в произвольную позицию все равно O(n)
• На практике ArrayList часто лучше для большинства случаев