Doppelt verkettete Liste sortieren

[negaH]

Der schnellste und effizientes Weg ist die unsortierten Einträge der Liste A in eine neue Liste B sortiert einzufügen. Man kann dies noch beschleunigen indem man zur ListB ein Array mit Ln2(ListA.Count) Pointern benutzt. In diesem Array wird ein Zeiger auf das jeweils ListB.Count/Ln2(ListA.Count) Element/Node gespeichert. Beim Enfügen einer Neuen Node wird nun dieses Array per QuickFind durchsucht um die Anfangsnode ab der die Liste itertiert werden muß zu finden. Dies beschleunigt ungemein das sortierte Einfügen in deine ListeB.
Das Zusatzarray wird von Anfang an auf ListA.Count Elemente initialisiert und dann deren enthaltene Pointer nur succesive nach dem Einfügen/Umkopieren der Node geupdatet. Bei diesem Update kann man sich weiter beschränken indem man nur die beiden "Rand" Nodes in diesem Array korregiert.

Hm, ich glaube nicht das ich das verständlich rübergebracht habe

Gruß Hagen