Связные списки: односвязные, двусвязные, кольцевые

Связный список — первая структура данных, где мы платим памятью за гибкость. В массиве элементы лежат подряд, и это одновременно его сила (мгновенный доступ по индексу) и его проклятие (вставка в середину сдвигает хвост). Список решает проблему радикально: пусть каждый элемент сам знает, где лежит следующий. Тогда «вставить» — это переписать пару указателей, а не двигать мегабайты.

Аналогия — товарный поезд. Массив — это платформа с пронумерованными местами: чтобы вклинить вагон в середину, надо все последующие переставить. Список — это сцепка: расцепил, вставил вагон, сцепил обратно, и вагоны при этом могут стоять на разных путях депо. Эта же аналогия объясняет обратную сторону: чтобы найти пятнадцатый вагон, придётся пройти по сцепке от локомотива — никакой арифметики адресов. Всё, что вы получите или потеряете со списками, выводится из этих двух фактов.

Анатомия: узел, ссылка, инвариант

Минимальная единица — узел (node): полезная нагрузка плюс одна или несколько ссылок.

class Node:
    __slots__ = ("value", "next")   # __slots__ убирает __dict__: экономия ~50 байт на узел

    def __init__(self, value, next=None):
        self.value = value
        self.next = next            # ссылка на следующий узел или None — конец списка

Сам «список» — это переменная head, указывающая на первый узел. Всё остальное — соглашения (инварианты), которые вы обязуетесь поддерживать после каждой операции: из head достижимы все элементы ровно по одному разу (нет циклов, если список не кольцевой); последний узел имеет next is None; если вы храните size или tail — они всегда согласованы с реальной цепочкой. Нарушение инварианта не падает сразу — оно падает через час, в другом модуле, при обходе. Поэтому список почти всегда прячут за классом, а не таскают голые узлы по всей программе.

Как это лежит в памяти

Массив — один непрерывный блок: адрес i-го элемента вычисляется арифметикой, а аппаратный префетчер, увидев два последовательных обращения, начинает подтягивать следующие кэш-линии заранее. Список — набор независимых аллокаций, разбросанных по куче в порядке, который определяет аллокатор, а не логика вашей программы. Каждый переход node = node.next — потенциальный промах кэша: процессор не может начать загрузку следующего адреса, пока не получил текущий. Это называется pointer chasing, и внутри одного ядра его нельзя распараллелить — зависимость по данным. Порядок величин (см. интерактивные latency numbers): попадание в L1 — ~1 нс, промах до DRAM — ~80–100 нс. Разница в 100 раз не видна в записи O(n), но именно она определяет, что вы увидите в профайлере; подробнее о модели памяти — в статье про асимптотику и стоимость.

Три вида списков

Отдельно стоит список с фиктивным узлом (sentinel / dummy head) — не отдельный вид, а приём, который убирает половину ошибок. О нём ниже.

Односвязный список: реализация и разбор

from typing import Optional


class SinglyLinkedList:
    """Инварианты: если _size == 0, то _head is _tail is None; иначе _tail —
    последний узел и _tail.next is None; _size = число узлов из _head."""

    def __init__(self) -> None:
        self._head: Optional[Node] = None
        self._tail: Optional[Node] = None
        self._size: int = 0

    # --- O(1) операции по краям ---

    def push_front(self, value) -> None:
        """Вставка в голову. O(1) по времени, O(1) по доп. памяти."""
        self._head = Node(value, self._head)
        if self._tail is None:          # список был пуст — голова же и хвост
            self._tail = self._head
        self._size += 1

    def push_back(self, value) -> None:
        """Вставка в хвост — O(1) ТОЛЬКО потому, что мы храним _tail."""
        node = Node(value)
        if self._tail is None:
            self._head = self._tail = node
        else:
            self._tail.next = node
            self._tail = node
        self._size += 1

    def pop_front(self):
        """Удаление из головы. O(1)."""
        if self._head is None:
            raise IndexError("pop from empty list")
        node = self._head
        self._head = node.next
        if self._head is None:          # сняли последний элемент
            self._tail = None
        self._size -= 1
        return node.value

    # --- O(n) операции внутри ---

    def remove(self, value) -> bool:
        """Удаление первого вхождения. O(n): нужно найти ПРЕДЫДУЩИЙ узел.
        Поиск тоже только линейный — бинарный невозможен, нет середины за O(1)."""
        prev, node = None, self._head
        while node is not None:
            if node.value == value:
                if prev is None:                # удаляем голову — частный случай!
                    self._head = node.next
                else:
                    prev.next = node.next
                if node is self._tail:          # и хвост — тоже частный случай
                    self._tail = prev
                self._size -= 1
                return True
            prev, node = node, node.next
        return False

