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

в 14:15, , рубрики: linked list, объяснение для новичков, связный список, структуры данных

Когда я увидела в разделе 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.

Теперь попробуем создать полноценный связный список из массива.

Создание связного списка из массива

Попробуем передать весь массив в качестве аргумента, чтобы убедиться, что это не работает:

my_list = LinkedList([1, 2, 3, 4, 5])
print(my_list)
<__main__.LinkedList object at 0x104d5fe30>

print(my_list.val)

[1, 2, 3, 4, 5] # ожидаемый вывод

Когда мы вывели print(my_list), то увидели ссылку на объект — никаких ошибок!
Это говорит о том, что элементом в узле связного списка может быть что угодно, в том числе и массив.

Однако то, что в val хранится массив, не делает этот массив связным списком. Мы просто создали один узел, у которого в качестве значения (val) лежит сам массив.

Второй print показывает, что просмотреть содержимое узла можно только через атрибут val.

Теперь корректно создадим связный список вручную, передав в него все элементы по отдельности.

list_object =  list([1, 2, 3, 4 5])
# Берем последний узел == 5 и создаем его вручную через класс LinkedList(object)
>>> node5 = LinkedList(5, None) # Next = None означает что это конец списка

>>> node4 = LinkedList(4, node5)

>>> node3 = LinkedList(3, node4)

>>> node2 = LinkedList(2, node3)

>>> node1 = LinkedList(1, node2)

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

Связный список работает только тогда, когда в next передаётся объект класса LinkedList. Если же мы попробуем сделать это интуитивно неправильно, например:

node5 = LinkedList(5, None)

node4 = LinkedList(4, 5) # Ошибка! Вместо next передаём число, а не объект LinkedList

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

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

AttributeError 'int' object has no attribute 'next'
File "/Users/anzhelikaboltneva/Desktop/алгоритмы/leetcode/easy/21. Merge Two Sorted Lists.py", line 50, in <module>
 print(node4.next.next)
^^^^^^^^^^^^^^^
AttributeError: 'int' object has no attribute 'next'

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

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

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

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

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

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

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

print(node1)

<__main__.LinkedList object at 0x104d5fe30>

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

list_object =  list(1, 2, 3, 4, 5)
print(list_object) 

# [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) 

print(my_list.val) 

1 1 1 1 1

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

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

print(my_list.val) # ожидаемый вывод 1
print(my_list.next.val) # ожидаемый вывод 2

print(my_list.next.next.val) # ожидаемый вывод 3
print(my_list.next.next.next.val) # ожидаемый вывод 4
print(my_list.next.next.next.next.val) # ожидаемый вывод 5

Вуаля!

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

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

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

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

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

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

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

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

class LinkedList:
  def __init__(self, val=0, next=None):
      self.val = val
      self.next = next

# Создаем связный список 1 -> 2 -> 3 -> 4 -> 5 -> None
node5 = LinkedList(5)
node4 = LinkedList(4, node5)
node3 = LinkedList(3, node4)
node2 = LinkedList(2, node3)
node1 = LinkedList(1, node2)

result = []

my_list = node1 # передаем первый узел в переменную и теперь тут лежит наш связный список из 5 узлов


while my_list: #-----> while my_list is not None тоже самое
    element = my_list.val # для удобства сохраним в переменную но это необязательно
    result.append(element) # добавили элемент
    # Поменяли указатель
    my_list = my_list.next

print(result)

[1, 2, 3, 4, 5]

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

Теперь разберёмся, почему в условии остановки используется 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 завершается.

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

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

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

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

Автор: AV-BOLT

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js