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

Это и есть связный список. Физически элементы разбросаны по памяти, логически — выстроены в цепочку через ссылки. Прямой доступ по номеру исчез, зато вставка и удаление в нужном месте стали дешёвыми.

Каждый прямоугольник — узел (node). В нём два поля: данные и ссылка на следующий узел (next). У последнего узла next = null — список закончился. Первый узел называется головой (head).

Реализуем узел на C#:

class Node
{
    public int Value { get; set; }
    public Node Next { get; set; }

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

Сам список — это класс, который хранит ссылку на первый узел:

class LinkedList
{
    private Node head;

    public void AddFirst(int value)
    {
        var newNode = new Node(value);
        newNode.Next = head;
        head = newNode;
    }

    public void Print()
    {
        var current = head;
        while (current != null)
        {
            Console.Write(current.Value + " → ");
            current = current.Next;
        }
        Console.WriteLine("null");
    }
}

Добавление в начало (AddFirst) работает за O(1): создаём новый узел, его Next указывает на бывшую голову, и head теперь указывает на новый узел. Ничего не сдвигается.

Обход списка — единственный вариант доступа к элементам. Нет индекса, нет прямого адреса. Только current = current.Next снова и снова, пока не встретится null:

// Найти элемент в связном списке
public bool Contains(int value)
{
    var current = head;
    while (current != null)
    {
        if (current.Value == value) return true;
        current = current.Next;
    }
    return false;
}

// Удалить первый узел с заданным значением
public void Remove(int value)
{
    if (head == null) return;
    if (head.Value == value) { head = head.Next; return; }

    var current = head;
    while (current.Next != null)
    {
        if (current.Next.Value == value)
        {
            current.Next = current.Next.Next;  // перепрыгиваем через удаляемый узел
            return;
        }
        current = current.Next;
    }
}

Удаление — ключевая операция. Нужно найти узел перед удаляемым, и перенаправить его Next. Сборщик мусора (GC) потом сам уберёт узел, на который больше нет ссылок. Сравним связный список с массивом по ключевым операциям:

Доступ по индексу. Массив — O(1): знаем адрес начала, умножаем индекс на размер элемента — готово. Связный список — O(n): нужно пройти от головы по ссылкам до нужного узла. Нет другого пути — элементы физически не стоят рядом.

Вставка в начало. Массив — O(n): нужно сдвинуть все элементы вправо. Связный список — O(1): меняем две ссылки.

Вставка в конец. Массив (без List) — O(1), если место есть. Связный список — O(n), если не храним ссылку на хвост; O(1), если храним.

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

Удаление из начала. Массив — O(n). Связный список — O(1): просто передвигаем head.

Есть и скрытый O(n): поиск по значению. И в массиве, и в связном списке — линейный поиск, если нет сортировки. Здесь они равны. Разница проявляется только при вставке и удалении, когда известна позиция.

На практике это означает вот что. Допустим, вы реализуете очередь задач: новые задачи добавляются в конец, обрабатываются из начала. Для этого нужны Enqueue (конец) и Dequeue (начало).

С List<T>: Add в конец — O(1). RemoveAt(0) — O(n), потому что все элементы сдвигаются влево.

С LinkedList<T>: AddLast — O(1). RemoveFirst — O(1). Для очереди связный список объективно лучше. Собственно, Queue<T> в стандартной библиотеке C# решает эту проблему иначе — через кольцевой буфер — но суть та же: O(1) с обоих концов.

Теперь о двусвязном списке. В односвязном каждый узел знает только о следующем. Это создаёт ограничение: нельзя пройти назад. Если нужно удалить узел — сначала ищем предыдущий, проходя от головы.

Узел двусвязного списка:

class DoublyNode
{
    public int Value { get; set; }
    public DoublyNode Next { get; set; }
    public DoublyNode Prev { get; set; }

    public DoublyNode(int value) { Value = value; }
}

Список теперь хранит и голову, и хвост — это даёт O(1) добавление с обоих концов. Именно поэтому двусвязный список идеально подходит для дека (double-ended queue) — структуры, где нужны O(1) операции на обоих концах:

class DoublyLinkedList
{
    private DoublyNode head;
    private DoublyNode tail;

