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



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

  • Июнь
    2020
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31