Implementacja listy jednokierunkowej

babubabu

2014-05-08 04:37:00
2022-01-17 21:01:01
0 komentarzy
9260 odsłon

Wstęp

W tym artykule opiszę implementację listy jednokierunkowej. Zaprezentuję jak taką listę stworzyć, jak dodawać do niej elementy, jak usuwać poszczególne elementy, jak przeszukać listę by wydobyć informacje, jak taką listę zapisać do pliku oraz jak ją z pliku wczytać. Implementacja będzie w postaci klasy, ze względu na wygodę programowania oraz przejrzystość kodu i nie będzie zawierała obsługi błędów, gdyż w tym artykule zajmuję się tylko i wyłącznie opisem listy jednokierunkowej, a nie opisem obsługi błędów.

Co to są listy?

Lista jest to struktura danych, służąca do przechowywania dynamicznych zbiorów danych, bardzo podobna do tablicy. Jednak od tablicy różni się szybkością dodawania i usuwania elementów, kosztem trudniejszego dostępu do poszczególnych elementów. Jest to spowodowane tym, że aby uzyskać dostęp do konkretnego elementu listy, trzeba najpierw uzyskać dostęp do wszystkich elementów, poprzedzających konkretny element.

Wyróżniamy dwa rodzaje list:

jednokierunkowa - każdy element posiada wskaźnik na następny element w liście,
dwukierunkowa - każdy element posiada wskaźniki na następny i poprzedni element w liście.

Oba rodzaje list mogą być również listami cyklicznymi, w których wskaźnik na następny element w ostatnim elemencie wskazuje na pierwszy element listy, a w przypadku listy dwukierunkowej wskaźnik na poprzedni element w pierwszym elemencie wskazuje na ostatni element listy.

Implementacja

Typy danych

Poniżej znajduje się opis typów danych, zdefiniowanych na potrzeby listy jednokierunkowej.

type
  TData = Word;

Typ TData jest aliasem typu Word, ale może być to dowolny inny typ, również rekordowy.

type
  PElement = ^TElement;
  TElement = record
    Data: TData;
    Next: PElement;
end;

PElement jest wskaźnikiem na TElement.

Typ TElement jest typem opisującym element listy o następującej strukturze:

Data - dane przechowywane w elemencie,
Next - wskaźnik na następny element listy.

Została zadeklarowana także jedna stała:

const
  ELEMENT_DATA_SIZE = SizeOf(TData);

przechowująca rozmiar typu TData w bajtach.

Klasa TSinglyLinkedList

type
  TSinglyLinkedList = class
    private
      FFirst: PElement;
      FLast: PElement;
      FCount: LongWord;
    private
      function CreateElement(AData: TData): PElement;
      procedure GetElementByIndex(AIndex: Cardinal; out APrev, AElement: PElement);
      function GetCapacity(): LongWord;
    public
      constructor Create();
      destructor Destroy(); override;
    public
      procedure Add(AElement: TData);
      procedure Insert(AElement: TData; AIndex: Word);
      procedure Delete(AIndex: Word);
      procedure Clear();
    public
      function Find(AData: TData): Integer;
      function Get(AIndex: Word): TData;
    public
      procedure SaveToFile(const AFileName: String);
      procedure LoadFromFile(const AFileName: String);
      procedure Print();
    public
      property Count: Integer read FCount;
      property Capacity: LongWord read GetCapacity;
  end;

Pola klasy

FFirst - wskaźnik na pierwszy element w liście,
FLast - wskaźnik na ostatni element w liście (nieobowiązkowe, ale znacznie przyspiesza niektóre operacje),
FCount - ilość elementów w liście.

Metody klasy

Konstruktor

Konstruktor klasy jest bardzo prosty:

constructor TSinglyLinkedList.Create();
begin
  inherited Create();
  FFirst := nil;
  FLast := nil;
  FCount := 0;
end;

W pierwszej kolejności wywołany jest konstruktor klasy bazowej, a następnie pola FFirst i FLast ustawiane są na Nil , oraz pole FCount jest zerowane.

Destruktor

Destruktor jest również prosty:

destructor TSinglyLinkedList.Destroy();
begin
  Clear();
  inherited Destroy();
end;

Najpierw jest wywoływana metoda Clear, a następnie wywoływany jest destruktor klasy bazowej.

Prywatne

Klasa posiada trzy metody prywatne:

function CreateElement(AData: TData): PElement;
procedure GetElementByIndex(AIndex: Cardinal; out APrev, AElement: PElement);
function GetCapacity(): LongWord;

Poniiżej znajdują się opisy ich przeznaczenia.

CreateElement

