doppelt verkettete listen

[tigerman33]

Das ist IMHO keine so gute Idee. Zumindest funktioniert sie nur, wenn einige (zusätzliche) Bedingungen, die du als gegeben vorausgesetzt hast erfüllt sind.

So muss zum Beispiel ein Element des Datentyps existieren, dass garantiert niemals angenommen wird (denn das benutzt du ja als Datum der Wurzel). Wenn du aber beispielsweise eine Liste von ganzen Zahlen verwalten willst, wird dieses Kriterium Probleme bereiten.

Zum anderen wird es schwieriger, gesicherte Aussagen über die einzelnen Listenelemente zu treffen, da als zusätzlicher Fall immer die Wurzel hinzukommt, die man beachten muss.

Außerdem ist es doch nicht so das Problem, die leere Liste auch als solche zu implementieren (sprich Wurzelknoten = nil <=> Liste leer). Erst recht, wenn man das ganze in einer anständige Klasse kapselt.

[alzaimar]

Zitat von tigerman33:

Das ist IMHO keine so gute Idee.

Wie willst Du dann in eine leere Liste das erste Element einfügen?

Zitat von tigerman33:

So muss zum Beispiel ein Element des Datentyps existieren, dass garantiert niemals angenommen wird (denn das benutzt du ja als Datum der Wurzel). Wenn du aber beispielsweise eine Liste von ganzen Zahlen verwalten willst, wird dieses Kriterium Probleme bereiten.

Die Prämisse, ein 'Alpha', also ein kleinstes Element zu verwenden, erhöht die Performance "beträchtlich", da eine Abfrage in der zentralen Routine (Suchen) entfällt. Der Code wird einfacher, weil es eben immer einen Anfang gibt. Zur Not kann man aber auch auf
Result^.Element := EinWertDerGarantiertKleinerAlsAlleJemalsEinzufuegendenElementeIst; verzichten. Dann kommt eben wieder eine kleine Abfrage hinzu (If Walker<>Root Then ...)

Zitat von tigerman33:

Zum anderen wird es schwieriger, gesicherte Aussagen über die einzelnen Listenelemente zu treffen, da als zusätzlicher Fall immer die Wurzel hinzukommt, die man beachten muss.

Nee, genau anders herum. Ich muss doch nie(!) die Wurzel beachten. Wie funktioniert denn der Code, wenn die leere Liste als 'Nil' deklariert ist?

Zitat von tigerman33:

Außerdem ist es doch nicht so das Problem, die leere Liste auch als solche zu implementieren (sprich Wurzelknoten = nil <=> Liste leer).

Zeig mal am Beispiel vom Verketten. Und zähle anschließend die Anzahl der Zeilen und die Performance.

Zitat von tigerman33:

Erst recht, wenn man das ganze in einer anständige Klasse kapselt.

Wie gesagt: Zeig mal.

[stoxx]

es macht sich sogar gut, wenn man nicht nur einen wurzelknoten, sondern sogar einen ungenutzen "Fußknoten" verwendet ( mit leerem nicht genutzten Inhalt)
man prüft also das Ende, ob Zeiger = Ende und nicht den Zeiger auf nil.
Das vereinfacht das ganze erheblich, da man im Code nicht die Fälle unterscheiden muss, ob man nun ein Element in der Mitte am Anfang oder am Ende einfügt.
Sondern man fügt es IMMER in der Mitte ein.

[tigerman33]

Zitat:

Zeig mal.

Gerne, aber nicht jetzt. Ich schreib nämlich diese und nächste Woche Klausuren und hab eigentlich keine Zeit.

Zitat:

Die Prämisse, ein 'Alpha', also ein kleinstes Element zu verwenden, erhöht die Performance "beträchtlich", da eine Abfrage in der zentralen Routine (Suchen) entfällt. Der Code wird einfacher, weil es eben immer einen Anfang gibt.

Hmm, da verstehe ich jetzt nicht so ganz was du mir sagen willst. Meinst du die einmalige Abfrage, ob Wurzel = nil? Und es bleibt immer noch das Problem, dass ein solches 'Alpha' nicht unbedingt existieren muss.

Zitat:

Zitat von tigerman33:

Zum anderen wird es schwieriger, gesicherte Aussagen über die einzelnen Listenelemente zu treffen, da als zusätzlicher Fall immer die Wurzel hinzukommt, die man beachten muss.

Nee, genau anders herum. Ich muss doch nie(!) die Wurzel beachten. Wie funktioniert denn der Code, wenn die leere Liste als 'Nil' deklariert ist?