    public void AddLast(int value)
    {
        var node = new DoublyNode(value);
        if (tail == null) { head = tail = node; return; }
        node.Prev = tail;
        tail.Next = node;
        tail = node;
    }

    public void RemoveLast()
    {
        if (tail == null) return;
        tail = tail.Prev;
        if (tail != null) tail.Next = null;
        else head = null;
    }
}

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

Двусвязный список лежит в основе многих структур: дек, LRU-кеш, история браузера с перемещением вперёд и назад. В C# стандартный LinkedList<T> — именно двусвязный. Его AddFirst, AddLast, RemoveFirst, RemoveLast — все O(1).

var history = new System.Collections.Generic.LinkedList<string>();
history.AddLast("google.com");
history.AddLast("stackoverflow.com");
history.AddLast("github.com");

// Назад
history.RemoveLast();           // убрали github.com
Console.WriteLine(history.Last.Value); // stackoverflow.com

Главный минус связных списков — память. Каждый узел хранит не только данные, но и одну или две ссылки (8 байт каждая на 64-битной системе). Для миллиона целых чисел массив займёт 4 МБ. Односвязный список — 12 МБ (данные + одна ссылка). Двусвязный — 20 МБ. Плюс накладные расходы garbage collector на отдельные объекты. Для задач, где важна экономия памяти и скорость обхода, массив выиграет.

Второй минус — локальность данных. Элементы массива лежат в памяти подряд: прочитали один — соседние уже в кеше процессора. Узлы связного списка разбросаны по куче. Каждое обращение к следующему узлу — потенциальный промах кеша. На современных процессорах это реальная разница в производительности при обходе больших списков.

Это не теоретическая проблема. Бенчмарки показывают: обход int[] из миллиона элементов может быть в 5–10 раз быстрее обхода LinkedList<int> того же размера — только из-за локальности данных. Если вы читаете список много раз и редко вставляете — массив или List<T> выиграют. Посмотрим, как выглядит работа со стандартным LinkedList<T> в C#. Он двусвязный и предоставляет богатый API:

var tasks = new LinkedList<string>();

// Добавление
tasks.AddLast("Написать тесты");
tasks.AddLast("Сделать ревью");
tasks.AddFirst("Срочная задача");  // в начало

// Поиск и вставка рядом
var reviewNode = tasks.Find("Сделать ревью");
tasks.AddBefore(reviewNode, "Обновить документацию");

// Обход
foreach (var task in tasks)
    Console.WriteLine(task);

// Удаление
tasks.Remove("Срочная задача");
tasks.RemoveLast();

Вывод:

Срочная задача
Написать тесты
Обновить документацию
Сделать ревью

Метод Find возвращает объект LinkedListNode<T> — это и есть узел списка. Через него можно добраться до соседей: node.Next, node.Previous, node.Value. Это удобно, когда нужно работать с контекстом вокруг конкретного элемента.

AddBefore и AddAfter — операции за O(1), потому что вы уже держите ссылку на нужный узел. Поиск через Find — O(n), но вставка — O(1). Это и есть главное преимущество связного списка: если вы уже знаете, куда вставлять — вставка мгновенная.

Типичные задачи, где связный список — правильный выбор: реализация дека (добавление/удаление с обоих концов), LRU-кеш (перемещение элементов к началу при обращении), планировщик задач с приоритетами, буфер ввода в текстовом редакторе. Во всех этих случаях операции на концах или в произвольном месте (при наличии узла) — O(1).

Связный список — структура из узлов, каждый из которых хранит значение и ссылку на следующий (в двусвязном — и на предыдущий). Элементы физически разбросаны по памяти.

Сильные стороны: вставка и удаление из начала — O(1). Не требует сдвига элементов. Размер не фиксирован.

Слабые стороны: доступ по индексу — O(n). Больше памяти на хранение ссылок. Плохая локальность данных — медленнее кеш процессора.

Односвязный — ссылка только вперёд. Двусвязный — ссылки вперёд и назад, O(1) вставка/удаление с обоих концов.

В C# — LinkedList<T> из System.Collections.Generic. Это двусвязный список с O(1) операциями на концах.