Список

TL;DR

Связный список (linked list) — линейная структура из узлов, каждый из которых хранит ключ и ссылку на следующий узел, а в двусвязном варианте — ещё и на предыдущий. Порядок элементов задаётся ссылками, а не расположением в памяти, поэтому вставка после известного узла и удаление при известном предшественнике стоят O(1), а поиск и доступ по позиции — O(n). Главный компромисс: гибкая перестройка и стабильные адреса узлов в обмен на память под указатели и плохую локальность кэша при обходе.

Поле	Значение
Класс / тип	Линейная последовательность узлов, связанных указателями; доступ по индексу не поддерживается
Изобретение	1955–1956, А. Ньюэлл, К. Шоу, Г. Саймон (IPL, RAND) [5]
Время операций	Худшее: поиск и удаление по ключу O(n); вставка после известного узла и удаление при известном prev — O(1); удаление по указателю без prev — O(n); среднее: то же; амортизированное: совпадает с худшим
Память	Θ(n) узлов; на узел — ключ, один-два указателя и накладные расходы аллокатора
Упорядоченность	Порядок задаётся связями; ключи могут идти в любом порядке
Стабильность / детерминированность	Детерминирован; адреса узлов не меняются при вставке и удалении других узлов
Альтернативы	Динамический массив, дека, сбалансированное дерево, хеш-таблица, unrolled list
Где встречается	Цепочки хеш-таблиц, free list аллокаторов, LRU-кэши, ядра ОС, LISP и функциональные языки, списки смежности

Определения

Узел (node) — запись, хранящая ключ и ссылки на соседние узлы. В односвязном списке это пара (key, next), в двусвязном — тройка (key, prev, next).

Односвязный список (singly linked list) — конечная последовательность узлов v₁, v₂, …, vₙ, в которой next(vᵢ) = vᵢ₊₁, а next(vₙ) = NIL. Формально список — это набор (V, head, next, key), где V — конечное множество узлов, K — множество ключей, key: V → K сопоставляет узлу ключ, next: V → V ∪ {NIL}, head ∈ V ∪ {NIL}, и выполняются два условия:

1. если head = NIL, то V = ∅; иначе существует единственная последовательность v₁, …, vₙ, покрывающая всё V, с v₁ = head и next(vᵢ) = vᵢ₊₁, next(vₙ) = NIL;
2. у каждого узла, кроме v₁, ровно один предшественник.

Условия исключают циклы, недостижимые узлы и «раздвоение» списка.

Голова (head) — первый узел списка; для пустого списка head = NIL.

Хвост (tail) — последний узел vₙ; его next равен NIL. Отдельный указатель на хвост не обязателен, но без него вставка в конец стоит O(n).

NIL — терминатор, означающий отсутствие узла. Это не адрес и не «нулевой элемент»: NIL нельзя разыменовать, а проверка curr = NIL — единственный признак конца линейного списка.

Двусвязный список (doubly linked list) — список, в котором каждый узел хранит ещё и prev, причём prev(next(v)) = v, если v — не хвост, и next(prev(v)) = v, если v — не голова; в кольце с sentinel оба равенства верны для всех узлов. Он позволяет обходить список в обе стороны и удалять узел по указателю без поиска предшественника.

Циклический список (circular list) — список, в котором next(vₙ) = v₁; терминатор NIL не используется. Обход такого списка обязан останавливаться на стартовом узле, иначе он не завершится.

Сторожевой узел (sentinel, dummy node) — фиктивный узел nil без ключа, который замыкает список в кольцо: next(vₙ) = nil, next(nil) = v₁. Пустой список состоит из одного nil; в двусвязном варианте next(nil) = prev(nil) = nil. Sentinel убирает особые случаи «пустой список» и «операция у головы».

Длина n — число узлов с ключами; nil в длину не входит.

Позиция i — номер узла от головы; в псевдокоде позиции нумеруются 1..n, в C++ — 0..n−1.

Владение (ownership) — соглашение о том, кто и когда освобождает узел. В односвязном списке владелец — список: каждый узел освобождается ровно один раз, либо при удалении, либо в деструкторе.

Интрузивный список (intrusive list) — список, у которого поля next/prev встроены в полезную структуру, а не лежат в отдельном узле. Один объект может входить в несколько списков без отдельного узла; на каждое членство нужно своё встроенное поле.

Персистентный список (persistent list) — неизменяемый список, в котором новые версии делят хвост со старыми: добавление в голову создаёт один узел и не копирует остальные.

Обозначения. n — длина первого списка, m — второго; T — список, T.head — его голова; p, q, curr, prev, next — указатели на узлы. log — двоичный логарифм (в этой теме он почти не нужен). Стоимость считаем в элементарных операциях: чтение и запись указателя, сравнение ключей, выделение и освобождение узла.

Мотивация и интуиция

Массив хранит элементы подряд, и это даёт быстрый доступ по индексу. Но непрерывность приходится поддерживать: вставка в начало массива из n = 10⁶ элементов сдвигает все 10⁶ элементов, то есть переписывает около 4 МБ памяти при 4-байтовом int. Связный список не переписывает данные: он хранит рядом с ключом ссылку на следующий узел, и вставка после известного узла — это две записи указателей.

Вторая выгода — стабильные адреса. Узел не переезжает при вставке или удалении других узлов, поэтому указатели на элементы остаются действительными. У динамического массива реаллокация инвалидирует все указатели и итераторы; у списка — только указатель на удалённый узел.

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

Ключевая идея: заменить непрерывность адресов явными связями. Тогда перестройка структуры становится локальной и дешёвой, а цена переносится на навигацию и память.

Устройство

Односвязный список состоит из трёх видов объектов:

• переменная head — указатель на первый узел или NIL;
• узлы — каждая запись содержит ключ и указатель next;
• терминатор NIL — значение, которым заканчивается цепочка.

Дополнительно можно хранить указатель на хвост tail и длину n. Хвост ускоряет вставку в конец до O(1), но требует аккуратного обновления при удалении последнего узла; длина убирает необходимость считать узлы обходом.

Инварианты, которые обязаны выполняться после каждой операции:

1. head = NIL тогда и только тогда, когда n = 0;
2. все узлы достижимы из head ровно одним путём, циклов нет;
3. next(vₙ) = NIL, и у каждого узла, кроме головы, ровно один предшественник;
4. каждый выделенный узел принадлежит списку не более одного раза и освобождается ровно один раз;
5. в двусвязном списке с sentinel дополнительно prev(next(v)) = v и next(prev(v)) = v для всех узлов, включая nil.

