doppelt verkettete listen

[alzaimar]

Ich würde Listen/Bäume etc., also verkettete Strukturen immer mit einem 'Wurzelknoten' beginnen. Dann sollte der Rest ohne Probleme gehen. Ob man die zirkulär oder nicht implementiert ist dann eigentlich Wurscht, soweit ich mich erinnere (o.k. eine Abfrage fällt weg).

Delphi-Quellcode:

Procedure EinfuegenInListe (EinWert : string; EineListe : PListenElement);
Var
  Q : PListenElement;

Begin
  P := FindeEinfuegePosition (EineListe, EinWert); // P ist das größte Element, das kleiner als EinWert ist.
  New (Q);
  Q^.Next := P^.Next;    // Der Nachfolger vom neuen Knoten Q ist der alte Nachfolger von P
  P^.Next := Q;          // Der neue Nachfolger von P ist Q.
  Q^.Prev := P;          // Der Vorgänger vom neuen Knoten ist P (den haben wir ja deswegen gesucht)
  If Q^.Next<>Nil Then   // Wenn der neue Knoten überhaupt einen Nachfolger hat, dann 
     Q^.Next^.Prev := Q; // ist Q der Vorgänger des Nachfolgers von Q (irgendwie logisch)
End;

Die 'leere Liste' wird einfach so initialisiert:

Delphi-Quellcode:

Function LeereListe : PListenElement;
Begin
  New(Result);
  Result^.Element := EinWertDerGarantiertKleinerAlsAlleJemalsEinzufuegendenElementeIst;
  Result^.Next := Nil;
  Result^.Prev := Nil;
End;

Wenn man die Liste zirkulär machen will (also dann zeigt das letzte Element nicht ins Leere, sondern wieder auf das vorderste Element, bzw. die Wurzel, dann sieht das so aus:

Delphi-Quellcode:

Procedure EinfuegenInListe (EinWert : string; EineListe : PListenElement);
Var
  Q : PListenElement;

Begin
  P := FindeEinfuegePosition (EineListe, EinWert); // P ist das größte Element, das kleiner als EinWert ist.
  New (Q);
  Q^.Next := P^.Next;    // Der Nachfolger vom neuen Knoten Q ist der alte Nachfolger von P
  P^.Next := Q;          // Der neue Nachfolger von P ist Q.
  Q^.Prev := P;          // Der Vorgänger vom neuen Knoten ist P (den haben wir ja deswegen gesucht)
  Q^.Next^.Prev := Q; // Q ist der Vorgänger des Nachfolgers von Q (irgendwie logisch)
End;

Die 'leere Liste' wird einfach so initialisiert:

Delphi-Quellcode:

Function LeereListe : PListenElement;
Begin
  New(Result);
  Result^.Element := EinWertDerGarantiertKleinerAlsAlleJemalsEinzufuegendenElementeIst;
  Result^.Next := Result;
  Result^.Prev := Result;
End;

Hier noch die Funktion zum Finden der Position:

Delphi-Quellcode:

Function FindeEinfuegePosition (EineListe : PListenElement; EinWert : TListenDatenTyp) : PListeElement;
       External 'IrgendwasMussJaAufDeinemMistGewachsenSein.DLL';

Ach ja: Alles aus dem Gedächtnis, ungetestet und eventuell fehlerhaft...