Два наблюдения. Первое: в remove два частных случая (голова и хвост) — именно их убирает страж, см. ниже. Второе: pop_back здесь нет, и это не лень. Удалить хвост односвязного списка — O(n), даже если _tail известен: чтобы новый хвост узнал, что он последний, нужен предпоследний узел, а дойти до него можно только с начала. Ровно поэтому односвязный список годится для стека и не годится для дека.

Сложность по памяти. На каждый элемент — объект узла плюс указатель. В CPython это ~56 байт на узел со __slots__ против 8 байт на указатель в list. В C-подобных языках — sizeof(payload) + 8 плюс заголовок аллокатора (обычно 8–16 байт) плюс выравнивание. Если вы храните список int32, накладные расходы могут превысить полезные данные в 5–6 раз.

Фиктивная голова: как убрать ветвления

Каждый if prev is None и if self._head is None — шанс ошибиться. Приём: завести всегда существующий узел-страж, не хранящий данных.

def insert_after(node: Node, value) -> Node:
    """Единственный код вставки — работает и для головы, если node = sentinel."""
    node.next = Node(value, node.next)
    return node.next

def remove_after(node: Node) -> None:
    """Единственный код удаления. Частного случая «удаляем голову» больше нет."""
    if node.next is not None:
        node.next = node.next.next

Голова списка теперь self._sentinel.next, и специальный случай «список пуст / удаляем первый» исчезает: страж всегда есть, у него всегда можно спросить next. Ценой одного лишнего узла вы удаляете целый класс NPE-подобных багов. В ядре Linux и в std::list этот приём доведён до предела: страж один, и список кольцевой — тогда даже if (node == head) не нужен.

Двусвязный список: цена и возможности

Добавляем prev — и получаем главную суперсилу: удаление узла за O(1), если у вас есть указатель на него. Именно эта операция делает возможным LRU-кэш, планировщики задач и интрузивные списки в ядре.

class DNode:
    __slots__ = ("value", "prev", "next")

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


class DoublyLinkedList:
    """Кольцевой двусвязный список с одним стражем — как в ядре Linux и std::list.
    Пустой список: _s.next is _s and _s.prev is _s.
    Ни одна операция не содержит проверки на None."""

    def __init__(self):
        s = DNode(None)
        s.next = s.prev = s
        self._s = s
        self._size = 0

    def _link_between(self, node: DNode, left: DNode, right: DNode) -> None:
        node.prev = left            # ① настраиваем новый узел
        node.next = right           # ②
        right.prev = node           # ③ и только теперь врезаем его в цепочку
        left.next = node            # ④
        self._size += 1

    def push_back(self, value) -> DNode:        # перед стражем = в конец
        node = DNode(value)
        self._link_between(node, self._s.prev, self._s)
        return node

    def push_front(self, value) -> DNode:       # после стража = в начало
        node = DNode(value)
        self._link_between(node, self._s, self._s.next)
        return node

    def unlink(self, node: DNode) -> None:
        """O(1). Требует только сам узел — ни головы, ни поиска."""
        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = node.next = None   # обнуляем, чтобы «удалённый» узел нельзя было
        self._size -= 1                # случайно использовать как живой (fail fast)

    def move_to_front(self, node: DNode) -> None:
        """Основа LRU: снять и переставить — две пары присваиваний, без аллокаций."""
        self.unlink(node)
        self._link_between(node, self._s, self._s.next)

    def __iter__(self):
        node = self._s.next
        while node is not self._s:      # условие обхода кольца — не «!= None»!
            yield node.value
            node = node.next