Рис. 1. Односвязный список из пяти узлов: head указывает на первый, next последнего равен NIL; адреса узлов в памяти не соседние.

См. рис. 1: стрелки next задают порядок 7 → 3 → 9 → 1 → 5, хотя узлы расположены в куче вразброс. Именно поэтому список не поддерживает арифметику адресов: следующий элемент находится только чтением поля next.

Операции и алгоритмы

Операция: поиск по ключу

Идея. Пройти список от головы, сравнивая ключи, и остановиться на первом совпадении. Другого способа нет: ссылки не позволяют перепрыгнуть часть списка.

Шаги.

1. Поставить curr на T.head.
2. Пока curr ≠ NIL, сравнить curr.key с искомым ключом.
3. При совпадении вернуть curr.
4. Иначе перейти к curr.next.
5. Если достигнут NIL, вернуть NIL.

Инвариант. Все узлы до curr проверены; если ключ есть в списке, он есть в подсписке с головой curr.

Псевдокод.

Алгоритм Search(T, k)
Вход:  T — односвязный список с головой T.head; k — ключ; позиции 1..n
Выход: указатель на первый узел с ключом k либо NIL
Инвариант: узлы до curr проверены; если k есть в T, то он есть в подсписке с головой curr

1  curr ← T.head
2  while curr ≠ NIL
3      if curr.key = k
4          return curr
5      curr ← curr.next
6  return NIL

Сложность: O(n) времени, O(1) памяти.
Корректность: при переходе curr ← curr.next инвариант сохраняется; при выходе либо
найден первый узел с ключом k, либо просмотрены все узлы и ключа нет.

Пример. В списке 4 → 8 → 15 → 16 → 23 → 42 поиск 15 делает три сравнения (4, 8, 15) и возвращает третий узел. Поиск 17 делает шесть сравнений и возвращает NIL.

Сложность. Время O(n): в худшем случае просматриваются все узлы. Память O(1): хранится только указатель curr. Среднее число сравнений при равновероятном успешном поиске — (n+1)/2, то есть Θ(n).

Крайние случаи. Пустой список: сразу NIL. Ключ в голове: одно сравнение. Дубликаты: возвращается первый; если нужен последний, список обходят до конца. Отсутствующий ключ: полный проход.

Рисунок. См. рис. 1: поиск идёт по стрелкам next от head.

Операция: вставка после узла

Идея. Если узел p уже известен, новый узел вставляется между p и p.next двумя записями указателей. Никакого сдвига элементов и обхода не требуется.

Шаги.

1. Выделить новый узел node и записать в него ключ.
2. node.next ← p.next — новый узел получает преемника p.
3. p.next ← node — p начинает указывать на новый узел.
4. Увеличить длину.

Инвариант. До шага 4 новый узел ещё не достижим из head; после шага 4 он достижим, а все остальные связи не изменились.

Псевдокод.

Операция Insert-After(T, p, x)
Вход:  T — список; p — узел T (p ≠ NIL); x — ключ
Выход: T с новым узлом сразу после p
Инвариант: p — узел T; новый узел ещё не в списке

1  node ← новый узел
2  node.key ← x
3  node.next ← p.next        # сначала новый узел получает преемника
4  p.next ← node             # только теперь p указывает на новый узел
5  T.n ← T.n + 1

Сложность: O(1) времени и памяти.
Корректность: node.next = v(k+1), p.next = node; последовательность становится
v1..vk, x, v(k+1)..vn, остальные ссылки не тронуты.

Порядок строк 3 и 4 критичен. Если сначала выполнить p.next ← node, ссылка на прежний p.next потеряется, и хвост списка станет недостижим.

Пример. Список 7 → 3 → 9 → 1 → 5, p — узел 9, вставляем 4. После node.next ← 1 новый узел ещё не в списке; после 9.next ← 4 получается 7 → 3 → 9 → 4 → 1 → 5.

Рис. 2. Вставка 4 после узла 9: сначала 4.next ← 9.next, затем 9.next ← 4; список становится 7 → 3 → 9 → 4 → 1 → 5.

Сложность. O(1) по времени и дополнительной памяти. Стоимость не зависит от n, но только если p уже известен. Поиск позиции p — отдельная операция, обычно O(i).

Крайние случаи. p — хвост: node.next получает NIL, это корректно. Пустой список: вставлять «после» нечего, нужна вставка в голову. p = NIL — ошибка; в C++ это неопределённое поведение.

Рисунок. См. рис. 2.

Операция: вставка в голову

Идея. Вставка в голову — это Insert-After с виртуальным sentinel перед первым узлом. Меняется только head.

Шаги.

1. Создать узел node с ключом x.
2. node.next ← T.head.
3. T.head ← node.
4. Увеличить длину.

Инвариант. Новый узел стал первым; прежний список целиком следует за ним.

Псевдокод.

Операция Push-Front(T, x)
Вход:  T — список; x — ключ
Выход: T с x в голове
Инвариант: T.head указывает на первый узел или NIL

1  node ← новый узел
2  node.key ← x
3  node.next ← T.head
4  T.head ← node
5  T.n ← T.n + 1

Сложность: O(1) времени и памяти.
Корректность: новый узел указывает на прежнюю голову; все прежние узлы остаются
достижимыми в том же порядке.

Пример. Для 7 → 3 → 9 → 1 → 5 вставка 0 в голову даёт 0 → 7 → 3 → 9 → 1 → 5. Пустой список: head был NIL, становится узлом 0 с next = NIL.

Сложность. O(1). Это самая дешёвая операция списка и основа реализации стека.

Крайние случаи. Пустой список обрабатывается тем же кодом, без ветвления. Если хранится tail, при вставке в пустой список его нужно обновить.

Рисунок. Отдельной схемы нет: перестановка двух ссылок та же по аналогии с рис. 2, только p — виртуальный sentinel перед головой.

Операция: удаление

Идея. Чтобы удалить узел, нужно перенаправить ссылку предшественника через него. В односвязном списке предшественника приходится искать, поэтому удаление по ключу стоит O(n); если указатель на предшественника уже есть, удаление стоит O(1).

Шаги для удаления по ключу.

1. Идти по списку, храня prev — узел перед curr.
2. Остановиться, когда curr = NIL или curr.key = k.
3. Если curr = NIL, ключа нет — вернуть false.
4. Если prev = NIL, удаляется голова: head ← curr.next.
5. Иначе prev.next ← curr.next.
6. Освободить curr и уменьшить длину.

