Когда я увидела в разделе 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. Если же мы попробуем сделать это интуитивно неправильно, например:

И попытаемся получить доступ к последнему узлу, то получим исключение:

❌ Ошибка Возникло исключение:

Почему возникает ошибка?

Мы положили в next число 5. Однако у int нет атрибута next, поэтому при попытке обратиться к нему программа падает с ошибкой.

Главное правило:

? В next всегда должен лежать объект LinkedList — тогда узлы смогут правильно "раскрываться" при вызове next, как матрёшки.

? Как просмотреть содержимое связного списка

Мы уже много говорили про next, и теперь посмотрим, как его использовать на практике.

Если мы просто выведем объект связного списка с print, то увидим, что это просто ссылка на объект, а не его содержимое:

? Чем LinkedList отличается от обычного списка? Связный список совсем не похож на обычный list в Python. Например, если мы выводим обычный список, всё просто:

Теперь выводим элементы связного списка

У нас 5 элементов и логично 5 раз выводить print() чтобы посмотреть все элементы, так?

Наверно ты уже догадался что будет 

Мы 5 раз увидим вывод 1-го элемента

Чтобы увидеть все элементы, нужно каждый раз сдвигаться к следующему узлу через next:

Вуаля!

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

Сейчас посмотрим как вывести связный список через цикл while

Вывод связного списка через while

Мы всегда начинаем проход связного списка с первого элемента.
Алгоритм:
1️⃣ Получаем значение узла через val.
2️⃣ Переходим к следующему узлу через next.

Если бы нам сразу дали последний узел, то next у него был бы None — значит, дальше двигаться некуда. (Мы разбираем только односвязный список, который умеет двигаться только вперёд.)

❓ Почему используем while, а не for?

В связном списке неизвестно заранее количество элементов.
Поэтому for не подходит, а while идеально вписывается в логику:

? Пока next не стал None, продолжаем движение по списку и выводим значения.

? Вуаля! Наш связный список распакован в массив

Теперь разберёмся, почему в условии остановки используется while my_list is not None

Как мы помним, в последнем узле next равен None, что означает, что за ним больше нет узлов.
Поскольку на каждой итерации мы обновляем my_list, присваивая ему следующий узел, на последнем шаге my_list становится None.

? Разбираем проход по списку шаг за шагом

1️⃣ Первая итерация

my_list = my_list  # 1-й узел (val = 1, next = node2)

element = my_list.val  # → 1

my_list = my_list.next  # Переходим к следующему узлу (node2)

2️⃣ Вторая итерация

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, и связный список "укорачивается" в процессе прохода.

3️⃣ Третья итерация

my_list = my_list  # 3-й узел (val = 3, next = node4)

element = my_list.val  # → 3

my_list = my_list.next  # Переход к node4

4️⃣ Четвёртая итерация

my_list = my_list  # 4-й узел (val = 4, next = node5)

element = my_list.val  # → 4

my_list = my_list.next  # Переход к node5

5️⃣ Пятая итерация

my_list = my_list  # 5-й узел (val = 5, next = None)

element = my_list.val  # → 5

my_list = my_list.next  # Переход к None

Теперь my_list = None, и мы подошли к концу списка.

6️⃣ Шестая итерация

while my_list is not None:  # Условие не выполняется

Цикл останавливается, так как my_list стал None.

? Итог

✔ Мы прошлись по всем узлам, шаг за шагом обрабатывая их.
✔ Как только my_list = None, цикл while завершается.

Теперь стало понятно, как связный список "раскручивается" в процессе прохода! ?

На этой анимации видно как двигается начало связного списка на каждой итерации