Разберём unlink придирчиво: он работает без единого if для четырёх разных случаев — узел в середине, первый, последний, единственный. Причина — страж: у любого узла всегда есть непустые prev и next. Именно так устроен list_del() в include/linux/list.h, только там вместо None записываются «отравленные» константы LIST_POISON1/2, чтобы обращение к удалённому узлу немедленно уронило систему, а не тихо повредило данные.

Порядок присваиваний в _link_between (①②③④) — не косметика: пока не выполнен шаг ④, список остаётся полностью корректным для любого, кто идёт по нему вперёд от головы. Это свойство называется publish-last и критично там, где обход может произойти между вашими присваиваниями — обработчик прерывания, другой поток, RCU-читатель; тот же принцип лежит в основе list_add_rcu().

Структура классов

Кольцевые списки

Кольцо получается из обычного списка, если tail.next = head. Хвоста нет — есть только курсор. Это естественная модель для всего, что «идёт по кругу»:

• round-robin планировщик: следующий поток — current = current.next, без проверки конца;
• кольцевой буфер на списке (когда размер не фиксирован, иначе лучше массив-ringbuffer, см. стеки и очереди);
• задача Иосифа Флавия — классическая иллюстрация удаления каждого k-го из круга;
• свободные слоты аллокатора, где кольцо позволяет начинать поиск с места прошлой удачи.

def josephus(n: int, k: int) -> int:
    """n человек в круге, выбывает каждый k-й. O(n·k) времени, O(n) памяти."""
    head = cur = Node(1)
    for i in range(2, n + 1):
        cur.next = cur = Node(i)   # строим цепочку
    cur.next = head                # замкнули кольцо
    prev, cur = cur, head          # prev всегда на шаг позади cur
    while cur.next is not cur:     # пока в кольце больше одного узла
        for _ in range(k - 1):
            prev, cur = cur, cur.next
        prev.next = cur = cur.next # выбывает cur, prev остаётся на месте
    return cur.value

Главная опасность кольца — обход: while node is not None никогда не завершится. Условие всегда формулируется относительно стартовой точки (node = start; do {...} while (node != start)), а «найти длину» или «найти конец» требует явного счётчика или маркера.

Классические приёмы на списках

Эти пять техник покрывают большую часть задач на списки — и на собеседованиях, и в реальном коде.

1. Два указателя разной скорости (tortoise and hare). Медленный делает шаг, быстрый — два. Когда быстрый дошёл до конца, медленный стоит ровно на середине — это даёт «найти середину» и «найти k-й с конца» за один проход и O(1) памяти (см. деление пополам в merge_sort ниже).

2. Обнаружение цикла (алгоритм Флойда). Если в списке есть цикл, быстрый указатель рано или поздно догонит медленный — они окажутся в одном узле. Классика из TAOCP т. 2 (упр. 3.1-6).

def find_cycle_start(head: Optional[Node]) -> Optional[Node]:
    """Первый узел цикла или None. O(n) времени, O(1) памяти. Почему работает:
    при хвосте длины L и цикле длины C встреча происходит на расстоянии, кратном C
    от входа, поэтому указатели из головы и из точки встречи сойдутся ровно на входе."""
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow, fast = slow.next, fast.next.next
        if slow is fast:                      # встретились — цикл есть
            probe = head
            while probe is not slow:
                probe, slow = probe.next, slow.next
            return probe
    return None