function TSinglyLinkedList.CreateElement(AData: TData): PElement;
begin
  New(Result);
  Result^.Next := nil;
  Result^.Data := AData;
end;

Metoda tworzy nowy element listy (rezerwuje pamięć) i zwraca wskaźnik na ten element.

GetElementByIndex

procedure TSinglyLinkedList.GetElementByIndex(AIndex: Cardinal; out APrev, AElement: PElement);
begin
  AElement := FFirst;
  APrev := nil;

  while AIndex > 0 do
  begin
    APrev := AElement;
    AElement := AElement^.Next;
    Dec(AIndex);
  end;
end;

Metoda wyszukuje element o podanym indeksie. Jest to metoda proceduralna, a nie funkcyjna, ponieważ zwraca dwie wartości: element o podanym indeksie oraz poprzednik szukanego elementu. Na początku przypisuje odpowiednie wartości zmiennym, kolejno do AElement jest przypisywany wskaźnik na pierwszy element listy, a do APrev jest przypisywane Nil. Następnie jest zwykła pętla While, która kończy działanie w momencie, gdy AIndex osiągnie wartość zero. W pętli przeskakuje poszczególne elementy listy. Do APrev przypisuje AElement, następnie do AElement przypisuje wskaźnik na następny element listy. Gdy pętla się zakończy - zwraca wartości APrev i AElement, w których znajdują się kolejno w APrev - wskaźnik na poprzednik szukanego elementu, w AElement - wskaźnik na szukany element.

GetCapacity

function TSinglyLinkedList.GetCapacity(): LongWord;
begin
  Result := FCount * ELEMENT_DATA_SIZE;
end;

Metoda zwraca liczbę bajtów, potrzebną na przechowanie listy w pamięci (rozmiary wskaźnika na następny element nie zostały uwzględnione).

Publiczne

Add

procedure TSinglyLinkedList.Add(AElement: TData);
var
  NewOne : PElement;
begin
  NewOne := CreateElement(AElement);

  if FFirst = nil then
  begin
    FFirst := NewOne;
    FLast := FFirst;
  end
  else
  begin
    FLast^.Next := NewOne;
    FLast := NewOne;
  end;

  Inc(FCount);
end;

Metoda dodaje kolejny element do końca listy. Najpierw tworzy nowy element, następnie sprawdza czy lista jest pusta. Jeśli tak, to wskaźnikowi na pierwszy element przypisuje wskaźnik nowego elementu, oraz wskaźnikowi na ostatni element przypisuje wskaźnik na pierwszy element (ponieważ jeśli lista zawiera jeden element, to ten element jest zarówno pierwszym, jak i ostatnim). Jeśli lista nie jest pusta, wskaźnikowi na następnik ostatniego elementu przypisuje wskaźnik na nowy element i wskaźnikowi na ostatni element również przypisuje wskaźnik nowego elementu.

Tutaj dokładnie widać po co jest wskaźnik na ostatni element w liście. Jeśli tego wskaźnika by nie było, trzeba by przeszukać całą listę w poszukiwaniu ostatniego elementu. Jeśli lista jest krótka to nie wydłuża to znacząco czasu dodawania nowego elementu, ale jeśli była by bardzo długa, to dodawanie nowego elementu zajmowało by dużo czasu. Na końcu zwiększa licznik elementów w liście o jeden.

Animacja ilustrująca zasadę działania:

Insert

procedure TSinglyLinkedList.Insert(AElement: TData; AIndex: Word);
var
  NewOne, Next, Prev: PElement;
begin
  if AIndex >= FCount then
    Add(AElement)
  else
  begin
    NewOne := CreateElement(AElement);
    GetElementByIndex(AIndex, Prev, Next);
 
    if Next = FFirst then
    begin
      NewOne^.Next := FFirst;
      FFirst := NewOne;
    end
    else
    begin
      Prev^.Next := NewOne;
      NewOne^.Next := Next;
    end;
 
    Inc(FCount);
  end;
end;

Metoda ta wstawia nowy element do listy, w miejsce o podanym indeksie. Najpierw sprawdza czy podany indeks nie jest większy niż ilość elementów na liście. Jeśli tak, to wywołana zostaje metoda Add. Jeśli nie - tworzy nowy element oraz szuka elementu o podanym indeksie (będzie on następnikiem nowego elementu) oraz jego poprzednika. Jeśli element o indeksie AIndex jest pierwszym elementem listy, ustawia wskaźnik na następnik nowego elementu na pierwszy element, a wskaźnik na pierwszy element ustawia na nowy element. Jeśli szukany element nie jest pierwszym na liście, wskaźnik na następnik poprzednika szukanego elementu ustawia na nowy element i wskaźnik na następnik nowego elementu ustawia na szukany element. Sprawdza również czy następnik nowego elementu jest równy Nil. Jeśli tak to oznacza, że nowy element jest ostatnim elementem na liście i wskaźnik ostatniego elementu ustawia na nowy element. Na samym końcu zwiększa licznik elementów.

