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

Предпосылки: массив (непрерывность, кэш-локальность), динамический массив (проблема O(n) вставки), указатели и ссылки, куча, освобождение памяти, оценка сложности O(…), базовое чтение Ruby (классы, методы, переменные экземпляра, nil).

← Динамический массив | Стек, очередь, дек →

Вставка в начало или середину динамического массива стоит O(n) — нужно сдвинуть все последующие элементы. Сдвиги — цена непрерывности: элементы лежат подряд, и чтобы освободить место, остальные подвигаются. Что если отказаться от непрерывности? Пусть каждый элемент живёт где угодно в памяти, но хранит указатель на следующий — адрес ячейки памяти, по которому лежит соседний элемент. Элементы связаны в цепочку, как вагоны поезда: отцепить вагон из середины — быстро, если ты уже на месте. Но добраться до вагона 500 — значит пройти через все предыдущие.

Это связный список (linked list): структура из узлов, где каждый узел содержит данные и указатель(и) на другие узлы, образуя последовательность. Поскольку указатель хранит адрес соседа, идти по цепочке можно только вперёд от узла к узлу: формулы адреса по индексу, как у массива, нет.

Операция	Сложность
Вставить элемент в известное место	O(1)*
Удалить элемент из известного места	O(1)*
Получить элемент по номеру позиции	O(n)

* — если уже есть указатель на это место в цепочке

O(1) доступ по индексу потерян, но взамен — O(1) вставка и удаление без сдвигов.

Односвязный список

Минимальная конструкция: каждый узел хранит данные и указатель на следующий. Сама цепочка нигде не записана целиком — её можно найти, только зная, с чего она начинается. Поэтому отдельно от узлов держат указатель на первый узел; его называют head («голова»). Конец цепочки помечается специальным «пустым» значением — nil: «дальше узлов нет».

На схеме узел показан как [данные|*], где * — указатель на следующий узел, а стрелка ведёт от указателя к тому узлу, на который он показывает:

head -> [A|*] -> [B|*] -> [C|*] -> nil

Вставка в начало: O(1)

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

Вставка в конец

Чтобы вставить в конец, нужно найти последний узел. Единственный путь от head — пройти по цепочке: O(n). Для списка из миллиона элементов — миллион шагов ради одной вставки.

Решение: держать ещё один внешний указатель — на последний узел; его называют tail («хвост»). При вставке в конец создаём новый узел, направляем указатель прежнего последнего узла на него и переставляем tail на новый узел. O(1).

Удаление из начала: O(1)

Забираем значение из первого узла и переставляем head на следующий за ним. На старый первый узел теперь не указывает ни head, ни какой-либо другой узел — добраться до него больше нельзя, и память под ним освобождается (вручную или сборщиком мусора, в зависимости от языка).

Ограничение односвязного списка: обратный ход

Вставка в начало, вставка в конец (с tail), удаление из начала — все эти операции работают за O(1), потому что двигаются по ссылке вперёд. Но любая операция, требующая обратного шага — к предыдущему узлу, — упирается в то, что у узла нет ссылки назад.

Удалить последний элемент: tail указывает на него, значение забираем. Но tail должен теперь показывать на предпоследний узел — а адреса предпоследнего узла нигде нет. В односвязном списке у узла есть указатель только вперёд, на следующий, и обратного нет: единственный способ найти предпоследний — пройти от head до узла, чей указатель ведёт на tail. O(n).

Та же проблема с удалением произвольного узла из середины. Есть указатель на узел C, нужно его убрать из цепочки. Узел не стирается на месте: чтобы выкинуть C, идущий к нему указатель предыдущего узла B нужно перенаправить на следующий за C узел D — тогда обход пойдёт мимо C. Но узел B в односвязном списке найти не из чего: указателя назад нет, и до B снова приходится идти от head. O(n).

Двусвязный список

Если каждый узел хранит не только указатель на следующий, но и на предыдущий — проблема исчезает. Удаляя узел C, мы сразу знаем его соседей: предыдущего (B) и следующего (D) узел C хранит в своих двух указателях. Остаётся перенаправить указатель «вперёд» у B на D, а указатель «назад» у D на B — и C выпадает из цепочки. Искать B обходом не нужно, поэтому O(1).

На схеме у узла теперь два указателя, [*|данные|*]: левый ведёт назад, правый — вперёд.

nil <- [*|A|*] <-> [*|B|*] <-> [*|C|*] -> nil
        ^                        ^
      head                     tail

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

Кольцевой список — вариант, в котором последний узел указывает на первый (и первый на последний в двусвязном). Может быть односвязным или двусвязным.

Операции и сложность

Операция	Односвязный	Двусвязный
Доступ по индексу	O(n)	O(n)
Вставка в начало	O(1)	O(1)
Вставка в конец (с tail)	O(1)	O(1)
Вставка после известного узла	O(1)	O(1)
Удаление из начала	O(1)	O(1)
Удаление из конца	O(n)	O(1)
Удаление известного узла	O(n)*	O(1)

* — нужен предыдущий узел

Накладные расходы памяти

