Односвязный список: узел, вставка, удаление и обход

На прошлом уроке мы разбирали задачу N ферзей — рекурсию с ограничениями и откатами. В односвязном списке состояние устроено иначе: его задаёт цепочка ссылок между объектами, а операции меняют эту цепочку в строго определённом порядке.

Узел и список: поля, инициализация, структура памяти

Связный список строится из двух классов, и важно сразу понять, что каждый из них делает ровно одно дело.

Node хранит само значение и знает, кто стоит следующим:

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None  # по умолчанию узел ни на кого не указывает

LinkedList хранит только указатель на первый узел — и больше ничего:

class LinkedList:
    def __init__(self):
        self.head = None  # пустой список

Весь список — это просто цепочка объектов Node, связанных полем next. Никакого массива внутри нет. Чтобы добраться до третьего элемента, придётся пройти первый, второй, а потом третий — прямого доступа по индексу не существует.

Это различие — принципиальное. В питоновском list обращение a[5] работает за O(1), потому что список хранит непрерывный массив ссылок и адрес нужной ячейки вычисляется арифметически. Сами объекты при этом не обязаны лежать рядом в памяти. В связном списке адрес следующего узла хранится в next, поэтому до нужной позиции приходится идти по цепочке.

Два базовых способа добавления различаются стоимостью поиска позиции.

Вставка в голову — O(1):

def prepend(self, val):
    new_node = Node(val)
    new_node.next = self.head  # новый узел смотрит на бывшую голову
    self.head = new_node        # голова теперь — новый узел

Два присваивания, константное время. Список из миллиона элементов вставляется в голову так же быстро, как список из одного.

Вставка в хвост — O(n):

def append(self, val):
    new_node = Node(val)
    if self.head is None:
        self.head = new_node
        return
    cur = self.head
    while cur.next is not None:  # ищем последний узел
        cur = cur.next
    cur.next = new_node

Здесь нужно обойти весь список, чтобы найти узел с next == None. Для списка из n элементов выполняется до n переходов или проверок ссылок. Без отдельного указателя tail «прыгнуть» к хвосту нельзя.

Последовательность двух добавлений в хвост и одного добавления в голову даёт цепочку 1 → 2 → 3:

ll = LinkedList()
ll.append(2)
ll.append(3)
ll.prepend(1)  # теперь: 1 -> 2 -> 3 -> None

cur = ll.head
while cur:
    print(cur.val, end=' ')  # 1 2 3
    cur = cur.next

Контракт списка предполагает ациклическую цепочку, которая заканчивается ссылкой None. Узлы — отдельные объекты и могут иметь внешние ссылки помимо цепочки. Удаление имени ll убирает только одну ссылку на объект списка; узлы могут быть освобождены, когда вся цепочка станет недостижимой и на них не останется других ссылок.

Обход списка: инвариант курсора и сбор значений

Обход — самая простая операция, но у неё есть точный инвариант, который стоит сформулировать явно: в начале каждой итерации cur указывает на узел, который ещё не обработан.

def to_list(self):
    result = []
    cur = self.head
    while cur is not None:
        result.append(cur.val)
        cur = cur.next
    return result

Проследим шаги для списка 1 → 2 → 3 → None:

Итерация	cur.val	действие	cur после шага
1	1	добавить 1	узел со значением 2
2	2	добавить 2	узел со значением 3
3	3	добавить 3	None
—	—	условие cur is not None ложно, выход	—

Результат: [1, 2, 3].

Для пустого списка self.head is None, значит cur = None с самого начала. Условие cur is not None сразу ложно — цикл не выполняется ни разу, метод возвращает []. Никакого специального случая не нужно.

Строка cur = cur.next сдвигает курсор к следующему узлу. Если случайно написать cur = cur или пропустить эту строку, цикл станет бесконечным. В связном списке нет счётчика, нет индекса — только следующая ссылка.

Сложность обхода: каждый из n узлов посещается ровно один раз, итого O(n) по времени. Рабочая память курсора — O(1), а возвращаемый список result занимает O(n): в него копируются ссылки на значения, но не сами узлы.

Удаление узла по значению: указатель prev и граничный случай головы

Чтобы удалить узел из середины цепочки, нужно заставить его предшественника смотреть не на него, а на его преемника. Узел исключается именно из основной цепочки; сам объект продолжит существовать, если на него осталась внешняя ссылка.

Отсюда и возникает техника двух указателей: prev — предшественник, cur — кандидат на удаление.

def remove(self, val):
    prev = None
    cur = self.head

    while cur is not None:
        if cur.val == val:
            if prev is None:
                # удаляем голову
                self.head = cur.next
            else:
                # обходим cur: предшественник смотрит на преемника
                prev.next = cur.next
            return  # удаляем только первое вхождение
        prev = cur
        cur = cur.next

Когда нужный узел найден и prev is not None, достаточно одного присваивания: prev.next = cur.next. Это не трогает сам cur — поле cur.next остаётся прежним, объект существует. Просто больше никто из основной цепочки на него не указывает.

А вот случай prev is None — это удаление головы, и здесь скрыта ловушка. Если попробовать написать prev.next = cur.next, Python немедленно выбросит AttributeError: 'NoneType' object has no attribute 'next'. Значение None — не объект Node, у него нет поля next. Поэтому голова обрабатывается отдельной веткой: self.head = cur.next.

Пример охватывает удаление из середины, удаление головы и отсутствующее значение:

ll = LinkedList()
for v in [1, 2, 3, 4]:
    ll.append(v)
# 1 -> 2 -> 3 -> 4 -> None

ll.remove(2)
print(ll.to_list())  # [1, 3, 4]

ll.remove(1)  # удаление головы
print(ll.to_list())  # [3, 4]

ll.remove(99)  # нет такого значения — список не меняется
print(ll.to_list())  # [3, 4]

Метод завершается через return сразу после удаления, потому что контракт требует удалить только первое вхождение. Само присваивание prev.next = cur.next не меняет поле cur.next, поэтому при удалении всех вхождений можно было бы продолжить с cur = cur.next. Отдельная переменная nxt понадобилась бы, если перед продолжением код дополнительно обнулял бы cur.next.

Сложность: в худшем случае (удаляемый элемент в хвосте или отсутствует) обходим весь список — O(n). Дополнительной памяти не тратим — O(1).

Разворот списка на месте: три указателя и граничные случаи

Задача — развернуть список так, чтобы 1 → 2 → 3 → None превратился в 3 → 2 → 1 → None. Никаких дополнительных списков, никакого рекурсивного стека — только перенаправление ссылок на ходу.

Идея: идём по списку и у каждого узла разворачиваем стрелку next назад. Для этого нужны три указателя: prev (куда будет смотреть cur.next), cur (текущий узел), nxt (следующий узел, которого нам нужно запомнить до того, как мы сломаем ссылку).

def reverse(self):
    prev = None
    cur = self.head

    while cur is not None:
        nxt = cur.next    # 1. запомнить следующий
        cur.next = prev   # 2. развернуть стрелку
        prev = cur        # 3. сдвинуть prev
        cur = nxt         # 4. перейти к следующему

    self.head = prev  # prev стоит на новой голове

Порядок этих четырёх строк — жёсткое требование. Если переставить шаги 1 и 2, произойдёт следующее:

# НЕВЕРНО:
cur.next = prev   # стрелка перенаправлена
nxt = cur.next    # nxt = prev, а не следующий узел — он потерян навсегда

Из состояния алгоритма остаток исходной цепочки становится недостижим: ни cur, ни prev на него больше не указывают, и список разрывается.

Проследим три шага для 1 → 2 → 3 → None:

Итерация	cur	nxt	cur.next стало	prev	cur после
1	1	2	None	1	2
2	2	3	1	2	3
3	3	None	2	3	None

После цикла prev = 3, self.head = 3.

Результат: 3 → 2 → 1 → None.

Пустой список (self.head is None): cur = None, условие цикла сразу ложно, тело не выполняется. self.head = prev = None — список остался пустым. Всё корректно.

Один узел (1 → None): одна итерация. nxt = None, cur.next = None (было и так), prev = узел_1, cur = None. Выходим. self.head = prev — тот же единственный узел. Список не изменился, и это правильно.

ll = LinkedList()
ll.reverse()
print(ll.to_list())  # []

ll.append(42)
ll.reverse()
print(ll.to_list())  # [42]

for v in [1, 2, 3]:
    ll.append(v)
# теперь: 42 -> 1 -> 2 -> 3
ll.reverse()
print(ll.to_list())  # [3, 2, 1, 42]

Сложность — O(n) по времени: каждый узел посещается ровно один раз. Дополнительная память — O(1): три указателя, никаких вспомогательных структур.

Заметьте, что nxt здесь выполняет другую роль, чем prev в операции удаления. При удалении prev нужен, чтобы знать, чью ссылку менять. При развороте nxt нужен исключительно для того, чтобы не потерять продолжение цепочки в момент, когда мы ломаем ссылку cur.next. Это две разные задачи, и обе решаются одним и тем же принципом: сначала сохрани то, что потеряешь, потом изменяй.

Как продолжить практику

После этого разбора важно уметь сравнивать стоимость поиска в списке и хеш-таблице, учитывать память и граничные случаи. Для сравнения решений открыт соседний урок: хеш-таблицы и dict. Текущий материал — бесплатное превью; полный курс алгоритмов и структур данных на Python платный. В его программе можно посмотреть последовательность тем и выбрать, подходит ли вам дальнейшая практика.