3. Einfuehrung - Einfach verkettete Listen

Einfuehrung - Einfach verkettete Listen

  • C

    virtuell Realisticer schrieb:

    Caipi schrieb:

    Ansonsten bzg. dem Design der Klasse schließe ich mich finix und hmmm ebenfalls an. Da ich dies für die bessere Variante halte. Ich lasse mich aber sehr gerne eines besseren belehren (wie gesagt, ich bin Noob 🙂 ).

    Wo genau siehst du die Probleme, dann koennen wir dahingehend was besseres
    ausarbeiten.

    Ich sehe eigentlich keine Probleme in der Art. Nur finde ich die Variante - wenn jeder Knoten eine eigene Klasse ist - irgendwie 'eleganter' und ich glaube diese wäre für einen absoluten Anfänger einen tick besser zu verstehen. D.h. wenn die Klasse, die die Knoten verwaltet getrennt ist von den einzelnen Knoten.

    Was meinst du? Ich lass mich gerne belehren 🙂

    Caipi

    0
  • F

    virtuell Realisticer schrieb:

    finix schrieb:

    Das würde ich nicht wirklich als einfach verkettete Liste durchgehen lassen - jeder Knoten hat ein Datenfeld (OK), Zeiger auf den nächsten Knoten (OK), Zeiger auf das Ende der Liste (Autsch!)

    Es ist gar nicht so unueblich, einen Zeiger aufs Ende der Liste zu haben. Sogar
    Sedgewick macht das in seinem Buch.

    Naja, hab den Sedgewick nicht hier um das zu verifizieren - will ja auch nicht sagen dass das nie einen Sinn haben könnte. Ich hab auch einen Zeiger auf das Ende - nur nicht in jedem Knoten. Das würde für mich spontan eher bei ner DoubleLinkedList mit Dummy-Tail Sinn machen - so müsstest du ja eigentlich bei jedem add die ganze Liste durchgehen und das Ende aktualisieren. Und die Liste allein mit Node implementiert hat Sicher seine Einsatzgebiete, aber den schnöden Container Of T würde ich nicht wirklich hinzuzählen.

    virtuell Realisticer schrieb:

    und vor allem: wofür steht "size"? Die Größe der Liste? Wenn ja, wieso wird sie nicht upgedated beim einfügen/löschen (nachfolgende Knoten)?

    In der Tat habe ich vergessen, es in die 'insert'-Funktion einzufuegen. In der
    'add'- und 'remove'-Funktion ist es drin.

    Ich steh immer noch vorm selben Problem - ich weiß nicht wirklich wofür size stehen soll 🙂
    Hab mir deine Klasse noch mal ein wenig genauer angeschaut, in add und insert sieht's aus wie

    size := size of list - position of node

    in remove(SingleLinkedList*) eher wie

    size := size of list

    es sei denn du hast vergessen die Vorgänger upzudaten.
    (edit: gerade den nächsten Punkt noch mal aufmerksam gelesen 😉 )

    virtuell Realisticer schrieb:

    Wie sinnvoll ist das eigentlich? Wenn's nicht die Listengröße ist, was ist "size" dann? Von Speicherverschwendung abgesehen.

    Man kann sich darueber streiten, ob ein paar Byte den Baeren dick machen oder
    nicht. Es ist auf jeden Fall schneller, als wenn du jedes mal erst die Liste
    durchlaufen musst, um die Anzahl Elemente zu zaehlen.

    Naja, ist immerhin sizeof(std::size_t) per Knoten + dem angesprochenen Aufwand um das ganze aktuell zu halten, auch wenn du vlt nur nach 300 oder 2000 oder 10000 add/insert/remove-calls mal die Größe haben möchtest, oder eben auch gar nicht.
    (Auch wenn's schon ein wenig betagt an, schau dir mal das SGI Rationale zu std::list an.)

    virtuell Realisticer schrieb:

    Und davon ausgehend kann man dann auch recht simpel Dummy-Elemente einführen, das ganze zu ner DoubleLinkedList ausbauen, etc...

    Ja, das ist korrekt. Das ist allerdings mit der anderen Variante auch kein
    Problem, da ich einfach nur einen prev-Zeiger benoetige ;).

    Hehe.. ja, dto hier. Wollte das bei deiner Lösung auch nicht in Abrede stellen.

    War mehr so der erste Gedanke der mir durch den Kopf schoss als ich den Threadtitel las: "Einführung - Einfach verkettete Liste. Einfach verkettet? WTF? Warum nicht doppelt?" 😃
    Obwohl's natürlich durchaus Sinn macht einfach zu anzufangen..

    0
  • J

    Vielleicht wäre es sinnvoll am Schluß noch kurz auf doppelt verkettet hinzuweisen und dann wichtig (vielleicht hab ich's auch übersehen) noch ein Hinweis auf std::list.

    0
  • S

    hier noch ein link zum thema.

    0
  • H

    Allgemein:
    Wie die meisten halte ich die Variante mit zwei Klassen (Liste/Node) für deutlich eleganter.

    C++-spezifisch:
    Wer in C++ einen Value-Type implementiert kommt nicht drum rum über Copy-Semantik zu reden. Konkret: Was mit fehlt ist ein Hinweis auf den Copy-Ctor, Assignment-Operator.

    0
  • ?

    hi!

    da findet man auch noch informationen zu ner einfach verketteten liste:
    http://zfx.info/Tutorials.php?ID=81

    cu

    0
  • F

    cplusplus. schrieb:

    da findet man auch noch informationen zu ner einfach verketteten liste:
    http://zfx.info/Tutorials.php?ID=81

    😮
    Da sollte man glaube ich niemanden ernsthaft drauf verweisen...

    0
  • W
     

    - Das Prinzip der einfach-verketteten Liste sollte bekannt sein / angewendet werden können
- Die Verwendung von Klassen unter C++ sollte verstanden sein und beherrscht werden

    Lol, was soll man denn in dem Tut noch lernen? Dass man vor Klassennamen ein XXX setzt?

    0
  • J

    Vor allem schreit seine Zieldefinition geradezu nach template... und dann nimmt er nen void*. Aber das ist bestimmt schneller! 🙄

    0
  • W

    hehe, geil! das ist mir ja garnicht aufgefallen. es lohnt sich scheinbar das ding komplett durchzulesen.

    0
  • V

    Caipi schrieb:

    virtuell Realisticer schrieb:

    Caipi schrieb:

    Ansonsten bzg. dem Design der Klasse schließe ich mich finix und hmmm ebenfalls an. Da ich dies für die bessere Variante halte. Ich lasse mich aber sehr gerne eines besseren belehren (wie gesagt, ich bin Noob 🙂 ).

    Wo genau siehst du die Probleme, dann koennen wir dahingehend was besseres
    ausarbeiten.

    Ich sehe eigentlich keine Probleme in der Art. Nur finde ich die Variante - wenn jeder Knoten eine eigene Klasse ist - irgendwie 'eleganter' und ich glaube diese wäre für einen absoluten Anfänger einen tick besser zu verstehen. D.h. wenn die Klasse, die die Knoten verwaltet getrennt ist von den einzelnen Knoten.

    Was meinst du?

    Ja, das sehe ich ein :).

    finix schrieb:

    so müsstest du ja eigentlich bei jedem add die ganze Liste durchgehen und das Ende aktualisieren.

    Das musst du nicht machen, es werden nicht alle Zeiger benutzt, da ja nur der
    Anfangsknoten die Liste verwaltet.

    Und die Liste allein mit Node implementiert hat Sicher seine Einsatzgebiete, aber den schnöden Container Of T würde ich nicht wirklich hinzuzählen.

    Ja, das habe ich mir auch schon gedacht. Da kommt dann meine schlechten Design-
    Faehigkeiten zum Zuge ;).

    Aber ich denke auch, dass zwei Klassen doch besser sind, so wie ihr es gesagt
    habt. Hab ich ehrlich gesagt gar nicht dran gedacht gehabt.

    Ich steh immer noch vorm selben Problem - ich weiß nicht wirklich wofür size stehen soll 🙂

    Nun, 'size' bedeutet, wie viele Elemente die Liste hat. Wenn ich das gerade
    recht im Sinn habe, dann ist das bei std::list<> doch genau so?

    Naja, ist immerhin sizeof(std::size_t) per Knoten + dem angesprochenen Aufwand um das ganze aktuell zu halten, auch wenn du vlt nur nach 300 oder 2000 oder 10000 add/insert/remove-calls mal die Größe haben möchtest, oder eben auch gar nicht.
    (Auch wenn's schon ein wenig betagt an, schau dir mal das SGI Rationale zu std::list an.)

    Das ist allerdings war. Habe ich auch nicht dran gedacht.

    Hehe.. ja, dto hier. Wollte das bei deiner Lösung auch nicht in Abrede stellen.

    War mehr so der erste Gedanke der mir durch den Kopf schoss als ich den Threadtitel las: "Einführung - Einfach verkettete Liste. Einfach verkettet? WTF? Warum nicht doppelt?" 😃
    Obwohl's natürlich durchaus Sinn macht einfach zu anzufangen..

    Naja, ich wollte erstmal die einfach verketteten Listen erklaeren. Ob das jetzt
    besser ist, weiss ich nicht. Das Prinzip der verketteten Listen bleibt ja
    eigentlich, unabhaengig ob ich einfach oder doppelt verkettete Listen habe,
    das selbe.

    Jester schrieb:

    Vielleicht wäre es sinnvoll am Schluß noch kurz auf doppelt verkettet hinzuweisen und dann wichtig (vielleicht hab ich's auch übersehen) noch ein Hinweis auf std::list.

    Einen hinweis auf doppelt verkettete Listen habe ich schon drin. Aber vielleicht
    ist es doch besser, diesen am Ende des Beitrags nochmal zu geben, damit man
    es nicht "ueberliesst". Und der Hinweis mit std::list, sollte in der Tat rein,
    da bin ich deiner Meinung.

    HumeSikkins schrieb:

    Allgemein:
    Wie die meisten halte ich die Variante mit zwei Klassen (Liste/Node) für deutlich eleganter.

    C++-spezifisch:
    Wer in C++ einen Value-Type implementiert kommt nicht drum rum über Copy-Semantik zu reden. Konkret: Was mit fehlt ist ein Hinweis auf den Copy-Ctor, Assignment-Operator.

    Ich werde das entsprechend ueberarbeiten.

    mfg
    v R

    0
  • H

    Ich hab den thread nur mal ganz kurz überflogen, also nicht aufrregen, wenn einiges schon besprochen wurde.

    1.) Was ist eine verkettete Liste

    Eine verkettete Liste ist eine Menge von Knoten, welche eine bestimmte
    Information speichern. Dabei gibt es einen Anfangsknoten und einen Endknoten
    und dazwischen endlich viele weitere Knoten. Der Anfangsknoten zeigt auf den
    naechsten Knoten, welcher wiederum auf den naechsten Knoten zeigt usw. Der
    vorletzte Knoten zeigt auf den Endknoten.

    Ich kenn das eher so:
    Eine Liste ist entweder eine leere Liste (Effektiv durch 0 repräsentiert) oder ein Knoten bestehend aus den zu speichernden Werten und einer weiteren Liste.
    So ist auch sofort der rekursive Character erkennbar

    Allgemein würde ich erst mal mit einer absolut minimalen Liste anfangen, die auch nur das ist, was eine Lsite ausmacht. Dinge, wie zeiger auf den letzten Knoten, größe speichern, etc. würde ich erstmal komplett weglassen. Schnickschnack kannste immernoch dazubauen.

    ---------------------------

    Vor allem bin ich froh, das ich mir mal 'ne kleine Bibliothek gebastelt habe, mit der man solche Datenstrukturen deutlich einfacher, wenn auch nicht unbedingt übermäßig performant umsetzen kann.

    Bei mir sähe eine Liste dann so aus:

    VARIANT (List)

CASE_0 (List, Nil)

CASE_2 (List, Cons, 
   int, head,
   List, tail
)

    Algorithmen müssen dementsprechend umgesetzt werden:

    size_t size (List const & list)
{
   MATCH (list)
      WITH0 (Nil)
         return 0;
      ELSE_WITH (Cons, cons)
         return 1 + size (cons->tail);
   END_MATCH
}

    -----------------------------

    Zurück zum Thema. Um liste generell zu erklären muss die Implementation nicht auf Geschwindigkeit achten. Lieber so aufbauen, dass es leicht leserlich ist:

    class NodeImpl {
   int head;
   shared_ptr<Node> tail;

   NodeImpl (int head) : head (head) {}

   NodeImpl (int head, shared_ptr<NodeImpl> tail) : head (head), tail (tail) {}
};

typedef shared_ptr<NodeImpl> Node;

Node node (int head) ( return Node (new NodeImpl(head)); }
Node node (int head, Node tail) ( return Node (new NodeImpl(head, tail)); }

size_t size (Node const & node)
{
   if (node.get() == 0) return 0;
   else return 1 + size (node->tail);
}

    So lassen sich sämmtliche gängige Algorithmen deutlich einfach aufbauen:

    int nth (Node const & node, size_t n)
{
   assert (node.get() != 0);

   if (n == 0) return node->head;
   else return nth (node->tail, n - 1);
}

int last (Node const & node)
{
   if (node->next.get() == 0) return node->head;
   else return last (node->tail);
}

template <typename F>
Node filter (Node const & node, F f)
{
   if (node.get() == 0) return node;
   else 
      if (f (node->head)) return node(node->head, filter (node->tail, f));
      else return filter (node->tail, f);
} 

template <typename M>
Node map (Node const & node, M m)
{
   if (node.get() == 0) return node;
   else return node(m (node->head), map (node->tail, m));
}

...

    Fehlen noch jede Menge standard-Algorithmen, wie Faltung, etc. Aber wie du sieht ist es so extrem einfach sie aufzubauen. Wenn man sie dann alle mal verstanden hat, kannste auch zu einer aufwendigen Listen-Implementation übergehen, die dann effizienter ist.

    0
Anmelden zum Antworten