Animacja ilustrująca dodanie elementu w środku listy:

Animacja obrazująca dodanie elementu na początek listy:

Delete

procedure TSinglyLinkedList.Delete(AIndex: Word);
var
  ToDelete, Prev: PElement;
begin
  if AIndex = 0 then
  begin
    ToDelete := FFirst;
    FFirst := FFirst^.Next;

    if FFirst = nil then
      FLast := nil;
  end
  else
  begin
    GetElementByIndex(AIndex, Prev, ToDelete);
    Prev^.Next := ToDelete^.Next;

    if ToDelete^.Next = nil then
      FLast := Prev;
  end;

  Dispose(ToDelete);
  Dec(FCount);
end;

Ta metoda usuwa element o podanym indeksie z listy. Na samym początku sprawdza czy podany indeks jest równy zero. Jeśli tak, wskaźnikowi na element do usunięcia przypisuje pierwszy element, następnie wskaźnikowi na pierwszy element przypisuje następnik pierwszego elementu. Sprawdza czy wskaźnik na pierwszy element nie jest równy Nil. Jeśli jest równy Nil oznacza to, że lista jest pusta i wskaźnikowi na ostatni element przypisuje Nil.

Jeśli podany indeks nie jest równy zero, szuka elementu o danym indeksie. Następnie sprawdza czy następnik elementu do usunięcia jest równy Nil. Jeśli tak, wskaźnikowi na ostatni element przypisuje poprzednik elementu do usunięcia oraz następnikowi poprzednika przypisuje wartość Nil. Jeśli nie - następnikowi poprzednika elementu do usunięcia przypisuje następnik elementu do usunięcia. Na samym końcu usuwa element i zmniejsza licznik elementów o jeden.

Animacja ilustrująca zasadę działania:

Clear

procedure TSinglyLinkedList.Clear();
var
  ToDelete: PElement;
begin
  while FFirst <> nil do
  begin
    ToDelete := FFirst;
    FFirst := FFirst^.Next;
    Dispose(ToDelete);
  end;
  FLast := nil;
  FCount := 0;
end;

Ta metoda usuwa całą zawartość listy. Jest to bardzo prosta pętla, której warunkiem zakończenia jest to, że wskaźnik na pierwszy element wskazuje Nil. W pętli przypisuje elementowi do usunięcia element pierwszy, elementowi pierwszemu przypisujemy jego następnik i usuwa element. Po wyjściu z pętli, wskaźnikowi na ostatni element przypisuje Nil i zeruje licznik elementów.

Find

function TSinglyLinkedList.Find(AData: TData): Integer;
var
  ToFind : PElement;
begin
  Result := 0;
  ToFind := FFirst;

  while ToFind <> nil do
  if ToFind^.Data = AData then
    Exit
  else
  begin
    ToFind := ToFind^.Next;
    Inc(Result);
  end;

  Result := -1;
end;

Ta metoda wyszukuje dany element w liście. Metoda po odnalezieniu danego elementu zwraca jego indeks, a jeśli nie znajdzie - zwraca -1. Na początku ustawia wartość, którą zwróci metoda na 0 i wskaźnik na szukany element ustawia na pierwszym elemencie listy. Następnie w pętli sprawdza czy dane, które zawiera element są równe danym, podanym w argumencie. Jeśli tak - kończy metodę. Jeśli nie - wskaźnikowi na szukany element przypisuje wartość jego następnika i zwiększa wartość którą zwróci metoda o 1. Jeśli pętla się skończy, a podany element nie zostanie znaleziony - wartości którą zwróci funkcja przypisuje -1.

Jest to bardzo prosta metoda wyszukująca, która kończy działanie po napotkaniu pierwszego pasującego elementu. Jest możliwe napisanie metody znajdującej wszystkie pasujące elementy, jednak nie jest ona opisana w tym artykule.

Get

function TSinglyLinkedList.Get(AIndex: Word): TData;
var
  ToGet, Unused: PElement;
begin
  if AIndex = FCount - 1 then
    Result := FLast^.Data
  else
  begin
    GetElementByIndex(AIndex, Unused, ToGet);
    Result := ToGet^.Data;
  end;
end;

