Einzelnen Beitrag anzeigen

alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#16

Re: doppelt verkettete listen

  Alt 14. Dez 2005, 21:57
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..
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat