[A]Algorithmen/Datenstrukturen: Einfach-/Doppeltverkettete Listen
-
Inhaltsverzeichnis
- Einleitung
- Struktur von Listen
- Einfachverkette Listen
- Doppeltverkette Listen
- Fazit
1 Einleitung
...
-
Hi,
dein Listen-Artikel wird vermutlich Teil 2 sein, da ich denke dass Vector, Queue und Stack vor der Liste behandelt werden sollten.
GPC
-
Hi GPC,
haben wir den schon einen Autor für Queue usw.? Wenn der Artikel vorher erscheint, ist das meiner Ansicht nach OK. Wenn nicht, dann würde ich es verwirrend finden, wenn Teil 2 vor Teil 1 kommt.
Grüsse
Tobi
-
Das einfachste wäre doch, einfach Überschriften ohne "Teil 1", "Teil3" usw zu vergeben, da ich kaum denke, dass die Artikel in der korrekten Reihenfolge fertig gestellt werden. Die Artikel werden ja wohl eh unabhängig voneinander geschrieben sein. Wenn dann mal alle Artikel fertig und veröffentlicht sind, kann man ja immer noch sowas wie "Teil 1" usw. in der Überschrift reineditieren.
-
Ok,
bin auch für den Vorschlag von nep. Und darum mach ich das jetzt er[edit]s[/edit]t einmal.
-
Tobias Gerg schrieb:
Hi GPC,
haben wir den schon einen Autor für Queue usw.? Wenn der Artikel vorher erscheint, ist das meiner Ansicht nach OK. Wenn nicht, dann würde ich es verwirrend finden, wenn Teil 2 vor Teil 1 kommt.
Grüsse
TobiDu glaubst doch wohl selbst net das Teil2 vor Teil1 kommt
BR
Vinzenz
-
Tobias Gerg schrieb:
haben wir den schon einen Autor für Queue usw.?
ja, CStoll hat Interesse bekundet.
Tobias Gerg schrieb:
Ok,
bin auch für den Vorschlag von nep. Und darum mach ich das jetzt er[edit]s[/edit]t einmal.
ACK.
-
Inhaltsverzeichnis
- Einleitung
- Struktur von Listen
- Einfachverkette Listen
- Doppeltverkette Listen
- Fazit
1 Einleitung
Um effiziente Programme erstellen zu können, braucht man immer wieder verschiedene Datenstrukturen auf denen dann verschiedene Algorithmen laufen müssen. In dieser Artikelreihe werden wir uns mit diversen Datenstrukturen und auch einigen Algorithmen befassen.Speziell in diesem Artikel werde ich einen kleinen Einblick in einfach- bzw. doppeltverkettete Listen geben. In den einzelnen Kapiteln wird durch Beispiele gezeigt, wo und wie Listen verwendet werden können.
2 Struktur von Listen.
Um Listen darstellen zu können benötigt man zu Beginn erst einmal das Aussehen eines Listenelementes. Das könnte beispielsweise so aussehen./* C Variante */ struct Listenelement { /* Zu verwaltende Daten im Listenelement */ /* ... */ /* Zeiger auf das nächste Element */ Listenelement* next; /* Bei einer Doppeltverkettung benötigen wir auch noch */ /* einen Zeiger auf das vorherige Element */ Listenelement* prev; }; /* cpp Variante */ class Listenelement { public: Listenelement() { } Listenelement(/*übergabe von zu speichernden Daten*/) { /*Daten initialisieren*/ } private: // Die Listenzeiger Listenelement* next; Listenelement* prev; };Neben der Struktur für das Listenelement brauchen wir noch das Aussehen für die Liste selbst. Normalerweise würde uns ein Zeiger auf ein Listenelement genügen, allerdings ist es geschickter sich eine eigene Struktur bzw. Klasse für die Liste zu definieren, da listenspezifische Dinge wie etwa die Anzahl der Listenelemente in dieser Struktur/Klasse gespeichert werden können.
Die Liste selbst könnte dann wie folgt aussehen.
/* C Variante */ struct Liste { /* Listenbeginn */ Listenelement* start; /* Anzahl der Elemente */ int Elementanzahl; }; /* cpp Variante */ class Liste { public: Liste { } Liste(/*übergabe von zu speichernden Daten*/) { /*Daten initialisieren*/ } private: /* Listenbeginn */ Listenelement* start; /* Anzahl der Elemente */ int Elementanzahl; };
-
Sollte es in C nicht so aussehen:
/* C Variante */ struct Listenelement { /* Zu verwaltende Daten im Listenelement */ /* ... */ /* Zeiger auf das nächste Element */ struct Listenelement* next; /* Bei einer Doppeltverkettung benötigen wir auch noch */ /* einen Zeiger auf das vorherige Element */ struct Listenelement* prev; };Das struct vor "Listenelement" ist afaik in C essentiell wenn kein typedef dafür da ist.
BR
Vinzenz
-
Upps,
danke hast natürlich recht. S****ß Leichtsinnsfehler.
-
Inhaltsverzeichnis
- Einleitung
- Struktur von Listen
- Einfachverkette Listen
- Doppeltverkette Listen
- Fazit
1 Einleitung
Um effiziente Programme erstellen zu können, braucht man immer wieder verschiedene Datenstrukturen auf denen dann verschiedene Algorithmen laufen müssen. In dieser Artikelreihe werden wir uns mit diversen Datenstrukturen und auch einigen Algorithmen befassen.Speziell in diesem Artikel werde ich einen kleinen Einblick in einfach- bzw. doppeltverkettete Listen geben. In den einzelnen Kapiteln wird durch Beispiele gezeigt, wo und wie Listen verwendet werden können.
2 Struktur von Listen.
Um Listen darstellen zu können benötigt man zu Beginn erst einmal das Aussehen eines Listenelementes. Das könnte beispielsweise so aussehen./* C Variante */ struct Listenelement { /* Zu verwaltende Daten im Listenelement */ /* ... */ /* Zeiger auf das nächste Element */ struct Listenelement* next; /* Bei einer Doppeltverkettung benötigen wir auch noch */ /* einen Zeiger auf das vorherige Element */ struct Listenelement* prev; }; /* cpp Variante */ class Listenelement { public: Listenelement() { } Listenelement(/*übergabe von zu speichernden Daten*/) { /*Daten initialisieren*/ } private: // Die Listenzeiger Listenelement* next; Listenelement* prev; };Neben der Struktur für das Listenelement brauchen wir noch das Aussehen für die Liste selbst. Normalerweise würde uns ein Zeiger auf ein Listenelement genügen, allerdings ist es geschickter sich eine eigene Struktur bzw. Klasse für die Liste zu definieren, da listenspezifische Dinge wie etwa die Anzahl der Listenelemente in dieser Struktur/Klasse gespeichert werden können.
Die Liste selbst könnte dann wie folgt aussehen.
/* C Variante */ struct Liste { /* Listenbeginn */ struct Listenelement* start; /* Anzahl der Elemente */ int Elementanzahl; }; /* cpp Variante */ class Liste { public: Liste { } Liste(/*übergabe von zu speichernden Daten*/) { /*Daten initialisieren*/ } private: /* Listenbeginn */ Listenelement* start; /* Anzahl der Elemente */ int Elementanzahl; };
-
Salute,
ich muss noch mal stören. Ich sehe gerade, dass du sowohl die C als auch die C++ Variante zeigst... hat das nen bestimmten Grund? Mir wäre es, wenn du nur eine zeigst. Entweder C oder C++. Ich würde C vorschlagen, da es u.a. einfacher is, den C Code auf C++ umzusatteln, als von C++ auf C runter zu müssen. Du kannst aber auch gerne C++ nehmen. Oder anders gesagt: Nimm die Sprache, in der du fitter bist
Wir könnten ja die Parallelimplementierung als Download zur Verfügung stellen, das wäre imo ein guter Mittelweg. Oder?
Grüße
GPC
-
OK,
ich wollt es halt für beide machen. Aber dann mach ich es in C und die C++ Variante kommt dann als Download mit rein.
Grüsse
Tobi
-
Gut, aber wie gesagt, wenn du lieber die C++ Variante zeigen und die C als Download anbieten willst, kein Problem.
-
Inhaltsverzeichnis
- Einleitung
- Struktur von Listen
- Einfachverkette Listen
- Doppeltverkette Listen
- Fazit
1 Einleitung
Um effiziente Programme erstellen zu können, braucht man immer wieder verschiedene Datenstrukturen auf denen dann verschiedene Algorithmen laufen müssen. In dieser Artikelreihe werden wir uns mit diversen Datenstrukturen und auch einigen Algorithmen befassen.Speziell in diesem Artikel werde ich einen kleinen Einblick in einfach- bzw. doppeltverkettete Listen geben. In den einzelnen Kapiteln wird durch Beispiele gezeigt, wo und wie Listen verwendet werden können.
2 Struktur von Listen.
Um Listen darstellen zu können benötigt man zu Beginn erst einmal das Aussehen eines Listenelementes. Das könnte beispielsweise so aussehen./* C Variante */ struct Listenelement { /* Zu verwaltende Daten im Listenelement */ /* ... */ /* Zeiger auf das nächste Element */ struct Listenelement* next; /* Bei einer Doppeltverkettung benötigen wir auch noch */ /* einen Zeiger auf das vorherige Element */ struct Listenelement* prev; };Neben der Struktur für das Listenelement brauchen wir noch das Aussehen für die Liste selbst. Normalerweise würde uns ein Zeiger auf ein Listenelement genügen, allerdings ist es geschickter sich eine eigene Struktur bzw. Klasse für die Liste zu definieren, da listenspezifische Dinge wie etwa die Anzahl der Listenelemente in dieser Struktur/Klasse gespeichert werden können.
Die Liste selbst könnte dann wie folgt aussehen.
/* C Variante */ struct Liste { /* Listenbeginn */ struct Listenelement* start; /* Anzahl der Elemente */ int Elementanzahl; //... };Die Basisoperationen bei verketteten Listen sind "Element einfügen" und "Element löschen". Implementierungen dieser und weiterer Operaptionen werden in den nächsten beiden Kapiteln gezeigt.
3 Einfachverkettete Listen
-
Hallo!
Ich habe das hier mal kurz überflogen und habe ein paar Empfehlungen dazu. Das Netz ist voll von Tutorials mit doppelt verketteten Listen.
Leider wird bei 99% dieser Listen eine etwas ungeschickte Implementierung verwendet, indem das Ende der Liste durch einen Null-Pointer markiert wird.Ich kann hier noch nicht erkennen, was es mal werden soll, würde aber, auch um den Artikel von anderen ein bißchen abzuheben auf jeden Fall eine andere Variante ohne Null als Ende vorschlagen. Das ist afaik auch der Weg, den die meisten STL-Implementierungen gehen. Die Einführung eines Dummy-Knotens macht die Suche performanter, erleichtert die Implementierung von Iteratoren und macht den Code einfacher. Man bezahlt dafür nur die Kosten für den Speicher eines einzelnen ListNodes.
MfG Jester
edit: da ich auf dem Forumtreffen sowas in der Art eh in nem Vortrag erzählen werde, kann ich Dir gerne ein paar Folien dazu schicken (auch wenn die alles andere als ausführlich sind).
-
Hallo Jester,
erstmal danke für die Tipps.
Ich hatte nicht vor, das Ende der Liste mit einem Nullpointer zu makieren. Auch die Idee mit dem Dummy Knoten ist mir schon gekommen. Mal sehen wie ich das realisiere. Muss wohl meine alten Vorlesungsunterlagen nochmal durchkauen ;).
Für die Folien wäre ich dir dankbar.
Grüsse
Tobi
-
Inhaltsverzeichnis
- Einleitung
- Struktur von Listen
- Einfachverkette Listen
- Doppeltverkette Listen
- Fazit
1 Einleitung
Um effiziente Programme erstellen zu können, braucht man immer wieder verschiedene Datenstrukturen auf denen dann verschiedene Algorithmen laufen müssen. In dieser Artikelreihe werden wir uns mit diversen Datenstrukturen und auch einigen Algorithmen befassen.Speziell in diesem Artikel werde ich einen kleinen Einblick in einfach- bzw. doppeltverkettete Listen geben. In den einzelnen Kapiteln wird durch Beispiele gezeigt, wo und wie Listen verwendet werden können.
2 Struktur von Listen.
Um Listen darstellen zu können benötigt man zu Beginn erst einmal das Aussehen eines Listenelementes. Das könnte beispielsweise so aussehen./* C Variante */ struct Listenelement { /* Zu verwaltende Daten im Listenelement */ /* ... */ /* Zeiger auf das nächste Element */ struct Listenelement* next; /* Bei einer Doppeltverkettung benötigen wir auch noch */ /* einen Zeiger auf das vorherige Element */ struct Listenelement* prev; };Neben der Struktur für das Listenelement brauchen wir noch das Aussehen für die Liste selbst. Normalerweise würde uns ein Zeiger auf ein Listenelement genügen, allerdings ist es geschickter sich eine eigene Struktur bzw. Klasse für die Liste zu definieren, da listenspezifische Dinge wie etwa die Anzahl der Listenelemente in dieser Struktur/Klasse gespeichert werden können.
Die Liste selbst könnte dann wie folgt aussehen.
/* C Variante */ struct Liste { /* Listenbeginn */ struct Listenelement* start; /* Anzahl der Elemente */ int Elementanzahl; //... };Die Basisoperationen bei verketteten Listen sind "Element einfügen" und "Element löschen". Implementierungen dieser und weiterer Operaptionen werden in den nächsten beiden Kapiteln gezeigt.
3 Einfachverkettete Listen
Bei einfachverketteten Listen gibt es "nur" eine Vorwärtsverkettung. Das bedeutet, dass jeder Knoten nur seinen Nachfolger, nicht aber seinen Vorgänger kennt.[bild]
...
[/bild]Im folgenden bauen wir uns eine Liste mit Beispieldaten auf. Die aneinanderzuhängenden Informationen sind hierbei der Einfachheit halber Integerwerte.
3.1 Die klassische Implementierung
Zunächst das Listenelement (die Node)typedef struct ListNode { int data; /* hier steht ein beliebiger Datentyp (auch Stukturen) */ ListNode* next; };Dann benötigen wir unsere Listenstruktur
typedef struct List { ListNode* begin; int ElementCounter; List() { begin = NULL; ElementCounter = 0; } };Als nächster Schritt ist eine Ein- bzw Anfügen Operation zu realisieren.
// unsortiertes Einfügen in die Liste int InsertIntoList(List* list, int data) { //keine Liste? Schlecht! return if(!list) return 1; //Liste leer? if(list->begin == NULL) { // platz reservieren list->begin = (ListNode*)malloc(sizeof(ListNode)); // Malloc schlägt fehl if(!(list->begin)) return 1; // Daten schreiben list->begin->data = data; list->begin->next = NULL; } //ansonsten else { // Laufknoten ListNode* node; node = list->begin; // ans Ende hangeln while(node->next != NULL) node = node->next; // Speicher reservieren node->next = (ListNode*)malloc(sizeof(ListNode)); if(!node) return 1; // Daten schreiben node->next->data = data; node->next->next = NULL; } ++(list->ElementCounter); return 0; }[Anmerkung: Den Code verbessere ich noch war jetzt nur mal aus dem Kopf hingefrickelt]
Als nächstes braucht es natürlich noch eine Löschoperation
...
-
Tobias Gerg schrieb:
int InsertIntoList(List* list, int data) { //keine Liste? Schlecht! return if(!list) return 1; //Liste leer? if(list->begin == NULL) { // platz reservieren list->begin = (ListNode*)malloc(sizeof(ListNode)); // Malloc schlägt fehl if(!(list->begin)) return 1; // Daten schreiben list->begin->data = data; list->begin->next = NULL; } //ansonsten else { // Laufknoten ListNode* node; node = list->begin; // ans Ende hangeln while(node->next != NULL) node = node->next; // Speicher reservieren node->next = (ListNode*)malloc(sizeof(ListNode)); if(!node) return 1; // Daten schreiben node->next->data = data; node->next->next = NULL; } ++(list->ElementCounter); return 0; }naja, man versteht irgendwie, wie du drauf kommst.
den ElementCounter würde ich wegwerfen und auch void returnen.das ans-ende-hangeln verstehe ich nicht. füge doch am anfang ein.
und dann hilft von der naiven implemetierung zum ferrari der listen volkards bewähtes 5-punkte-tuning für verhettete listen.
schritt1:
oder du willst unbedingt ne lifo und keine fifo, dann merk die anfangs- und endezeiger. problem: zu viel if unf alles schwer zuz lesen und zu schreiben.schritt2:
mach nen ring draus. ein bisschen if geht schon weg.schriit3:
und merk die den letzten knoten statt beiden. member gespart und updatearbeit.schritt4:
leg am anfang nen dummyknoten an, und merk dir den. sorge damit dafür, daß die liste nie leer ist. kein if mehr!
schritt5:
mach noch die indirektion weg, indem der dummyknoten selbst dein member ist und nicht ein zeiger drauf.die ganzen schritte würde ich am insert vormachen. jede zwischenstufe ausprogrammiert. die anderen methoden kann man dann direkt an den ferrari löten.
außerdem ist die verwandlung der nativen implementierung in den ferrari bei der doppelt verketteten liste besser und am ende steht auch eine vollständige klasse da, an der nichts fehlt oder ungeschickt ist.
bei der einfach verketteten liste haste eine remove-methode der zeitkomplexität o(n). die wirste fein los mit nem iterator, der aufs vorgängerelement zeigt (nebst wunderbarkeit, daß remove(it);++it; geht und der iterator nicht zerstört wurde). da wäre es vielleicht nett, die dopplet verkettete vor der einfach verketteten zu machen.
-
volkard schrieb:
(nebst wunderbarkeit, daß remove(it);++it; geht und der iterator nicht zerstört wurde). da wäre es vielleicht nett, die dopplet verkettete vor der einfach verketteten zu machen.
Aber das löschen könnte andere Iteratoren invalidieren, obwohl ihre Knoten nicht gelöscht werden. Klingt unschön.
Vielleicht kann man in singly linked-lists einfach kein schönes delete anbieten.