{задать прямые и обратные указатели для начального и конечного узлов}
for i := 0 to pred(tdcMaxSkipLevels) do
FHead^.sknNext[i] := FTail;
FHead^.sknPrev := nil;
FTail^.sknNext[0] :=nil;
FTail^.sknPrev := FHead;
{установить курсор на начальный узел}
FCursor := FHead;
{сохранить функцию сравнения и процедуру dispose}
FCompare := aCompare;
FDispose :=aDispose;
{создать генератор случайных чисел}
FPRNG := TtdMinStandardPRNG.Create(0);
end;
destructor TtdSkipList.Destroy;
begin
Clear;
slFreeNode(FHead);
slFreeNode(FTail);
FPRNG.Free;
inherited Destroy;
end;
Конструктор использует функцию сравнения, что позволяет корректно выбирать позицию вставляемых узлов (конечно, функция сравнения не может быть nil). Кроме того, в качестве входного параметра присутствует процедура dispose. Если она содержит nil, список с пропусками не является владельцем хранящихся в нем данных, поэтому при удалении списка данные удаляться не будут. В противном случае список является владельцем данных, и при его удалении данные также будут удаляться. Конструктор Create создает начальный и конечный узлы и устанавливает их указатели. И, наконец, создается генератор случайных чисел. Он впоследствии будет использоваться в методе Add.
Деструктор Destroy очищает содержимое списка с помощью метода Clear, освобождает начальный и конечный узлы и уничтожает генератор случайных чисел.
Метод Clear предназначен для очистки содержимого всех узлов, находящихся между начальным и конечным узлами, путем прохождения списка по указателям нижнего уровня и уничтожения узлов.
Листинг 6.20. Очистка содержимого списка с пропусками
procedure TtdSkipList.Clear;
var
i : integer;
Walker, Temp : PskNode;
begin
{пройти по узлам уровня 0, освобождая все узлы}
Walker := FHead^.sknNext[0];
while (Walker <> FTail) do
begin
Temp Walker;
Walker := Walker^.sknNext[0];
slFreeNode(Temp);
end;
{восстановить начальный и конечный узлы}
for i := 0 to pred(tdcMaxSkipLevels) do
FHead^.sknNext[i] := FTail;
FTail^.sknPrev := FHead;
FCount := 0;
end;
Методы выделения и уничтожения узлов достаточно просты. Они пользуются диспетчерами узлов класса и определяют требуемый диспетчер на основе значения уровня. Для метода выделения узла уровень передается в качестве входного параметра, для метода уничтожения оно определяется исходя из значения, полученного из освобождаемого узла.
Листинг 6.21. Выделение и уничтожение узлов в списке с пропусками
class function TtdSkipList.slAllocNode(aLevel : integer): PskNode;
begin