Фундаментальные алгоритмы и структуры данных в Delphi | страница 76
InsertAtCursor(aItem);
end;
function TtdSingleLinkList.IndexOf(aItem : pointer): longint;
var
WorkCursor : PslNode;
WorkParent : PslNode;
WorkCursorIx : longint;
begin
{установить рабочий курсор на первый узел (если таковой существует)}
WorkParent := FHead;
WorkCursor := WorkParent^.slnNext;
WorkCursorIx := 0;
{идти по списку в поисках требуемого элемента}
while (WorkCursor <> nil) do
begin
if (WorkCursor^.slnData = aItem) then begin
{требуемый элемент найден; записать результат; установить реальный курсор в позицию рабочего курсора}
Result := WorkCursorIx;
FCursor := WorkCursor;
FParent := WorkParent;
FCursorIx := WorkCursorIx;
Exit;
end;
{перешли к следующему узлу}
WorkParent := WorkCursor;
WorkCursor := WorkCursor^.slnNext;
inc(WorkCursorIx);
end;
{требуемый элемент не найден}
Result := -1;
end;
procedure TtdSingleLinkList.Remove(aItem : pointer);
begin
if (IndexOf (aItem) <> -1) then
DeleteAtCursor;
end;
Полный код класса TtdSingleLinkList можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDLnlLst.pas.
Только что написанный нами класс обладает максимально возможной эффективностью. Узлы распределяются блоками. Определяющим фактором эффективности перехода от одного узла к другому, в общем случае, является скорость работы операционной системы по листанию страниц виртуальной памяти, но очевидно, что она будет зависеть от схемы использования связного списка. Если вставки и удаления элементов выполняются в случайном порядке, узлы будут разбросаны по различным страницам памяти. Как и в случае с классом TList, данные, на которые указывают ссылки каждого узла, будут находиться в разных участках памяти. Но здесь, к сожалению, мы ничего поделать не можем.
Двухсвязные списки
После достаточно подробных исследований односвязных списков можно переходить к рассмотрению двухсвязных списков. Как и в случае с односвязными списками, здесь имеется набор связанных между собой узлов, но помимо ссылки на следующий узел существует ссылка и на предыдущий узел:
type
PSimpleNode = ^TSimpleNode;
TSimpleNode = record
Next : PSimpleNode;
Prior : PSimpleNode;
Data : SomeDataType;
end;
Таким образом, двухсвязный список позволяет двигаться по узлам не только вперед, по ссылкам Next, но и назад, по ссылкам Prior. Схематично двухсвязный список показан на рис. 3.4.
Рисунок 3.4. Двухсвязный список
Вставка и удаление элементов в двухсвязном списке
Каким образом вставлять новый узел в двухсвязный список? В односвязном списке для этого нужно было разорвать одну ссылку и вставить две новых, а для двухсвязного списка потребуется разорвать две ссылки и вставить четыре новых. Причем вставку можно выполнять как перед, так и после определенного элемента, поскольку указатель Prior позволяет проходить список в обратном направлении. Фактически операцию "вставить перед" можно запрограммировать как "перейти к предыдущему узлу и вставить после". Поэтому в главе мы рассмотрим только операцию "вставить после".
