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

Цели урока

• Понять структуру узла (Node) со ссылками
• Реализовать вставку и удаление за O(1)
• Сравнить сложности массива и связного списка
• Выбирать правильную структуру для задачи

Предварительные знания

• Массивы и их сложности O(1)/O(n)

• Массивы: Фундамент структур данных

**1993 год. Bell Labs.** Bjarne Stroustrup изучает производительность связных списков против векторов на реальном железе. Результат шокирует: vector с O(n) вставкой в середину бьёт list с O(1) вставкой на любом разумном n. Причина - cache locality. Правильный выбор структуры данных требует знать не только Big O, но и физику памяти.

• **Браузеры (Chrome, Firefox)** - история вкладок как двусвязный список: назад/вперёд за O(1)
• **Redis LRU eviction** - двусвязный список + hash map для O(1) вытеснения старых ключей
• **Linux kernel** - list_head внутри каждой структуры данных ядра
• **Undo/Redo редакторов** - каждое действие как узел в двусвязном списке

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

В 1958 году Джон Маккарти разработал LISP - первый язык, где связный список был центральной структурой данных. Само название LISP расшифровывается как 'LISt Processing'. Практически весь код на LISP - это вложенные связные списки, что заложило концепцию homoiconicity (код как данные). Именно из LISP выросли идеи функционального программирования: map, filter, reduce работали на связных списках задолго до появления Python или JavaScript.

Проблема массивов

**Spotify обрабатывает 600 миллионов изменений плейлистов в сутки.** Добавить трек, удалить трек, поменять порядок. Если плейлист - массив из 1000 треков, удаление третьего требует сдвига 997 элементов. Умножи на 600 миллионов - и понятно, почему массив здесь не работает.

Каждое удаление из середины - **O(n)** операций. При частых изменениях это катастрофа.

Решение: каждый элемент **знает только своего соседа**. Тогда удаление - это просто перенаправление стрелки. Никаких сдвигов.

Узел - кирпичик списка

**Узел (Node)** - контейнер с двумя полями: данные и адрес следующего. Не сами данные рядом в памяти, как в массиве, - а цепочка указателей. Узлы могут быть разбросаны по всей куче.

• **data** - полезная нагрузка (число, строка, объект)
• **next** - ссылка на следующий узел (или null)

**Head** - единственное, что знает список. Указатель на первый узел. Потерять head - потерять весь список. Ни O(1), ни O(n) поиска не поможет.

Обход списка - O(n)

В массиве прыжок к `arr[i]` - это одна арифметическая операция: `base_address + i * element_size`. В связном списке адрес i-го элемента неизвестен без прохода по цепочке. **Доступ по индексу - O(n).** Это главная цена.

**Доступ по индексу - O(n).** Это главный недостаток. CPU не может вычислить адрес без прохода по цепочке - нет непрерывного блока памяти.

Вставка - суперсила списка

Связный список **блистает** на вставках. Вставка в начало - всегда **O(1)**. Независимо от размера списка: создать узел, переключить два указателя, готово.

**Вставка в середину** - O(1) после нахождения позиции. Но поиск позиции - O(n). Это критично: если уже есть указатель на нужный узел (например, в LRU Cache), вставка мгновенная.

Удаление - перенаправление стрелки

Удаление - это просто **пропуск узла в цепочке**. Предыдущий узел начинает указывать на следующий за удаляемым. Никаких сдвигов. Сам удалённый узел просто становится недостижимым - garbage collector заберёт.

**Ловушка:** для удаления узла нужен указатель на **предыдущий**. В односвязном списке без tail это значит O(n) поиск. Поэтому сами операции удаления O(1), а общая сложность часто O(n).

Двусвязный список - назад и вперёд

**Двусвязный список (Doubly Linked List)** - каждый узел знает и следующего, и предыдущего. Дополнительный указатель `prev` стоит одного слова памяти на узел, но даёт O(1) удаление по указателю и обход в обоих направлениях.

