Почему временная сложность операций в LinkedList имеет именно такие характеристики?

Почему временная сложность операций в LinkedList имеет такие характеристики

Это глубокий вопрос о том, как устроена структура данных LinkedList и почему разные операции имеют разные сложности. За 10+ лет я видел много bagov именно потому что разработчики не понимали сложность операций в LinkedList.

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

public class LinkedList<E> {
    transient int size = 0;
    
    /**
     * Pointer на первый node
     */
    transient Node<E> first;
    
    /**
     * Pointer на последний node
     */
    transient 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;
        }
    }
}

Визуально:

Две указателя:
first ──┐
        ↓
     [Node1] ←→ [Node2] ←→ [Node3]
                              ↑
                           last ──┐

Каждый Node содержит:
- item (значение)
- next (указатель на следующий)
- prev (указатель на предыдущий)

Временная сложность операций

Почему get(index) это O(n)

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;  // Вот это дорого!
}

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

Примеры:

LinkedList с 1000 элементов:

get(0):    O(1) — x = first ✅ Быстро
get(1):    O(1) — x = first, x = x.next ✅ Очень быстро
get(500):  O(500) — идём с конца: 1000-500=500 шагов
get(999):  O(1) — x = last ✅ Быстро
get(100):  O(100) — идём с начала ❌ Медленно

Почему add(E) это O(1)

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

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

Визуально:

До добавления:
first ──→ [1] ←→ [2] ←→ [3] ←── last

Добавляем 4:
last указывает на [3], создаём новый [4]

После добавления:
first ──→ [1] ←→ [2] ←→ [3] ←→ [4] ←── last

Время: O(1)
Потому что мы сразу знаем where to add (last)
Не нужно ничего искать или сдвигать

Почему add(int, E) это 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(index)
}

private void linkBefore(E e, Node<E> succ) {
    final Node<E> pred = succ.prev;  // O(1)
    final Node<E> newNode = new Node<>(pred, e, succ);  // O(1)
    succ.prev = newNode;  // O(1)
    if (pred == null)
        first = newNode;  // O(1)
    else
        pred.next = newNode;  // O(1)
    size++;  // O(1)
}

Примеры:

LinkedList с 1000 элементов:

add(0, value):    O(1) — вставляем перед first ✅
add(1000, value): O(1) — вставляем в конец (linkLast) ✅
add(500, value):  O(500) — node(500) это O(500) ❌
add(100, value):  O(100) — node(100) это O(100) ❌

Почему remove(int) это O(n)

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));  // node(index) это O(index)
}

E unlink(Node<E> x) {
    final E element = x.item;  // O(1)
    final Node<E> next = x.next;  // O(1)
    final Node<E> prev = x.prev;  // O(1)
    
    if (prev == null) {
        first = next;  // O(1)
    } else {
        prev.next = next;  // O(1)
        x.prev = null;  // O(1)
    }
    
    if (next == null) {
        last = prev;  // O(1)
    } else {
        next.prev = prev;  // O(1)
        x.next = null;  // O(1)
    }
    
    x.item = null;  // O(1)
    size--;  // O(1)
    return element;
}

Визуально:

До удаления:
first ──→ [1] ←→ [2] ←→ [3] ←── last

Удаляем элемент с индексом 1 ([2]):
Сначала находим его: node(1) это O(1) шаг
Потом распутываем:
prev ([1]).next = next ([3])
next ([3]).prev = prev ([1])

После удаления:
first ──→ [1] ←→ [3] ←── last

Общая сложность: O(1) для распутывания + O(n) для поиска = O(n)

Сравнение с ArrayList

// ArrayList
get(100):  O(1)    — прямой доступ по индексу
add():     O(1)*   — амортизированная O(1)
add(100):  O(n)    — нужно сдвинуть элементы
remove():  O(n)    — нужно сдвинуть элементы

// LinkedList
get(100):  O(100)  — идём по цепочке
add():     O(1)    — всегда O(1)
add(100):  O(100)  — нужно найти место
remove():  O(n)    — нужно найти элемент

Выбор:

// Если часто делаете get(index) по случайному индексу
List<String> list = new ArrayList<>();  // ✅

// Если часто добавляете/удаляете из конца
List<String> list = new LinkedList<>();  // ✅

// Если часто добавляете/удаляете из начала
List<String> list = new LinkedList<>();  // ✅
list.addFirst(element);   // O(1)
list.removeFirst();        // O(1)

// Если случайный доступ + добавление
List<String> list = new ArrayList<>();  // ✅ ArrayList лучше

Оптимизация в Java LinkedList

// Оптимизация 1: Двусвязный список
// Позволяет идти как с начала, так и с конца
private Node<E> node(int index) {
    if (index < (size >> 1))  // Если первая половина
        return fromFirst(index);  // Идём с начала
    else                           // Если вторая половина
        return fromLast(index);    // Идём с конца
}

// Оптимизация 2: last указатель
public void add(E e) {
    linkLast(e);  // O(1) потому что у нас есть last
}

// Оптимизация 3: first указатель
public E getFirst() {
    return first.item;  // O(1) потому что у нас есть first
}

На практике

// ❌ ПЛОХО: O(n²) сложность!
public void badExample(LinkedList<Integer> list) {
    for (int i = 0; i < list.size(); i++) {
        Integer value = list.get(i);  // O(i) для каждой итерации
    }
    // Общая сложность: 1+2+3+...+n = n(n+1)/2 = O(n²)
}

// ✅ ХОРОШО: O(n) сложность
public void goodExample(LinkedList<Integer> list) {
    for (Integer value : list) {  // Итератор, O(1) за итерацию
        // ...
    }
    // Общая сложность: O(n)
}

// ✅ ХОРОШО: O(n) сложность
public void goodExample2(LinkedList<Integer> list) {
    ListIterator<Integer> iter = list.listIterator();
    while (iter.hasNext()) {  // O(1) за итерацию
        Integer value = iter.next();
    }
}

Вывод: Временная сложность операций

LinkedList сложности:

add(E)              O(1)   — добавляем в конец (last известен)
addFirst(E)         O(1)   — добавляем в начало (first известен)
addLast(E)          O(1)   — добавляем в конец (last известен)
add(int, E)         O(n)   — нужно найти индекс

get(int)            O(n)   — нужно идти по цепочке
getFirst()          O(1)   — first известен
getLast()           O(1)   — last известен

remove(int)         O(n)   — нужно найти индекс
removeFirst()       O(1)   — first известен
removeLast()        O(1)   — last известен
remove(Object)      O(n)   — нужно найти элемент

contains(Object)    O(n)   — нужно линейный поиск
indexOf(Object)     O(n)   — нужно линейный поиск

Почему именно так:

1. get(index) это O(n) — потому что LinkedList это цепочка, нет индексации
2. add() это O(1) — потому что у нас есть указатель last
3. add(int, E) это O(n) — потому что нужно сначала найти индекс
4. remove это O(n) — потому что нужно найти элемент
5. Операции с first/last это O(1) — потому что у нас есть прямые указатели

Это базовые знания структур данных, критичные для Java разработчика.