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

var
FirstNode, TempNode : PSimpleNode;
begin
• • •
TempNode := FirstNode;
while TempNode <>
nil do begin
Process(TempNodeA.Data);
TempNode : = TempNodeA.Next;
end;

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

var
MyLinkedList, TempNode, NodeToGo : PSimpleNode;
begin
NodeToGo := MyLinkedList;
while NodeToGo <>
nil do begin
TempNode : = NodeToGoA. 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 ;= ParentNodeA.Next;
end;
if TempNode = GivenNode then begin if (ParentNode = nil) then begin
NewNodeA. Next : = FirstNode;
FirstNode := NewNode;
end
else begin
NewNodeA.Next : = ParentNodeЛ.Next;
ParentNodeA.Next : = NewNode;
end;
end;

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

Вставка и удаление элементов в односвязном списке || Оглавление || Соображения по поводу эффективности


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



Новости за месяц

  • Июнь
    2019
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс