TCyclicList - Eine doppelt verknüpfte, zyklische Liste

[3_of_8]

Morgen.

Heute kamen in der Uni einfach verlinkte Listen in Java dran.

Ich hab mir dann gedacht, warum nicht ein bisschen erweitern und in Delphi schreiben?

Hier ist der Code für eine sog. doppelt verknüpfte, zyklische Liste. (Beschreibung unten)

Delphi-Quellcode:

unit CyclicList;

interface

type
  TSortMode = (smAscending, smDescending);
  TInsertMode = (imBefore, imAfter);

  TNode = class
  protected
    FNext, FPrevious: TNode;
    FData: Variant;
  public
    property Previous: TNode read FPrevious write FPrevious;
    property Next: TNode read FNext write FNext;
    property Data: Variant read FData write FData;
  end;

  TIterator = class;

  TCyclicList = class
  protected
    FFirst, FLast: TNode;
    FCount: Cardinal;
    procedure QuickSortAsc(iLo, iHi: Cardinal);
    procedure QuickSortDesc(iLo, iHi: Cardinal);
    function GetNode(Index: Cardinal): TNode;
  public
    constructor Create;
    destructor Destroy; override;
    procedure Clear;
    function IsEmpty: Boolean;
    function Get(Index: Cardinal): Variant;
    function GetObject(Index: Cardinal): TObject;
    procedure Put(Index: Cardinal; Value: Variant);
    procedure PutObject(Index: Cardinal; Obj: TObject);
    procedure Add(Data: Variant);
    procedure AddObject(Obj: TObject);
    procedure Insert(Index: Cardinal; Data: Variant; InsertMode:
      TInsertMode = imBefore);
    procedure Delete(Index: Cardinal);
    procedure Sort(SortMode: TSortMode = smAscending);
    function GetRandom: Variant;
    function MakeIterator: TIterator;
    property Count: Cardinal read FCount;
    property Items[Index: Cardinal]: Variant read Get write Put; default;
  end;

  TIterator = class
  private
    List: TCyclicList;
    Node: TNode;
    FIndex: Cardinal;
  public
    constructor Create(List: TCyclicList; FirstNode: TNode);
    function EndOfList: Boolean;
    function Next: Variant;
    function NextObject: TObject;
    function Previous: Variant;
    function PreviousObject: TObject;
    procedure Put(Data: Variant);
    procedure PutObject(Obj: TObject);
    procedure JumpForward(Steps: Cardinal);
    procedure JumpBackward(Steps: Cardinal);
    function GetRandom: Variant;
    function GetRandomObject: TObject;
    property Index: Cardinal read FIndex;
  end;

implementation

constructor TCyclicList.Create;
begin
  inherited Create;
  FFirst := nil;
  FLast := nil;
  FCount := 0;
  Randomize;
end;

destructor TCyclicList.Destroy;
begin
  Clear;
  inherited Destroy;
end;

// Löscht alle Listenelemente
procedure TCyclicList.Clear;
var
  node, node2: TNode;
begin
  node := FFirst;
  repeat
    node2 := node.next;
    node.Free;
    node := node2;
  until (node <> nil)and(node <> FLast);
  FFirst := nil;
  FLast := nil;
  FCount := 0;
end;

// Gibt true zurück, wenn die Liste leer ist
function TCyclicList.IsEmpty: Boolean;
begin
  Result := FFirst = nil;
end;

// Gibt den Knoten an gegebenem Index zurück
function TCyclicList.GetNode(Index: Cardinal): TNode;
var
  I: Cardinal;
