Сложность вставки в связный список: O(1) или O(n)?

Почему вставка в связный список — это не всегда O(1)

Многие разработчики сталкиваются с путаницей, когда слышат, что вставка в связный список выполняется за O(1). Ведь чтобы вставить элемент, нужно сначала найти нужное место! В этой статье мы разберем, когда вставка действительно быстрая, а когда нет, и почему важно понимать контекст. Вы научитесь точно оценивать сложность алгоритмов и избежите типичных ошибок на собеседованиях.

Основная часть: разбор сложности вставки

Что такое связный список и как он устроен

Связный список — это структура данных, состоящая из узлов, каждый из которых содержит значение и ссылку на следующий узел. В отличие от массива, элементы не хранятся в непрерывной памяти, а «связаны» указателями.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

# Создаем список: A -> B -> C -> D
a = Node('A')
b = Node('B')
c = Node('C')
d = Node('D')
a.next = b
b.next = c
c.next = d

Чтобы вставить новый узел после существующего, достаточно изменить пару ссылок. Это операция, не зависящая от размера списка, то есть O(1).

Когда вставка действительно O(1)

Если у вас уже есть ссылка на узел, после которого нужно вставить новый элемент, вставка занимает константное время. Например, у нас есть ссылка на узел C, и мы хотим вставить X после него:

def insert_after(prev_node, new_value):
    # Создаем новый узел
    new_node = Node(new_value)
    # Переставляем указатели
    new_node.next = prev_node.next
    prev_node.next = new_node

# Вставляем X после C
insert_after(c, 'X')
# Теперь список: A -> B -> C -> X -> D

Здесь мы не проходим по списку — просто меняем ссылки. Сложность — O(1).

Когда вставка становится O(n)

Но что если у нас нет ссылки на нужный узел? Например, мы хотим вставить X после узла со значением 'C'. Тогда нам придется сначала найти этот узел, а это уже линейный проход по списку:

def find_node(head, value):
    current = head
    while current is not None:
        if current.value == value:
            return current
        current = current.next
    return None

# Находим узел C
node_c = find_node(a, 'C')
# Вставляем после него
insert_after(node_c, 'X')

Поиск занимает O(n) времени, потому что в худшем случае мы просматриваем все узлы. Суммарно операция «найти и вставить» — O(n).

Ключевое различие: поиск и вставка — разные операции

Важно понимать: связный список не ускоряет поиск элемента. Его преимущество — в дешевой перестройке структуры, когда у вас уже есть ссылка на нужное место. Это принципиальное отличие от массивов, где вставка в середину требует сдвига элементов, но доступ по индексу — O(1).

Когда говорят «вставка в связный список — O(1)», всегда подразумевают, что у вас есть ссылка на узел. Это скрытое допущение часто опускают в объяснениях, что и приводит к путанице.

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

Теперь вы знаете, как точно оценивать сложность операций со связными списками. На собеседовании всегда уточняйте, дана ли ссылка на узел, или нужно сначала найти его. Это покажет ваше глубокое понимание алгоритмов.

Попробуйте прямо сейчас: реализуйте функцию удаления узла из связного списка, когда дана ссылка на удаляемый узел. Подумайте, какова сложность и какие подводные камни могут возникнуть. Упражнение поможет закрепить материал.