begin
{переместить курсор по его прямому указателю}
if (FCursor <> FTail) then begin
FCursor := FCursor^.dlnNext;
inc(FCursorIx);
end;
end;
procedure TtdDoubleLinkList.MovePrior;
begin
{переместить курсор по его обратному указателю}
if (FCursor <> FHead) then begin
FCursor := FCursor^.dlnPrior;
dec(FCursorIx);
end;
end;
Если сравнить приведенный код с его эквивалентом для односвязных списков (листинг 3.9), можно понять, каким образом дополнительные обратные связи влияют на реализацию методов. С одной стороны, методы стали немного проще. Так, например, в случае двухсвязных списков для метода MoveNext не нужно вводить переменную FParent. С другой стороны, требуется дополнительный код для обработки обратных ссылок. Примером могут служить методы InsertAtCursor и DeleteAtCursor.
Методы, основанные на использовании индекса, в случае двухсвязного списка реализуются проще, чем в случае односвязного. Единственную сложность представляет метод dllPositionAtNth, предназначенный для установки курсора в позицию с заданным индексом. Вспомните алгоритм для односвязного списка: если заданный индекс соответствует позиции после курсора, начать с позиции курсора и идти вперед, вычисляя индекс. В двухсвязном списке при необходимости можно двигаться и в обратном направлении. Таким образом, алгоритм поиска можно немного изменить. Как и ранее, мы определяем, где по отношению к курсору находится узел с заданным индексом. После этого выполняется еще одно вычисление -ближе к какому узлу находится узел с заданным индексом: к начальному, конечному или к текущему? Далее мы начинаем прохождение с ближайшего узла, при необходимости двигаясь вперед или назад.
Листинг 3.16. Установка курсора на узел с индексом n для класса TtdDoubleLinkList
procedure TtdDoubleLinkList.dllPositionAtNth(aIndex : longint);
var
WorkCursor : PdlNode;
WorkCursorIx : longint;
begin
{проверить, корректно ли задан индекс}
if (aIndex < 0) or (aIndex >= Count) then
dllError(tdeListInvalidIndex, 'dllPositionAtNth');
{для увеличения быстродействия используются локальные переменные}
WorkCursor := FCursor;
WorkCursorIx := FCursorIx;
{обработать наиболее простой случай}
if (aIndex = WorkCursorIx) then
Exit;
{заданный индекс либо перед курсором, либо после него; в любом случае, заданный индекс ближе либо к курсору, либо к соответствующему концу списка; определить самый короткий путь}
if (aIndex < WorkCursorIx) then begin
if ((aIndex - 0) < (WorkCursorIx - aIndex)) then begin
{начать с начального узла и двигаться вперед до индекса aIndex}
WorkCursor := FHead;
WorkCursorIx := -1;
end;
end
else {aIndex > FCursorIx}
begin
if ((aIndex - WorkCursorIx) < (Count - aIndex)) then begin
{начать с конечного узла и двигаться назад до индекса aIndex}
WorkCursor :=FTail;
WorkCursorIx := Count;
end;
end;
{пока индекс рабочего курсора меньше заданного индекса, перемещать рабочий курсор на одну позицию вперед}
while (WorkCursorIx < aIndex) do
begin
WorkCursor := WorkCursor^.dlnNext;
inc(WorkCursorIx);
end;
{пока индекс рабочего курсора больше заданного индекса, перемещать рабочий курсор на одну позицию назад}
while (WorkCursorIx > aIndex) do
begin
WorkCursor := WorkCursor^.dlnPrior;
dec(WorkCursorIx);
end;
{установить реальный курсор равным рабочему курсору}
FCursor := WorkCursor;
FCursorIx := WorkCursorIx;
end;
Теперь, когда мы умеем находить узел по заданному индексу, можно перейти к реализации остальных методов: все они очень похожи на соответствующие методы для односвязных списков.
Листинг 3.17. Методы класса TtdDoubleLinkList, основанные на использовании индекса
function TtdDoubleLinkList.Add(aItem : pointer): longint;
begin
{перейти к концу связного списка}
FCursor := FTail.FCursorIx := Count;
{вернуть индекс нового узла}
Result Count;
{вставить элемент в позицию курсора}
InsertAtCursor(aItem);
end;
procedure TtdDoubleLinkList.Delete(aIndex : longint);
begin
{установить курсор в позицию с заданным индексом}
dllPositionAtNth(aIndex);
{удалить элемент в позиции курсора}
DeleteAtCursor;
end;
function TtdDoubleLinkList.dllGetItem(aIndex : longint): pointer;
begin
{установить курсор в позицию с заданным индексом}
dllPositionAtNth(aIndex);
{вернуть данные из позиции курсора}
Result := FCursor^.dlnData;
end;
procedure TtdDoubleLinkList.dllSetItem(aIndex : longint;
aItem : pointer);
begin
{установить курсор в позицию с заданным индексом}
dllPositionAtNth(aIndex);
{если возможно удалить заменяемые данные, удалить их}
if Assigned(FDispose) and (aItem <> FCursor^.dlnData) then
FDispose(FCursor^.dlnData);
{заменить данные}
FCursor^.dlnData := aItem;
end;
function TtdDoubleLinkList.First : pointer;
begin
{установить курсор на первый узел}
dllPositionAtNth(0);
{вернуть данные из позиции курсора}
Result := FCursor^.dlnData;
end;
function TtdDoubleLinkList.IndexOf(aItem : pointer): longint;
var
WorkCursor : PdlNode;
WorkCursorIx : longint;
begin
{установить рабочий курсор на первый узел (если он существует)}
WorkCursor := FHead^.dlnNext;
WorkCursorIx := 0;
{идти по списку в поисках требуемого элемента}
while (WorkCursor <> FTail) do
begin
if (WorkCursor^.dlnData = aItem) then begin
