Когда я увидела в разделе Easy LeetCode задачи со связными списками, сначала было недоумение: что это такое???? Я погуглила, но это не помогло, потому что мне не нужны были ответы вроде:
-
Почему связный список эффективнее, чем то-то и то-то?
-
Как хранит данные связный список?
-
И при чём тут вообще O(n)???
Мне хотелось найти подробное и понятное объяснение вот чего:
-
Связный список и список — это одно и то же?
-
Как им пользоваться? (Не супералгоритмы, а просто увидеть, что он хранит внутри.)
-
Почему в разговорах о связных списках всегда есть упоминание класса, который создаёт этот список?
-
Как создавать, как выводить и как вообще что-то с ними делать на уровне LeetCode Easy и на собеседованиях?
Поэтому, если вам тоже непонятно — погнали разбираться!
Почему разговор про связные списки начинают с классов
В Python нет такой структуры, как linked list, которую можно использовать напрямую, как, например, dict, list или deque (который, кстати, реализован на двусвязном списке).
То есть любая структура данных в Python — это класс. Часть из них уже реализована в стандартной библиотеке (чаще на языке C) и готова к использованию, а другие нужно сначала написать самостоятельно.
Поэтому, когда в Python заходит речь о связных списках, либо даётся готовый класс, который нужно использовать (как, например, в задаче, которую я привожу ниже), либо его требуется написать самостоятельно.
Разница между написанием класса самостоятельно и использованием готового варианта лишь в том, что нам нужно знать имена атрибутов класса, чтобы корректно работать с ним. Особенно это важно при автоматической проверке на платформе, куда мы отправляем задачу: если решение не соответствует ожиданиям, оно просто не запустится.
Теперь давайте посмотрим на пример реализации класса из одной из задач LeetCode (он даётся в прекоде к задаче 21. Merge Two Sorted Lists):
class LinkedList(object):
def __init__(self,val=0, next=None):
self.val = val
self.next = next
Здесь всего два атрибута: val и next. Этого вполне достаточно — в односвязных списках обычно используются именно они. Эти атрибуты могут называться по-разному (value, next_item), но принцип работы от этого не меняется, и в дальнейшем мы это рассмотрим.
Что такое связный список
Из предыдущего параграфа мы выяснили, что класс для связного списка нужен лишь потому, что эта структура не реализована в Python. Она и правда не широко используется в этом языке (почему — разбираться здесь не будем).
Начнём с того, что создадим объект LinkedList, используя вышеописанный класс.
# Ничего не передаем и смотрим что будет у этого объекта
my_list = LinkedList() # создали объект класса
# Смотрим какие атрибуты у этого объекта
print(my_list.val) # ожидаемый вывод 0
print(my_list.next) # ожидаемый вывод None
Разбор работы конструктора
Если при создании объекта ничего не передавать в качестве параметров, то по умолчанию присваиваются значения, указанные в методе __init__ класса LinkedList: def __init__(self,val=0, next=None)
Это означает, что при создании объекта связного списка без параметров мы получим один узел:
-
val — значение узла (по умолчанию 0).
-
next — ссылка на следующий узел (по умолчанию None).
Что можно хранить в val и next
-
В качестве val можно использовать любой объект: int, str, list, dict — что угодно.
-
Что должно быть в next — станет понятнее дальше.
Однако с этим классом пока ничего нельзя сделать: ни append, ни insert.
Теперь попробуем создать полноценный связный список из массива.
Создание связного списка из массива
Попробуем передать весь массив в качестве аргумента, чтобы убедиться, что это не работает:
|
print(my_list.val)
[1, 2, 3, 4, 5] # ожидаемый вывод
Когда мы вывели print(my_list), то увидели ссылку на объект — никаких ошибок!
Это говорит о том, что элементом в узле связного списка может быть что угодно, в том числе и массив.
Однако то, что в val хранится массив, не делает этот массив связным списком. Мы просто создали один узел, у которого в качестве значения (val) лежит сам массив.
Второй print показывает, что просмотреть содержимое узла можно только через атрибут val.
Теперь корректно создадим связный список вручную, передав в него все элементы по отдельности.
|
Теперь понятно, почему мы начинаем с конца:
чтобы у каждого узла next уже указывал на следующий готовый узел.
Связный список работает только тогда, когда в next передаётся объект класса LinkedList. Если же мы попробуем сделать это интуитивно неправильно, например:
|
И попытаемся получить доступ к последнему узлу, то получим исключение:
Ошибка Возникло исключение:
AttributeError 'int' object has no attribute 'next' |
Почему возникает ошибка?
Мы положили в next число 5. Однако у int нет атрибута next, поэтому при попытке обратиться к нему программа падает с ошибкой.
Главное правило:
В next всегда должен лежать объект LinkedList — тогда узлы смогут правильно "раскрываться" при вызове next, как матрёшки.
Как просмотреть содержимое связного списка
Мы уже много говорили про next, и теперь посмотрим, как его использовать на практике.
Если мы просто выведем объект связного списка с print, то увидим, что это просто ссылка на объект, а не его содержимое:
|
Чем LinkedList отличается от обычного списка? Связный список совсем не похож на обычный list в Python. Например, если мы выводим обычный список, всё просто:
# [1, 2, 3, 4, 5] |
Теперь выводим элементы связного списка
print(my_list.val) # Ожидаемый вывод: 1 |
У нас 5 элементов и логично 5 раз выводить print() чтобы посмотреть все элементы, так?
Наверно ты уже догадался что будет
print(my_list.val) print(my_list.val) print(my_list.val) print(my_list.val) 1 1 1 1 1 |
Мы 5 раз увидим вывод 1-го элемента
Чтобы увидеть все элементы, нужно каждый раз сдвигаться к следующему узлу через next:
print(my_list.val) # ожидаемый вывод 1 print(my_list.next.next.val) # ожидаемый вывод 3 |
Вуаля!
Но конечно это хардкод, и так делать стоит исключительно из любопытства и для демонстрации. Вот тут то и пригождается нам понятие голова списка (но об этом в другой статье)
Сейчас посмотрим как вывести связный список через цикл while
Вывод связного списка через while
Мы всегда начинаем проход связного списка с первого элемента.
Алгоритм: Получаем значение узла через val.
Переходим к следующему узлу через next.
Если бы нам сразу дали последний узел, то next у него был бы None — значит, дальше двигаться некуда. (Мы разбираем только односвязный список, который умеет двигаться только вперёд.)
Почему используем while, а не for?
В связном списке неизвестно заранее количество элементов.
Поэтому for не подходит, а while идеально вписывается в логику:
Пока next не стал None, продолжаем движение по списку и выводим значения.
# Создаем связный список 1 -> 2 -> 3 -> 4 -> 5 -> None |
|
Вуаля! Наш связный список распакован в массив
Теперь разберёмся, почему в условии остановки используется while my_list is not None
Как мы помним, в последнем узле next равен None, что означает, что за ним больше нет узлов.
Поскольку на каждой итерации мы обновляем my_list, присваивая ему следующий узел, на последнем шаге my_list становится None.
Разбираем проход по списку шаг за шагом
Первая итерация
my_list = my_list # 1-й узел (val = 1, next = node2)
element = my_list.val # → 1
my_list = my_list.next # Переходим к следующему узлу (node2)
Вторая итерация
my_list = my_list # 2-й узел (val = 2, next = node3)
element = my_list.val # → 2
my_list = my_list.next # Переходим к следующему узлу (node3)
Важно! Прошлые узлы уже не хранятся в my_list. После перехода my_list уже не содержит ссылку на node1, и связный список "укорачивается" в процессе прохода.
Третья итерация
my_list = my_list # 3-й узел (val = 3, next = node4)
element = my_list.val # → 3
my_list = my_list.next # Переход к node4
Четвёртая итерация
my_list = my_list # 4-й узел (val = 4, next = node5)
element = my_list.val # → 4
my_list = my_list.next # Переход к node5
Пятая итерация
my_list = my_list # 5-й узел (val = 5, next = None)
element = my_list.val # → 5
my_list = my_list.next # Переход к None
Теперь my_list = None, и мы подошли к концу списка.
Шестая итерация
while my_list is not None: # Условие не выполняется
Цикл останавливается, так как my_list стал None.
Итог
Мы прошлись по всем узлам, шаг за шагом обрабатывая их.
Как только my_list = None, цикл while завершается.
Теперь стало понятно, как связный список "раскручивается" в процессе прохода!
На этой анимации видно как двигается начало связного списка на каждой итерации

Автор: AV-BOLT