Переходим к новому разделу в нашем цикле, и теперь в нескольких последующих постах поговорим про структуры данных.
Структура данных под названием "связный список" представляет собой цепочку элементов, где каждый элемент, называемый узлом, содержит в себе полезные данные и ссылку на следующий узел в последовательности. Это можно сравнить с железнодорожным составом, где каждый вагон — это узел, перевозящий пассажиров (данные), а сцепка между вагонами — это ссылка, указывающая на следующий вагон.
Ключевое отличие связного списка от привычного массива заключается в организации хранения элементов в памяти. Массив подобен многоквартирному дому, где все квартиры расположены строго по порядку в одном месте, что позволяет мгновенно найти нужную по номеру. Элементы массива находятся в памяти непрерывно.
Массив в памяти:
[10][20][30][40][50]
↑ ↑ ↑ ↑ ↑
0 1 2 3 4 ← индексы
Связный список же напоминает квест по городу, где дома с подсказками разбросаны в разных местах. Каждый дом содержит не только информацию, но и адрес следующего пункта маршрута. Чтобы добраться до сотого дома, придется последовательно посетить все предыдущие. В памяти узлы списка могут располагаться где угодно, будучи связанными лишь ссылками.
Связный список в памяти:
[10|•]---→[20|•]---→[30|•]---→[40|•]---→[50|×]
↑ ↑
head tail
(начало) (конец)
Основным строительным блоком списка является узел. Этот контейнер включает в себя два поля: для хранения данных и для ссылки на последующий узел. Визуализировать его можно так:
┌─────────────┐
│ data: 42 │ ← наши данные
│ next: •────┼──→ следующий узел
└─────────────┘
Реализуется узел следующим образом:
class Node:
def __init__(self, data):
self.data = data # Храним данные
self.next = None # Изначально никуда не указываем
Создание нескольких связанных узлов выглядит следующим образом:
# Создаем три отдельных узла
node1 = Node(10) # [10|None]
node2 = Node(20) # [20|None]
node3 = Node(30) # [30|None]
# Связываем их вместе
node1.next = node2 # [10|•]→[20|None]
node2.next = node3 # [10|•]→[20|•]→[30|None]
# Теперь у нас есть цепочка: 10 → 20 → 30
Сам связный список — это управляющая структура, которая хранит лишь ссылку на самый первый узел, называемый головой. Изначально список пуст.
class LinkedList:
def __init__(self):
self.head = None # Изначально список пустой
Одной из фундаментальных операций является добавление элемента в конец списка. Этот процесс требует создания нового узла, поиска последнего узла в цепочке и обновления его ссылки.
def append(self, data):
new_node = Node(data) # Создаем новый узел
# Случай 1: Список пустой
if not self.head:
self.head = new_node # Новый узел становится головой
return
# Случай 2: В списке уже есть элементы
last_node = self.head
# Идем по цепочке до последнего узла
while last_node.next:
last_node = last_node.next
# Присоединяем новый узел к концу
last_node.next = new_node
Процесс можно проследить наглядно:
Шаг 1: Пустой список
head → ×
Добавляем 10:
head → [10|×]
Добавляем 20:
head → [10|•]→[20|×]
Добавляем 30:
head → [10|•]→[20|•]→[30|×]
Более подробный пример использования:
ll = LinkedList()
# Добавляем первый элемент
ll.append(1)
# head → [1|×]
# Добавляем второй элемент
ll.append(2)
# head → [1|•]→[2|×]
# ↑ ↑
# last new_node
# Добавляем третий элемент
ll.append(3)
# head → [1|•]→[2|•]→[3|×]
# ↑ ↑
# last new_node
Чтобы увидеть все элементы списка, необходимо пройти по цепочке от головы до самого конца, собирая данные каждого узла.