Каким образом вставлять новый узел в двухсвязный список? В односвязном списке для этого нужно было разорвать одну ссылку и вставить две новых, а для двухсвязного списка потребуется разорвать две ссылки и вставить четыре новых. Причем вставку можно выполнять как перед, так и после определенного элемента, поскольку указатель Prior позволяет проходить список в обратном направлении. Фактически операцию "вставить перед" можно запрограммировать как "перейти к предыдущему узлу и вставить после". Поэтому в главе мы рассмотрим только операцию "вставить после".

Ссылка Next нового узла устанавливается на узел, расположенный после заданного узла, а ссылка Next заданного узла устанавливается на новый узел. Для установки обратных ссылок ссылка Prior нового узла устанавливается на заданный узел, а ссылка Prior узла, следующего за новым, устанавливается на новый узел. В коде это выглядит следующим образом:

var
GivenNode, NewNode : PSimpleNode;
begin
• • •
New(NewNode);
.. задать значение поля Data.. NewNodeA. Next : = GivenNode A. Next;
GivenNode A. Next : = NewNode ; NewNodeA.Prior := GivenNode;
NewNodeA.NextA.Prior : = NewNode;

В случае с удалением проще всего удалить узел, находящийся после заданного узла. Необходимо установить ссылку Next заданного узла на узел, находящийся после удаляемого, а ссылку Prior узла, находящегося после удаляемого, на заданный узел.

Вставка нового узла в двухсвязный список

Рисунок 3.5. Вставка нового узла в двухсвязный список

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

var
GivenNode, NodeToGo : PSimpleNode;
begin
• • •
NodeToGo : = GivenNodeA. Next ; GivenNodeA.Next : = NodeToGoA.Next;
NodeToGoA.NextA.Prior : = GivenNode;
Dispose(NodeToGo);

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

Удаление узла в двухсвязном списке

Рисунок 3.6. Удаление узла в двухсвязном списке

Вставка: var FirstNode, NewNode : PSimpleNode; begin • • 9

New(NewNode) ;
.. задать значение поля Data.. NewNodeA. Next : = FirstNode;
NewNodeA.Prior : - nil;
FirstNodeA.Prior : = NewNode;
FirstNode := NewNode;

Удаление: var FirstNode, NodeToGo : PSimpleNode; begin • • •

NodeToGo := FirstNode;
FirstNode : = NodeToGoA.Next;
FirstNodeA.Prior : - nil;
Dispose(NodeToGo);

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


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



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

  • Сентябрь
    2019
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс