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);
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;
