Все методы класса односвязного списка можно разбить на две категории: методы, действующие по последовательной схеме (MoveBeforeFirst, InsertAtCursor и т.д.), и методы, которые работают со списком как с массивом (свойство Items, методы Delete, IndexOf и т.д.). Рассмотрим сначала методы первой группы, поскольку мы уже говорили о принципе их работы в начале главы при описании связных списков. Для упрощения реализации мы не только храним курсор (т.е. указатель на текущий узел) в объекте, но и родительский объект курсора (т.е. указатель на родительский объект текущего курсора). Такая схема позволяет упростить методы вставки и удаления элементов.
Листинг 3.9. Стандартные операции со связным списком для класса TtdSingleLinkList
procedure TtdSingleLinkList.Clear;
var
Temp : PslNode;
begin
{удалить все узлы, за исключением начального; при возможности освободить все данные}
Temp := FHead^.slnNext;
while (Temp <> nil) do
begin
FHead^.slnNext := Temp^.slnNext;
if Assigned(FDispose) then
FDispose(Temp^.slnData);
SLNodeManager.FreeNode(Temp);
Temp := FHead^.slnNext;
end;
FCount := 0;
MoveBeforeFirst;
end;
procedure TtdSingleLinkList.DeleteAtCursor;
begin
if (FCursor = nil) or (FCursor = FHead) then
sllError(tdeListCannotDelete, 'Delete');
{удалить все элементы}
if Assigned(FDispose) then
FDispose(FCursor^.slnData);
{удалить ссылки на узел и удалить сам узел}
FParent^.slnNext := FCursor^.slnNext;
SLNodeManager.FreeNode(FCursor);
FCursor := FParent^.slnNext;
dec(FCount);
end;
function TtdSingleLinkList.Examine : pointer;
begin
if (FCursor = nil) or (FCursor = FHead) then
sllError(tdeListCannotExamine, 'Examine');
{вернуть данные с позиции курсора}
Result := FCursor^.slnData;
end;
procedure TtdSingleLinkList.InsertAtCursor(aItem : pointer);
var
NewNode : PslNode;
begin
{убедиться, что вставка производится не перед первой позицией; если курсор находится перед первой позицией, переместить его на одну позицию вперед}
if (FCursor = FHead) then
MoveNext;
{распределить новый узел и вставить его в позицию курсора}
NewNode := PslNode (SLNodeManager.AllocNode);
NewNode^.slnData := aItem;
NewNode^.slnNext := FCursor;
FParent^.slnNext := NewNode;
FCursor := NewNode;
inc(FCount);
end;
function TtdSingleLinkList.IsAfterLast : boolean;
begin
Result := FCursor;
nil;
end;
function TtdSingleLinkList.IsBeforeFirst : boolean;
begin
Result := FCursor = FHead;
end;
function TtdSingleLinkList.IsEmpty : boolean;
begin
Result := (Count = 0);
end;
procedure TtdSingleLinkList.MoveBeforeFirst;
begin
{установить курсор на начальный узел}
FCursor := FHead;
FParent := nil;
FCursorIx := -1;
end;
procedure TtdSingleLinkList.MoveNext;
begin
{переместить курсор по его указателю Next, игнорировать попытку выхода за конечный узел списка}
if (FCursor <> nil) then begin
FParent := FCursor;
FCursor := FCursor^.slnNext;
inc(FCursorIx);
end;
end;
Вы, возможно, обратили внимание, что некоторые из приведенных методов пользуются полем объекта FCursorIx. Именно это поле позволяет обеспечить высокую эффективность методов, основанных на использовании индекса, поскольку в нем хранится индекс курсора (при этом первый узел имеет индекс 0, точно так же как в TList). Значение поля используется методом ellPositionAtNth, который оптимальным образом перемещает курсор в позицию с указанным индексом.
Листинг 3.10. Метод sllPositionAtNth
procedure TtdSingleLinkList.sllPositionAtNth(aIndex : longint);
var
WorkCursor : PslNode;
WorkParent : PslNode;
WorkCursorIx : longint;
begin
{проверить, корректно ли задан индекс}
if (aIndex < 0) or (aIndex >= Count) then
sllError(tdeListInvalidIndex, 'sllPositionAtNth');
{обработать наиболее простой случай}
if (aIndex = FCursorIx) then
Exit;
{—для повышения быстродействия использовать локальные переменные—}
{если заданный индекс меньше индекса курсора, переместить рабочий курсор в позицию перед всеми узлами}
if (aIndex < FCursorIx) then begin
WorkCursor := FHead;
WorkParent :=nil;
WorkCursorIx := -1;
end
{в противном случае поставить рабочий курсор в позицию текущего курсора}
else begin
WorkCursor :=FCursor;
WorkParent := FParent;
WorkCursorIx := FCursorIx;
end;
{пока индекс рабочего курсора меньше заданного индекса, передвинуть его на одну позицию вперед}
while (WorkCursorIx < aIndex) do
begin
WorkParent := WorkCursor;
WorkCursor := WorkCursor^.slnNext;
inc(WorkCursorIx);
end;
{установить реальный курсор равным рабочему курсору}
FCursor := WorkCursor;
FParent := WorkParent;
FCursorIx := WorkCursorIx;
end;
Метод sllPositionAtNth для увеличения быстродействия использует локальные переменные. Вначале метод определяет, больше ли заданный индекс индекса курсора (в этом случае поиск узла начинается с позиции курсора) или же он меньше (поиск узла начинается с начала списка). Без знания позиции курсора мы всегда бы начинали поиск с начала списка.
Реализация остальных методов, основанных на использовании индекса, после написания кода метода sllPositionAtNth не представляет особых трудностей.
Листинг 3.11. Методы класса TtdSingleLinkList, основанные на использовании индекса
procedure TtdSingleLinkList.Delete(aIndex : longint);
begin
