Implementacja listy dwukierunkowej ze znacznikiem

flowCRANE

2015-09-04 00:36:37
2016-12-29 00:24:52
0 komentarzy
1720 odsłon

W tym artykule opisana jest specyficzna lista dwukierunkowa. Specyficzna z tego względu, że co prawda jej budowa nie odbiega od tej znanej, to dodatkowo zapamiętuje ostatnio używany węzeł, który wykorzystywany jest podczas przeszukiwania listy. Ten specjalny wskaźnik nazywany będzie znacznikiem.

Przykład implementacji opisywanej listy opakowany jest w standardową klasę i nie zawiera obsługi błędów (poprzez wyjątki). Prezentowane kody napisane są w języku Free Pascal i przeznaczone dla kompilatora FPC, jednak bez większych modyfikacji mogą być używane w środowisku Delphi.

Pomysł listy zapamiętującej ostatnio użyty węzeł jest autorski, jednak nie jest wykluczone, że jest on już powszechnie znany i stosowany.

Spis treści:

Lista dwukierunkowa

Tak jak każda lista dwukierunkowa, ta opisywana składa się z węzłów, w których skład wchodzą przede wszystkim dwa wskaźniki - na poprzedni oraz następny węzeł. Natomiast domyślnymi danymi przechowywanymi w pojedynczych węzłach są obiekty, a konkretnie instancje klas(y) dziedziczących po TObject. Dzięki temu tak przygotowana bazowa lista będzie mogła przechowywać obiekty różnych klas.

Znacznik listy

Wskaźnik określany mianem znacznika jest dokładnie tego samego typu co wszystkie inne węzły listy. W przypadku, gdy lista jest pusta, znacznik zawsze wskazuje na wartość Nil, natomiast w każdej niepustej liście zawsze wskazuje na ostatnio użyty węzeł lub na pierwszy węzeł listy.

Zapamiętywanie ostatnio użytego węzła ma służyć przede wszystkim do przyspieszenia wyszukiwania węzła o zadanym indeksie. Z racji tej, że w liście dwukierunkowej iterowanie po węzłach możliwe jest w dwie strony, możliwości iterowania są cztery:

od pierwszego węzła w przód (w stronę końca listy),
od ostatnio użytego węzła w tył (w kierunku początku listy),
od ostatnio użytego węzła w przód (w stronę końca listy),
od ostatniego węzła w tył (w kierunku początku listy).

To od którego węzła i w którym kierunku odbędzie się wyszukiwanie zależy od zadanego indeksu oraz od indeksu ostatnio użytego węzła. Dzięki temu, że wyszukiwanie zadanego węzła może się odbywać łącznie od trzech różnych węzłów - maksymalna ilość koniecznych iteracji nie będzie większa, niż połowa ilości węzłów znajdujących się w liście; Ma to duże znaczenie przede wszystkim w bardzo długich listach i wielu operacjach wstawiania bądź usuwania węzłów.

Implementacja w języku Free Pascal

Typ danych węzłów

Każdy węzeł listy musi posiadać wskazanie na poprzedni oraz następny węzeł listy, a także pole do przechowywania danych, w tym przypadku obiektów bazowej klasy TObject. Deklaracja rekordu oraz wskaźnika na taką strukturę przedstawia się następująco:

type
  PListNode = ^TListNode;
  TListNode = record
    PreviousNode: PListNode;
    NextNode: PListNode;
    Element: TObject;
  end;

Typ TListNode zawiera trzy pola - wskaźnik PreviousNode przechowujący adres poprzedniego węzła, wskaźnik NextNode trzymający adres następnego węzła, a także Element, służący do przechowywania obiektu jako danych węzła.

Typ TListNode służy jedynie do deklaracji wskaźnika na taki rekord, czyli typu PListNode - wszystkie pola, metody i właściwości klasy listy będą korzystać tylko i wyłącznie ze wskaźników, nie faktycznych rekordów.

Deklaracja klasy TDoublyLinkedList

Poniżej widnieje kompletna deklaracja klasy listy dwukierunkowej. Opis jej składowych znajduje się w kolejnych podpunktach.

