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). Код для вставки перед заданным узлом медленнее кода вставки после заданного узла, поскольку он требует прохождения списка с целью обнаружения родительского узла заданного узла. В общем случае, при необходимости вставки нового узла перед заданным мы будет использовать двухсвязный список, который будет подробно рассмотрен немного ниже.
Соображения по поводу эффективности
Если бы это было все, что можно сказать о связных списках, то глава оказалась бы очень короткой. До сих пор была представлена только реализация класса, инкапсулирующего односвязный список. Но перед написанием класса связного списка нужно рассмотреть еще несколько вопросов, касающихся, в частности, эффективности.