Инвариант. Если curr ≠ NIL, то prev — его предшественник (prev = NIL, если curr — голова); все узлы до curr проверены и не совпали с ключом.

Псевдокод.

Операция Delete(T, k)
Вход:  T — список; k — ключ
Выход: true, если узел удалён; false, если ключа нет
Инвариант: если curr ≠ NIL, то prev — его предшественник (prev = NIL, если curr — голова)

1  prev ← NIL
2  curr ← T.head
3  while curr ≠ NIL and curr.key ≠ k
4      prev ← curr
5      curr ← curr.next
6  if curr = NIL
7      return false
8  if prev = NIL
9      T.head ← curr.next        # удаление головы — особый случай
10 else
11     prev.next ← curr.next
12 освободить curr
13 T.n ← T.n − 1
14 return true

Сложность: O(n) времени, O(1) памяти.
Корректность: при выходе curr — первый узел с ключом k; ссылка prev.next или head
переводится через curr, поэтому остальные узлы сохраняют порядок.

Удаление после узла. Если p известен, удаляемый узел q = p.next исключается за O(1).

Операция Delete-After(T, p)
Вход:  T — список; p — узел T (p ≠ NIL)
Выход: T без узла, следующего за p; ошибка, если p — хвост
Инвариант: q = p.next; если q ≠ NIL, то q — удаляемый узел

1  q ← p.next
2  if q = NIL
3      error "после p нет узла"
4  p.next ← q.next
5  освободить q
6  T.n ← T.n − 1

Сложность: O(1) времени и памяти.
Корректность: p.next переводится на q.next; остальные ссылки не меняются.

Это та же операция, что и вставка, только в обратную сторону.

Пример. Список 7 → 3 → 9 → 1 → 5, удаляем 9. Обход: prev = 7, curr = 3; затем prev = 3, curr = 9 — совпадение. Так как prev ≠ NIL, выполняется 3.next ← 1; получается 7 → 3 → 1 → 5. Если затем удалить голову 7 из уже полученного списка, обход сразу даёт prev = NIL, и меняется head: head ← 3, результат 3 → 1 → 5.

Рис. 3. Удаление узла 9 с предшественником 3, затем удаление головы 7 из полученного списка: в первом случае меняется prev.next, во втором — head.

Сложность. Время O(n): доминирует поиск. Сама перестройка — две-три операции, O(1). Память O(1). Если известен prev, удаление O(1); если известен только указатель на удаляемый узел в односвязном списке, предшественника всё равно нужно искать, поэтому O(n).

Крайние случаи. Единственный узел: head становится NIL. Удаление хвоста: prev.next получает NIL. Удаление отсутствующего ключа: полный проход и false. Дубликаты: удаляется первый. Удаление NIL — ошибка.

Приём «копирование следующего». Иногда предлагают удалить узел x за O(1) без предшественника: скопировать ключ из x.next в x и удалить x.next. Приём работает не всегда: для последнего узла он невозможен, а личность узла подменяется — внешний указатель на удаляемый узел продолжает существовать, но видит уже другой ключ, а указатель на x.next становится висячим. В обычном списке с владением этот приём применять не следует.

Рисунок. См. рис. 3.

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

Идея. В двусвязном списке у каждого узла есть prev, поэтому удаление по указателю не требует поиска предшественника. Sentinel nil замыкает список в кольцо и убирает отдельные случаи для головы, хвоста и пустого списка.

Шаги удаления узла x.

1. x.prev.next ← x.next — предшественник перешагивает через x.
2. x.next.prev ← x.prev — преемник получает нового предшественника.
3. Освободить x, уменьшить длину.

Инвариант. x.prev.next = x и x.next.prev = x; после двух записей кольцо снова согласовано, а nil остаётся достижимым с обеих сторон.

Псевдокод.

Операция Delete-Node(L, x)
Вход:  L — двусвязный список с sentinel L.nil; x — узел данных (x ≠ L.nil)
Выход: L без узла x
Инвариант: x.prev.next = x и x.next.prev = x

1  x.prev.next ← x.next
2  x.next.prev ← x.prev
3  освободить x
4  L.n ← L.n − 1

Сложность: O(1) времени и памяти.
Корректность: обе ссылки, ведущие к x, переводятся на его соседей; порядок остальных
узлов не меняется, sentinel не участвует в особых случаях.

Для сравнения, вставка после узла p требует четырёх записей: node.prev ← p, node.next ← p.next, p.next.prev ← node, p.next ← node. Порядок снова важен: строку p.next ← node выполняют последней, иначе прежний p.next потеряется.

Пример. Кольцо nil ↔ 7 ↔ 3 ↔ 9 ↔ nil. Удаляем узел 9: 3.next ← nil и nil.prev ← 3; получается nil ↔ 7 ↔ 3 ↔ nil. Если удалять 7 (первый узел данных), отдельного случая нет: nil.next ← 3 и 3.prev ← nil.

Рис. 4. Двусвязный список с sentinel: кольцо nil ↔ 7 ↔ 3 ↔ 9; удаление узла 9 меняет 3.next и nil.prev, голова списка не участвует.

Сложность. Удаление и вставка при известном узле — O(1). Память на узел больше: два указателя вместо одного. Обход — O(n) в любую сторону.

Крайние случаи. Пустой список: nil.next = nil.prev = nil, удалять нечего. Один узел данных: обе ссылки nil указывают на него, после удаления снова замыкаются на nil. Попытка удалить nil — ошибка.

Рисунок. См. рис. 4.

Операция: обход

Идея. Обход — базовая операция, на которой строятся поиск, печать, подсчёт и преобразование списка. Он последовательно посещает каждый узел ровно один раз.

Шаги.

1. curr ← T.head.
2. Пока curr ≠ NIL, обработать curr.key.
3. Перейти к curr.next.

Инвариант. Посещены ровно узлы v₁..v_{i−1}, а curr указывает на vᵢ.

Псевдокод.

Алгоритм Traverse(T, visit)
Вход:  T — список; visit — процедура обработки ключа
Выход: visit вызвана для каждого узла ровно один раз, в порядке списка
Инвариант: посещены ровно узлы v1..v(i−1), curr = vi

1  curr ← T.head
2  while curr ≠ NIL
3      visit(curr.key)
4      curr ← curr.next

Сложность: O(n) времени, O(1) памяти сверх visit.
Корректность: индукция по i; ацикличность гарантирует, что через n шагов curr = NIL.