type
  TDoublyLinkedList = class(TObject)
  private
    FFirstNode: PListNode;
    FLastNode: PListNode;
    FLastUsedNode: PListNode;
    FLastUsedNodeIndex: Integer;
    FCount: Integer;
    FOwnsElements: Boolean;
  private
    procedure DisposeRemainingNodes();
    procedure DisposeRemainingElements();
  private
    function CreateNode(AElement: TObject): PListNode;
  private
    function NodeAtIndex(AIndex: Integer): PListNode;
    function ElementAtIndex(AIndex: Integer): TObject;
  public
    constructor Create(AOwnsElements: Boolean);
    destructor Destroy(); override;
  public
    procedure AddElement(AElement: TObject);
    procedure InsertElement(AIndex: Integer; AElement: TObject);
  public
    procedure RemoveElement(AIndex: Integer);
    procedure RemoveAllElements();
  public
    property Count: Integer read FCount;
    property OwnsElements: Boolean read FOwnsElements;
  public
    property Element[AIndex: Integer]: TObject read ElementAtIndex; default;
  end;

Pola klasy

Pierwszą grupą pól klasy są wskaźniki, na podstawie których zbudowana jest lista, a także służących do dostępu do poszczególnych jej węzłów. Drugą grupą są pola liczbowe, służące do celów informacyjnych a także do obsługi znacznika. W skład ostatniej grupy wchodzi pole z wartością logiczną, określające sposób przechowywania obiektów.

FFirstNode

Jest to wskaźnik typu PListNode, wskazujący na pierwszy węzeł listy. Jeśli lista jest pusta, wskaźnik ten posiada wartość Nil, a jeśli nie jest pusta - wskazanie na węzeł początkowy.

FLastNode

Wskaźnik typu PListNode, posiadający wskazanie na ostatni węzeł listy. W przypadku gdy lista jest pusta - posiada wartość Nil. Jeżeli lista posiada tylko jeden element, wartość tego wskaźnika jest taka sama jak wartość pola FFirstNode, dlatego że oba pola wskazują na ten sam węzeł. W pozostałych przypadkach (jeżeli lista zbudowana jest z więcej niż jednego węzła) zawiera wartość różną od Nil i różną od wartości pola FFirstNode.

FLastUsedNode

Jest to specjalny wskaźnik typu PListNode, zawierający adres ostatnio użytego węzła. Jeśli lista jest pusta, wskaźnik ten zawiera wartość Nil. Natomiast w każdej niepustej liście wskazuje na konkretny węzeł:

albo na pierwszy węzeł listy, jeśli lista nie była do tej pory przeszukiwana,
albo na ostatnio użyty węzeł (dowolny na liście, również pierwszy lub ostatni).

Używanie tego pola jest ściśle powiązane z polem FLastUsedNodeIndex.

FLastUsedNodeIndex

Pole typu Integer, przechowujące indeks ostatnio użytego węzła (czyli indeks węzła, na który wskazuje pole FLastUsedNode). Jeśli lista jest pusta, pole to przyjmuje wartość -1, natomiast w przypadku niepustej listy przechowuje indeks w postaci liczby naturalnej (indeks pierwszego węzła to 0, a ostatniego to n - 1).

FCount

Przechowuje liczbę węzłów znajdujących się w liście, w postaci liczby naturalnej typu Integer. Dla pustej listy posiada wartość 0, dla niepustej - liczbę dodatnią.

FOwnsElements

Jest to specjalne pole typu Boolean. Służy do określenia, czy podczas usuwania węzłów listy mają także zostać zwolnione instancje klas z pola Element, za pomocą metody Free. Jeśli pole to posiada wartość True - obiekty zostaną zwolnione z pamięci podczas usuwania węzłów pojedynczo, a także w destruktorze klasy, gdzie usuwane są wszystkie istniejące węzły listy.

Dzięki temu polu możliwe będzie tworzenie i usuwanie obiektów poza listą oraz traktowanie listy jako tymczasowego kontenera.

Metody klasy

Create

Konstruktor klasy ma za zadanie utworzyć instancję obiektu listy, a także zainicjować wartości wszystkich pól w taki sposób, aby od momentu utworzenia listy mogła być rozpoznana jako pusta.

constructor TDoublyLinkedList.Create(AOwnsElements: Boolean);
begin
  inherited Create();

  FFirstNode := nil;
  FLastNode := nil;

  FLastUsedNode := nil;
  FLastUsedNodeIndex := -1;

  FCount := 0;
  FOwnsElements := AOwnsElements;
