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

Как видите, этот интерфейс очень похож на интерфейс класса 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);

FHead^.dlnNext := FTail;

FHead^.dlnPrior :=nil;

FHead^.dlnData := nil;

FTail^.dlnNext := nil;

FTail^.dlnPrior := FHead;

FTail^.dlnData := nil;

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

FCursor := FHead;

FCursorIx := -1;

end;

destructor TtdDoiibleLinkList.Destroy;

begin

if (Count <> 0) then

Clear;

DLNodeManager.FreeNode (FHead);

DLNodeManager.FreeNode(FTail);

inherited Destroy;

end;

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

Листинг 3.15. Стандартные для связного списка операции для класса TtdDoubleLinkList

procedure TtdDoubleLinkList.Clear;

var

Temp : PdlNode;

begin

{удалить все узлы, за исключением начального и конечного; если возможно их освободить, то сделать это}

Temp := FHead^.dlnNext;

while (Temp <> FTail) do

begin

FHead^.dlnNext := Temp^.dlnNext;

if Assigned(FDispose) then

FDispose(Temp^.dlnData);

DLNodeManager.FreeNode(Temp);

Temp := FHead^.dlnNext;

end;

{устранить "дыру" в связном списке}

FTail^.dlnPrior := FHead;

FCount := 0;

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

FCursor := FHead;

FCursorIx := -1;

end;

procedure TtdDoubleLinkList.DeleteAtCursor;

var

Temp : PdlNode;

begin

{записать в Temp удаляемый узел}

Temp := FCursor;

if (Temp = FHead) or (Temp = FTail) then

dllError(tdeListCannotDelete, 'Delete');

{избавиться от его содержимого}

if Assigned(FDispose) then

FDispose(Temp^.dlnData);

{удалить ссылки на узел и освободить его; курсор перемещается на следующий узел}

Temp^.dlnPrior^.dlnNext := Temp^.dlnNext;

Temp^.dlnNext^.dlnPrior := Temp^.dlnPrior;

FCursor := Temp^.dlnNext;

DLNodeManager.FreeNode(Temp);

dec(FCount);

end;

function TtdDoubleLinkList.Examine : pointer;

begin

if (FCurgor = nil) or (FCursor = FHead) then

dllError(tdeListCannotExamine, 'Examine');

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

Result := FCursor^.dlnData;

end;

procedure TtdDoubleLinkList.InsertAtCursor(aItem : pointer);

var

NewNode : PdlNode;

begin

{если курсор находится на начальном узле, не генерировать исключение, а перейти на следующий узел}

if (FCursor = FHead) then

MoveNext;

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

NewNode := PdlNode (DLNodeManager.AllocNode);

NewNode^.dlnData := aItem;

NewNode^.dlnNext := FCursor;

NewNode^.dlnPrior := FCursor^.dlnPrior;

NewNode^.dlnPrior^.dlnNext := NewNode;

FCursor^.dlnPrior := NewNode;

FCursor := NewNode;

inc(FCount);

end;

function TtdDoubleLinkList.IsAfterLast : boolean;

begin

Result := FCursor = FTail;

end;

function TtdDoubleLinkList.IsBeforeFirst;

boolean;

begin

Result := FCursor = FHead;

end;

function TtdDoubleLinkList.IsEmpty : boolean;

begin

Result := (Count = 0);

end;

procedure TtdDoubleLinkList.MoveAfterLast;

begin

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

FCursor := FTail;

FCursorIx := Count;

end;

procedure TtdDoubleLinkList.MoveBeforeFirst;

begin

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

FCursor := FHead;

FCursorIx := -1;

end;

procedure TtdDoubleLinkList.MoveNext;