Пример. Обход 7 → 3 → 9 → 1 → 5 вызывает visit пять раз с аргументами 7, 3, 9, 1, 5.

Сложность. Θ(n) — меньше нельзя, если нужно увидеть все элементы. Память O(1) у итеративного варианта; рекурсивный обход занимает O(n) стека.

Крайние случаи. Пустой список: ноль вызовов. Циклический список: условие curr ≠ NIL всегда истинно, поэтому цикл не завершается; нужен счётчик n или остановка на стартовом узле. Мутация списка во время обхода — отдельная проблема: удаление curr без сохранения next обрывает обход.

Рисунок. См. рис. 1.

Операция: разворот

Идея. Пройти список один раз, на каждом шаге разворачивая ссылку curr.next назад. Три указателя prev, curr, next позволяют не потерять остаток списка.

Шаги.

1. prev ← NIL, curr ← T.head.
2. Пока curr ≠ NIL: сохранить next ← curr.next.
3. Направить curr.next ← prev.
4. Сдвинуть prev ← curr, curr ← next.
5. После цикла T.head ← prev.

Инвариант. prev — голова уже развёрнутого префикса v_{i−1} → … → v₁ → NIL (при i = 1 префикс пуст и prev = NIL), curr — первый неразвёрнутый узел vᵢ; связи от curr вперёд ещё не изменены.

Псевдокод.

Операция Reverse(T)
Вход:  T — односвязный список
Выход: T, развёрнутый в обратном порядке
Инвариант: префикс до prev развёрнут; curr — первый неразвёрнутый узел

1  prev ← NIL
2  curr ← T.head
3  while curr ≠ NIL
4      next ← curr.next        # сохранить остаток до перезаписи
5      curr.next ← prev
6      prev ← curr
7      curr ← next
8  T.head ← prev

Сложность: O(n) времени, O(1) памяти.
Корректность: каждая итерация добавляет один узел к развёрнутому префиксу; после n
итераций prev указывает на прежний хвост, curr = NIL.

Пример. 1 → 2 → 3 → 4 → 5 → 6 после разворота становится 6 → 5 → 4 → 3 → 2 → 1; прежняя голова 1 становится хвостом с next = NIL. Пошаговое состояние — в таблице раздела «Трассировка примера».

Сложность. O(n) времени, O(1) дополнительной памяти. Рекурсивный вариант тоже O(n) по времени, но требует O(n) стека.

Крайние случаи. Пустой список: цикл не выполняется, head остаётся NIL. Один узел: next = NIL, curr.next ← NIL, head не меняется по существу. Два узла: после первой итерации prev = 1, curr = 2; после второй — 2 → 1.

Рисунок. См. рис. 6 в разделе «Трассировка примера».

Операция: слияние двух отсортированных списков

Идея. Идти по двум спискам двумя указателями и каждый раз присоединять меньший из голов к результату. Узлы не копируются: меняются только ссылки, поэтому дополнительная память — O(1).

Шаги.

1. Завести head и tail результата, пустые.
2. Сравнить головы a и b.
3. Присоединить меньшую к хвосту результата и сдвинуть соответствующий указатель.
4. Когда один список исчерпан, присоединить остаток второго целиком.

Инвариант. Цепочка от head до tail — отсортированный результат слияния уже просмотренных префиксов; a и b — головы необработанных остатков.

Псевдокод.

Операция Merge-Sorted(T1, T2)
Вход:  T1, T2 — списки, отсортированные по неубыванию
Выход: голова списка из тех же узлов, отсортированного по неубыванию
Инвариант: результат отсортирован и содержит ровно просмотренные узлы

1  head ← NIL; tail ← NIL
2  a ← T1.head; b ← T2.head
3  while a ≠ NIL and b ≠ NIL
4      if b.key < a.key              # при равенстве берём a — устойчивость
5          node ← b; b ← b.next
6      else
7          node ← a; a ← a.next
8      node.next ← NIL
9      if head = NIL
10         head ← node
11     else
12         tail.next ← node
13     tail ← node
14 rest ← a
15 if rest = NIL
16     rest ← b
17 if head = NIL
18     head ← rest
19 else
20     tail.next ← rest
21 return head

Сложность: O(n + m) времени, O(1) дополнительной памяти.
Корректность: на каждом шаге в результат попадает минимальная из двух голов;
остаток одного списка уже отсортирован и не меньше последнего добавленного.

Пример. A = 1, 4, 7, B = 2, 4, 8. Сравнения: 1 из A, 2 из B, 4 из A (при равенстве берётся A), 4 из B, 7 из A, 8 из B. Результат: 1, 2, 4, 4, 7, 8. Первая четвёрка — из A, вторая — из B: слияние устойчиво.

Сложность. O(n + m) времени: на каждом шаге один узел покидает входной список. Дополнительная память O(1) — только указатели; новые узлы не выделяются. Если реализовывать слияние копированием, память станет O(n + m).

Крайние случаи. Один список пуст: результат — второй список. Оба пусты: NIL. Одинаковые ключи: при строгом сравнении b.key < a.key элементы A идут раньше, что сохраняет их взаимный порядок. Списки с разной длиной: остаток присоединяется за O(1).

Рисунок. Отдельной схемы нет: каждая итерация — одна перестановка ссылки, по аналогии с рис. 2.

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

Операция	Худшее	Среднее	Амортизированное	Память
Поиск по ключу	O(n)	O(n)	—	O(1)
Вставка в голову	O(1)	O(1)	—	O(1)
Вставка после узла p	O(1)	O(1)	—	O(1)
Вставка в позицию i	O(i)	O(n)	—	O(1)
Удаление головы	O(1)	O(1)	—	O(1)
Удаление после узла p	O(1)	O(1)	—	O(1)
Удаление по указателю (с prev)	O(1)	O(1)	—	O(1)
Удаление по указателю (без prev)	O(n)	O(n)	—	O(1)
Удаление по ключу	O(n)	O(n)	—	O(1)
Обход	O(n)	O(n)	—	O(1)
Разворот	O(n)	O(n)	—	O(1)
Слияние n и m	O(n + m)	O(n + m)	—	O(1)
Память контейнера	—	—	—	Θ(n) узлов

Примечание. У списка нет «скрытой» дорогой работы, которую можно разложить на много операций, поэтому амортизированная оценка совпадает с худшей, а столбец «амортизированное» заполнен прочерками. Это отличает список от динамического массива, где push_back амортизированно O(1) при O(n) в худшем случае.

