Einfuehrung - Einfach verkettete Listen

finix

Respekt vor der Mühe die du dir gemacht hast. Tolle Idee obendrein!

virtuell Realisticer schrieb:

Die Klasse ist sicherlich nicht perfekt. Viel mehr geht es um das Prinzip, welches hinter den verketteten Listen steckt.
[...]
Bitte unterlasst es, dumme Kommentare abzugeben. Die helfen uns
naemlich garantiert nicht dabei, das Thema verstaendlich
rueberzubringen!

Trotzdem 'ne kurze Anmerkung:

class SingleLinkedList {
    private:
        int    info;

        SingleLinkedList*    next; //zeiger auf naechsten knoten
        SingleLinkedList*    tail; //zeiger auf das ende der liste

        std::size_t size;
// ...
};

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!) 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)? Wie sinnvoll ist das eigentlich? Wenn's nicht die Listengröße ist, was ist "size" dann? Von Speicherverschwendung abgesehen.

Aber vielleicht verstehe ich die Klasse einfach nicht genau, soll auf jeden Fall kein dummer Kommentar sein.

Mein Vorschlag, genau wie hmmms (nur ohne prev;)):

struct Node
{
  Node( int data ) : data(data), next(0) { }
  int    data;
  Node*  next;
};

class SingleLinkedList
{
private:
  Node*        head;
  Node*        tail;
  std::size_t  size; // vlt auch eher OTF, um die "Navigation"
                     // in der Liste nochmal zu verdeutlichen
};

Mit zwei Klassen lässt sich das denke ich auch wesentlich einfacher auf deine hübschen Ascii-Zeichnungen übertragen
Die Methoden & Implementierung vielleicht auch erst im Laufe des Textes hinzufügen, genau dann wenn sie relevant werden und nicht schon vorher eine Riesenklasse mit Details hinklatschen.

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

Caipi

Ohne jetzt ein Nachredner sein zu wollen, aber:

finix schrieb:

Respekt vor der Mühe die du dir gemacht hast. Tolle Idee obendrein!

100% Ack. Sehr sozial!

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

Caipi

@virtuell Realisticer:
vielen dank für deine mühe, deine erklärung ist echt ganz toll! kannst du das für ne doppelt verkettete liste auch noch so schön zeigen? was ich weiss hast du da noch einen pointer der auf das vorige element zeigt...

cu

virtuell Realisticer

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.

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.

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.

Aber vielleicht verstehe ich die Klasse einfach nicht genau, soll auf jeden Fall kein dummer Kommentar sein.

So habe ich es auch nicht aufgefasst

Mein Vorschlag, genau wie hmmms (nur ohne prev;)):

struct Node
{
  Node( int data ) : data(data), next(0) { }
  int    data;
  Node*  next;
};

class SingleLinkedList
{
private:
  Node*        head;
  Node*        tail;
  std::size_t  size; // vlt auch eher OTF, um die "Navigation"
                     // in der Liste nochmal zu verdeutlichen
};

Ok, so kann man es auch machen. Ich schau mir das mal alles noch etwas genauer
an.

Mit zwei Klassen lässt sich das denke ich auch wesentlich einfacher auf deine hübschen Ascii-Zeichnungen übertragen

Ja, die waren eine Qual

Die Methoden & Implementierung vielleicht auch erst im Laufe des Textes hinzufügen, genau dann wenn sie relevant werden und nicht schon vorher eine Riesenklasse mit Details hinklatschen.

Nun, die Funktionalitaet, die wir haben wollten habe ich ja vorher festgelegt.
Man kann sich natuerlich darueber streiten, ob dass jemanden beim Lesen sofort
ueberfordert, oder ob das andere besser ist.

Die Frage ist jetzt natuerlich, wie wuerden es gerne die Leute sehen, die noch
nicht bis gar keine Erfahrung mit Listen haben, vielleicht kann der ein oder
andere von denen auch was dazu sagen.

Vor allem dazu, wo etwas unverstaendlich oder zu kompliziert erklaert ist.

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

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.

marsi schrieb:

@virtuell Realisticer:
vielen dank für deine mühe, deine erklärung ist echt ganz toll! kannst du das für ne doppelt verkettete liste auch noch so schön zeigen? was ich weiss hast du da noch einen pointer der auf das vorige element zeigt...

Das hatte ich auch vor. Ich muss schauen, wie ich das Zeitmaessig hinbekomme.
Allerdings sollte dashier vorher moeglichst perfekt sein, damit ich bei den
doppelt verketteten Listen nicht die gleichen Fehler mache

mfg
v R

Caipi

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

finix

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

Jester

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.

Sunday

hier noch ein link zum thema.

HumeSikkins

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.

hi!

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

cu

finix

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

Walli

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

Jester

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

Walli

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

virtuell Realisticer

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

Helium

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.