3. Разворот за O(1) памяти. Итеративно переставляем ссылки, храня три указателя: prev, node = None, head, затем в цикле node.next, prev, node = prev, node, node.next. O(n) времени, O(1) памяти. Рекурсивная версия занимает O(n) стека и на длинном списке даёт RecursionError в Python и переполнение стека в C — пишите итеративно.

4. Сортировка слиянием. Единственный случай, где список объективно лучше массива по памяти: merge sort на списке не требует буфера — слияние переставляет ссылки. O(n log n) времени, O(log n) памяти на стек рекурсии (или O(1) в bottom-up варианте). Именно поэтому std::list::sort и сортировка списков в ядре Linux (list_sort()) — это merge sort, а не quicksort.

def merge_sort(head: Optional[Node]) -> Optional[Node]:
    """O(n log n) времени. Дополнительной памяти под данные — НОЛЬ."""
    if head is None or head.next is None:
        return head
    # 1. Делим пополам двумя указателями
    slow, fast = head, head.next
    while fast is not None and fast.next is not None:
        slow, fast = slow.next, fast.next.next
    second, slow.next = slow.next, None
    # 2. Рекурсивно сортируем половины
    left, right = merge_sort(head), merge_sort(second)
    # 3. Сливаем, переставляя ссылки (dummy убирает частный случай первого узла)
    dummy = tail = Node(None)
    while left and right:
        if left.value <= right.value:
            tail.next, left = left, left.next
        else:
            tail.next, right = right, right.next
        tail = tail.next
    tail.next = left or right
    return dummy.next

5. Интрузивность. Не «список хранит объект», а «объект содержит в себе поле-звено». Это убирает аллокацию на элемент и позволяет одному объекту состоять сразу в нескольких списках. Каноническая реализация — struct list_head в Linux:

type Link struct{ prev, next *Task }   // звено встроено в объект, а не оборачивает его

type Task struct {
    ID     int
    runq   Link // звено очереди выполнения
    timers Link // ЭТОТ ЖЕ объект одновременно в списке таймеров
}

func (t *Task) unlinkFromRunq() { // O(1), ноль аллокаций
    t.runq.prev.runq.next = t.runq.next
    t.runq.next.runq.prev = t.runq.prev
}

Сложность: сводная таблица

* амортизированно, см. разбор амортизации.

Две строки в этой таблице объясняют, зачем списки вообще существуют: слияние за O(1) (splice) и стабильность указателей — узел никогда не переезжает, поэтому ссылку на него можно раздать наружу и хранить сколько угодно. У std::vector любая вставка может инвалидировать все итераторы; у std::list — только итератор удалённого элемента.

Почему на практике списки почти всегда проигрывают

Асимптотика говорит: «вставка в середину — O(1) против O(n)». Реальность говорит другое. Классический эксперимент Бьярне Страуструпа (ISO C++: «Are lists evil?»): генерируем n случайных чисел, вставляем каждое в отсортированный контейнер, затем в случайном порядке удаляем. std::vector обгоняет std::list при любых n, и разрыв растёт с ростом n.

Как так, если у вектора сдвиг O(n), а у списка вставка O(1)? Четыре причины:

1. Поиск позиции доминирует. Вставка O(1) требует, чтобы вы уже знали место. Найти его в списке — O(n) промахов кэша. В векторе — O(log n) с бинарным поиском, невозможным на списке.
2. Сдвиг в векторе — это memmove. Линейный проход по непрерывной памяти на скорости шины: сотни байт за такт с SIMD. Обход списка — цепочка зависимых загрузок по 80 нс каждая.
3. Аллокатор. Каждый узел — вызов malloc/new. Это блокировки, фрагментация, метаданные. Вектор аллоцирует раз в log n раз.
4. Память. Список с int32 тратит 24–32 байта на 4 байта данных. В кэш-линию 64 Б помещается 16 элементов вектора и 2 узла списка.