Почему асимптотика не всё решает

O(1) и O(n) описывают рост, но не константы. Обход массива читает соседние элементы: на типичной x86-64 линия кэша — 64 байта, и в неё помещается 16 последовательных int. Аппаратный префетчер замечает последовательный доступ и подтягивает следующие линии заранее.

У списка каждый переход curr ← curr.next зависит от предыдущего: пока не прочитан текущий узел, адрес следующего неизвестен. Узлы выделялись в разное время и могут лежать в разных линиях; в худшем случае — по одной линии на узел. Это не меняет O(n), но увеличивает константу в разы, а иногда и на порядок.

Рис. 5. Обход массива читает соседние элементы одной линией кэша; обход списка зависит от каждой ссылки, и узлы могут лежать в разных линиях.

Отсюда практическое правило: если операция — обход или поиск, массив почти всегда быстрее; если операция — вставка и удаление в известную позицию, список может выиграть, но только когда эти операции действительно часты. Подробнее о массивах — динамический-массив.

Трассировка примера

Развернём список 1 → 2 → 3 → 4 → 5 → 6. В таблице — состояние после каждого шага; next сохраняется в начале итерации, до перезаписи curr.next.

Шаг	prev	curr	Развёрнутый префикс	Неразвёрнутый остаток
0	NIL	1	—	1 → 2 → 3 → 4 → 5 → 6
1	1	2	1 → NIL	2 → 3 → 4 → 5 → 6
2	2	3	2 → 1 → NIL	3 → 4 → 5 → 6
3	3	4	3 → 2 → 1 → NIL	4 → 5 → 6
4	4	5	4 → 3 → 2 → 1 → NIL	5 → 6
5	5	6	5 → 4 → 3 → 2 → 1 → NIL	6 → NIL
6	6	NIL	6 → 5 → 4 → 3 → 2 → 1 → NIL	—

После шага 6 head ← prev = 6. Прежняя голова 1 стала хвостом, её next равен NIL — именно это и означает «развёрнутый список».

Рис. 6. Разворот списка 1–2–3–4–5–6 тремя указателями: к концу prev стоит на 6, curr равен NIL, все ссылки перевёрнуты.

Корректность и оценка сложности

Лемма 1 (инвариант обхода). Перед i-й итерацией Traverse указатель curr указывает на vᵢ, а посещены ровно v₁..v_{i−1}.

Доказательство. Индукция по i. База: i = 1, curr = head = v₁, посещённых узлов нет. Шаг: обрабатывается vᵢ, затем curr ← next(vᵢ) = v_{i+1}; множество посещённых становится v₁..vᵢ. Так как список ацикличен и конечен, после n шагов curr = NIL, и цикл завершается. [math]\displaystyle{ \blacksquare }[/math]

Лемма 2 (корректность вставки). После Insert-After(T, p, x), где p = v_k, последовательность списка равна v₁, …, v_k, x, v_{k+1}, …, vₙ.

Доказательство. Новый узел получает next = p.next = v_{k+1} (или NIL, если p — хвост), затем p.next начинает указывать на новый узел. Ссылки остальных узлов не меняются, поэтому единственный путь из head проходит через v_k → x → v_{k+1}. [math]\displaystyle{ \blacksquare }[/math]

Лемма 3 (корректность удаления). Delete(T, k) удаляет первый узел с ключом k и не меняет порядок остальных; при отсутствии ключа список не меняется.

Доказательство. Инвариант цикла: prev — предшественник curr. При выходе либо curr = NIL (просмотрены все узлы), либо curr.key = k. В первом случае возвращается false. Во втором ссылка prev.next (или head, если prev = NIL) переводится на curr.next; остальные ссылки не тронуты, поэтому все узлы, кроме curr, сохраняют порядок. [math]\displaystyle{ \blacksquare }[/math]

Теорема 4 (корректность разворота). После Reverse(T) список содержит те же узлы в обратном порядке, а head указывает на прежний хвост.

Доказательство. Инвариант: перед i-й итерацией префикс v₁..v_{i−1} развёрнут в цепочку v_{i−1} → … → v₁ → NIL (при i = 1 префикс пуст, prev = NIL), prev указывает на v_{i−1}, curr — на vᵢ, а связи от vᵢ вперёд не изменены. Итерация сохраняет next = v_{i+1}, затем направляет vᵢ.next на prev, то есть на v_{i−1}; теперь развёрнутый префикс — vᵢ → … → v₁, prev = vᵢ, curr = v_{i+1}. Инвариант восстановлен. После n итераций prev = vₙ, curr = NIL, и head ← vₙ. [math]\displaystyle{ \blacksquare }[/math]

Теорема 5 (нижняя граница поиска и удаления по ключу). В худшем случае любой детерминированный алгоритм поиска или удаления по ключу в неупорядоченном односвязном списке делает Ω(n) сравнений ключей.

Доказательство. В односвязном списке доступна только операция next, а признак конца — NIL. Чтобы корректно вернуть NIL при отсутствии ключа, алгоритм обязан дойти до NIL; это требует ровно n переходов от head и n сравнений. Если алгоритм остановился раньше, он не прочитал next текущего узла и не может отличить отсутствие ключа от ключа в непросмотренном хвосте. Для удаления дополнительно нужно найти узел и его предшественника, что также требует Ω(n). [math]\displaystyle{ \blacksquare }[/math]

Теорема 6 (слияние). Merge-Sorted возвращает отсортированный список из n + m узлов за O(n + m) времени и O(1) дополнительной памяти.

Доказательство. Инвариант: результат отсортирован и состоит ровно из просмотренных узлов. На каждом шаге сравниваются головы остатков; меньшая (при равенстве — из первого списка) присоединяется к хвосту и не может быть больше ранее добавленных, потому что оба остатка отсортированы. Когда один остаток исчерпан, второй уже отсортирован и его элементы не меньше последнего добавленного, поэтому присоединение целого остатка сохраняет порядок. Каждая итерация удаляет один узел из входов, всего итераций не больше n + m. [math]\displaystyle{ \blacksquare }[/math]