**Преимущества двусвязного списка:** удаление по указателю O(1) (prev известен), обход в обе стороны, удаление с хвоста O(1) при наличии tail pointer. Браузерная история вкладок - именно двусвязный список.

**Цена:** каждый узел занимает на одно слово памяти больше (указатель prev). При миллиарде узлов это дополнительные 8 GB на 64-битной системе.

Массив vs Связный список

Связный список против массива - не вопрос вкуса. Это вопрос того, какие операции доминируют. Cache locality решает многое: массив лежит в непрерывном блоке памяти, CPU грузит его в кеш одним DMA-трансфером. Узлы списка разбросаны - каждый следующий узел почти гарантированно cache miss.

**Выбирать связный список когда:** частые вставки/удаления в начало или середину при наличии указателя, неизвестный заранее размер, нет потребности в произвольном доступе по индексу.

• Часто вставляем/удаляем в начало
• Размер неизвестен заранее
• Не нужен произвольный доступ по индексу

**Когда НЕ использовать:** нужен быстрый доступ по индексу, важна cache locality, экономия памяти критична (каждый узел несёт overhead на указатель).

Реализуй функцию подсчёта длины списка: ```python def length(head): # Верни количество узлов в списке pass ```

def length(head): count = 0 current = head while current is not None: count += 1 current = current.next return count

Реализуй функцию разворота односвязного списка: ```python def reverse(head): # Верни новый head развёрнутого списка # [1] -> [2] -> [3] превращается в [3] -> [2] -> [1] pass ```

def reverse(head): prev = None current = head while current is not None: next_node = current.next # Сохраняем следующий current.next = prev # Разворачиваем стрелку prev = current # Сдвигаем prev current = next_node # Сдвигаем current return prev # prev теперь указывает на бывший хвост

Определи, есть ли цикл в списке (Floyd's Cycle Detection): ```python def has_cycle(head): # Верни True если в списке есть цикл # [1] -> [2] -> [3] -> [2] (цикл!) pass ``` Ограничение: используй O(1) дополнительной памяти.

def has_cycle(head): if head is None: return False slow = head # Черепаха - 1 шаг fast = head # Заяц - 2 шага while fast is not None and fast.next is not None: slow = slow.next fast = fast.next.next if slow == fast: # Встретились! return True return False # fast дошёл до конца - цикла нет

Куда дальше?

Связный список - фундамент для более сложных структур. Стек и очередь - это список с ограниченным интерфейсом. LRU Cache - список плюс hash map.

• Стеки — Стек на связном списке - push/pop в head за O(1)
• Очереди — Очередь на двусвязном списке - enqueue/dequeue за O(1)
• LRU Cache — HashMap + Doubly Linked List для O(1) операций

Ключевые идеи

• **Узел** хранит данные и ссылку на следующий (и предыдущий в двусвязном)
• **Вставка/удаление** - O(1) при наличии указателя на нужную позицию
• **Доступ по индексу** - O(n), главный недостаток против массива
• **Двусвязный список** даёт O(1) удаление по указателю на узел
• **Cache locality** - почему массив на практике бьёт список при n < 10^5
• **LRU Cache** = список + hash map: комбинация убирает O(n) поиск

Вопросы для размышления

• Почему браузер использует двусвязный список для истории, а не односвязный?
• В каких случаях массив будет быстрее несмотря на O(n) вставку?
• Как реализовать плейлист с функцией shuffle за O(n) время и O(1) дополнительной памяти?

Связанные уроки

• ds-01-arrays — Массивы - контраст, без которого список непонятен
• ds-03-stacks — Стек - это список с ограниченным интерфейсом
• ds-04-queues — Очередь на двусвязном списке - enqueue/dequeue за O(1)
• ds-20-lru-cache — LRU Cache = HashMap + Doubly Linked List - классический продакшн кейс
• alg-02-space — Указатели prev/next - наглядный пример space-time tradeoff
• alg-01-big-o