Вставка после выбранной записи

У нас уже есть способы хранить последовательности: массив фиксированной длины и динамический массив с резервом. Оба хороши для доступа по индексу, но у них есть слабое место, которое мы разбирали на оценках. Чтобы вставить значение в середину динамического массива, приходится сдвигать весь правый хвост вправо. Чем длиннее хвост, тем дороже операция. Если мы часто вставляем что-то после уже найденной записи, эти сдвиги становятся обузой.

Хочется структуру, в которой вставка после известного места не требовала бы сдвигать соседей. Не потому, что она обязательно быстрее массива во всём, — у массивов свои сильные стороны, и мы их не трогаем. А именно для вставки и удаления в известной позиции. Так мы приходим к связному списку.

Узел и связь

Связный список — это последовательность узлов, где каждый узел хранит значение и связь со следующим узлом. Связь называется Next. Узел со значением 10 связан с узлом 20, тот — с узлом 30, а узел 30 ни с чем не связан: его связь равна null, что означает конец списка.

Первый узел называется головой списка. Через голову мы попадаем в список и дальше идём по связям.

Схематически это выглядит так:

head → [10 | •] → [20 | •] → [30 | null]

Каждый квадратик — узел. Первое поле — значение, второе — связь со следующим. Голова хранит доступ к первому узлу, а не ко всем сразу. Дальше всё держится на связях.

Доступ к k-й позиции

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

Значит, чтобы попасть в k-ю позицию, нужно пройти от головы k шагов по связям. Стоимость — O(k), а в худшем случае, когда k близко к n, — O(n). Это принципиальное отличие: доступ по индексу в связном списке не O(1). Мы платим за гибкость вставки и удаления тем, что простой проход к нужной позиции стал дороже.

Небольшой код, чтобы закрепить модель. Здесь Node — просто описание узла, без подробностей синтаксиса; нам важен сам принцип.

using System;

var head = new Node(10);
head.Next = new Node(20);
head.Next.Next = new Node(30);
Node? current = head;
while (current != null)
{
    Console.WriteLine(current.Value);
    current = current.Next;
}

class Node
{
    public int Value;
    public Node? Next;
    public Node(int value) { Value = value; }
}

Вывод:

10
20
30

Мы прошли цепочку от головы до null, печатая значения по пути. Это и есть обход связного списка — O(n) по времени, потому что каждый узел посещается ровно один раз.

Вставка после известного узла

Разберём главную операцию, ради которой связный список и существует. Пусть у нас цепочка 10 → 20 → 30, и мы нашли узел со значением 10. Хотим вставить после него узел со значением 15, чтобы получилось 10 → 15 → 20 → 30.

Казалось бы, что тут сложного. Но здесь есть ловушка. Если сразу написать current.Next = inserted, мы потеряем хвост: узел 20 и всё за ним станут недостижимы, потому что единственная связь к ним шла через current.Next, а мы её только что переписали. Никто больше на них не указывает.

Правильный порядок такой. Сначала связать новый узел с тем, что шло после current: inserted.Next = current.Next. Теперь узел 15 указывает туда же, куда указывал узел 10. И только потом переключить связь current: current.Next = inserted. После этого цепочка принимает нужный вид.

using System;

var head = new Node(10);
head.Next = new Node(20);
head.Next.Next = new Node(30);
var current = head;
var inserted = new Node(15);
inserted.Next = current.Next;
current.Next = inserted;
Node? p = head;
while (p != null)
{
    Console.WriteLine(p.Value);
    p = p.Next;
}

class Node
{
    public int Value;
    public Node? Next;
    public Node(int value) { Value = value; }
}

Вывод:

10
15
20
30

Трассировка двух присваиваний. До вставки current — это узел 10, current.Next — узел 20. Первое присваивание: inserted.Next = current.Next — теперь узел 15 указывает на узел 20. Хвост сохранён: мы его не трогали, он по-прежнему цел. Второе присваивание: current.Next = inserted — теперь узел 10 указывает на узел 15. Цепочка собрана. Если поменять порядок, хвост потеряется: после current.Next = inserted связь с 20 пропадёт, и до присваивания inserted.Next мы уже не будем знать, куда его вести.

Стоимость самой вставки — O(1): два присваивания, вне зависимости от длины списка. Обратите внимание, что в примере мы взяли current = head, то есть узел 10 был нам известен с самого начала, и никакого поиска по списку не выполнялось. Если бы по условию задачи нужный узел ещё предстояло найти по значению, это была бы отдельная операция, и её стоимость могла бы достигать O(n). Вставка дёшева именно тогда, когда узел уже в руках.

Вставка в голову

Отдельно стоит вставка в начало списка. Здесь предшественника нет: новым первым узлом становится только что созданный, а его связь должна указывать на прежнюю голову. Два действия: new.Next = head и head = new. После этого new становится головой, а прежний список целиком идёт за ним.

Эта операция работает и для пустого списка. Если head был равен null, new.Next = null, и новый узел становится единственным. Никаких особых случаев писать не нужно: пустой список превращается в одноэлементный той же самой последовательностью действий.

Удаление после известного предшественника

Удаление устроено похоже на вставку и тоже требует аккуратности. Пусть у нас цепочка 10 → 15 → 20 → 30, и мы хотим удалить узел 15. Для этого нужно знать его предшественника — узел 10. Тогда удаление выполняется одним присваиванием: p.Next = p.Next.Next. Узел 10 теперь указывает на узел 20, а узел 15 из цепочки выпал.