Рекуррентности. Рекурсивный разворот описывается как T(n) = T(n−1) + Θ(1), T(0) = Θ(1). Подстановка даёт T(n) = T(0) + n·Θ(1) = Θ(n). Для слияния сцепкой цикл делает не больше n + m − 1 итераций (для n, m ≥ 1): каждая итерация поглощает один узел, а цикл завершается, когда один из списков опустел. Поэтому T(n, m) = O(n + m), а при чередовании ключей достигается Θ(n + m). В виде рекуррентности для верхней оценки: T(n, m) ≤ max(T(n−1, m), T(n, m−1)) + Θ(1), базы T(0, m) = T(n, 0) = Θ(1) — остаток присоединяется одной ссылкой. Если остаток копировать, база становится T(0, m) = Θ(m), и тогда T(n, m) = Θ(n + m). Итеративные варианты из псевдокода имеют ту же оценку времени и O(1) дополнительной памяти, поэтому предпочтительнее там, где важна глубина стека.

Память. Каждый узел хранит ключ и один указатель (два в двусвязном списке), то есть O(1) слов на элемент, суммарно Θ(n). Нижняя граница Ω(n) следует из того, что n различных ключей нужно где-то хранить. Для int на 64-битной платформе узел односвязного списка обычно занимает 16 байт (4 байта ключа, 8 байт указателя, 4 байта выравнивания), двусвязного — 24 байта; массив хранит те же ключи по 4 байта плюс запас ёмкости. Накладные расходы аллокатора на каждый узел в эту оценку не входят и могут быть заметными.

Сравнение с альтернативами

Вариант	Доступ по индексу	Вставка после узла / удаление при prev	Вставка в голову	Удаление по указателю	Обход	Память на элемент	Когда выбирать
Динамический массив	O(1)	O(n)	O(n)	O(n)	быстрый, локальный	ключ + запас ёмкости	частый доступ по индексу и обход
Односвязный	O(i)	O(1) после узла	O(1)	O(n) без prev	медленный	ключ + 1 указатель	вставки после известного узла, стек, персистентность
Двусвязный	O(i)	O(1)	O(1)	O(1)	медленный, в обе стороны	ключ + 2 указателя	удаление по указателю, LRU, дека
Циклический	O(i)	O(1)	O(1)	O(1) с prev	медленный, без NIL	ключ + 1–2 указателя	round-robin, кольцевые буферы
Двусвязный с sentinel	O(i)	O(1)	O(1)	O(1)	медленный	ключ + указатели (+1 узел на список)	убрать особые случаи головы и пустого списка

Вердикт. Динамический массив — выбор по умолчанию, если нужен доступ по индексу, обход или сортировка. Односвязный список оправдан, когда вставки и удаления происходят в уже найденной позиции, а память под указатель не критична; он же естественен для функциональных языков и стека. Двусвязный список нужен, когда требуется удаление по указателю за O(1) или обход в обе стороны. Циклический вариант удобен для структур, в которых нет естественного конца. Sentinel не меняет асимптотику, но уменьшает число ветвлений и ошибок.

Кэш-локальность (рис. 5) часто важнее асимптотики: обход массива из 10⁶ int и обход списка из 10⁶ узлов имеют одинаковую O(n)-оценку, но различаются по константе в разы. Поэтому «список вместо массива» — не оптимизация по умолчанию, а осознанный выбор в пользу перестройки.

Где применяется

1. Цепочки в хеш-таблицах. Каждый бакет — связный список элементов с одинаковым хешем. Вставка в голову бакета — O(1), поиск — Θ(1 + α) при равномерном хешировании и коэффициенте заполнения α, удаление при известном узле — O(1) в двусвязном варианте. Список удобен тем, что размер бакета заранее неизвестен, а перестраивать таблицу при каждой вставке не нужно [1].
2. Free list в аллокаторах памяти. Свободные блоки кучи связываются в список: выделение — изъятие головы, освобождение — вставка в голову, обе операции O(1). Такой список не требует отдельной памяти под узлы, если хранить ссылку внутри самого свободного блока [3].
3. LRU-кэш. Хеш-таблица ключ → узел плюс двусвязный список: при обращении узел переносится в голову за O(1), при переполнении удаляется хвост за O(1). Без двусвязного списка пришлось бы искать предшественника хвоста за O(n) [6].
4. Ядро ОС и драйверы. Двусвязные интрузивные списки (list_head в ядре Linux) связывают задачи, устройства и буферы. Интрузивность позволяет одному объекту находиться в нескольких списках одновременно и не выделять память под членство; удаление по указателю — O(1) [5].
5. Функциональные и персистентные списки. В LISP, Scheme и Haskell список строится из cons-ячеек: добавление в голову — O(1) и не копирует хвост, поэтому старые версии остаются доступными. Это делает односвязный список естественной структурой для неизменяемых данных [5].
6. Списки смежности графов. Граф с n вершинами и m рёбрами хранится как массив из n списков: память Θ(n + m), перебор соседей вершины — O(deg(v)). Для разреженных графов это экономнее матрицы смежности [1].
7. Стандартные библиотеки. std::list — двусвязный список, std::forward_list — односвязный; std::list::splice и std::forward_list::splice_after переставляют один узел или целый список за O(1) и не инвалидируют указатели на остальные элементы. Плата — отсутствие доступа по индексу и дополнительная память [4].

Историческая справка

• 1953. Ханс Петер Лун (Hans Peter Luhn) предложил использовать связные списки в цепочках хеш-таблиц во внутренней записке IBM [5].
• 1955–1956. Аллен Ньюэлл, Клифф Шоу и Герберт Саймон в RAND Corporation разработали связный список как основную структуру языка IPL (Information Processing Language) для задач искусственного интеллекта, включая Logic Theory Machine и General Problem Solver. Отчёты появились в IRE Transactions on Information Theory в 1956 году [5].
• 1957. В работе «Programming the Logic Theory Machine» (Proc. WJCC, февраль 1957) появилась классическая схема из блоков-узлов и стрелок к следующим узлам [5].
• 1958–1960. Джон Маккарти создал LISP, где список из cons-ячеек стал основной структурой данных; описание опубликовано в Communications of the ACM в 1960 году [5].
• 1968. Дональд Кнут систематизировал связное распределение памяти в TAOCP, том 1, §2.2.5 «Linked Allocation» [3].
• 1975. Ньюэлл и Саймон получили премию Тьюринга, в том числе за вклад в list processing [5].
• 1998–2011. std::list входит в STL C++ с C++98, std::forward_list — с C++11 [4].

Название «linked list» подчёркивает главное: элементы связаны ссылками, а не следуют друг за другом в памяти.

Типичные ошибки и подводные камни

