Doppelt verkettete Liste sortieren

[Mr.P-Funk]

Was ist der beste Weg eine doppelt verkettete Liste zu sortieren?
Das Problem ist nicht der Sortieralgorythmus selbst [zb: Quicksort, Shellsort,...], sondern der Zugriff auf ein Element in der Liste?

Wenn man ein Array sortiert, hat man ja einen Index und somit einen direkten Zugriff.


Ein paar Lösungen die mir eigefallen sind:

1. Ein weiteres Feld für eine eindeutige ID in den record mitaufnehmen.
Funktion die sequentiell sucht und das Element zurückliefert.

Denke aber das es bei einer großen Liste wohl sehr lange dauert immer sequentiell zu suchen.


2. Einen Record mit 2 Feldern hinzufügen.

Delphi-Quellcode:

type
  TDAddress = record
  Value : string;
  PADR   : Pointer;
  end;

Ein DynArray von TDAddress anlegen. Dann in einer Schleife die Liste durchlaufen und den Wert nachdem sortiert werden soll in Value schreiben. In PADR kommt dann die Adresse von dem Element.
Das Array sortieren und anschließend die Liste anpassen.
Liste in das Array schreiben:

Delphi-Quellcode:

var 
    AoTDA : array of TDAddress;
    Runner: Pzeiger;
    i     : integer;
begin
  Runner := Root;
  i      := 0;
  while Runner <> NIL do
  begin
     inc(i);
     Setlength(AoTDA, Length(AoTDA)+1);
     AoTDA[i-1].PADR   := Pointer(Runner);
     AoTDA[i-1].Value  := Runner^.IRGENDWAS;  //Irgendwas ist der Wert nachdem sortiert werden soll 
     Runner := Runner^.next;
  end;
end;

Liste anpassen:

Delphi-Quellcode:

var i : integer;
    Runner : PZeiger;
begin
   Root       := AoTDA[low(AoTDA)].PADR;
   Root^.next := AoTDA[low(AoTDA)+1].PADR;
   Root^.prev := NIL;

   FOR i := low(AoTDA)+1 TO high(AoTDA)-1 DO begin
      Runner        := AoTDA[i].PADR;
      Runner^.prev  := AoTDA[i-1].PADR;
      Runner^.next  := AoTDA[i+1].PADR;
   end;

   Runner       := AoTDA[high(AoTDA)].PADR;
   Runner^.next := NIL;
   Runner^.prev := AoTDA[high(AoTDA)-1].PADR;
end;

Die 2 Variante benutze ich im moment, allerdings habe ich gehört das man das so nicht machen darf.
Hatte jemand mit sowas schonmal Erfahrungen gemacht? Gibt es eine Muster-, Standartlösung?