Einfuehrung - Einfach verkettete Listen
-
Morgen allerseits,
mir ist aufgefallen, dass in den letzten Wochen des oefteren Fragen ueber
verkettete Listen gestellt worden sind. Das hat mich mal dazu angeregt, etwas
dazu zu schreiben, um die Idee und Funktionalitaet, welche hinter verketteten
Listen steckt, aufzuzeigen.Vorweg:
Ich habe vor, das Ganze anhand einer Klasse 'SingleLinkedList' zu erklaeren. Die
Klasse ist sicherlich nicht perfekt. Viel mehr geht es um das Prinzip,
welches hinter den verketteten Listen steckt.Verbesserungsvorschlaege sind immer willkommen.
Ich hoffe meine schlechte Faehigkeit zu erklaeren ist nicht zu gross
Bitte unterlasst es, dumme Kommentare abzugeben. Die helfen uns
naemlich garantiert nicht dabei, das Thema verstaendlich
rueberzubringen!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.Zur Verdeutlichung:
Anfangsknoten: K0
Knoten: K1, K2, ..., Kn
Endknoten: Kn+1------ ------ ------ ------ ------ | K0 |------>| K1 |------>| K2 |->..->| Kn |----->|Kn+1| ------ ------ ------ ------ ------Was wir hier sehen, ist eine single linked list. Wir koennen hier auch eine
wesentliche Eigenschaft einer solchen erkennen:**
single linked lists haben die Eigenschaft, dass sie jeweils nur auf den
naechsten Knoten in der Liste zeigen.
**D. h., befinden wir uns beim Knoten K1, so haben wir keine Information ueber
den Knoten K0. Wir koennen aber weiter zu Knoten K2 gehen.Um es schon einmal vorweg zu nehmen: Das ist eine negative Eigenschaft der
single linked list. Deswegen gibt es auch die doppelt verkettete Liste (double
linked list). Zu ihr werde ich ein andermal einen Beitrag schreiben.Was sind die Vorteile?
Nehmen wir einmal an, wir haben einen vector<int> V mit, sagen wir mal, 1000
Elementen. Und nun wollen wir an V[500] ein neues Element einfuegen. Was muss
gemacht werden? Es muss umkopiert werden, denn alle Elemente ab V[500+1]
verschieben sich um ein Element nach rechts.Nehmen wir nun eine verkettete Liste L, mit gleich vielen Elementen, wie V.
Was muss gemacht werden, um an L[500] ein neues Element Lneu einzufuegen?Wir muessen folgende Schritte erledigen:
[] L[500-1] muss nun auf Lneu zeigen
[] L[500] (Lneu) muss auf L[500+1] zeigenHier ist auch schoen zu sehen, wie spaeter die verketteten Listen realisiert
werden: Mit Zeiger auf den jeweils folgenden Knoten.**
Es werden keine Elemente umkopiert, sondern lediglich zwei Zeiger verbogen.
**Der Nachteil ist, man muss durch die Liste bis zur gewuenschten Position
iterieren.Schauen wir uns das mal etwas naeher an und entwerfen eine Klasse
SingleLinkedList. Was soll diese Klasse leisten?[] Wir wollen eine Information in Form eines Integers speichern (was letztlich
gespeichert wird, ist voellig egal) und drauf zugreifen koennen
[] Wir wollen der Liste neue Knoten hinzufuegen koennen
[] Wir wollen aus der Liste Knoten entfernen koennen
[] Wir wollen einen Knoten an eine beliebige Position innerhalb der Liste
einfuegen und loeschen koennenUnsere Klasse sieht wie folgt aus:
class SingleLinkedList { private: int info; SingleLinkedList* next; //zeiger auf naechsten knoten SingleLinkedList* tail; //zeiger auf das ende der liste std::size_t size; public: SingleLinkedList(); SingleLinkedList(const int& info); ~SingleLinkedList(); int getInfo() const { return info; } void setInfo(const int& i) { info = i; } std::size_t getSize() const { return size; } SingleLinkedList* getNext() const { return next; } SingleLinkedList* find(const int& info); //knoten an das ende anhaengen mit 'info' als inhalt void add(const int& info); //neuen knoten mit 'info' an position 'position' einfuegen void insert(const int& info, std::size_t position); //knoten an position 'position' entfernen void remove(std::size_t position); //diesen knoten entfernen void remove(SingleLinkedList* sll); };Nun, unsere CTors sehen wie folgt aus:
SingleLinkedList::SingleLinkedList() : info(0), next(0), tail(this), size(0) { } SingleLinkedList::SingleLinkedList(const int& info) : info(0), next(0), tail(this), size(0) { add(info); }Der erste erzeugt keinen Knoten in der Liste, waehrend der zweite einen neuen
Knoten mit der zu speichernden Information 'info' erzeugt.Unseren Anfangsknoten stellt hier 'this' dar, welcher jedoch keine
Information speichert.Schauen wir uns den DTor an:
SingleLinkedList::~SingleLinkedList() { SingleLinkedList* hlp = next, *tmp; while(hlp) { tmp = hlp; //1 hlp = hlp->next; //2 tmp->next = 0; //3 delete tmp; } }Hier wird die komplette Liste durchlaufen, angefangen beim ersten Knoten. Damit
wir uns den Knoten nicht 'wegloeschen', wird er in der Variablen 'tmp'
zwischengespeichert und hlp auf den naechsten Knoten gesetzt. Jetzt wird
'tmp->next' auf 0 gesetzt, damit der DTor von 'tmp' uns nicht die Liste weg-
loescht und wir somit beim delete einen Speicherzugriffsfehler produzieren.Wir koennen das Ganze so veranschaulichen:
//zu (1), hlp zeigt auf den ersten knoten ------ ------ ------ ------ ------ | tmp| = | hlp|------>| K2 |->..->| Kn |----->|Kn+1| ------ ------ ------ ------ ------'tmp' zeigt nun auf hlp und 'tmp->next' auf 'K2'. Jetzt koennen wir im naechsten
Schritt 'hlp' auf 'K2' zeigen lassen (ACHTUNG: ich rede nicht von 'hlp->next')://zu (2), hlp zeigt jetzt auf K2 (hlp = hlp->next) ------ ------ ------ ------ | hlp| = | K2 |->..->| Kn |----->|Kn+1| ------ ------ ------ ------Nun koennen wir 'tmp->next' auf 0 setzen. Das ist vorher nicht moeglich gewesen,
da wir sonst die Information zu 'hlp->next' geloescht haetten. Wir erinnern uns,
dass nach dem ersten Schritt, 'tmp' == 'hlp' ist.Letztlich kann 'tmp' ohne weiteres geloescht werden und das Ganze spielchen geht
von vorne los, bis wir an das Ende der Liste kommen. Hier ist 'hlp' durch
die Anweisung 'hlp->next' auf '0' gesetzt worden und die Schleife wird somit
verlassen.Nun brauchen wir aber auch noch die Funktion 'add' um ein Element an das Ende
der Liste anhaengen zu koennen. Sie sieht wie folgt aus:void SingleLinkedList::add(const int& info) { SingleLinkedList* newNode = new SingleLinkedList(); newNode->info = info; tail->next = newNode; tail = tail->next; ++size; }Zunaechst einmal erzeugen wir einen neuen Knoten und weisen diesem die zu
speichernde Information zu. 'tail' zeigt auf den letzten Knoten in der Liste.
Durch die Zuweisung von 'newNode' an 'tail->next', wird newNode an das Ende
der Liste angehangen:------ ------ ------ ------ ------------ | K0 |------>| K1 |------>| K2 |->..->|tail|----->|tail->next| ------ ------ ------ ------ ------------ //tail->next zeigt nun auf newNode ------ ------ ------ ------ --------- | K0 |------>| K1 |------>| K2 |->..->|tail|----->|newNode| ------ ------ ------ ------ --------- //und im letzten schritt, tail wieder auf den letzten knoten zeigen lassen ------ ------ ------ ------ --------- | K0 |------>| K1 |------>| K2 |->..->| Kn |----->|newNode| ------ ------ ------ ------ _--------- /| / ------ |tail| ------Nun haben wir unsere 'add'-Funktion fertig und koennen bereits Knoten der
Liste hinzufuegen. Allerdings nur an das Ende der Liste. Wir wollen aber auch
in der Lage sein, ein Element an einer beliebigen Position innerhalb der Liste
hinzuzufuegen. Hierzu haben wir die Funktion 'insert':void SingleLinkedList::insert(const int& info, std::size_t position) { if(position > size) return; if(position == size) add(info); //ans ende der liste anhaengen else { SingleLinkedList* hlp = this, *newNode = new SingleLinkedList; newNode->info = info; /* wir bewegen uns in der liste zur gewuenschten position */ while(position--) hlp = hlp->next; //der neue knoten zeigt nun auf den neuen, den auf ihn nachfolgenden knoten newNode->next = hlp->next; //der vorhergehende knoten zeigt nun auf den neuen knoten hlp->next = newNode; } }Schauen wir uns das einmal genauer an, wir wollen z. b. einen Knoten an
Position 11 hinzufuegen. Dazu durchlaufen wir die Liste, bis wir an der
Position angekommen sind.--------- |newNode| (zeigt auf noch gar nix) --------- ------ ------ ------ ------ ------ | K10|------>| K11|------>| K12 |->..->| Kn |----->|Kn+1| ------ ------ ------ ------ ------ /|\ | ------ |hlp | ------'newNode' wird zwischen 'K10' und 'K11' eingefuegt. 'newNode' hat also 'K10'
und 'K11' als Nachbarn. 'K10->next' muss auf 'newNode' zeigen und
'newNode->next' auf 'K11'. Nach der Anweisung 'newNode->next = hlp->next',
sieht das Ganze wie folgt aus:--------------- |newNode->next| --------------- | \|/ ------ ------ ------ ------ ------ | K10|------>| K11|------>| K12 |->..->| Kn |----->|Kn+1| ------ _------ ------ ------ ------ /|\ /| | / ---------------- |hlp |hlp->next| ----------------Damit ist der neue Knoten aber noch nicht vollstaendig in die Liste integriert.
Was noch fehlt ist, dass 'K10' auf 'newNode' zeigt. Das erledigt die Anweisung
'hlp->next = newNode' (zu beachten: hlp == K10)------ --------- ------ ------ ------ ------ | K10|------>|newNode|------>| K11|------>| K12 |->..->| Kn |----->|Kn+1| ------ ----_---- ------ ------ ------ ------ /|\ /| | / | / | / ---------------- |hlp |hlp->next| ----------------Nun wollen wir noch Knoten loeschen koennen. Hierzu haben wir zwei Funktionen,
einmal die remove-Funktion, welche lediglich die Position entgegennimmt und
einem diejenige, welche einen Knoten erwartet:void SingleLinkedList::remove(std::size_t position) { if(position > size) return; if(position == size) remove(tail); else { SingleLinkedList* hlp = next; while(position--) hlp = hlp->next; remove(hlp); } }Wenn die Position gleich dem Ende ist, wird der letzte Knoten entfernt.
Ansonsten durchlaufen wir die Liste bis zu der Position, wo der Knoten entfernt
werden soll und rufen dann die zweite remove-Funktion auf, welche folgenden
Aufbau hat:void SingleLinkedList::remove(SingleLinkedList* sll) { //auf den anfang der liste zeigen SingleLinkedList* hlp = this; while(hlp) { //ist der naechste knoten der gesuchte? if(hlp->next == sll) { //dann next auf den uebernaechsten knoten zeigen lassen hlp->next = sll->next; sll->next = 0; //zu loeschenden knoten entfernen delete sll; sll = 0; --size; break; } //auf naechsten knoten zeigen lassen hlp = hlp->next; } }Warum schauen wir uns hier 'hlp->next' an und warum nicht 'hlp'? Die Antwort
ist recht einfach:Nehmen wir einmal an, der dritte Knoten ist der gesuchte. 'hlp' wird Anfangs auf
'next' und nicht auf 'this' gesetzt. Dann kommen wir durch 'hlp = hlp->next'
irgendwann zu folgender Situation:------ ------ ------ ------ ------ ------ | K0 |------>| K1 |------>| K2 |----->| K3 |------>| Kn |------>|Kn+1| ------ ------ ------ ------ ------ ------ /|\ | ------ |hlp | ------Jetzt haben wir aber ein Problem: Denn wir haben keinen Bezug mehr zu 'K2',
koennen also 'K2->next' nicht auf 'K4' umbiegen. Loeschen wir 'K3', so wird
'K2->next' ungueltig. Ein Zugriff auf 'K2->next' fuehrt daher zu UB.Daher schauen wir uns 'hlp->next' an. Hier ist 'hlp', in unserem Beispiel,
gleich 'K2' und 'hlp->next' gleich 'K3':---------------- | sll|sll->next| ---------------- | \ | \ \/ \/ ------ ------ ------ ------ ------ ------ | K0 |------>| K1 |------>| K2 |----->| K3 |------>| Kn |------>|Kn+1| ------ ------ ------ -_---- ------ ------ /|\ /| | / ---------------- |hlp |hlp->next| ----------------'hlp->next', und somit 'K2->next', wird auf den uebernaechsten Knoten gesetzt
und 'sll->next' auf 0. Damit ergibt sich folgendes Bild und 'sll' bzw. 'K3'
kann problemlos entfernt werden:---------------- | sll|sll->next| ---------------- _______|_ \| / | \ _\ 0 / \/ \__ / / ------ ------ ------ ------ /\ ------ ------ | K0 |------>| K1 |------>| K2 | | K3 |-- -->| Kn |------>|Kn+1| ------ ------ ------ ------ / ------ ------ /|\ _______/ | / ---------------- |hlp |hlp->next| ----------------Ascii-Zeichnungen sind was tolles, ich hoffe man sieht, was passiert ist.
'sll->next' und 'K3->next' zeigen nun auf 0. 'K2->next' und 'hlp->next' zeigen
auf den uebernaechsten Knoten (hier Kn).Letztlich wird K3 entfernt und die Operation 'remove' ist abgeschlossen.
Zum Schluss haben wir noch eine find-Funktion, mit der wir nach einem
gespeicherten Wert suchen und den entsprechenden Knoten zurueckgeben koennen:SingleLinkedList* SingleLinkedList::find(const int& info) { SingleLinkedList* hlp = next; while(hlp) { if(hlp->info == info) return hlp; hlp = hlp->next; } return 0; }Diese Funktion durchlaeuft einfach die Liste und sucht nach 'info'. Wird 'info'
gefunden, wird der entsprechende Knoten zurueckgeliefert. Ansonsten 0.Damit bin ich eigentlich auch schon am Ende :). Ein Testprogramm zeigt, dass
die Liste funktioniert:int main(int argc, char **argv) { SingleLinkedList* list = new SingleLinkedList(); for(size_t i = 0; i < 10; ++i) list->add(i); SingleLinkedList* item = list->find(5); if(item) cout<<"Gefunden: "<<item->getInfo()<<endl; item = item->getNext(); list->remove(5); if(!list->find(5)) cout<<"Gut, 5 nicht mehr gefunden"<<endl; list->remove(item); if(!list->find(6)) cout<<"Gut, 6 auch nicht mehr gefunden"<<endl; list->insert(5, 5); item = list->find(5); if(item) cout<<"Da isse wieder: "<<item->getInfo()<<endl; list->remove(5); delete list; return 0; }So, ich glaube ich habe zwischendurch des oefteren mal den Ueberblick beim
schreiben verloren.
Ich hoffe, dass das Prinzip klar geworden ist.
Und jetzt duerft ihr den Beitrag zerreissen :D.mfg
v R
-
Konstruktive Kritik:
Für relativ fortgeschrittene Programmierer sicher einen Blick wert aber für Anfänger ist das ganze imho vollkommen ungeeignet.
Du willst zuviel erklären und die wirklich wichtigen Grundlagen bleiben dabei auf der Strecke. So könnte ein Anfänger viel mehr mit einer simplen
class Node { public: // prev, next };, wovon mehrere aneinander gehangen werden mehr anfangen. Danach hätte man ja weiter gehen können. Aber die leute die hier immer fragen wie so etwas geht haben gerade mal Pointer so halb verstanden, wie gesagt das ist denke ich viel zu viel für die
-
Hallo,
Du willst zuviel erklären und die wirklich wichtigen Grundlagen bleiben dabei auf der Strecke.
Von welchen konkreten Grundlagen sprichst du? Das kann man ja mit einbauen.
So könnte ein Anfänger viel mehr mit einer simplen
class Node { public: // prev, next };, wovon mehrere aneinander gehangen werden mehr anfangen. Danach hätte man ja weiter gehen können.
Ok, man haette erst einmal eine kleine Klasse machen koennen und diese dann
im laufe des Beitrags weiter ausbauen., wovon mehrere aneinander gehangen werden mehr anfangen. Danach hätte man ja weiter gehen können. Aber die leute die hier immer fragen wie so etwas geht haben gerade mal Pointer so halb verstanden, wie gesagt das ist denke ich viel zu viel für die
Da hast du sicherlich recht. Aber man fangt ja immer und immer wieder an zu
erklaeren. Vielleicht kann man dann ja auf diesen Thread verweisen.Habe ich zu kompliziert erklaert? Ich habe gehoft, dass es mit der bildlichen
Darstellung vielleicht etwas klarer wird, als wenn man es sich nur im Kopf
vorstellt.mfg
v R
-
Am Anfang geht es auch richtig gut los, nur danach machst du irgendwie so einen merkwürdigen Sprung
Unter "Was ist eine verkettete Liste" hättest du ruhig ein wenig ausführlicher werden dürfen, vielleicht 1-2 wirklich ganz kurze Beispiele wie man so etwas implementiert und damit umgeht. Damit ein wenig das Gefühl dafür kommt.
Wie gesagt, dass sind nur meine 2 Eurocent
-
hmmm23525 schrieb:
Am Anfang geht es auch richtig gut los, nur danach machst du irgendwie so einen merkwürdigen Sprung
Unter "Was ist eine verkettete Liste" hättest du ruhig ein wenig ausführlicher werden dürfen, vielleicht 1-2 wirklich ganz kurze Beispiele wie man so etwas implementiert und damit umgeht. Damit ein wenig das Gefühl dafür kommt.
Du meinst Beispiele im Sinne von Code, oder? Dachte die Zeichnung sei Aussage-
kraeftig genug. Aber das ist ok. Du meinst sowas:class List { public: List* next; }; List* kopf, *ende; //neues element List* myList = new List; kopf = myList; //kopf zeigt auf erstes element ende = myList; //ende zeigt auf, im moment, einziges element List* newElem = new List; //neues element an liste ranhaengen kopf->next = newElem; newElemt->next = 0; ende = newElem;Aber ist sowas einfacher zu verstehen? Die Frage ist, versucht man dann nicht
evtl. zu sehr, dem Pointer-Wirrwar zu folgen?Ist da meine Zeichnung nicht vielleicht etwas besser zu verstehen, wo einfach
nur gezeigt wird, dass ein Knoten auf einen anderen zeigt etc.?Ich frage ernsthaft :).
mfg
v R
-
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...
-
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
-
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 machemfg
v R
-
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
-
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 wiesize := size of list - position of nodein remove(SingleLinkedList*) eher wie
size := size of listes 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..
-
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.
-
hier noch ein link zum thema.
-
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=81cu
-
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...
-
- Das Prinzip der einfach-verketteten Liste sollte bekannt sein / angewendet werden können - Die Verwendung von Klassen unter C++ sollte verstanden sein und beherrscht werdenLol, was soll man denn in dem Tut noch lernen? Dass man vor Klassennamen ein XXX setzt?
-
Vor allem schreit seine Zieldefinition geradezu nach template... und dann nimmt er nen void*. Aber das ist bestimmt schneller!
-
hehe, geil! das ist mir ja garnicht aufgefallen. es lohnt sich scheinbar das ding komplett durchzulesen.
-
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