Базовый принцип выбора

После прошлого урока может показаться, что linked list — это всегда плохо. Это не так. Когда вы выбираете между структурами, надо смотреть на операции, которые будут выполняться чаще всего, а не на абсолютные сравнения.

Linked list проигрывает массиву на:

• random access по индексу — O(n) vs O(1).
• iteration over all elements — pointer chasing медленнее массива.
• размере памяти — на каждый элемент дополнительный указатель (или два).

Linked list выигрывает на:

• insert/delete в произвольной точке, если у вас уже есть указатель на узел — O(1) vs O(n).
• splice (соединение двух списков) — O(1) vs O(n) для массивов.
• persistent (immutable) сценарии — можно «расшарить» хвост между версиями.

Если ваше workload состоит в основном из вторых операций — linked выигрывает. Если первых — массив.

Кейс 1: LRU cache

Уже разбирали в уроке 02. Самый частый пример. Операции:

• get(key): найти узел и перенести в head — O(1) с doubly linked.
• put(key, value): добавить в head, если переполнен — выкинуть tail — O(1).

Цикл операций: lookup -> remove(node) -> push_front(node). Без doubly linked это было бы O(n) на каждую операцию (find prev в singly или сдвиги в массиве).

В Python functools.lru_cache — реализация именно на doubly linked + dict. Реальный production-код.

Кейс 2: persistent (immutable) data structures

В функциональных языках (Haskell, OCaml, Clojure, Erlang) lists по умолчанию immutable. Когда вы делаете 1 : xs (prepend в Haskell), вы получаете новый список, у которого:

• head — новый узел со значением 1.
• next — указатель на старый xs (без копирования!).

старый: [2] -> [3] -> [4] -> nil
новый:  [1] -> [2] -> [3] -> [4] -> nil  (next старого головы)

Старый xs цел, его другая часть кода продолжает использовать. Новый разделяет с ним хвост. Это structural sharing — критическая фишка immutable structures.

Для массива такое невозможно: нельзя «расшарить хвост» массива без копирования всего блока (потому что добавление в начало физически сдвигает остальное). Linked list даёт это бесплатно.

В Erlang/OTP актеры обмениваются immutable списками — никаких локов, потому что данные не меняются. Это основа надёжных распределённых систем.

Кейс 3: hash table chaining

В hash table при коллизии часто используется chaining: внутри bucket’а лежит линейная цепочка элементов с одинаковым хешем. Структура цепочки — обычно singly linked.

class HashEntry:
    __slots__ = ('key', 'value', 'next')

    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None


class ChainHashMap:
    def __init__(self, capacity=16):
        self.buckets = [None] * capacity
        self.size = 0

    def put(self, key, value):
        idx = hash(key) % len(self.buckets)
        node = self.buckets[idx]
        while node is not None:
            if node.key == key:
                node.value = value
                return
            node = node.next
        # вставка в начало bucket-цепочки
        new_node = HashEntry(key, value)
        new_node.next = self.buckets[idx]
        self.buckets[idx] = new_node
        self.size += 1

Почему linked list тут разумен:

• Цепочка короткая (1-5 элементов при правильном load factor). Pointer chasing не критичен.
• Вставка/удаление часты — нужен O(1).
• Размер заранее неизвестен — нельзя предаллоцировать массив каждый bucket.

В Python dict использует open addressing (другая стратегия разрешения коллизий, без linked list), но Java HashMap, Go map при больших цепочках, Rust HashMap, многие БД-индексы используют chaining. Об этом подробно в модуле 8-8.

Кейс 4: scheduler / event queue

В операционных системах планировщик хранит список задач. Часто задачи добавляются/удаляются в произвольных местах:

• задача проснулась — добавить в queue.
• задача засыпает на I/O — убрать из run queue, добавить в wait queue.
• timer expired — переместить из timer queue в run queue.

Если у вас есть указатель на task struct, удаление из текущей очереди и вставка в новую — это две O(1) операции в doubly linked. Linux kernel использует doubly linked везде: list_head (include/linux/list.h) — каноническая структура.

В user space аналогичные задачи: scheduling в Python asyncio, корутины в Go runtime.

Кейс 5: undo-redo

Текстовый редактор хранит историю операций. Каждая операция = node. Undo — двинуться на prev, redo — на next. Это doubly linked, потому что движение в обе стороны.

Если линейная история (без branching) — list тоже подойдёт (insert/pop в конец). Но: если пользователь сделал undo, потом ввёл новое — нужно «обрезать» все next от текущей позиции. На list это пересоздание буфера; на linked — обнуление одного указателя.

Для древовидной истории (Vim, git-style) — обязательно tree, не linked, но базовая идея остаётся.

Кейс 6: free list в аллокаторе

Когда malloc отдаёт блок, он помнит освобождённые блоки в free list — линейном списке блоков того же размера. При следующем malloc(N) если в free list есть подходящий блок — отдаёт его, не идя в ОС.

Это singly linked: блоки сами хранят указатель на следующий свободный блок прямо «у себя» (часто в первых 8 байтах освобождённой памяти). Никаких дополнительных Node объектов — линковка in-place. Это и есть intrusive list — приём из C, который не имеет аналога в Python.

Какой Linked Lists популярные библиотеки реально используют

Чек-лист «нужен ли мне linked list»

Перед тем как написать свой class Node, ответьте на вопросы:

1. Нужны ли O(1) insert/delete в произвольной точке? Да -> возможно linked.
2. Будут ли запросы по индексу xs[i] на больших размерах? Да -> только массив.
3. Часто ли iteration по всему списку? Да -> массив выигрывает на cache.
4. Нужны ли immutable «версии» с разделяемой структурой? Да -> linked.
5. Размер заранее неизвестен и растёт неравномерно? Возможно linked, но deque обычно лучше.
6. Python? Чаще всего нет — list или deque покрывают почти все сценарии.

Если ответили «нужен Linked List» — спросите ещё раз: «а нельзя ли решить через dict + list?» Обычно можно: hash map даёт O(1) доступ к узлу, список — порядок. Это та же связка, что в LRU.

Попробуй сам

Реализуйте простую LRU cache. Замерьте, как меняется время get/put с ростом N:

from functools import lru_cache
import time

@lru_cache(maxsize=10_000)
def expensive(x):
    return x * x + x

# warmup
for i in range(20_000):
    expensive(i % 5_000)

# benchmark
t0 = time.perf_counter()
for i in range(100_000):
    expensive(i % 5_000)  # часть хитов, часть промахов
t1 = time.perf_counter()
print(f"100k ops: {(t1-t0)*1000:.2f} ms => {(t1-t0)/100_000 * 1e6:.2f} us per op")

Должно быть менее микросекунды на операцию — это O(1) get/put на doubly linked + dict.