end;

Wszystkim wskaźnikom przypisane zostają adresy zerowe, czyli wartości Nil. Indeks ostatnio użytego węzła to -1, a ilość węzłów na liście jest od tej pory równa 0. Pole FOwnsElements przyjmuje wartość z argumentu AOwnsElements.

Destroy

Zadaniem destruktora jest przede wszystkim zwolnienie instancji klasy listy z pamięci, ale także zwolnienie wszystkich istniejących w liście węzłów oraz ewentualnie wszystkich obiektów.

destructor TDoublyLinkedList.Destroy();
begin
  if FCount > 0 then
    DisposeRemainingNodes();

  inherited Destroy();
end;

Jeżeli lista nie jest pusta, najpierw trzeba zwolnić z pamięci wszystkie jej węzły. W tym celu sprawdzana jest wartość pola FCount i jeśli jest większa od 0 - wywoływana jest metoda DisposeRemainingNodes, zwalniająca węzły listy (metoda ta opisana jest w dalszej części artykułu).

DisposeRemainingNodes

Metoda ta służy do zwolnienia z pamięci wszystkich istniejących w liście węzłów oraz do ustawienia wszystkim polom wartości początkowych.

procedure TDoublyLinkedList.DisposeRemainingNodes();
var
  plnNext, plnDispose: PListNode;
begin
  if FOwnsElements then
    DisposeRemainingElements();

  plnDispose := FFirstNode;

  while plnDispose <> nil do
  begin
    plnNext := plnDispose^.NextNode;
    Dispose(plnDispose);

    plnDispose := plnNext;
  end;

  FFirstNode := nil;
  FLastNode := nil;

  FLastUsedNode := nil;
  FLastUsedNodeIndex := -1;

  FCount := 0;
end;

W pierwszej kolejności sprawdzana jest wartość pola FOwnsElements i jeśli posiada wartość True - wywołana zostaje metoda DisposeRemainingElements, która zwalnia z pamięci obiekty, znajdujące się w polu Element każdego istniejącego węzła.

Następnie w pętli od pierwszego węzła listy (czyli od węzła na który wskazuje pole FFirstNode) do ostatniego, zwalniane są struktury z pamęci. Do iterowania po węzłach listy używane są pola NextNode. Na koniec wszystkie wskaźniki są **Nil**owane, pole FLastUsedNodeIndex przyjmuje wartość -1, a pole FCount wartość 0.

Po wykonaniu kodu metody DisposeRemainingNodes, lista posiada dokładnie takie same wartości pól, jakie zostały ustawione w konstruktorze klasy. Dzięki temu metoda ta wykorzystywana jest w dwóch innych - w destruktorze klasy, a także w metodzie RemoveAllElements, służącej do wyczyszczenia listy.

DisposeRemainingElements

Ta metoda służy jedynie do zwolnienia z pamięci obiektów, przechowywanych w poszczególnych węzłach listy.

procedure TDoublyLinkedList.DisposeRemainingElements();
var
  plnElement: PListNode;
begin
  plnElement := FFirstNode;

  while plnElement <> nil do
  begin
    plnElement^.Element.Free();
    plnElement := plnElement^.NextNode;
  end;
end;

Jej zadaniem jest jedynie przeiterowanie po wszystkich węzłach oraz wywołanie metody Free dla każdego pola Element. Metoda ta uzywana jest tylko i wyłącznie przez metodę DisposeRemainingNodes i tylko i wyłącznie w przypadku, gdy wartość pola FOwnsElements jest równa True.

CreateNode

Jest to metoda funkcyjna, służąca do zaalokowania pamęci dla nowego węzła, który zwraca w rezultacie.

function TDoublyLinkedList.CreateNode(AElement: TObject): PListNode;
begin
  New(Result);

  Result^.PreviousNode := nil;
  Result^.NextNode := nil;
  Result^.Element := AElement;
end;

Alokuje pamięć dla nowego węzła, ustawia wskaźniki na wartość Nil, dlatego że w tym miejscu i momencie nie jest znane położenie nowo tworzonego węzła. Ostatni krok to przepisanie referencji do obiektu z parametru AElement do pola Element.

NodeAtIndex

Metoda ta służy do odnalezienia węzła, znajdującego się pod zadanym indeksem.