• Утечка при удалении. Ссылка переставлена, а узел не освобождён. В C++ это утечка; при большом числе операций память растёт линейно. Лечится парой «переставить ссылку — освободить узел» в одном месте.
• Двойное освобождение. Два указателя считают себя владельцами узла. Причина — поверхностное копирование списка или передача указателя без передачи владения. Решение — Rule of Five и явное владение.
• Висячий указатель. После delete узел нельзя читать, но внешний указатель на него остаётся. Список не может это обнаружить; помогает дисциплина «не хранить указатели на удалённые узлы».
• Потеря остатка при вставке. Если выполнить p.next ← node до node.next ← p.next, прежний хвост теряется. Порядок строк 3–4 в Insert-After обязателен.
• Освобождение до сохранения next. Если выполнить delete curr раньше, чем next ← curr.next, следующий узел уже не найти, а чтение поля освобождённого узла — неопределённое поведение. Сначала сохраните next, затем освобождайте.
• Вставка в конец без tail. Каждая такая вставка — O(n); построение списка из n элементов превращается в O(n²). Храните tail или стройте список вставками в голову и разворачивайте в конце.
• Копирование указателя вместо узла. b = a для указателя создаёт второго «владельца» того же списка; для независимой копии нужны новые узлы.
• Бесконечный обход циклического списка. Условие curr ≠ NIL всегда истинно, поэтому цикл не завершается. Нужен счётчик n или остановка на стартовом узле; для проверки цикла — алгоритм Флойда с двумя указателями.
• Удаление последнего узла «копированием следующего». Приём не работает для хвоста, а для среднего узла подменяет ключ в узле: внешние указатели на удалённый ключ начинают видеть другой ключ, хотя адрес узла не меняется.
• Рекурсия на большом списке. Рекурсивный обход или разворот на 10⁵–10⁶ узлах исчерпывает стек. Итеративный вариант использует O(1) памяти.
• Вывод «список быстрее массива». Верен только для вставки после известного узла и удаления при известном prev (в двусвязном — по указателю). На поиске и обходе список проигрывает из-за локальности (рис. 5).

Задачи для практики

1. Разворот. Реализуйте разворот односвязного списка итеративно и рекурсивно. Ограничения: O(n) времени. Подсказка: сохраняйте next до перезаписи. Ответ: итеративно O(1) памяти, рекурсивно O(n) стека.
2. Середина. Найдите средний узел за один проход. Ограничения: O(1) памяти. Подсказка: медленный указатель на один шаг, быстрый на два. Ответ: при чётном n медленный остановится на втором из двух средних; O(n) времени.
3. Цикл. Определите, есть ли в списке цикл, и найдите его начало. Ограничения: O(1) памяти. Подсказка: алгоритм Флойда; после встречи один указатель верните в голову. Ответ: O(n) времени, O(1) памяти.
4. k-й с конца. Найдите k-й узел с конца за один проход. Ограничения: k ≤ n, O(1) памяти. Подсказка: два указателя с зазором k. Ответ: O(n).
5. Палиндром. Проверьте, читается ли список одинаково в обе стороны. Ограничения: O(n) времени, O(1) памяти. Подсказка: найдите середину, разверните вторую половину, сравните, восстановите список. Ответ: O(n) времени, O(1) памяти.
6. Слияние. Слейте два отсортированных списка, не создавая новых узлов. Ограничения: O(1) дополнительной памяти. Подсказка: сравнение голов и перестановка ссылок. Ответ: O(n + m); при равенстве берите элемент из первого списка — слияние устойчиво.
7. Двусвязный список. Реализуйте кольцо с sentinel и удаление по указателю за O(1). Ограничения: без особых случаев для головы. Подсказка: x.prev.next ← x.next и x.next.prev ← x.prev. Ответ: проверьте инвариант после случайной серии вставок и удалений.
8. Нижняя граница. Докажите, что удаление по ключу в неупорядоченном списке требует Ω(n) в худшем случае. Подсказка: два входа, неразличимые для алгоритма, который просмотрел не все узлы.

Ответы (кратко). 1. Итеративно — три указателя; рекурсивно — стек O(n). 2. Медленный и быстрый указатели. 3. Флойд: встреча, затем синхронный шаг от головы и от точки встречи. 4. Зазор k. 5. Середина + разворот половины. 6. Сцепка узлов. 7. Sentinel убирает ветвления. 8. Аргумент противника из теоремы 5.

Реализация на C++

Учебная реализация SinglyLinkedList с владением. Класс следует Rule of Five: деструктор, копирующий конструктор, копирующее присваивание (copy-and-swap), перемещающий конструктор и перемещающее присваивание. Копия глубокая, перемещение передаёт владение и оставляет источник пустым. Тест проверяет вставку, удаление головы и середины, разворот, копирование, перемещение и слияние.

#include <cassert>
#include <cstddef>
#include <initializer_list>
#include <iostream>
#include <utility>
#include <vector>

template <class T>
class SinglyLinkedList {
    struct Node {
        T value;
        Node* next;
        explicit Node(const T& v, Node* n = nullptr) : value(v), next(n) {}
        explicit Node(T&& v, Node* n = nullptr) : value(std::move(v)), next(n) {}
    };

    Node* head_ = nullptr;
    std::size_t size_ = 0;

public:
    SinglyLinkedList() noexcept = default;

    ~SinglyLinkedList() { clear(); }

    // Копирование: глубокая копия узлов.
    SinglyLinkedList(const SinglyLinkedList& other) {
        Node** tail = &head_;
        try {
            for (Node* p = other.head_; p != nullptr; p = p->next) {
                *tail = new Node(p->value);
                tail = &((*tail)->next);
                ++size_;
            }
        } catch (...) {
            clear();
            throw;
        }
    }

    SinglyLinkedList& operator=(const SinglyLinkedList& other) {
        if (this != &other) {
            SinglyLinkedList tmp(other);   // copy-and-swap
            swap(tmp);
        }
        return *this;
    }

    // Перемещение: владение переходит, источник становится пустым.
    SinglyLinkedList(SinglyLinkedList&& other) noexcept
        : head_(other.head_), size_(other.size_) {
        other.head_ = nullptr;
        other.size_ = 0;
    }

    SinglyLinkedList& operator=(SinglyLinkedList&& other) noexcept {
        if (this != &other) {
            clear();
            head_ = other.head_;
            size_ = other.size_;
            other.head_ = nullptr;
            other.size_ = 0;
        }
        return *this;
    }

    void swap(SinglyLinkedList& other) noexcept {
        std::swap(head_, other.head_);
        std::swap(size_, other.size_);
    }

