Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
Листинг 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
{требуемый элемент найден; записать результат; установить реальный курсор в позицию рабочего курсора}
Result := WorkCursorIx;
FCursor := WorkCursor;
FCursorIx := WorkCursorIx;
Exit;
end;
{перейти к следующему узлу}
WorkCursor := WorkCursor^.dlnNext;
inc(WorkCursorIx);
end;
{требуемый элемент не найден}
Result := -1;
end;
procedure TtdDoubleLinkList.Insert(aIndex : longint;
aItem : pointer);
begin
{установить курсор в позицию с заданным индексом}
dllPositionAtNth(aIndex);
{вставить элемент в позицию курсора}
InsertAtCursor(aItem);
end.-function TtdDoubleLinkList.Last : pointer;
begin
{установить
dllPositionAtNth(pred(Count));
{вернуть данные из позиции курсора}
Result := FCursor^.dlnData;
end;
procedure TtdDoubleLinkList.Remove(aItem : pointer);
begin
if (IndexOf (aItem) <> -1) then
DeleteAtCursor;
end;
Полный код класса TtdDoubleLinkList можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDLnkLst.pas.
Достоинства и недостатки связных списков
Связные списки обладают одним очень важным преимуществом: для них операции вставки и удаления принадлежат к классу O(1). Независимо от текущего элемента спуска и его емкости, для вставки или удаления элемента всегда требуется одно и то же время.
Основным недостатком связных списков является то, что получение доступа к их элементам принадлежит к классу О(n). В этом случае важно количество элементов в списке: при поиске n-ного элемента мы начинаем с некоторой позиции в списке и переходим по ссылкам вплоть до искомого элемента. Чем больше элементов в списке, тем больше переходов придется совершить. Для увеличения быстродействия в реализации классов списков мы воспользовались небольшими хитростями, но, тем не менее, операция все равно принадлежит к классу O(n).
По сравнению с классом TList связные списки требуют большего объема памяти. В качестве ссылки на элемент в TList используется один указатель, т.е. в массиве TList для каждого элемента требуется, по крайней мере, sizeof(pointer) байт. С другой стороны, односвязный список содержит два указателя: указатель на данные и указатель на следующий элемент. Таким образом, для каждого элемента в односвязном списке нужно, по меньшей мере, 2*sizeof(pointer) байт.
Очевидно, что для каждого элемента в двухсвязном списке требуется не менее 3*sizeof(pointer) байт.
Но это еще не все. Если неэффективно использовать массив TList (другими словами, не использовать свойство Capacity для установки размера массива), будут распределяться несколько блоков памяти, каждый из которых больше предыдущего, и потребуется больший объем работ, связанный с копированием данных массива. Если элементы вставляются только в начало, быстродействие массива TList существенно уменьшается. В настоящей книге будут приведены несколько реализаций алгоритмов и структур данных, которые позволяют достичь для связных списков гораздо большей эффективности, нежели это показывает TList, однако в общем случае массив TList лучше, быстрее и эффективнее связных списков.