Das bezog sich jetzt eigentlich nicht direkt auf Code, sondern auf "normalsprachliche" oder mathematische Aussagen über die Listenelemente etwa nach der Art "Alle Listendatümmer" () sind Zweierpotenzen" o.ä.

[simonko]

also das einfügen ist eigentlich ganz leicht.
du hast einen listenkopf der am anfang der liste zeigt.

du übergibst ihn einer prozedur und den wert den du einfügen willst

Delphi-Quellcode:

new(neu);
neu.inhalt:=wert;
..
if zeiger = nil then
...zeiger:=neu
else
  if neu.inhalt<zeiger.inhalt then begin
    neu^.naechster:=zeiger;
    zeiger:=neu;
  end
    else
      einfuegen(zeiger^.naechster,wert);

so in etwa. löschen ist mit doppeltverketten listen auch leicht. und ausgeben sowieso

aja und der parameter zeiger muss VAR sein

[alzaimar]

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..

[simonko]

ja aber meines ist besser :p ausserdem hab ich keine lust alle threads zu lesn

[daswurm]

huhu
danke schon mal für eure nette hilfe ... ich werde es mir morgen mal alles ganz genau ansehen und denn versuchen es selbst zu programmieren ... das kann ja ganz schön schwer werden, denn ich bin echt der meinung, dass ich in meiner noch recht jungen programmier laufbahn(2jahre) *g* noch nix schwierigeres gemacht habe. aba egal da muss ich wohl durch, wenn ich noch weitere fragen habe melde ich mal wieder *g* ... bei der netten hilfe komm ich echt gerne wieder
also rechnet damit dass ich bald wieder komme

[tigerman33]

Zitat:

Buuuuh! Zwinkern 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?

Na gut, aber wenn ich Freitag durchfalle mach ich dich verantwortlich (juhu...endlich einen Schuldigen gefunden!)

Delphi-Quellcode:

type PListElement = ^TListElement;
     TListElement = record
       Next: PListElement;
       Data: pointer; // Beispielsweise 
     end;
type TVList = class
     private
       FCount: integer;
       FWurzel: PListElement;
       function IsEmpty: boolean; inline;
       property RawItems[Index: integer]: PListElement read... // Den Code zum durchiterieren lass ich jetzt mal weg, ja?
     public
       property Count: integer read FCount;
       procedure Add(Element: pointer);
     end;

...
function EmptyList: TVList;
begin
  Result := TVList.Create;
end;

constructor TVList.Create;
begin
  FWurzel := nil;
  FCount := 0;
end;

function TVList.Empty: boolean;
begin 
  Result := FWurzel = nil;
end;

procedure TVList.Add(Element: pointer);
var InsIndex: integer;
    NewEl: PListElement;
begin
  if Empty then 
    InsIndex := 0 else
    InsIndex := GetInsIndex(Element);

  New(NewEl);
  if InsIndex <= Count - 1 then
    NewEl^.Next := RawItems[InsIndex];
  if InsIndex = 0 then
    Wurzel := NewEl else
    RawItems[InsIndex - 1].Next := NewEl;
end;

Das ist zwar natürlich nicht besonders sauber und beileibe nicht vollständig (außerdem ungetested), aber zumindest das Einfügen müsste so funktionieren. Dass die Funktion zum Einfüge-Index finden gegeben ist habe ich einfach mal angenommen. Das ließe sich zwar auch mit einem Methodenzeiger-Feld erledigen, aber so viel Arbeit wollte ich jetzt eigentlich nicht investieren.

//edit:
Okay, das

Zitat:

Eine leere Liste ist doch nicht Nichts, oder? Sondern eine 'leere Liste'.

ist natürlich ein Argument. Fragt sich nur, ob das programmiertechnisch irgendeinen Unterschied machen wird. Denn Konkatenation, Schnitt etc. musst du ja sowieso selbst implementieren.
Letztendlich handelt es sich also um verschiedene "Darstellungen" ein und desselben: Deine leere Liste wird charakterisiert durch "nur der Grundknoten vorhanden", meine durch "Wurzel = nil"

Ich sehe zwar mittlerweile, dass du namhafte Verstärkung auf deiner Seite hast, aber so ganz überzeug bin ich immer noch nicht.

PS: Wenn du mir jetzt sagst, dass mein Code länger ist, dann halte ich dem entgegen, dass da ja auch der ganze Klassenoverhead mit drinhängt (bis auf das was ich mir mal geschenkt habe...). Meine Add-Methode ist auch nicht viel länger als deine, und EmptyList sogar noch kürzer

//edit2:
Ooh, so ein Quark. EmptyList geändert.