Класс узла и построение списка

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

В Python каждый узел представляется небольшим классом, содержащим val и next. Соединение узлов образует список; у последнего узла next равен None, что обозначает конец списка.

На собеседованиях Вам часто дают список и просят построить его эквивалент в виде связного списка или выполнить обратное преобразование. Вспомогательные функции build и to_list стоит запомнить: build соединяет узлы из массива, а to_list проходит по списку и собирает значения для удобной проверки.

Построение связного списка из n элементов занимает время O(n) и пространство O(n). Использование фиктивного головного узла упрощает пограничные случаи, когда первый узел может измениться.

Вставка нового узла в начало выполняется за O(1): создайте узел, укажите в его next старую голову списка и верните новый узел как голову. Вставка в конец (tail) требует пройти до последнего узла (O(n)), а затем связать его с новым узлом.

Использование фиктивного головного узла устраняет особый случай пустого списка при обеих вставках, поскольку dummy.next всегда указывает на настоящую голову списка.

Чтобы удалить первый узел с заданным значением, поддерживайте указатель prev на один шаг позади curr. Когда curr.val == target, установите prev.next = curr.next, чтобы обойти этот узел. Фиктивный головной узел особенно полезен здесь, поскольку устраняет особый случай удаления самой головы списка: prev всегда может начинаться с фиктивного узла.

Распространённая ошибка — потерять узел при обновлении указателей. Всегда сохраняйте next перед его перезаписью: saved = curr.next, а затем переназначайте указатель. Изобразите список в виде блоков, соединённых стрелками, и перед написанием кода на бумаге выполните каждое обновление указателя. Такой визуальный подход предотвращает случайные ошибки обращения через нулевой указатель на собеседованиях.

Помните: в Python переназначение curr.next не влияет на сам curr, но если перед сохранением потерять ссылку на curr.next, продолжить обход вперёд уже невозможно.

Односвязный список хранит только указатель next; обход выполняется в одном направлении. Двусвязный список хранит и prev, и next, обеспечивая обход назад за O(1) и удаление за O(1) при наличии прямой ссылки на узел (цикл с отслеживанием предыдущего узла не нужен).

collections.deque в Python реализован как двусвязный список, поэтому поддерживает appendleft и popleft за O(1). На собеседованиях Вы будете реализовывать односвязные списки; двусвязные списки встречаются при проектировании кэша LRU.

Три вспомогательные функции, которые стоит иметь под рукой на любом собеседовании по связным спискам: length(head) подсчитывает узлы за O(n), tail(head) возвращает последний узел за O(n), а print_list(head) форматирует список для отладки. Если они готовы заранее, Вы сможете сосредоточиться на основном алгоритме, а не заново реализовывать вспомогательную логику.

Техника двух указателей так же важна для связных списков, как и для массивов, но здесь указателями служат узлы связного списка, а не индексы. Распространённые варианты включают медленный и быстрый указатели (быстрый перемещается в 2 раза быстрее) для поиска середины и обнаружения циклов, а также пару предшествующий и текущий узлы для удаления и разворота.

Всегда явно инициализируйте оба указателя и внимательно обрабатывайте проверку завершения списка — fast and fast.next предотвращает ошибки обращения через нулевой указатель, когда быстрый указатель находится рядом с концом.

Шаблон фиктивной головы (узла-сторожа) — один из самых полезных приёмов в задачах со связными списками. Добавив в начало фиктивный узел со значением 0, Вам не придётся отдельно обрабатывать пустой список или изменение настоящей головы. Результат всегда находится в dummy.next. Этот шаблон встречается при слиянии отсортированных списков, удалении узла с конца по заданному номеру, разделении списка и во многих других задачах.

Большинство операций со связными списками имеют следующие оценки сложности. Доступ по индексу: O(n) — необходимо пройти от головы списка. Вставка или удаление в известном узле: O(1) — достаточно перенастроить указатели. Вставка или удаление в позиции k: O(k) — сначала нужно выполнить обход. Поиск: O(n) — в худшем случае просматривается весь список. Для всех операций на месте пространственная сложность равна O(1), если не учитывать дополнительные структуры данных.

Сравните это с массивами: массивы обеспечивают доступ за O(1), но вставка и удаление занимают O(n) из-за сдвига элементов. Связные списки лучше подходят, когда часто выполняются вставки и удаления в произвольных позициях.

Перед написанием кода для связного списка изобразите список наглядно, используя блоки и стрелки. Вслух проверьте пограничные случаи: пустой список, один узел, чётная и нечётная длина. Используйте фиктивный головной узел для упрощения граничных условий. Всегда рано проверяйте if not head. После написания кода выполните трассировку решения на списке из трёх узлов, чтобы обнаружить ошибки в указателях раньше интервьюера.

Большинство ошибок в связных списках возникает по одной из трёх причин: забыли сохранить next перед его перезаписью, допустили ошибку на единицу в условии завершения или не обработали случай изменения головы списка — фиктивный узел полностью устраняет третью причину.

Проверьте, насколько хорошо Вы понимаете изложенные в этом уроке концепции структур данных и алгоритмов — подготовки к техническим собеседованиям.

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