Сначала проверим, что удалять вообще есть что: если p.Next равен null, удалять нечего, операция ничего не делает. Иначе — одно присваивание, и хвост сам собой «переподключается» к предшественнику.

Удаление головы — отдельный случай. Здесь предшественника нет, потому что голова первая. Удаляем её так: head = head.Next. Если список был пуст, ничего не делаем; если в списке один узел, head становится null, и список пустеет.

И вот ключевое ограничение односвязного списка. Для удаления нужен именно известный предшественник. Известного удаляемого узла недостаточно. Можно, конечно, посмотреть на узел, который нужно удалить, и увидеть его Next, но мы не знаем, кто на этот узел указывает. Единственная связь в односвязном списке ведёт вперёд, а не назад. Поэтому, чтобы удалить узел за O(1), нужно заранее иметь доступ к узлу перед ним.

Если предшественник неизвестен, придётся искать его проходом от головы, и тогда операция становится O(n).

Поиск по значению

Поиск в связном списке — это отдельная операция, и в худшем случае она стоит O(n). Мы идём от головы по связям, сравнивая значение каждого узла с искомым. Если повезёт и нужное значение стоит в первом узле, мы увидим его сразу — это O(1). Если значение стоит в конце или его вовсе нет, придётся пройти весь список, и тогда работа растёт линейно. То есть O(n) — это верхняя граница, а не неизменная цена на каждом входе.

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

Хвост и его особенности

Иногда полезно хранить не только голову, но и хвост — доступ к последнему узлу списка. Тогда добавление в конец становится O(1): новый узел привязывается к хвосту, а хвост сдвигается на новый узел. Без сохранённого хвоста добавление в конец требовало бы прохода до последнего узла, то есть O(n).

Но у хвоста в односвязном списке есть особенность. Удалить последний узел за O(1) не получится, даже если хвост сохранён. Чтобы убрать последний узел, нужно переключить связь предшественника на null, а предшественника мы не знаем: связь идёт вперёд, не назад. Придётся искать предпоследний узел проходом от головы, и это O(n).

Ещё одна тонкость — пустой и одноэлементный списки. Когда мы добавляем первый узел, и голова, и хвост должны указывать на него. Когда удаляем последний узел, оба должны стать null. Если забыть обновить хвост, он останется указывать на узел, которого в списке больше нет, и структура будет думать, что хвост существует. Такое состояние называют висячим логическим хвостом: сам узел ещё где-то есть, но список его больше не содержит. От этого легко получить неверные ответы на последующих операциях.

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

Ограничение односвязного списка — невозможность идти назад. Отсюда и требование знать предшественника при удалении, и невозможность удалить хвост за O(1), даже когда хвост сохранён. Что, если дать каждому узлу вторую связь — на предыдущий узел?

Двусвязный список устроен так: каждый узел хранит два поля связи — Prev и Next. Prev ведёт к предыдущему узлу, Next — к следующему. У головы Prev равен null, у хвоста Next равен null. По такой цепочке можно двигаться в обе стороны.

Схема для трёх узлов со значениями 10, 20, 30:

null ← [10] ⇄ [20] ⇄ [30] → null

Здесь стрелки в обе стороны показывают, что узлы связаны взаимно: у узла 20 Prev — узел 10, а Next — узел 30. И наоборот.

Что это даёт? При известном удаляемом узле удаление становится O(1) без предшественника: мы и так знаем его через Prev. Достаточно перенастроить связи двух соседей навстречу друг другу — или обновить голову или хвост, если удаляется крайний узел.

Посмотрим на маленьком примере.

using System;

var head = new DoubleNode(10);
var middle = new DoubleNode(20);
var tail = new DoubleNode(30);
head.Next = middle;
middle.Prev = head;
middle.Next = tail;
tail.Prev = middle;
middle.Prev.Next = middle.Next;
middle.Next.Prev = middle.Prev;

DoubleNode? p = head;
while (p != null)
{
    Console.Write(p.Value);
    if (p.Next != null) Console.Write(" ");
    p = p.Next;
}
Console.WriteLine();
DoubleNode? q = tail;
while (q != null)
{
    Console.Write(q.Value);
    if (q.Prev != null) Console.Write(" ");
    q = q.Prev;
}
Console.WriteLine();

class DoubleNode
{
    public int Value;
    public DoubleNode? Prev;
    public DoubleNode? Next;
    public DoubleNode(int value) { Value = value; }
}

Вывод:

10 30
30 10

Мы удалили средний узел, и обе связи подтверждают результат. Проход вперёд печатает 10 и 30, проход назад — 30 и 10. Список по-прежнему согласован в обе стороны: у узла 30 Prev теперь указывает на узел 10, у узла 10 Next — на узел 30.

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

Цена двух связей

Двусвязный список удобнее, но не бесплатен. Каждый узел теперь хранит два поля связи вместо одного — Prev и Next. Узлов по-прежнему n, и общий объём памяти остаётся O(n), но постоянный множитель больше: на каждом узле лежит дополнительное поле связи. В задачах, где памяти критично много, это может иметь значение, и стоит помнить, что речь идёт о разнице в полях связей, а не обо всём содержимом узла целиком.

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

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

Известный узел — не бесплатное условие

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

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

Про готовый вариант

В C# есть LinkedList<int> — готовая реализация двусвязного списка. Если в будущем понадобится структура с операциями на обоих концах, полезно помнить, что она существует. Подробно её интерфейс разбирать сейчас не будем: нам важен не конкретный API, а сама модель, которую мы разобрали.

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

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