Практическое правило: по умолчанию берите динамический массив. Переходите на список только тогда, когда указатель на нужный узел у вас уже есть (получен из хеш-таблицы, из поля объекта, из внешнего API) и вы часто перекладываете узлы между списками. Если задача звучит как «найти и вставить» — список не поможет. Компромисс — unrolled linked list: узел хранит не один элемент, а массив из 16–64 элементов, что даёт локальность массива и O(1)-вставку в середину блока. Именно так устроен collections.deque в CPython: двусвязный список блоков по 64 указателя (Modules/_collectionsmodule.c). Тот же приём — в std::deque и в B-деревьях, которым посвящена статья про сбалансированные деревья.

Как это применяют в проде

LRU-кэш: хеш-таблица + двусвязный список

Каноничный и самый частый продакшн-случай. Словарь даёт O(1) поиск, список — O(1) перемещение в «горячий» конец и O(1) вытеснение из «холодного».

class LRUCache:
    """O(1) на get и put. Память: O(capacity)."""

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.map: dict = {}                   # key -> DNode, где node.value = (key, val)
        self.order = DoublyLinkedList()       # голова = самый свежий

    def get(self, key, default=None):
        node = self.map.get(key)
        if node is None:
            return default
        self.order.move_to_front(node)        # ключевая O(1)-операция
        return node.value[1]

    def put(self, key, value) -> None:
        node = self.map.get(key)
        if node is not None:
            node.value = (key, value)
            self.order.move_to_front(node)
            return
        if len(self.map) >= self.capacity:
            victim = self.order._s.prev       # последний реальный узел
            self.order.unlink(victim)
            del self.map[victim.value[0]]     # ОБЯЗАТЕЛЬНО чистим map, иначе утечка
        self.map[key] = self.order.push_front((key, value))

Реальные системы усложняют схему, но каркас тот же. Memcached использует сегментированный LRU с несколькими списками (HOT/WARM/COLD) и ленивым перемещением, чтобы не дёргать список на каждый hit под глобальным замком — см. doc/new_lru.txt. Redis, наоборот, отказался от точного LRU: держать двусвязный список на миллионы ключей дорого по памяти, поэтому используется приближённая выборка (см. Redis: key eviction). Это отличная иллюстрация того, что 16 лишних байт на элемент — это архитектурное решение, а не деталь.

Ядро, хеш-таблицы, аллокаторы, БД

• Ядро Linux. struct list_head { struct list_head *next, *prev; } встраивается в любую структуру, а макрос container_of восстанавливает адрес объекта по адресу его звена: ноль аллокаций, объект состоит в десятке списков одновременно, list_del — O(1). Плюс RCU-варианты (list_add_rcu, list_for_each_entry_rcu), где читатели ходят по списку без блокировок — благодаря тому самому publish-last порядку записей.
• Цепочки коллизий в хеш-таблицах — односвязные списки (подробнее в статье про хеш-таблицы). Java до 8-й версии использовала чистые цепочки; с Java 8 длинная цепочка превращается в красно-чёрное дерево, чтобы убрать O(n) в худшем случае при hash-flooding атаках.
• Free-list аллокатора: свободные блоки хранят указатель на следующий свободный блок внутри себя — структура с нулевым оверхедом.
• Журналы и WAL: цепочки записей, где каждая ссылается на предыдущую.
• Skip list — вероятностная надстройка над списком, дающая O(log n) поиск; используется в LevelDB/RocksDB memtable и в Redis sorted sets (оригинальная статья Пью, 1990).

Lock-free: стек Трейбера и проблема ABA

Односвязный список — основа простейшей неблокирующей структуры: стек, где push/pop делаются одним CAS по указателю на голову.

