linked-list

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

Предпосылки: массив (непрерывность, кэш-локальность), динамический массив (проблема O(n) вставки).

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

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

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

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

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

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

Минимальная конструкция: каждый узел хранит данные и указатель на следующий. Для работы со списком нужен внешний указатель на первый узел — head.

head → [A|*] → [B|*] → [C|*] → nil

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Операция	Односвязный	Двусвязный
Доступ по индексу	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)

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

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

Односвязный список добавляет минимум один указатель на узел — обычно 8 байт на 64-bit, плюс возможный padding из-за выравнивания. Двусвязный — два указателя, обычно 16 байт.

Для маленьких значений (например, int на 4 байта) накладные расходы доминируют:

struct Node {
  int value;         // 4 байта
  struct Node *next; // 8 байт
};
// итого 16 байт из-за выравнивания: 4 байта данных, 12 накладных

В языках со сборщиком мусора (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-history, некоторые реализации очередей. Полная реализация операций remove_node и add_to_head для двусвязного списка показана в контексте LRU-кэша, где эти операции составляют ядро структуры.

Проблема: избыточная свобода интерфейса

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

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

Теория описывает операции через сложность — O(1) вставка, O(1) удаление. При реализации проявляются нюансы, не видные на уровне асимптотики: синхронизация нескольких указателей, граничные случаи пустого списка, управление памятью.

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 становится nil, а tail продолжает указывать на удалённый узел. При следующем append проверка @tail даёт true (он не nil), и код пишет через @tail.next — модифицирует узел, который уже не принадлежит списку. При этом @head остаётся nil, и обход возвращает пустой результат, хотя элемент «добавлен».

До:     @head → [A] < @tail      (один элемент)

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, и наоборот.