begin
  Index := Index mod FCount;
  if Index <= (FCount div 2= then
  begin
    Result := FFirst;
    if Index > 0 then
      for I := 0 to Index-1 do
        Result := Result.Next
  end
  else begin
    Result := FLast;
    if Index < FCount-1 then
      for I := count-1 downto Index do
        Result := Result.Previous;
  end;
end;

// Gibt Inhalt des Knotens an gegebenem Index zurück
function TCyclicList.Get(Index: Cardinal): Variant;
begin
  Result := GetNode(Index).Data;
end;

// Konvertiert den Inhalt des Knotens an gegebenem Index in ein TObject
// und gibt dieses zurück
function TCyclicList.GetObject(Index: Cardinal): TObject;
begin
  Result := TObject(Pointer(Integer(Get(Index))));
end;

// Setzt Inhalt des Knotens an gegebenem Index auf Value.
procedure TCyclicList.Put(Index: Cardinal; Value: Variant);
begin
  GetNode(Index).Data := Value;
end;

// Setzt Inhalt des Knotens an gegebenem Index auf Obj.
procedure TCyclicList.PutObject(Index: Cardinal; Obj: TObject);
begin
  GetNode(Index).Data := Integer(Obj);
end;

// Fügt einen Knoten ans Ende der Liste hinzu
procedure TCyclicList.Add(Data: Variant);
var
  Node: TNode;
begin
  Node := TNode.Create;
  Node.Data := Data;
  if IsEmpty then
  begin
    Node.Next := Node;
    Node.Previous := Node;
    FFirst := Node;
    FLast := Node;
  end else
  begin
    FFirst.Previous := Node;
    FLast.Next := Node;
    Node.Previous := FLast;
    Node.Next := FFirst;
    FLast := Node;
  end;
  inc(FCount);
end;

// Fügt einen Knoten ans Ende der Liste hinzu. (Inhalt wird auf Obj gesetzt)
procedure TCyclicList.AddObject(Obj: TObject);
begin
  Add(Integer(Obj));
end;

// Bei InsertMode = imBefore: Fügt neuen Knoten vor dem Knoten mit
// gegebenem Index hinzu.
// Bei InsertMode = imAfter: Fügt neuen Knoten nach dem Knoten mit
// gegebenem Index hinzu.
procedure TCyclicList.Insert(Index: Cardinal; Data: Variant; InsertMode:
  TInsertMode = imBefore);
var
  insertpoint, node: TNode;
begin
  if Index >= FCount then
  begin
    Add(Data);
    Exit;
  end;
  insertpoint := GetNode(Index);
  node := TNode.Create;
  node.Data := Data;
  case InsertMode of
    imBefore:
      begin
        Node.Previous := insertpoint.Previous;
        Node.Next := insertpoint;
        insertpoint.Previous.Next := Node;
        insertpoint.Previous := Node;
        if insertpoint = FFirst then
          FFirst := Node;
      end;
    imAfter:
      begin
        Node.Previous := insertpoint;
        Node.Next := insertpoint.Next;
        insertpoint.Next.Previous := Node;
        insertpoint.Next := Node;
        if insertpoint = FLast then
          FLast := Node;
      end;
  end;
  inc(FCount);
end;

// Löscht Knoten an gegebenem Index.
procedure TCyclicList.Delete(Index: Cardinal);
var
  node: TNode;
begin
  node := GetNode(Index);
  if FCount = 1 then
  begin
    node.Free;
    FFirst := nil;
    FLast := nil;
    dec(FCount);
    exit;
  end;
  node.previous.Next := node.Next;
  node.Next.previous := node.previous;
  if node=FFirst then FFirst := node.Next;
  if node=FLast then FLast := node.Previous;
  node.Free;
  dec(FCount);
end;

// Führt aufsteigenden Quicksort durch
procedure TCyclicList.QuickSortAsc(iLo, iHi: Cardinal);
var
  Lo, Hi, Mid: Cardinal;
  T: Variant;
begin
  Lo := iLo;
  Hi := iHi;
  Mid := Get((Lo+Hi)div 2);
  repeat
    while Get(Lo) < Mid do
      Inc(Lo);
    while Get(Hi) > Mid do
      Dec(Hi);
    if Lo <= Hi then
    begin
      T := Get(Lo);
      Put(Lo, Get(Hi));
      Put(Hi, T);
      Inc(Lo);
      Dec(Hi);
    end;
  until Lo>Hi;
  if Hi > iLo then
    QuickSortAsc(iLo, Hi);
  if Lo < iHi then
    QuickSortAsc(Lo, iHi);
end;

// Fügt absteigenden Quicksort durch
procedure TCyclicList.QuickSortDesc(iLo, iHi: Cardinal);
var
  Lo, Hi, Mid: Cardinal;
  T: Variant;
begin
  Lo := iLo;
  Hi := iHi;
  Mid := Get((Lo+Hi)div 2);
  repeat
    while Get(Lo) > Mid do
      Inc(Lo);
    while Get(Hi) < Mid do
      Dec(Hi);
    if Lo <= Hi then
    begin
      T := Get(Lo);
      Put(Lo, Get(Hi));
      Put(Hi, T);
      Inc(Lo);
      Dec(Hi);
    end;
  until Lo > Hi;
  if Hi > iLo then
    QuickSortDesc(iLo, Hi);
  if Lo < iHi then
    QuickSortDesc(Lo, iHi);
end;

// Sortier auf- bzw. absteigend
procedure TCyclicList.Sort(SortMode: TSortMode = smAscending);
begin
  if SortMode = smAscending then
    QuickSortAsc(0, FCount-1)
  else
    QuickSortDesc(0, FCount-1);
end;

// Gibt den Wert eines zufälligen Knotens zurück.
function TCyclicList.GetRandom: Variant;
begin
  Result := GetNode(Random(count)).Data;
end;

// Erzeugt ein Iteratorobjekt. Wenn es mehrmals verwendet werden soll,
// muss es in einer Variable gespeichert werden.
function TCyclicLIst.MakeIterator: TIterator;
begin
  Result := TIterator.Create(Self, FFirst);
end;

constructor TIterator.Create(List: TCyclicList; FirstNode: TNode);
begin
  inherited Create;
  Self.List := List;
  Self.Node := FirstNode.Previous;
  FIndex := 0;
end;

// Gibt True zurück, wenn das Listenende erreicht wurde.
function TIterator.EndOfList: Boolean;
begin
  Result := Index = List.Count-1;
end;

// Gibt den nächsten Wert zurück.
function TIterator.Next: Variant;
begin
  Node := Node.Next;
  Result := Node.Data;
  FIndex := (FIndex+1) mod List.count;
end;

// Gibt den nächsten Wert als TObject zurück.
function TIterator.NextObject: TObject;
begin
  Result := TObject(Pointer(Integer(Next)));
end;

// Gibt den vorherigen Wert zurück.
function TIterator.Previous: Variant;
begin
  Node := Node.Previous;
  Result := Node.Data;
  FIndex := (FIndex-1) mod List.count;
end;

// Gibt den vorherigen Wert als TObject zurück.
function TIterator.PreviousObject: TObject;
begin
  Result := TObject(Pointer(Integer(Previous)));
end;

// Setzt den aktuellen Wert auf Data.
procedure TIterator.Put(Data: Variant);
begin
  Node.Data := Data;
end;

// Setzt den aktuellen Wert auf Obj.
procedure TIterator.PutObject(Obj: TObject);
begin
  Node.Data := Integer(Obj);
end;

// Springt Steps Elemente nach vorne.
procedure TIterator.JumpForward(Steps: Cardinal);
var
  I: Cardinal;
begin
  for I := 1 to Steps do
    Node := Node.Next;
  FIndex := (FIndex+Steps) mod List.count;
end;

// Springt Steps Elemente nach hinten.
procedure TIterator.JumpBackward(Steps: Cardinal);
var
  I: Cardinal;
begin
  for I := 1 to Steps do Node := Node.Previous;
  FIndex := (FIndex-Steps) mod List.count;
end;

// Gibt einen Wert an zufälliger Position zurück.
function TIterator.GetRandom: Variant;
begin
  Self.FIndex := Random(List.Count);
  Result := List.Get(FIndex);
end;

// Gibt einen Wert an zufälliger Position an TObject zurück.
function TIterator.GetRandomObject: TObject;
begin
  Result := TObject(Pointer(Integer(GetRandom)));
end;

end.

So, jetzt zu den Frage: Was ist das? Wozu brauche ich das?

Also:
Eine verknüpfte Liste ist eine Liste, die aus einzelnen Knoten (Nodes) besteht. Die Liste kennt jeweils Start- und Endknoten. Bei einer einfach verknüpften Liste kennt jeder Knoten seinen Nachfolger. Bei einer doppelt verknüpften Liste kennt jeder Knoten sowohl seinen Vorgänger als auch seinen Nachfolger.

Der Vorteil dieser Listen liegt darin, dass Manipulationen wie Einfügen, Löschen usw. von Einträgen sehr viel leichter als bei Listen mit dynamischen Arrays gemacht werden können. Außerdem können sie (so wie diese Liste) zyklisch sein.

Das heißt, dass der Nachfolger des letzten Knoten der Anfangsknoten ist und der Vorgänger des ersten Knoten der Endknoten ist.

Diese Listen lassen sich zum Beispiel für Quizfragen einsetzen (Beispiel im Anhang).

Ein Nachteil ist, dass diese Listen bei Abfragen sehr langsam sein können. An einer Optimierung arbeite ich noch.

Nun zur Erklärung der einzelnen Methoden:

• MakeIterator() - Erzeugt ein Iteratorobjekt zum Zugriff auf die Liste.
• Clear() - Löscht alle Elemente der Liste.
• IsEmpty() - Gibt zurück, ob die Liste leer ist
• GetNode(Index: Integer) - Gibt den Knoten mit dem gegebenen Index zurück. (Wenn der Index höher ist als der Index des letzten Knoten, dann wird vom Anfang weitergezählt, also bei 10 Knoten und Index 11 wird der 2. Knoten zurückgegeben)
• Get(Index: Integer) - Gibt den Wert des Knotens mit dem gegebenen Index zurück.
• Put(Index: Integer; Value: Variant) - Setzt den Wert des Knotens mit dem angegebenen Index auf value;
• Add(Data: Variant) - Fügt einen neuen Knoten am Ende der Liste hinzu mit dem Wert Data.
• Insert(Index: Integer; Data: Variant; InsertMode: TInsertMode = imAfter) - Fügt einen Knoten mit dem Inhalt Data vor (InsertMode=imBefore) oder hinter (InsertMode = imAfter) dem Knoten mit dem gegebenen Index hinzu.
• Delete(Index: Integer) - Löscht den Knoten mit dem gegebenen Index.
• Sort(SortMode: TSortMode = smAscending) - Sortiert die Liste aufsteigend (SortMode = smAscending) oder absteigend (SortMode = smDescending). Dafür wird der QuickSort-Algorithmus verwendet.
• GetRandom() - Gibt den Wert eines zufälligen Knotens zurück.

Außerdem gibt es noch einige Propertys:

• Count - Enthält die Gesamtanzahl an Knoten
• Items[Index: Integer] - Gibt einen Knoten mit gegebenen Index zurück. (Wie Get(Index))

EDIT: Jetzt eine neue Version mit einem Iteratorobjekt zum Zugriff auf die Liste. Funktioniert so:

Delphi-Quellcode:

var iterator: TIterator;
begin
  showmessage(iterator.Next);
end;

EDIT2: Wieder leicht überarbeitet und mit 3 Implementationen: TStack, TQueue, TDeque, alle abgeleitet von TCyclicList. Im Anhang.

[edit=Chakotay1308]Code (im Beitrag, *nicht* im Anhang) formatiert. Mfg, Chakotay1308[/edit]