function TDoublyLinkedList.NodeAtIndex(AIndex: Integer): PListNode;
begin
  if FLastUsedNodeIndex - AIndex > FLastUsedNodeIndex shr 1 then
  begin
    FLastUsedNode := FFirstNode;
    FLastUsedNodeIndex := 0;
  end
  else
    if AIndex - FLastUsedNodeIndex > FCount - 1 - AIndex then
    begin
      FLastUsedNode := FLastNode;
      FLastUsedNodeIndex := FCount - 1;
    end;

  if FLastUsedNodeIndex < AIndex then
    while FLastUsedNodeIndex < AIndex do
    begin
      FLastUsedNode := FLastUsedNode^.NextNode;
      Inc(FLastUsedNodeIndex);
    end
  else
    while FLastUsedNodeIndex > AIndex do
    begin
      FLastUsedNode := FLastUsedNode^.PreviousNode;
      Dec(FLastUsedNodeIndex);
    end;

  Result := FLastUsedNode;
end;

Z racji tej, że wyszukiwanie węzła musi bazować na węźle-znaczniku - pierwsza część metody implementuje sprawdzenie, czy bliżej do szukanego węzła o indeksie z argumentu AIndex jest od początku listy, czy od jej końca.

Pierwszy warunek porównuje odległości od pierwszego węzła listy do węzła ostatnio użytego. Jeśli bliżej tej od pierwszego, ustawia znacznik na pierwszy węzeł listy, a indeks znacznika na 0. Natomiast jeżeli bliżej jest iterować od końca listy (drugi warunek) to ustawia znacznik na ostatni węzeł. W przypadku gdy oba warunki nie zostaną spełnione, wartość pól FLastUsedNode i FLastUsedNodeIndex nie zmieniają się, więc wyszukiwanie rozpocznie się od ostatnio użytego węzła;

Druga część metody to porównanie dwóch indeksów - FLastUsedNodeIndex i AIndex - aby określić kierunek iteracji; Jeśli szukany węzeł znajduje się po ostatnio użytym - iterowanie bazować będzie na polu NextNode i inkrementowaniu pola FLastUsedNodeIndex, do czasu, aż jego wartość zrówna się z indeksem z argumentu. W przeciwnym razie iterowanie odbędzie się w stronę początku listy, czyli z wykorzystaniem pola PreviousNode oraz dekrementowaniem indeksu znacznika.

Po wykonaniu warunków oraz niezbędnych iteracji, do rezultatu funkcji przypisany zostaje wskaźnik FLastUsedNode, który w tym momencie wskazuje na szukany węzeł.

Ważne w tym kodzie są dwa przypadki. Jeżeli szukanym węzłem jest ten ostatnio użyty (wartości pola FLastUsedItemIndex oraz argumentu AIndex są sobie równe), żaden z początkowych warunków sprawdzających odległości nie zostanie wykonany, a także żadna z pętli While z drugiej części metody nie wykona ani jednej iteracji. W rezultacie pole ze znacznikiem nie ulegnie zmianie.

Drugim wartym uwagi przypadkiem jest sytuacja, gdy odległość od pierwszego lub ostatniego węzła do węzła szukanego jest taka sama jak od tego ostatnio użytego. Wtedy wartość pola FLastUsedNode nie ulegnie zmianie, dzięki czemu iterowanie odbędzie się od ostatnio użytego węzła.

ElementAtIndex

Metoda ta wykorzystywana jest do pobrania obiektu z węzła, znajdującego się pod zadanym indeksem.

function TDoublyLinkedList.ElementAtIndex(AIndex: Integer): TObject;
begin
  Result := NodeAtIndex(AIndex)^.Element;
end;

Jak widać jest to tylko wrapper na metodę NodeAtIndex, dodatkowo zwracający instancję klasy z pola Element znalezionego węzła. Ważne jest tutaj użycie wymienionej metody, aby znacznik został przesunięty.

Metoda ElementAtIndex wykorzystywana jest jedynie jako akcesor dla domyślenej dla klasy właściwości Element (właściwości ta opisana jest kilka punktów dalej).

AddElement

Pierwsza publiczna metoda, służąca do dodania nowego elementu na koniec istniejącej listy.

procedure TDoublyLinkedList.AddElement(AElement: TObject);
var
  plnNew: PListNode;