Лечится счётчиком версий в указателе (tagged pointer), hazard pointers или epoch-based reclamation. Формальная постановка и решения — в работе Майкла и Скотта о неблокирующих очередях (PODC'96). Подробный разбор — в статье про персистентные и конкурентные структуры.

Персистентность в функциональных языках

Односвязный список — идеальная персистентная структура: cons(x, rest) создаёт новый список за O(1), не трогая старый, потому что хвост разделяется между версиями. Отсюда списки как базовый тип в Lisp, Haskell, Erlang и Elixir, где [head | tail] — не сахар, а буквально узел списка. Обратная сторона — length/1 в Elixir это O(n), а list ++ other копирует левый список целиком.

Типичные ошибки

1. Потеря ссылки при перестановке. node.next = new_node до того, как new_node.next = node.next — и весь хвост списка становится мусором. Всегда сначала настраивайте новый узел, потом врезайте его.
2. Забытый tail или size. Удалили последний элемент — не обновили _tail. Через сто операций список «отрастит» хвост из удалённого узла. Сюда же off-by-one при удалении головы — оба лечатся стражем.
3. Обход кольцевого списка условием != None. Бесконечный цикл. Условие только относительно стартового узла.
4. Рекурсия по длинному списку. reverse или merge_sort в рекурсивной форме на списке из 10⁶ элементов — переполнение стека. В Python RecursionError уже на ~1000. Пишите итеративно.
5. Утечки при удалении из составных структур. В LRU: сняли узел из списка, но не удалили ключ из словаря. Или в языках с ARC/подсчётом ссылок: двусвязный список создаёт циклические ссылки, и без weak для prev (Swift, Rust Rc) память не освободится.
6. Итератор поверх изменяемого списка. Удалили узел, по которому идёт итератор — обращение к node.next после unlink даст None или отравленное значение. Собирайте кандидатов на удаление заранее или используйте list_for_each_safe-паттерн с сохранённым next.
7. Выбор списка «по асимптотике». Самая дорогая ошибка. Прежде чем брать список ради «O(1) вставки», проверьте: у вас правда уже есть указатель на позицию? Если нет — берите массив.

Что в стандартных библиотеках

Мини-итог

• Список меняет O(1)-доступ по индексу на O(1)-перестановку ссылок и стабильность указателей.
• Односвязный — минимальный оверхед, стек, цепочки, персистентность. Двусвязный — O(1) удаление известного узла, основа LRU и планировщиков. Кольцевой + страж — способ убрать все частные случаи из кода.
• Порядок присваиваний при вставке (сначала новый узел, потом врезка) — не стиль, а требование корректности при конкурентном чтении.
• Асимптотика списка обманчива: pointer chasing и аллокатор съедают выигрыш. По умолчанию — массив; список — когда указатель на узел уже в руках.
• Побеждающие на практике гибриды — unrolled-варианты (deque, B-деревья) и связка «хеш-таблица + двусвязный список».

Источники

• Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms, 4th ed., гл. 10.2 «Linked lists» — mitpress.mit.edu; Sedgewick, Wayne. Algorithms, 4th ed., раздел 1.3 — algs4.cs.princeton.edu
• Knuth. TAOCP, Vol. 1, 2.2.3–2.2.5 (списки, кольца, освобождение памяти) — www-cs-faculty.stanford.edu/~knuth/taocp.html
• Linux kernel: include/linux/list.h и RCU-документация
• Stroustrup. Are lists evil? — isocpp.org/blog/2014/06/stroustrup-lists
• Michael, Scott. Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms, PODC'96 — cs.rochester.edu
• Pugh. Skip Lists: A Probabilistic Alternative to Balanced Trees, CACM 1990 — PDF
• CPython: Modules/_collectionsmodule.c — устройство deque
• Learn Rust With Entirely Too Many Linked Lists — лучший текст о том, кто владеет узлом и кто его освобождает

Что дальше

Списки — фундамент структур с ограниченным доступом: если разрешить вставку и удаление только с одного конца, получится стек; если с разных — очередь; если с обоих — дек. Именно там односвязные и двусвязные списки раскрываются в полную силу и там же становится видно, когда их стоит заменить кольцевым буфером на массиве. Следующая статья: Стеки, очереди и деки.