Каждый узел платит за связь памятью. Односвязный список добавляет один указатель на узел (на 64-битной машине — 8 байт), двусвязный — два, то есть 16 байт. Сам элемент при этом может быть маленьким: если в узле лежит одно целое число в 4 байта, то на 8–16 байт полезных данных приходится столько же или больше служебных. К этому добавляется выравнивание — узел может занять чуть больше из-за округления размера, — но порядок цифр задают именно указатели.

Где память за узлы выделяется не вручную, а автоматически (Ruby, Java), накладные расходы ещё выше: каждый узел — отдельный объект со своим служебным заголовком, и чем больше узлов, тем больше работы у механизма автоматического освобождения памяти.

Локальность, прыжки и выбор структуры

Вставка в начало — O(1), но доступ по индексу — O(n). Ещё хуже то, чего асимптотика не видит: узлы выделяются по одному и лежат в памяти где попало, а не подряд. На каждом шаге обхода теряется локальность данных (из предпосылки про массив: соседние по обращению данные дешевле читать, если они рядом), и переход по указателю легко уводит в ещё не загруженную область — промах кеша (cache miss). Последовательный обход массива, где кэш-линии подтягиваются заранее, на практике часто в несколько раз быстрее обхода списка с его случайными прыжками по памяти.

Текстовый редактор, хранящий строку как связный список: курсор — указатель на узел, вставка рядом с ним O(1), удаление тоже O(1). Но клик мышкой на позицию 5 000 — переход по 5 000 указателям от head. Массив даёт O(1) для такого прыжка. Список выигрывает при последовательной работе (набор текста), массив — при произвольных прыжках (навигация). Реальные редакторы используют гибриды: gap buffer (массив с дыркой в позиции курсора) или rope (дерево из фрагментов).

Критерий	Массив	Связный список
Произвольный доступ по индексу	O(1)	O(n)
Вставка/удаление в начало	O(n)	O(1)
Вставка/удаление в середину	O(n)	O(1)*
Обход всех элементов	Быстрый (локальность)	Медленный (cache miss)
Склейка двух списков в один	O(n)	O(1)

* — если есть указатель на место вставки

На практике динамический массив выигрывает в большинстве случаев из-за лучшей локальности данных. Связный список берут там, где ключевая операция — O(1) удаление или перемещение узла по уже имеющемуся указателю: LRU-кэш, история отмен операций (undo), некоторые реализации очередей. Полная реализация операций remove_node и add_to_head для двусвязного списка показана в контексте LRU-кэша, где эти операции составляют ядро структуры.

Когда полная свобода доступа мешает

Массив и список дают полную свободу: доступ по индексу, вставка и удаление в любом месте. Но иногда эта свобода опасна. Проверке скобок в выражении нужен строгий порядок «последним пришёл — первым ушёл» (LIFO): открылась скобка — запомнили её, закрылась — снимаем последнюю запомненную. Если хранить эти записи прямо в массиве или списке, ничто не мешает по ошибке удалить элемент из середины и сломать порядок. Структуры, которые сознательно ограничивают доступ только концами цепочки, — стек, очередь, дек — таких ошибок просто не допускают.

Реализация: односвязный список (Ruby)

Теория описывает операции через сложность — O(1) вставка, O(1) удаление. В коде всплывает то, чего асимптотика не показывает: head и tail нужно держать согласованными друг с другом, а пустой список и список из одного элемента ведут себя иначе, чем «обычный».

class Node
  attr_accessor :value, :next
 
  def initialize(value, node = nil)
    @value = value
    @next = node
  end
end
 
class List
  def initialize
    @head = nil
    @tail = nil
  end
 
  def prepend(value)
    new_node = Node.new(value, @head)
    @tail = new_node unless @head
    @head = new_node
  end
 
  def append(value)
    new_node = Node.new(value)
    if @tail
      @tail.next = new_node
      @tail = new_node
    else
      @tail = @head = new_node
    end
  end
 
  def remove_first
    return nil unless @head
    value = @head.value
    @head = @head.next
    @tail = nil unless @head  # head стал nil → список пуст → tail тоже nil
    value
  end
end

Ловушка: два указателя на одну структуру

В теории удаление из начала — одна операция: обновить head. Но в реализации с двумя указателями (@head и @tail) возникает тонкая ошибка. Если в списке ровно один элемент, head и tail указывают на один и тот же узел. При удалении head обнуляется (@head = nil), а tail продолжает указывать на узел, уже выпавший из цепочки. При следующем append проверка if @tail проходит (tail не nil), и код дописывает через @tail.next к узлу, которого в списке больше нет. При этом @head остаётся nil, и обход списка (метод to_a, собирающий значения от head до конца) возвращает пустоту, хотя элемент «добавлен».

До:     @head -> [A] <- @tail     (один элемент, оба указывают на [A])

remove_first:
        @head = nil               (head обнулился)
        @tail -> [A]              (tail всё ещё ссылается!)

append(B):
        @tail.next = [B]          (пишем через указатель на выпавший узел)
        @tail = [B]

to_a:   @head = nil -> []         (список выглядит пустым)

Исправление — одна строка: @tail = nil unless @head. Общее правило: когда два указателя смотрят на одну структуру, изменение одного может оставить другой указывать на то, чего в структуре уже нет. Поэтому каждая операция, меняющая @head, должна проверять @tail, и наоборот.