Ta metoda zwraca dane elementu o podanym indeksie. Najpierw musi sprawdzić czy podany indeks nie jest indeksem ostatniego elementu listy. Jeśli jest, zwraca dane ostatniego elementu. Jeśli nie - wyszukuje element o podanym indeksie i zwraca dane, które zwiera.

SaveToFile

procedure TSinglyLinkedList.SaveToFile(const AFileName: String);
var
  SaveFile : TFileStream;
  ToSave   : PElement;
begin
  SaveFile := TFileStream.Create(AFileName, fmCreate);
  ToSave := FFirst;
  try
    while ToSave <> nil do
    begin
      SaveFile.WriteBuffer(ToSave^.Data, ELEMENT_DATA_SIZE);
      ToSave := ToSave^.Next;
    end;
  finally
    FreeAndNil(SaveFile);
  end;
end;

Ta metoda zapisuje listę do pliku o podanej nazwie.

Zanim opiszę tą metodę to wyjaśnię co i czemu zapisujemy do pliku, a czego nie powinniśmy. Do pliku zapisujemy tylko i wyłącznie dane, które zawierają poszczególne elementy. Jeśli zerkniemy na deklarację naszego typu TElement, to przy zapisie do pliku interesuje nas tylko Data. A dlaczego nie możemy zapisać całego TElement? Ponieważ zawiera wskaźnik na następnik. Wyobraź sobie, że mieszkasz przy ulicy A. I dochodzą do ciebie listy zaadresowane na ulicę A. Jeśli się przeprowadzisz na ulicę B i nikogo o tym nie poinformujesz to wszystkie listy będą dalej adresowane na ulicę A i nie będziesz ich otrzymywał. Wskaźnik to adres danych w pamięci, więc jeśli zapiszemy go do pliku, a następnie zrestartujemy komputer i wczytamy listę z pliku, to nie mamy pewności czy odpowiednie informacje znajdują się akurat pod tym adresem, na który wskazuje wskaźnik wczytany z pliku. Powiedział bym, że możemy być pewni, że tych informacji tam nie będzie, a program zgłosi błąd.

Teraz przejdźmy do opisu metody. Na początku przy pomocy klasy TFileStream tworzy strumień i wskaźnikowi na element do zapisu przypisuje pierwszy element listy. Następnie w pętli zapisuje dane każdego elementu z listy do strumienia i na samym końcu zamyka ów strumień.

LoadFromFile

procedure TSinglyLinkedList.LoadFromFile(const AFileName: String);
var
  LoadFile: TFileStream;
  ToLoad: TData;
begin
  LoadFile := TFileStream.Create(AFileName, fmOpenRead);
  try
    while LoadFile.Position < LoadFile.Size do
    begin
      LoadFile.ReadBuffer(ToLoad, ELEMENT_DATA_SIZE);
      Add(ToLoad);
    end;
  finally
    FreeAndNil(LoadFile);
  end;
end;

Ponieważ do pliku zapisane zostały tylko dane z listy, to podczas wczytywania taką listę trzeba zbudować. Metoda na początku otwiera plik, następnie w pętli wczytuje dane i metodą Add dodaje je do listy. Po wczytaniu wszystkich danych zamyka plik.

Print

procedure TSinglyLinkedList.Print();
var
  ToPrint: PElement;
  Index: Word;
begin
  ToPrint := FFirst;
  Index := 0;

  Writeln('Count: ', FCount);
  Writeln('Capacity: ', GetCapacity);
  while ToPrint <> nil do
  begin
    Writeln('Index: ',Index,' Data: ',  ToPrint^.Data);

    ToPrint := ToPrint^.Next;
    Inc(Index);
  end;
end;

Ta metoda wyświetla zawartość naszej listy oraz ilość pamięci, zajmującej przez dane w liście. Myślę, że opis tej metody jest zbędny.

Właściwości klasy.

Count

Właściwość tylko do odczytu, zwraca ilość elementów, znajdujących się na liście.

Capacity

Właściwość tylko do odczytu, zwraca ilość bajtów, jakie zajmują w pamięci dane, umieszczone na liście.

Podsumowanie.

Przedstawiona tutaj klasa jest w pełni funkcjonalna, odnośnie typów podstawowych. Niestety superuniwersalnej klasy implementujacej listę jednokierunkową nie da się napisać, ponieważ w zaleznosci od typu elementu trzeba by było dostosować metody Add, Insert oraz Find i prawdopodobnie również metody SaveToFile i LoadFromFile, jednak klasa, która została opisana w tym artykule, może służyć jako baza do swojej własnej, gdyż zasada działania została przedstawiona. Kod źródłowy można znaleźć pod linkiem: http://pastebin.com/nK71apb8