Хуже то, что память под каждый узел распределяется отдельно. Сравним эту ситуацию с аналогичной ситуацией для массива. Распределение памяти под 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;
Это тривиальная задача. В самом простом случае первый узел в связном списке описывает весь список. Первый узел иногда называют головой списка.
var
MyLinkedList : PSimpleNode;
Если MyLinkedList содержит nil, списка еще нет. Таким образом, это начальное значение связного списка.
{инициализация связного списка}
MyLinkedList := nil;
А каким образом можно вставить новый элемент в связный список? Или удалить? Оказывается, что для выполнения этих операций требуется выполнить небольшую работу с указателями.
Для односвязного списка существует только один вариант вставки - после заданного элемента списка. Нужно установить так, чтобы указатель Next нашего нового узла указывал на узел после заданного, а указатель Next заданного узла - на наш новый узел. В коде это выглядит следующим образом:
var
GivenNode, NewNode : PSimpleNode;
begin
• • •
New(NewNode);
.. задать значение поля Data..
NewNode^.Next := GivenNode^.Next;
GivenNode^.Next := NewNode;
Рисунок 3.2. Вставка нового узла в односвязный список
Аналогично, для удаления простейшим вариантом является удаление элемента, находящегося после заданного узла. В этом случае мы устанавливаем, чтобы указатель Next заданного узла указывал на узел, расположенный после удаляемого. После этого удаляемый узел уже выделен из списка и может быть освобожден. В коде это выглядит следующим образом:
var
GivenNode, NodeToGo : PSimpleNode;
begin
• • •
NodeToGo := GivenNode^.Next;
GivenNode^.Next := NodeToGo^.Next;
Dispose(NodeToGo);
Рисунок 3.3. Удаление узла из односвязного списка
Тем не менее, для обеих операций существует специальный случай: вставка перед первым элементом списка (т.е. новый элемент становиться первым) и удаление первого элемента списка (т.е. первым становится другой элемент). Поскольку в наших рассуждениях первый элемент считается определяющим узлом всего списка, код для этих случаев нужно написать отдельно. Вставка перед первым узлом будет выглядеть следующим образом:
var
GivenNode, NewNode : PSimpleNode;
begin
• • •
New(NewNode);
.. задать значение поля Data..
NewNode^.Next := MyLinkedList;
MyLinkedList := NewNode;
а удаление будет выглядеть так:
var
GivenNode, NodeToGo : PSimpleNode;
begin
• • •
NodeToGo := GivenNode^.Next;
MyLinkedList := NodeToGo^.Next;
Dispose(NodeToGo);
Обратите внимание, что код вставки элемента будет работать даже в случае, когда исходный список пуст, т.е. содержит nil, а код удаления элемента правильно установит содержимое связного списка в случае удаления из него последнего узла.
