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

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

По своей сути связный список (linked list) представляет собой цепочку элементов или объектов с некоторыми описаниями (обычно называемых узлами). При этом каждый элемент содержит указатель, указывающий на следующий элемент в списке. Такая структура данных называется односвязным списком (singly linked list) - каждый элемент имеет только одну ссылку или указатель на следующий элемент. Сам список начинается с первого узла, от которого путем последовательных переходов по ссылкам можно обойти все остальные узлы. Обратите внимание, что определение связного списка отличается от определения массива, для которого следующий элемент находится в памяти рядом с предыдущим. В связном списке элементы могут быть разбросаны по разным местам памяти, а их порядок определяется ссылками.

Рисунок 3.1. Односвязный список

А каким образом помечается конец списка? Самый простой способ - установить указатель ссылки в последнем элементе списка равным nil. Это будет означать, что следующий элемент отсутствует. Второй способ - ввести специальный узел, называемый конечным узлом, и установить так, чтобы ссылка последнего узла указывала на этот узел. И третий способ - установить так, чтобы ссылка последнего узла указывала на первый элемент. В этом случае мы получим круговой связный список.

А теперь рассмотрим, чем же связный список отличается от массива. Первое, что нужно отметить, - размер связного списка можно не устанавливать. Для массива нам всегда было нужно заранее знать, сколько элементов будет в нем храниться (чтобы можно было статически распределить непрерывный участок памяти) или разработать некоторую схему расширения массива (или его сокращения), чтобы массив мог разместить большее (или меньшее) количество элементов. В связном списке каждый узел является отдельным элементом. И в простых случаях распределение памяти под каждый узел выполняется отдельно. При необходимости добавления в список нового элемента под него распределяется память, а затем элемент просто на него устанавливается ссылка из списка. При удалении узла нужно всего лишь удалить ссылки на него и освободить занимаемую им память.

Хорошо. Если связный список настолько удобен, почему бы его не использовать вместо массива? В чем состоят его недостатки? Первый, хотя и незначительный, состоит в том, что каждый элемент связного списка должен содержать указатель на следующий элемент. Таким образом, чтобы вставить элемент в список, его реальный размер необходимо увеличить на размер указателя (в настоящее время это 4 байта).

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

Самым большим недостатком связного списка является получение доступа к некоторому элементу n. В массиве доступ к n-ному элементу требует проведения простых арифметических вычислений, поскольку все элементы содержатся в одном непрерывном блоке памяти. С другой стороны, в списке получение доступа к элементу n требует прохождения по ссылкам от первого элемента до n-ного. Другого метода доступа не существует, мы всегда должны следовать по ссылкам. (Обратите внимание, что можно применить определенные хитрости, например, хранить элемент и его позицию в рамках списка в кэш-памяти. В таком случае можно определять целесообразность начала прохождения списка с его первого элемента или с элемента, хранящегося в кэш-памяти.)

Узлы связного списка

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

type

PSimpleNode = ^TSimpleNode;

TSimpleNode = record

Next : PSimpleNode;

Data : SomeDataType;

end;

Тип PSimpleNode представляет собой указатель на запись TSimpleNode, поле Next которой содержит ссылку на точно такой же узел, а поле Data - сами данные. В приведенном примере тип данных узла задан как SomeDataType. Для перехода по ссылке нужно написать примерно следующий код:

var

NextNode, CurrentNode : PSimpleNode;

begin

• • •

NextNode := CurrentNode^.Next;