begin
  plnNew := CreateNode(AElement);

  if FCount = 0 then
  begin
    FFirstNode := plnNew;
    FLastUsedNode := plnNew;
    FLastUsedNodeIndex := 0;
  end
  else
  begin
    plnNew^.PreviousNode := FLastNode;
    FLastNode^.NextNode := plnNew;
  end;

  FLastNode := plnNew;
  Inc(FCount);
end;

W pierwszej kolejności alokowana jest pamięć dla nowego węzła za pomocą prywatnej metody CreateNode, przekazując jej obiekt z parametru AElement.

Następnie sprawdzane jest, czy lista jest w pusta i jeśli tak - nowy węzeł wstawiany jest na początek listy, co wymusza ustawienie pola FFirstNode oraz pól znacznika. Natomiast jeśli lista nie jest pusta - nowy węzeł ląduje na końcu listy. Tutaj konieczne jest ustawienie pola PreviousNode na poprzedni węzeł, czyli na ostatni na liście - do tego celu używany jest wskaźnik z pola FLastNode. Z kolei węzeł z pola FLastNode nie będzie od tej chwili ostatnim, a przedostatnim, więc jego pole NextNode musi wskazywać na nowo utworzony węzeł.

Ostatnim krokiem jest ustawienie pola FlastNode na nowo utworzony węzeł oraz inkrementowanie pola FCount.

InsertElement

Druga publiczna metoda, służąca do wstawienia nowego węzła w miejsce o zadanym indeksie.

procedure TDoublyLinkedList.InsertElement(AIndex: Integer; AElement: TObject);
var
  plnNew, plnAtIndex: PListNode;
begin
  if AIndex >= FCount then
    AddElement(AElement)
  else
  begin
    plnNew := CreateNode(AElement);

    if AIndex = 0 then
    begin
      plnNew^.NextNode := FFirstNode;
      FFirstNode^.PreviousNode := plnNew;
      FFirstNode := plnNew;
    end
    else
    begin
      plnAtIndex := NodeAtIndex(AIndex);

      plnNew^.PreviousNode := plnAtIndex^.PreviousNode;
      plnNew^.NextNode := plnAtIndex;

      plnAtIndex^.PreviousNode^.NextNode := plnNew;
      plnAtIndex^.PreviousNode := plnNew;
    end;

    FLastUsedNode := FLastUsedNode^.PreviousNode;
    Inc(FCount);
  end;
end;

W pierwszej kolejności wykonuje sprawdzenie, czy indeks pod który ma być wstawiony nowy węzeł jest większy od indeksu ostatniego węzła w liście i jeśli tak - wywoływana jest metoda AddElement, do której zostaje przekazany argument AElement. Jeśli indeks wskazuje na istniejący węzeł to wykonywana jest standardowa procedura wstawiania.

Najpierw tworzony jest nowy węzeł w pamięci - alokacji obszaru pamęci dla nowego węzła dokonuje metoda CreateNode. Następnie sprawdzane jest, czy nowy węzeł ma być wstawiony na początek listy - w takim przypadku argument AIndex zawiera wartość 0. Jeśli warunek zostanie spełniony, nowemu węzłowi przypisuje się adres spod wskaźnika FFirstNode, a z kolei temu w polu PreviousNode przypisuje się adres nowego węzła. Na koniec do pola FFirstNode wpisuje się adres nowego węzła.

Jeśli nowy węzeł ma być wstawiony w dalszej części listy - metodą NodeAtIndex pobiera się węzeł, który zostanie zepchnięty w stronę końca listy o jedno oczko. W odróżnieniu od listy jednokierunkowej, nie potrzeba pobierać także drugiego wskaźnika, wskazującego na poprzedni węzeł, dlatego że ten spod indeksu posiada takie wskazanie w polu PreviousNode. Kolejną rzeczą jest ustawienie czterech wskaźników, aby od tego momentu włączyć nowy węzeł do listy.

