Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi

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

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, а код удаления элемента правильно установит содержимое связного списка в случае удаления из него последнего узла.

Прохождение связного списка также не представляет никаких трудностей. Фактически мы переходим от узла к узлу по указателям Next до достижения указателя nil, который свидетельствует об окончании списка.

var

FirstNode, TempNode : PSimpleNode;

begin

• • •

TempNode := FirstNode;

while TempNode <> nil do

begin

Process(TempNode^.Data);

TempNode := TempNode^.Next;

end;

В этом простом цикле процедура Process (определенная в другом месте) выполняет обработку поля Data переданного ей узла. Очистка связного списка требует небольшого изменения алгоритма, чтобы гарантировать, что мы не ссылаемся на поле Next после освобождения узла (довольно-таки частая ошибка).

var

MyLinkedList, TempNode, NodeToGo : PSimpleNode;

begin

NodeToGo := MyLinkedList;

while NodeToGo <> nil do

begin

TempNode := NodeToGo^.Next;

Dispose(NodeToGo);

NodeToGo := TempNode;

end;

MyLinkedList :=nil;

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

var

FirstNode, GivenNode, TempNode,

ParentNode : PSimpleNode;

begin

ParentNode := nil;

TempNode := FirstNode;

while TempNode <> GivenNode do

begin

ParentNode := TempNode;

TempNode := ParentNode^.Next;

end;

if TempNode = GivenNode then begin

if (ParentNode = nil) then begin

NewNode^.Next := FirstNode;

FirstNode := NewNode;

end

else begin

NewNode^.Next := ParentNode^.Next;

ParentNode^.Next := NewNode;

end;

end;

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

Если бы это было все, что можно сказать о связных списках, то глава оказалась бы очень короткой. До сих пор была представлена только реализация класса, инкапсулирующего односвязный список. Но перед написанием класса связного списка нужно рассмотреть еще несколько вопросов, касающихся, в частности, эффективности.

Еще раз просмотрите код вставки и удаления элемента связного списка. Не кажется ли вам неудобным наличие двух случаев для обеих операций? Отдельные специальные случаи нужны для обработки вставки и удаления первого узла - операция, которая, возможно, будет выполняться не очень часто. Может быть, существует другой способ? Другой способ действительно есть, он предусматривает использование фиктивного начального узла. Фиктивный начальный узел - это узел, который нужен только в качестве заполнителя, в нем не будут храниться данные. Первым реальным узлом будет тот, на который указывает указатель Next фиктивного узла. Связный список, как и раньше, заканчивается узлом, указатель Next которого равен nil. При создании такого списка его нужно правильно инициализировать, выделив память под начальный узел и установив его указатель Next равным nil.