Модуль 21 ⏱ ~19 мин чтения 📐 3 Mermaid диаграмм

1. Теория. Связные списки

«Указатель — это мост между абстрактной мыслью и физической ячейкой памяти. Но горе тому строителю, чей мост ведет в никуда».
— Брайан Керниган

Динамическая топология памяти

До сих пор мы исследовали массивы, слайсы и кольцевые буферы — структуры данных, где элементы лежат в физической памяти строго непрерывным блоком. Это идеальный сценарий для аппаратного обеспечения CPU, однако он накладывает жесткое ограничение: вставка или удаление в середину непрерывного блока требует сдвига всех последующих элементов за $O(N)$, а расширение емкости вынуждает аллокатор выделять новый блок и копировать старые данные (runtime.growslice).

В системном дизайне часто требуются структуры, способные динамически расти, менять форму, мгновенно разрываться и склеиваться за строгое $O(1)$ без единого перемещения байтов в памяти.

Здесь на сцену выходят Связные списки (Linked Lists). На собеседованиях задачи на связные списки — это главная лакмусовая бумажка: они мгновенно показывают, насколько свободно кандидат управляет указателями, держит в голове динамические топологии памяти и предотвращает разрывы цепочек ссылок.

Анатомия Связного Списка

Односвязный список (Singly Linked List) — это линейная последовательность узлов (Nodes), где каждый узел хранит полезную нагрузку (Payload) и указатель на следующий узел в памяти.

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

flowchart LR
    classDef entry   fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef accent  fill:#1e1b4b,stroke:#818cf8,stroke-width:1px,color:#f8fafc
    classDef aux     fill:#334155,stroke:#64748b,stroke-width:1px,color:#f8fafc

    Head["Голова (Head)<br>Адрес: 0x1040<br>Val: 10"]:::entry -->|"Next"| Node2["Узел 2<br>Адрес: 0x8020<br>Val: 20"]:::process
    Node2 -->|"Next"| Node3["Узел 3<br>Адрес: 0x2400<br>Val: 30"]:::accent
    Node3 -->|"Next"| Nil["nil (Конец списка)"]:::aux

Каноническая структура в Go

В языке Go представление узла списка для алгоритмических задач и прикладных систем выглядит лаконично:

Go 
package list

// ListNode представляет узел односвязного списка.
type ListNode struct {
    Val  int
    Next *ListNode
}

Mechanical Sympathy: Почему списки — тяжелое испытание для CPU

На собеседовании уровня Senior популярен вопрос на понимание физики «железа»:
«Что выполнит последовательный обход миллиона элементов быстрее: []int или связный список *ListNode?»

Неопытный кандидат ответит: «Одинаково, сложность $O(N)$ в обоих случаях».
Senior-инженер ответит: «Слайс будет быстрее в десятки, а на некоторых процессорах — в сотни раз».

Почему абстрактная сложность $O(N)$ скрывает колоссальную разницу в физических миллисекундах?

flowchart TD
    classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef error   fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc

    subgraph SliceMemory["Память слайса: Непрерывный массив"]
        S1["[0] 8B"]:::success --- S2["[1] 8B"]:::success --- S3["[2] 8B"]:::success --- S4["[3] 8B"]:::success
    end

    subgraph ListMemory["Память списка: Разрозненные аллокации в куче"]
        L1["Узел 0x1040"]:::process -.->|"Cache Miss (100-200 тактов)"| L2["Узел 0x9080"]:::error
        L2 -.->|"Cache Miss (100-200 тактов)"| L3["Узел 0x3010"]:::error
    end
  1. Локальность данных и строки кэша (L1/L2 Cache Lines):
    Современные процессоры не читают оперативную память по 8 байт. Минимальная единица обмена между RAM и кэшем ядра CPU — кэш-линия размером 64 байта.
    Когда вы читаете первый элемент слайса nums[0], контроллер памяти автоматически подтягивает следующие 7 чисел типа int64 в L1d-кэш. Аппаратный Prefetcher распознает линейный шаг и непрерывно закачивает следующие килобайты на опережение.
    В связном списке каждый узел живет по случайному адресу кучи. Переход по указателю curr = curr.Next с вероятностью почти 100% вызывает промах кэша (Cache Miss). Процессор вынужден простаивать (CPU Pipeline Stall) 100–250 тактов, дожидаясь доставки байтов из медленной шины памяти.
  2. Накладные расходы по памяти (Memory Overhead):
    В []int одно число занимает ровно 8 байт. В ListNode мы храним Val (8 байт) + указатель Next (8 байт) = 16 байт на полезное значение (ровно в 2 раза больше).
  3. Нагрузка на сборщик мусора (GC Pressure):
    Слайс на 1 000 000 чисел — это ровно один объект в куче.
    Связный список на 1 000 000 узлов — это 1 000 000 отдельных объектов. Аллокатор Go тратит время на поиск свободных слотов в размерных классах mcache/mcentral, а фаза разметки сборщика мусора вынуждена обходить миллион указателей.

Фундаментальный паттерн: Dummy Node (Фиктивный узел)

Если в алгоритмах на связные списки и существует один паттерн, спасающий от 90% багов и nil pointer dereference, то это Dummy Node (Sentinel Node).

При удалении или перестановке узлов самая уязвимая точка — первый элемент (Голова / Head). Если удаляется голова, меняется точка входа в список. Без фиктивного узла код обрастает множеством ветвлений if head == nil, if prev == nil.

Dummy Node — это фиктивная структура, которую мы размещаем перед реальной головой списка. Она гарантирует, что у настоящей головы всегда есть предыдущий элемент.

flowchart LR
    classDef dummy   fill:#78350f,stroke:#fbbf24,stroke-width:2px,color:#f8fafc
    classDef head    fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc

    Dummy["Dummy Node<br>(Фиктивный узел)"]:::dummy -->|"Next"| Head["Head<br>(Реальная голова)"]:::head
    Head -->|"Next"| Node2["Узел 2"]:::process
    Node2 -->|"Next"| Node3["Узел 3"]:::process

Идиоматичный пример: Удаление элементов по значению

Go 
package list

// removeElements удаляет все узлы со значением targetVal.
func removeElements(head *ListNode, targetVal int) *ListNode {
    // 1. Создаем фиктивный узел, указывающий на реальную голову.
    // Escape Analysis разместит dummy на стеке, так как сам dummy наружу не возвращается!
    dummy := &ListNode{Next: head}

    // 2. Инициализируем указатель обхода
    curr := dummy

    // 3. Пока существует следующий узел
    for curr.Next != nil {
        if curr.Next.Val == targetVal {
            // Перенаправляем стрелку в обход удаляемого узла.
            // Сборщик мусора Go сам освободит отсеченный узел!
            curr.Next = curr.Next.Next
        } else {
            curr = curr.Next
        }
    }

    // 4. Возвращаем настоящую новую голову (все, что за dummy)
    return dummy.Next
}

Благодаря dummy случай удаления реальной головы ничем не отличается от удаления узла из середины списка. Никаких специальных проверок if head.Val == targetVal не требуется!

Золотые правила работы с указателями

При манипуляциях со списками разработчик обязан соблюдать строгую дисциплину:

Итог

Связные списки переносят нас в мир явных топологических графов и ссылочных моделей памяти. Понимание устройства указателей и паттерна Dummy Node закладывает фундамент для проектирования деревьев, графов и lock-free очередей.

Освоив базовую механику, перейдем к главному алгоритмическому приему в списках, позволяющему за один проход находить середины, определять циклы и пересечения: 2. Быстрый и медленный указатели.