Ostatnim krokiem jest inkrementacja pola FCount oraz cofnięcie o jedno oczko znacznika, aby pasował do indeksu z pola FLastUsedNodeIndex. Ta instrukcja wykonywana jest niezależnie od tego czy warunek zostanie spełniony czy nie. Dzieje się tak, dlatego że bez względu na to, czy nowy węzeł zostanie wstawiony na początku listy, w środku czy w miejsce ostatniego węzła, nowy węzeł zawsze wstawiany jest przed znacznikiem. Jeśli znacznik wskazuje pierwszy węzeł a nowy węzeł wstawiany jest na początek listy, nowy węzeł wstawiany jest przed znacznikiem. Natomiast jeśli znacznik wskazuje na jeden z dalszych węzłów, a nowy węzeł wstawiany jest po pierwszym węźle, ale przez znacznikiem - metoda NodeAtIndex przesunie znacznik w miejsce spod indeksu parametru AIndex. Nowy węzeł znów zostanie wstawiony przed węzeł na który wskazuje znacznik, dlatego też trzeba go cofnąć, aby zgrywał się z indeksem z pola FLastUsedNodeIndex.

Alternatywą jest pozostawienie wartości wskaźnika FLastUsedNode bez zmian, a w zamian inkrementacja samego indeksu, czyli wartości pola FLastUsedNodeIndex. W takim przypadku znacznik nie będzie wskazywał na nowo dodany węzeł, a na następny względem niego.

RemoveElement

Publiczna metoda służąca do usunięcia z listy węzła spod zadanego indeksu.

procedure TDoublyLinkedList.RemoveElement(AIndex: Integer);
var
  plnDispose: PListNode;
begin
  plnDispose := NodeAtIndex(AIndex);

  if FLastUsedNode = FLastNode then
  begin
    FLastUsedNode := FLastUsedNode^.PreviousNode;
    Dec(FLastUsedNodeIndex);
  end
  else
    FLastUsedNode := FLastUsedNode^.NextNode;

  if AIndex = 0 then
  begin
    plnDispose := FFirstNode;
    FFirstNode := FFirstNode^.NextNode;

    if FFirstNode = nil then
      FLastNode := nil
    else
      FFirstNode^.PreviousNode := nil;
  end
  else
  begin
    plnDispose^.PreviousNode^.NextNode := plnDispose^.NextNode;

    if plnDispose = FLastNode then
      FLastNode := plnDispose^.PreviousNode
    else
      plnDispose^.NextNode^.PreviousNode := plnDispose^.PreviousNode;
  end;

  if FOwnsElements then
    plnDispose^.Element.Free();

  Dispose(plnDispose);
  Dec(FCount);
end;

W pierwszej kolejności zostaje pobrany węzeł spod indeksu z argumentu AIndex (od tej pory znacznik wskazuje na usuwany węzeł). Następnie sprawdzane jest, czy znacznik przesunięty podczas pobierania węzła do usunięcia wskazuje na ostatni węzeł listy. Jeśli tak - wskaźnik znacznika zostaje cofnięty o jeden węzeł, a jego indeks z pola FLastUsedNodeIndex dekrementowany. W przeciwnym razie, gdy usuwany jest węzeł nieostatni - znacznikowi przypisuje się wskazanie na następny węzeł względem usuwanego.

Kolejnym krokiem jest spradzenie, który węzeł jest usuwany. Jeśli usuwany jest pierwszy węzeł listy - zmianie ulega wartość pola FFirstItem i przeskakuje o jedno oczko do przodu. Jeśli nowy pierwszy węzeł jest pusty (czyli metoda usuwa jedyny węzeł na liście), modyfikacji ulega także pole FLastNode, któremu przypisywany jest adres zerowy, czyli wartość Nil. W przeciwnym razie **Nil**owane jest pole PreviousNode nowego pierwszego węzła.

Jeżeli usuwany jest niepierwszy węzeł listy, zmianie ulega wskazanie spod NextNode w poprzednim węźle; Od teraz poprzedni węzeł w polu NextNode będzie posiadał adres następnego węzła po węźle usuwanym. W przypadku, gdy usuwany jest ostatni węzeł - przyjmie wartość Nil i sam stanie się ostatnim węzłem listy. Jeśli faktycznie tak jest, pole FLastNode musi otrzymać adres węzła poprzedniego od węzła usuwanego. Natomiast jeżeli usuwany jest nieostatni węzeł - pole PreviousNode w następnym węźle po usuwanym otrzymuje adres węzła poprzedzającego usuwany.