    bool empty() const noexcept { return head_ == nullptr; }
    std::size_t size() const noexcept { return size_; }

    void clear() noexcept {
        Node* p = head_;
        while (p != nullptr) {
            Node* next = p->next;
            delete p;
            p = next;
        }
        head_ = nullptr;
        size_ = 0;
    }

    void push_front(const T& x) {
        head_ = new Node(x, head_);
        ++size_;
    }

    void push_back(const T& x) {          // O(n) без указателя на хвост
        Node** link = &head_;
        while (*link != nullptr) link = &((*link)->next);
        *link = new Node(x);
        ++size_;
    }

    bool contains(const T& x) const {
        for (Node* p = head_; p != nullptr; p = p->next)
            if (p->value == x) return true;
        return false;
    }

    bool erase(const T& x) {
        Node** link = &head_;             // ссылка на поле, ведущее к curr
        while (*link != nullptr && !((*link)->value == x))
            link = &((*link)->next);
        if (*link == nullptr) return false;
        Node* victim = *link;
        *link = victim->next;
        delete victim;
        --size_;
        return true;
    }

    void reverse() noexcept {
        Node* prev = nullptr;
        Node* curr = head_;
        while (curr != nullptr) {
            Node* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        head_ = prev;
    }

    // предусловие: &other != this; слияние сцепкой узлов
    void merge_sorted(SinglyLinkedList&& other) {
        Node* a = head_;
        Node* b = other.head_;
        Node* merged = nullptr;
        Node** tail = &merged;
        while (a != nullptr && b != nullptr) {
            Node* node;
            if (b->value < a->value) { node = b; b = b->next; }
            else                     { node = a; a = a->next; }  // при равенстве — из *this
            node->next = nullptr;
            *tail = node;
            tail = &(node->next);
        }
        *tail = (a != nullptr) ? a : b;
        head_ = merged;
        size_ += other.size_;
        other.head_ = nullptr;
        other.size_ = 0;
    }

    std::vector<T> to_vector() const {
        std::vector<T> out;
        out.reserve(size_);
        for (Node* p = head_; p != nullptr; p = p->next)
            out.push_back(p->value);
        return out;
    }
};

int main() {
    SinglyLinkedList<int> a;
    for (int x : {7, 3, 9, 1, 5}) a.push_back(x);
    assert(a.size() == 5);
    assert((a.to_vector() == std::vector<int>{7, 3, 9, 1, 5}));

    a.push_front(0);
    assert(a.size() == 6);
    assert(a.to_vector().front() == 0);

    assert(a.erase(9));
    assert((a.to_vector() == std::vector<int>{0, 7, 3, 1, 5}));
    assert(a.erase(0));                       // удаление головы
    assert((a.to_vector() == std::vector<int>{7, 3, 1, 5}));
    assert(!a.erase(42));                     // ключа нет
    assert(a.size() == 4);

    a.reverse();
    assert((a.to_vector() == std::vector<int>{5, 1, 3, 7}));

    SinglyLinkedList<int> b = a;              // копирование
    b.push_front(100);
    assert(a.size() == 4 && b.size() == 5);   // списки независимы
    assert(a.to_vector().front() == 5);

    SinglyLinkedList<int> d;
    d = a;                                    // копирующее присваивание
    assert(d.size() == 4);
    d.erase(7);
    assert(a.size() == 4 && d.size() == 3);

    SinglyLinkedList<int> c = std::move(b);   // перемещение
    assert(b.size() == 0 && b.to_vector().empty());
    assert(c.size() == 5);
    b = std::move(c);                         // перемещающее присваивание
    assert(b.size() == 5 && c.size() == 0);

    SinglyLinkedList<int> s1, s2;
    for (int x : {1, 4, 7}) s1.push_back(x);
    for (int x : {2, 4, 8}) s2.push_back(x);
    s1.merge_sorted(std::move(s2));
    assert((s1.to_vector() == std::vector<int>{1, 2, 4, 4, 7, 8}));
    assert(s2.size() == 0);

    SinglyLinkedList<int> empty;
    empty.reverse();
    assert(empty.size() == 0);
    assert(!empty.erase(1));
    assert(empty.to_vector().empty());

    std::cout << "ok\n";
    return 0;
}

Замечания по реализации.

• erase использует Node**: указатель на head_ или на поле next предшественника; отдельный случай головы не нужен.
• merge_sorted перецепляет существующие узлы и не выделяет память; после вызова other пуст, а его узлы принадлежат результату. Это соответствует оценке O(1) дополнительной памяти из псевдокода.
• Копирующий конструктор освобождает частично построенный список при любом исключении; сильная гарантия для копирования достигнута ценой try/catch.
• push_back намеренно оставлен O(n), чтобы показать разницу с push_front; в production-коде хранят tail или берут контейнер с дешёвой вставкой в конец (std::list, std::vector).
• Перегрузки с T&& и emplace_front опущены для краткости.

Связанные темы

• Динамический массив — альтернатива с непрерывным буфером, доступом O(1) и амортизированной вставкой в конец.
• Асимптотическая сложность — O, Ω, Θ и нижние границы, использованные в доказательствах.
• Амортизационный анализ — почему амортизация не даёт списку выигрыша, а массиву даёт.
• Хеш-таблица — цепочки как основной способ разрешения коллизий.
• Дека — двусвязный список блоков и операции с двух концов.
• Стек — односвязный список с вставкой и удалением в голове.
• Очередь — список с указателем на хвост.
• Графы — списки смежности как представление разреженного графа.

Источники

1. Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms (CLRS). 3rd ed. — MIT Press, 2009. — Гл. 10 «Elementary Data Structures», §10.2 «Linked lists»; гл. 11 «Hash Tables»; гл. 22 «Elementary Graph Algorithms», §22.1.
2. Sedgewick R., Wayne K. Algorithms. 4th ed. — Addison-Wesley, 2011. — §1.3 «Bags, Queues, and Stacks» (связные реализации).
3. Knuth D. E. The Art of Computer Programming. Vol. 1: Fundamental Algorithms. 3rd ed. — Addison-Wesley, 1997. — §2.2.5 «Linked Allocation».
4. cppreference.com: std::list. URL: https://en.cppreference.com/w/cpp/container/list; std::forward_list. URL: https://en.cppreference.com/w/cpp/container/forward_list.
5. Wikipedia: Linked list. URL: https://en.wikipedia.org/wiki/Linked_list.
6. LeetCode 146: LRU Cache. URL: https://leetcode.com/problems/lru-cache/.