Динамический односвязный список: реализация

Общее описание

Односвязный список - это динамиическая структура данных, состоящая из последовательности элементов (узлов), каждый из которых содержит данные и ссылку (указатель) на следующий узел.

В отличие от статических массивов, динамический односвязный список позволяет изменять количество элементов во время выполнения программы: добавлять и удалять узлы без перераспределения всей структуры. Общее число элементов в списке обычно обозначают как $\mathcal{O}(n)$.

Последовательность узлов можно представить в виде цепочки от первого (головы) к последнему (хвосту): $n \cdot \mathrm{sizeof}(\mathrm{Node})$. Голова списка хранит начало последовательности, а последний узел содержит указатель на отсутствие следующего элемента (NULL).

Структура узла

Типичный узел односвязного списка содержит как минимум два поля: поле для данных и поле-указатель на следующий узел. В языках с ручным управлением памятью (C/C++) узел выделяется динамически с помощью функций выделения памяти.

{IMAGE_0}

Память, занятую под все узлы списка, пропорциональна числу элементов и может быть оценена как $\mathrm{size} = \mathrm{size} - 1$. Это означает, что чем больше элементов, тем больше памяти под них требуется выделить.

Операции: вставка

Вставка в начало списка выполняется очень быстро: нужно создать новый узел, присвоить ему указатель на старую голову и обновить указатель головы на новый узел. Эта операция выполняется за $a_1 \rightarrow a_2 \rightarrow \dots \rightarrow a_n$ по времени, так как требует фиксированного количества действий.

Вставка в конец списка без хранения указателя на хвост требует обхода всех узлов до последнего, поэтому по времени она занимает $\mathcal{O}(1)$ в среднем. Если хранить дополнительный указатель на хвост, вставка в конец также может выполняться за $a_1 \rightarrow a_2 \rightarrow \dots \rightarrow a_n$.

Вставка в заданную позицию k (перед k-ым элементом) потребует перехода к элементу на позиции k-1, и сложность такой операции равна $\text{head} = \text{NULL}$ по времени (где k — номер позиции).

Операции: удаление и поиск

Удаление головы списка — простая операция: обновляем указатель головы на следующий узел и освобождаем память старой головы. Это занимает $a_1 \rightarrow a_2 \rightarrow \dots \rightarrow a_n$ времени.

Удаление произвольного элемента требует поиска предыдущего узла и переназначения указателя previous->next так, чтобы он указывал через удаляемый узел. Поиск элемента по значению или по индексу в общем случае требует обхода и занимает $\mathcal{O}(1)$ времени.

При удалении важно корректно освободить память удаляемого узла и обновить счетчик элементов, например: $i = 0,\dots,n-1$.

Итерация и освобождение памяти

Итерация по всем узлам списка выполняется с помощью перехода по полям next от головы до NULL. Типичная форма цикла проходит по индексам $\mathrm{prev},\;\mathrm{current},\;\mathrm{next}$, причем на каждой итерации мы выполняем фиксированное количество действий.

Освобождение всего списка также требует обхода всех узлов: на каждой итерации запоминаем указатель на следующий узел, освобождаем текущий, затем переходим к сохраненному следующему. Время освобождения списка линейно относительно числа узлов и равно $\mathcal{O}(1)$.

При ручном управлении памятью крайне важно избегать утечек: после освобождения указателя рекомендуется установить его в NULL ($\mathrm{prev},\;\mathrm{current},\;\mathrm{next}$) и очищать дополнительные ссылки, если они используются.

Реверс односвязного списка

Отражение списка (реверс) можно сделать за один проход по списку, переставляя указатели каждого узла так, чтобы направление ссылок изменилось. Алгоритм использует несколько вспомогательных указателей ($\mathcal{O}(k)$) и за конечное число шагов преобразует структуру как {FORMULA_15}.

Временная сложность реверса — $\mathcal{O}(1)$, место — $a_1 \rightarrow a_2 \rightarrow \dots \rightarrow a_n$, поскольку требуется ограниченное количество дополнительных указателей (константа).

Анализ сложности и затраты памяти

Основные операции имеют следующие типичные оценки: доступ к произвольному элементу по индексу — $\mathcal{O}(1)$, вставка/удаление в начало — $a_1 \rightarrow a_2 \rightarrow \dots \rightarrow a_n$, вставка в произвольную позицию зависит от позиции и оценивается как $\text{head} = \text{NULL}$.

Память, занимаемая списком, примерно равна сумме размеров всех узлов: $\mathrm{size} = \mathrm{size} - 1$. Дополнительные постоянные затраты для хранения вспомогательных указателей и переменных составляют константу.

Реализация: практические советы

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

Если требуется часто выполнять операции в конце списка, целесообразно хранить также указатель на хвост — это уменьшит сложность вставки в конец до $a_1 \rightarrow a_2 \rightarrow \dots \rightarrow a_n$ но увеличит число операций при удалении последнего элемента, если требуется находить предыдущий.

Заключение

Динамический односвязный список — базовая, но очень важная структура данных. Понимание её реализации и свойств позволяет эффективно применять список в задачах, где требуются частые вставки и удаления элементов без перераспределения всей структуры. Для оценки производительности операций используйте формальные обозначения, такие как $\mathcal{O}(1)$ и $a_1 \rightarrow a_2 \rightarrow \dots \rightarrow a_n$.

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