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

Сложность операций в LinkedList в Java

Базовая теория структур данных

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

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

Эти особенности напрямую влияют на временную сложность операций.

Сложность поиска (доступа по индексу)

Временная сложность: O(n) - линейное время

// Пример поиска по индексу в LinkedList
LinkedList<String> list = new LinkedList<>();
list.add("A");
list.add("B");
list.add("C");
list.add("D");

// Внутренняя реализация get(index)
String element = list.get(2); // O(n) операция

Почему O(n):

1. LinkedList не имеет прямого доступа к элементам по индексу
2. Для поиска элемента с индексом i необходимо пройти от начала (или конца, если индекс ближе к концу) списка, переходя по ссылкам next/prev
3. В худшем случае (поиск среднего элемента) требуется пройти n/2 узлов
4. В Big O нотации это оценивается как O(n)

// Упрощенное представление обхода в get(index)
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;
    }
}

Сложность вставки

Здесь ситуация интереснее и зависит от точки вставки:

1. Вставка в начало/конец (addFirst()/addLast()): O(1)

LinkedList<Integer> list = new LinkedList<>();
list.addFirst(1);  // O(1) - просто создаем новый узел
list.addLast(10);  // O(1) - обновляем ссылки last

2. Вставка в середину по индексу: O(n)

list.add(2, 5);  // O(n) - сначала поиск позиции O(n), затем вставка O(1)

Разбор сложности вставки в середину:

1. Поиск позиции вставки: O(n)
2. Создание нового узла и обновление ссылок: O(1)
3. Итоговая сложность: O(n)

Однако сама операция изменения ссылок после нахождения позиции — O(1):

// Псевдокод вставки после нахождения позиции
void linkBefore(E element, Node<E> successor) {
    final Node<E> predecessor = successor.prev;
    final Node<E> newNode = new Node<>(predecessor, element, successor);
    successor.prev = newNode;
    if (predecessor == null)
        first = newNode;
    else
        predecessor.next = newNode;
    size++;
}

Сравнение с ArrayList

*В ArrayList возможен resize массива, что дает O(n)

Практические рекомендации

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

• Часто вставляете/удаляете элементы в начале списка
• Работаете с очередями (FIFO) или стеками (LIFO)
• Имеете частые вставки/удаления при итерации через итератор (O(1) при известной позиции)

Избегайте LinkedList, когда:

• Нужен частый доступ по индексу (get(index)) – Имеете много операций поиска элементов
• Важна cache-локальность процессора (ArrayList использует непрерывный блок памяти)

Оптимизации в современной Java

В Java 8+ для операций get(index) в LinkedList добавлена оптимизация — поиск начинается с начала или конца в зависимости от того, какая половина списка ближе к целевому индексу. Однако это лишь сокращает константный множитель, но не меняет асимптотическую сложность O(n).

Ключевой вывод: Выбор между LinkedList и ArrayList должен основываться на преобладающих операциях в вашем конкретном сценарии использования, а не на интуитивных представлениях о производительности.