Связные списки: основа динамических структур данных

🎯 Зачем это нужно?

Представь, что у тебя есть плейлист в Spotify 🎵. Песни идут одна за другой, ты можешь добавить новую в любое место, удалить надоевшую, перейти к следующей. Вот именно так работают связные списки!

Где используется:

• Музыкальные плееры: переключение треков (следующий/предыдущий)
• Браузеры: история посещений (кнопки “назад”/“вперед”)
• Текстовые редакторы: undo/redo операции
• Социальные сети: лента новостей (бесконечная прокрутка)

📚 История вопроса

В 1955 году Аллен Ньюэлл создал первый язык программирования со списками - IPL (Information Processing Language). Тогда компьютерная память была ОЧЕНЬ дорогой, и нужна была структура, которая использует только необходимое количество памяти.

Интересный факт: в языке Lisp (1958) списки были ОСНОВНОЙ структурой данных - даже код программы представлялся в виде списков! 🤯

💡 Интуиция

Массив = общежитие: комнаты идут подряд, номера 101, 102, 103… Если хочешь найти соседа - просто прибавь 1 к номеру.

Связный список = квест по городу: у тебя есть записка с адресом первого места. Приходишь туда, находишь подсказку с адресом следующего места. И так далее, пока не дойдешь до финиша!

[МЕДИА: image_01] Описание: Сравнение массива и связного списка через аналогию общежития и квеста Промпт: “educational illustration comparing array vs linked list, dormitory rooms numbered sequentially vs treasure hunt with clues, arrows showing connections, modern clean style, suitable for technical audience”

📐 Формальное определение

Связный список - это линейная динамическая структура данных, состоящая из узлов, где каждый узел содержит:

• Данные (data): само значение
• Указатель (next): ссылку на следующий узел

class Node:
    def __init__(self, data):
        self.data = data        # данные узла
        self.next = None        # указатель на следующий узел

class LinkedList:
    def __init__(self):
        self.head = None        # указатель на первый узел

Типы связных списков:

• Односвязный: каждый узел знает только следующий
• Двусвязный: каждый узел знает и предыдущий, и следующий
• Кольцевой: последний узел ссылается на первый

🔍 Примеры с разбором

Пример 1: Создание списка плейлиста

# Создаем узлы для песен
song1 = Node("Imagine Dragons - Believer")
song2 = Node("The Weeknd - Blinding Lights") 
song3 = Node("Billie Eilish - Bad Guy")

# Связываем их
song1.next = song2
song2.next = song3
song3.next = None  # конец списка

# Создаем сам список
playlist = LinkedList()
playlist.head = song1

[МЕДИА: image_02] Описание: Визуализация создания связного списка с песнями Промпт: “step-by-step diagram showing linked list creation with music tracks, nodes connected by arrows, clear labeling of data and next pointers, educational programming style”

Пример 2: Добавление в начало списка

def add_to_beginning(playlist, new_song):
    # Создаем новый узел
    new_node = Node(new_song)
    
    # Новый узел ссылается на старый первый
    new_node.next = playlist.head
    
    # Обновляем голову списка
    playlist.head = new_node

# Добавляем хит в начало плейлиста
add_to_beginning(playlist, "Justin Bieber - Peaches")

Временная сложность: O(1) - константное время! Почему быстро: не нужно сдвигать элементы, как в массиве

Пример 3: Поиск песни в плейлисте

def find_song(playlist, target):
    current = playlist.head
    position = 0
    
    while current is not None:
        if current.data == target:
            return position  # найдено!
        current = current.next
        position += 1
    
    return -1  # не найдено

# Ищем песню
pos = find_song(playlist, "Billie Eilish - Bad Guy")
print(f"Песня найдена на позиции: {pos}")

Временная сложность: O(n) - линейное время Почему медленно: нужно пройти список до нужного элемента

🎮 Практика

Базовый уровень 🟢

Задание 1: Напиши функцию для подсчета количества узлов в списке

def count_nodes(linked_list):
    # Твой код здесь
    pass

Задание 2: Реализуй функцию вывода всех элементов списка

def print_list(linked_list):
    # Твой код здесь
    pass

Задание 3: Добавь элемент в конец списка

def add_to_end(linked_list, data):
    # Твой код здесь
    pass

Продвинутый уровень 🟡

Задание 4: Удали первое вхождение элемента из списка

def remove_first(linked_list, target):
    # Твой код здесь
    pass

Задание 5: Реверсируй связный список (разверни порядок элементов)

def reverse_list(linked_list):
    # Твой код здесь
    pass

Задание 6: Найди средний элемент списка за один проход (техника “двух указателей”)

def find_middle(linked_list):
    # Твой код здесь
    pass

Челлендж 🔴

Задание 7: Определи, есть ли цикл в списке (алгоритм Флойда)

def has_cycle(linked_list):
    # Используй "зайца и черепаху"
    pass

Задание 8: Объедини два отсортированных списка в один отсортированный

def merge_sorted_lists(list1, list2):
    # Твой код здесь
    pass

⚠️ Частые ошибки

❌ Ошибка: Забыть проверить, что узел не None перед обращением к .next

# ПЛОХО
current = current.next
print(current.data)  # может вызвать ошибку!

✅ Правильно: Всегда проверяй на None

# ХОРОШО
if current is not None:
    current = current.next
    print(current.data)

💡 Почему: None.next вызовет AttributeError

❌ Ошибка: Потерять ссылку на голову при удалении первого элемента

# ПЛОХО - потеряли весь список!
def remove_first_wrong(linked_list):
    linked_list.head = linked_list.head.next

✅ Правильно: Проверить, есть ли элементы

# ХОРОШО
def remove_first_correct(linked_list):
    if linked_list.head is not None:
        linked_list.head = linked_list.head.next

❌ Ошибка: Создать бесконечный цикл при обходе

# ПЛОХО - зацикливание!
while current:
    # забыли написать current = current.next
    print(current.data)

✅ Правильно: Обязательно обновлять указатель

# ХОРОШО
while current:
    print(current.data)
    current = current.next  # ВАЖНО!

🎓 Главное запомнить

✅ Связный список = цепочка узлов со ссылками друг на друга ✅ Добавление в начало: O(1), поиск: O(n)
✅ Используется везде: плееры, браузеры, редакторы ✅ Главное - следить за указателями и проверять на None!

🔗 Связь с другими темами

Откуда пришли: Указатели и динамическое выделение памяти (урок 253) Куда ведет:

• Стеки и очереди (урок 255) - построены на основе списков
• Деревья (урок 258) - узлы с несколькими ссылками
• Хеш-таблицы (урок 262) - списки для разрешения коллизий
• Графы (урок 265) - списки смежности

В машинном обучении: связные списки используются для хранения последовательностей в RNN, цепочек в LSTM, и оптимизации памяти в больших нейронных сетях! 🧠