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

Рисунок 3.4. Двухсвязный список

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

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

var

GivenNode, NewNode : PSimpleNode;

begin

• • •

New(NewNode);

.. задать значение поля Data ..

NewNode^.Next := GivenNode^.Next;

GivenNode^.Next := NewNode;

NewNode^.Prior := GivenNode;

NewNode^.Next^.Prior := NewNode;

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

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

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

var

GivenNode, NodeToGo : PSimpleNode;

begin

• • •

NodeToGo := GivenNode^.Next;

GivenNode^.Next := NodeToGo^.Next;

NodeToGo^.Next^.Prior := GivenNode;

Dispose(NodeToGo);

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

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

Вставка:

var

FirstNode, NewNode : PSimpleNode;

begin

• • •

New(NewNode);

.. задать значение поля Data..

NewNode^.Next := FirstNode;

NewNode^.Prior := nil;

FirstNode^.Prior := NewNode;

FirstNode := NewNode;

Удаление:

var

FirstNode, NodeToGo : PSimpleNode;

begin

• • •

NodeToGo := FirstNode;

FirstNode := NodeToGo^.Next;

FirstNode^.Prior := nil;

Dispose(NodeToGo);

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

Как и для односвязного списка, данные в списке удобно хранить в виде указателей. Это позволяет написать общий класс двухсвязного списка. В двухсвязном списке в каждом узле будет находиться прямой указатель, обратный указатель и указатель на данные. Общий размер узла составит 12 байт (т.е. 3*sizeof(pointer)). Все узлы одинаковы, таким образом, можно реализовать диспетчер узлов и для двухсвязного списка.

Интерфейс класса двухсвязного списка выглядит следующим образом:

Листинг 3.13. Класс TtdDoubleLinkList

TtdDoubleLinkList = class private

FCount : longint;

FCursor : PdlNode;

FCursorIx: longint;

FDispose : TtdDisposeProc;

FHead : PdlNode;

FName : TtdNameString;

FTail : PdlNode;

protected

function dllGetItem(aIndex : longint): pointer;

procedure dllSetItem(aIndex : longint; aItem : pointer);

procedure dllError(aErrorCode : integer;

const aMethodName : TtdNameString);

class procedure dllGetNodeManager;

procedure dllPositionAtNth(aIndex : longint);

public

constructor Create(aDispose : TtdDisposeProc);

destructor Destroy; override;

function Add(aItem : pointer): longint;

procedure Clear;

procedure Delete(aIndex : longint);

procedure DeleteAtCursor;

function Examine : pointer;

function First : pointer;

function IndexOf(aItem : pointer): longint;

procedure Insert(aIndex : longint; aItem : pointer);

procedure InsertAtCursor(aItem : pointer);

function IsAfterLast : boolean;

function IsBeforeFirst : boolean;

function IsEmpty : boolean;

function Last : pointer;

procedure MoveAfterLast;

procedure MoveBeforeFirst;

procedure MoveNext;

procedure MovePrior;

procedure Remove(aItem : pointer);

procedure Sort(aCompare : TtdCompareFunc);

property Count : longint read FCount;

property Items[aIndex : longint] : pointer

read dllGetItem write dllSetItem; default;

property Name : TtdNameString read FName write FName;

end;

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

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

Конструктор Create распределяет при помощи диспетчера узлов еще один дополнительный фиктивный узел - FTail. Как упоминалось во введении к двухсвязным спискам, он предназначен для обозначения конца списка. Начальный и конечный фиктивные узлы вначале будут связаны друг с другом, т.е. ссылка Next начального узла указывает на конечный узел, а ссылка Prior конечного узла - на начальный узел. Естественно, деструктор Destroy будет удалять фиктивный конечный узел и возвращать его вместе с начальным узлов в диспетчер узлов.

Листинг 3.14. Конструктор Create и деструктор Destroy класса TtdDoubleLinkList

constructor TtdDoubleLinkList.Create;

begin

inherited Create;

{сохранить процедуру удаления}

FDispose :=aDispose;

{получить диспетчер узлов}

dllGetNodeManager;

{распределить и связать начальный и конечный узлы}

FHead := PdlNode (DLNodeManager.AllocNode);

FTail := PdlNode (DLNodeManager.AllocNode);