W całej tej zagmatwanej modyfikacji wskaźników zostaje zapamiętany adres usuwanego węzła w pomocniczej zmiennej plnDispose. Jeśli lista ma sama dbać o zwalnianie obiektów przechowywanych w liście (czyli gdy pole FOwnsElements zawiera wartość True) - obiekt przechowywany w polu Element usuwanego węzła zostaje najpierw zwolniony z pamięci, za pomocą wywołania metody Free.

Ostatnim krokiem jest zwolnienie pamęci zajmowanej przez usuwany węzeł (na ten blok pamięci wskazuje w tym miejscu tymczasowa zmienna plnDispose) oraz dekrementowanie pola FCount.

RemoveAllElements

Ostatnia z publicznych metod, służąca do usunięcia wszystkich węzłów listy i uczynienia jej pustą.

procedure TDoublyLinkedList.RemoveAllElements();
begin
  DisposeRemainingNodes();
end;

Jedynym jej zadaniem jest wywołanie metody DisposeRemainingNodes, która dokonuje fizycznego zwolnienia z pamięci wszystkich węzłów i ewentualnie także przechowywanych obiektów, a także ustawienia polom wartości początkowych.

Właściwości klasy

Count

Właściwość typu Integer służąca tylko do odczytu, łącząca bezpośrednio z polem FCount, zwracająca ilość przechowywanych w liście obiektów (a tym samym węzłów). Jeśli lista jest pusta - zwraca wartość 0, w przeciwnym razie liczbę dodatnią.

OwnsElements

Właściwość typu Boolean, także tylko do odczytu. Służy do sprawdzenia, czy lista ma zwalniać przechowywane obiekty podczas usuwania pojedynczych węzłów, podczas czyszczenia listy, a także podczas zwalniania z pamięci obiektu listy. Łączy bezpośrednio z polem FOwnsElements.

Element

Indeksowana właściwość tylko do odczytu, zwracająca instancję klasy ogólnego typu TObject. Wykorzystuje metodę ElementAtIndex jako metodę dostępową, do pobrania obiektu z węzła o indeksie podanym w AIndex. Właściwość ta opatrzona jest klauzulą Default, dzięki czemu jest domyślną właściwością klasy.

Domyślna właściwość oznacza, że nie ma obowiązku wstawiania operatora odniesienia oraz nazwy właściwości pomiędzy identyfikatorem obiektu a nawiasami z indeksem. Mając np. zmienną DoublyLinkedList typu TDoublyLinkedList, posiadającą referencję do instancji klasy listy, gdyby właściwość Element nie była domyślna, pobranie pierwszego obiektu w liście wyglądałoby tak:

objElement := DoublyLinkedList.Element[0];

ale że właściwość Element jest domyślna - jej nazwy nie trzeba zapisywać:

objElement := DoublyLinkedList[0];

Podsumowanie

W ten sposób przygotowana lista może być użyta do przechowywania dowolnych obiektów, nie tylko tej samej klasy. Dzięki temu, że listy dwukierunkowe nie potrzebują ciągłego bloku pamięci i każdy węzeł może znajdować się w dowolnym miejscu pamięci - może zawierać dowolną ilość węzłów (mniej więcej tyle, ile jest dostępnej dla aplikacji pamęci). A dodatkowo dzięki zapamiętywaniu ostatnio użytego węzła, jej przeszukiwanie jest co najmniej o połowe szybsze niż w przypadku tradycyjnej listy dwukierunkowej.

Prezentowana w tym artykule klasa listy jest klasą bazową. Aby móc z niej wygodnie korzystać w przypadku przechowywania obiektów tej samej klasy, należy przygotować klasę opakowującą, dziedziczącą po klasie bazowej. W tym celu wystarczy przygotować zestaw metod, które maskować będą rzutowanie ogólnego typu TObject na typ klasy, której obiekty są przechowywane.

Kod klasy został solidnie przetestowany i zdebugowany, dzięki czemu jest pewne, że zawsze będzie działał poprawnie oraz nie będzie powodował wycieków pamięci. W przypadku jakichkolwiek pytań bądź sugestii proszę o kontakt przez wiadomość prywatną w tym serwisie.

Niniejszy materiał udostępniany jest bez licencji i bez konkretnych wytycznych co do zastosowań domowych, darmowych oraz komercyjnych - bierzcie i jedzcie z tego wszyscy.

Załączniki

DblLinkedList.zip - archiwum zawierające moduł DblLinkedList.pp z implementacją listy.