Zitat von
tigerman33:
Zitat:
Zeig mal.
Gerne, aber nicht jetzt. Ich schreib nämlich diese und nächste Woche Klausuren und hab eigentlich keine Zeit.
Buuuuh!
Das ist aber eine Ausrede, denn die paar Zeilen solltest Du in 2 Minuten heruntergetippt haben: Es ist ja einfacher, als meine 5 Zeilen, oder?
Die leere Liste besteht aus genau einem Element, der Wurzel. Eine leere Liste ist doch nicht Nichts, oder? Sondern eine 'leere Liste'.
Die Wurzel kann ein 'Alpha' (also ein kleinstes vorstellbares Element beinhalten) oder auch nicht. Ich arbeite meistens mit 'Alpha', weil es, wie gesagt, einen Vergleich spart. Das mit dem Alpha war übrigens dezenter Quark
. Kein Wunder, das Du das nicht kapiert hast. Um Performance zu sparen, sollte man ein 'Omega' haben, also ein Element, das größer als alles Andere ist (siehe stoxx's Vorschlag)
Ich korrigiere also meinen Code:
Delphi-Quellcode:
Function LeereListe : PListenElement;
Begin
New(Result);
Result^.Element := EinWertDerGarantiertGrößerAlsAlleJemalsEinzufuegendenElementeIst;
Result^.Next := Result;
Result^.Prev := Result;
End;
Ich implementiere Linked Lists nicht mehr. Verwenden tu ich sie auch nicht, dafür gibts schliesslich SkipLists oder Dictionaries.
Schau mal in der einschlägigen Literatur (Wirth, Algorithms & Datastructures von Leiserson & Rivest, Sedgewick oder die Bibel:Knuth, etc.). Ist ja nicht auf meinem Mist gewachsen.
Die Idee, noch ein Tail zu verwenden ist äquivalent mit einer zirkulären Liste. Beide Versionen sind charmant, aber nicht ganz so trivial wie die 'reine Liste'. Dafür zu Ende gedacht.
@simonko: Das Einfügen hatte ich bereits kodiert..