Doppelt Verkettete Liste C++ Beispiel Essay

Einführung

Stellen wir uns vor, wir schreiben ein Programm, welches eine Filmsammlung verwalten soll. Einfachheitshalber werden nur Merkmale wie Titel, Erscheinungsjahr und Genre erfasst.

Diese Daten werden in einer Datenstruktur zusammengefasst.

struct Film { std::string titel; unsigned int jahr; int genre; };

Jetzt stellt sich die Frage wie die Filme in unserem Programm intern dargestellt werden.
Man könnte ein Array mit Filmen anlegen.

const int filmAnzahl = 100; Film filme[filmAnzahl];

So weit so gut. Wir programmieren das Programm fertig und verschicken es an alle unseren Bekannte und Freunde. Es dauert nicht lange bis sich einer von ihren beschwert, dass das Programm nicht mehr als 100 Filme verwalten kann. Es bleib uns nichts anderes übrig als den Quellecode des Programms abzuändern um die Filmenanzahl anzupassen. Nicht gerade optimal.

Man könnte auch gleich ein Array für 10000 Filme anlegen, damit auch der größte Filmfreak zufrieden ist, aber dann nimmt man in Kauf, dass das Programm den Arbeitsspeicher unnötig blockiert, wenn vielleicht nur 200 Filme verwaltet werden.

Wie man sieht, ist die Verwendung eines statischen Arrays in diesem Fall nicht optimal. Man benötigt eine dynamische Datenstruktur, die nur sowieso Objekte verwaltet, die auch wirklich nötig sind. Wohl die einfachste dynamische Datenstruktur ist eine einfach verkettete Liste.

Einfach verkettete Liste

Eine Liste ist eine Kette aus beliebig vielen Listenelementen (Knoten), die untereinander über Zeiger verbunden sind. Die Anzahl von Elementen kann zu Laufzeit des Programms beliebig variieren.

Jedes Listenelement besteht aus dem Datenbereich und einen Zeiger, der auf das nächste Listenelement zeigt. Mit dem Datenbereich ist eine oder mehrere Variablen gemeint, die die eigentlichen Daten(Werte, Strings u.s.w.) speichern.

Schematische Darstellung eines Listenelements:

Ein einzelnes Element hat keine Informationen über seine Position in der Liste. Alles was es weiß, ist die Adresse seines Nachfolgers. Eine Abbildung soll das ganze Prinzip noch mal verdeutlichen.

Schematische Darstellung einer einfach verketteter Liste mit vier Elementen:

Das erste Element in der Liste wird als Listenkopf (head oder root) bezeichnet und das letzte als Listenende (tail). Da das letzte Element keinen Nachfolger hat, wird der Zeiger auf Null gesetzt, damit man später das Listenende erkennen kann.
So eine Liste wird als einfach verkettet bezeichnet, da die Elemente untereinander nur eine 1-fache Verbindung haben. Es gibt auch eine doppelt verkettete Liste, aber dazu kommen wir später.

Kommen wir zu der Implementierung.

// Definition eines Listenelements struct Listenelement { // Das sind die Daten die wir verwalten wollen (Datenbereich) Film film; // Zeiger auf den Nachfolger (Zeiger) Listenelement *nachfolger; };

Damit haben wir ein Listenelement definiert, auf dem wir unsere Liste aufbauen.
Wie wir bereits wissen, beginnt die Liste mit einem Listenkopf, also erstellen wir dynamisch einen.

// Listenkopf erstellen Listenelement *listenkopf = new Listenelement();

Da der Listenkopf auch ein Element der Liste ist müssen wir es auch mit Daten belegen.

// Listenkopf mit Daten belegen listenkopf->film.titel = "Stargate"; listenkopf->film.jahr = 2005; listenkopf->film.genre = 1; // Den Zeiger auf Null setzen, da kein weiteres Element in der Liste existiert listenkopf->nachfolger = NULL;

Nach dem der Listenkopf erstellt wurde, können weitere Listenelemente in die Liste eingefügt werden.
Die Erzeugung von Elementen erfolgt durch dynamische Speicherreservierung.

// Ein Listenelement erzeugen Listenelement *neuesListenelement = new Listenelement(); // Element mit Daten belegen neuesListenelement->film.titel = "V"; neuesListenelement->film.jahr = 2009; neuesListenelement->film.genre = 1; neuesListenelement->nachfolger = NULL;

Nach dem ein neues Listenelement erstellt wurde, hat es noch keine Verbindung zum Listenkopf.

Symbolische Darstellung von beiden Elementen im RAM:

Um die Elemente zu verbinden, müssen wir den Nachfolgerzeiger vom Listenkopf auf das zweite Listenelement (neuesListenelement) setzen.
Und das geschieht durch eine einfache Adressenzuweisung.

// Listenkopf mit neuesListenelement verbinden listenkopf->nachfolger = neuesListenelement;

Symbolische Darstellung von beiden verbundenen Elementen im RAM:

Um mit einer Liste produktiv arbeiten zu können, erstellen wir eine Klasse und implementieren elementarste Listenoperationen.

// Grundgerüst class FilmListe { // Definition eines Listenelements class Listenelement { public: // Konstruktor Listenelement(Film film) { this->film.genre = film.genre; this->film.jahr = film.jahr; this->film.titel = film.titel; this->nachfolger = NULL; } // Das sind die Daten die wir verwalten wollen (Datenbereich) Film film; // Zeiger auf den Nachfolger (Zeiger) Listenelement *nachfolger; }; // Listenkopf Listenelement* kopf; // Listenende Listenelement* ende; public: // Konstruktor FilmListe(void) { kopf = ende = NULL; } // Destruktor ~FilmListe() { } // einen Film in die Liste einfügen void hinzufuegen(Film film) { // ... } // prüft ob die Liste leer ist bool istLeer() { return (kopf == NULL) ? true : false; } // Liste löschen void loeschen(void) { // ... } // zeigt alle Listenelemente void elementeAnzeigen(void) { // ... } };

Wie man ein neues Element erstellen haben wir bereits gesehen. Man erstellt dynamisch ein neues Element und lässt den Zeiger im letzten Element auf das neue Objekt zeigen. Wir müssen uns also merken, welches Element an der letzten Position ist. Dazu wird das Attribut Listenelement* ende verwendet. Dieses wird nach jedem einfügen in die Liste aktualisiert.

Zusätzlich muss unterschieden werden ob die Liste leer ist oder nicht, denn in einer leeren Liste können wir nicht auf das letzte Element zugreifen.

Zusammengenommen ist die Methode recht überschaubar.

// einen Film in die Liste einfügen void hinzufuegen(Film film) { // Ein neues Listenelement erstellen und mit 'film' initialisieren Listenelement *neuesListenelement = new Listenelement(film); // liste ist leer if(istLeer()) ende = kopf = neuesListenelement; else { // das letzte Element zeigt auf das neue Element ende->nachfolger = neuesListenelement; // das neue Element wird zum Letzten ende = neuesListenelement; } }

Damit wir überhaupt überprüfen können ob die Liste wie gewünscht funktioniert, brauchen wir eine Methode die uns den Listeninhalt auf den Bildschirm bringt.

// zeigt alle Listenelemente void elementeAnzeigen(void) { // aktueller Knoten Listenelement *p = kopf; // solange der Knoten nicht Null ist, also das Ende nicht erreicht ist... while(p != NULL) { // ...Inhalt ausgeben std::cout << "Titel: "<< p->film.titel.c_str() << " Jahr: " << p->film.jahr << " Genre: " << p->film.genre << std::endl; // der Nachfolger wird zum aktuellen Knoten p = p->nachfolger; } }

Der Eifrige hat bereits den Code kompiliert und ausgeführt, doch das war ein etwas zu früh. Warum? Beim Erstellen eines neuen Elementes reservieren mit new Arbeitsspeicher und geben diesen nicht wieder frei. Doch das sollten wir, wenn wir nicht wollen, dass unser Computer wegen eines Arbeitsspeicherfehlers abstürzt. Also bauen wir uns eine Funktion, die die komplette Liste löscht und den reservierten Speicher wieder frei gibt.

Wir müssen bedenken, dass wir mit dem letzten Element anfangen müssen und dann von hinten nach vorne alle Elemente nacheinander löschen sollten. Würden wir zum Beispiel von vorne anfangen und das erste dynamisch erzeugte Element löschen, würden wir die Adresse zum nächsten Element verlieren und könnten dieses dann nicht finden bzw. löschen.

Eine weitere Schwierigkeit ist, dass wir mit einer einfach verketteter Liste arbeiten, d.h. wir können uns in der Liste nur in eine Richtung bewegen, nämlich nach vorne.

Wir löschen immer das letzte Element in der Liste, dass uns bereits bekannt ist. Zuerst müssen wir aber das vorletzte Element finden, damit wir den Zeiger für den nächsten Durchgang auf null setzen können.
Dieser Vorgang wird so lange wiederholt bis die Liste nur aus einen Element besteht – den Listenkopf. Dieser wird anschließend separat gelöscht.

// Liste löschen void loeschen(void) { if(istLeer()) return; // solange der Zeiger nicht Null ist, also noch Elemente vorhanden sind... while(kopf->nachfolger != NULL) { // ...suche das vorletzte ELement Listenelement *vorletztesElement = kopf; while(vorletztesElement->nachfolger != ende) { vorletztesElement = vorletztesElement->nachfolger; } // lösche das letzte Element delete ende; // das vorletzte Element wird zum Letzten vorletztesElement->nachfolger = NULL; ende = vorletztesElement; } // zuletzt noch den Listenkopf löschen delete kopf; }

Somit hätten wir eine einfache Implementierung einer einfach verketteten Liste.
Kompletten Quellcode downloaden: Einfach verkettete Liste (2086 Downloads)

Unsere Implementierung funktioniert zwar, ist aber bei Weitem nicht optimal. Zum Beispiel ist die Liste auf eine feste Datenstruktur festgelegt. Man bräuchte also für verschiedene Datenstrukturen unterschiedliche Listenklassen, was selbstverständlich nicht akzeptabel ist.
Des Weiteren ist das Löschen sehr langsam, weil für jedes Listenelement die ganze Liste durchgelaufen werden muss.
Allgemein kann man diese Implementierung nur bedingt in der Praxis einsetzen. Sie verdeutlicht aber die Funktionsweise einer verketteten Liste.

Im zweiten Teil des Tutorials implementieren wir eine doppelt verkettete Liste.

Für Kritik, Anregungen, Fragen oder Verbesserungsvorschläge steht wie immer die Kommentarfunktion zu Verfügung.

Referenz:

Einleitung

Im ersten Teil des Tutorials haben wir gesehen, wie eine einfach verkettete Liste aufgebaut ist und welche Nachteile sie besitzt.
In diesem Abschnitt werden wir diese Nachteile eliminieren und so eine brauchbare Liste bekommen, die sich sehen lassen kann. Um mehr Flexibilität zu erreichen, werden wir auf das Konzept der Template-Klassen zurückgreifen. Grundkenntnisse der Templates sind also eine Voraussetzung um dieses Tutorial zu verstehen, allerdings gibt’s hier eine Minieinführung zu diesen interessanten Themengebiet.
Fangen wir gleich damit an.

Template – Klassen

Mit Hilfe von Template-Klassen lässt sich ein Datentyp in einer Klasse variieren ohne, dass dafür die Klassendeklaration geändert werden muss.

Wenn eine neue Instanz der Liste erstellt werden soll, so muss nur angegeben werden, welchen Datentyp die Liste verwalten soll.

Ein Beispiel einer Template-Klasse.

template <typename T > class Classname { public: Classname (void); ~ Classname (); void setData(const T &data); const T &getData(void) const; private: T data; };

Die Zeile template < typename T > sagt dem Compliler, dass es sich um eine Template-Klasse handelt und dass der frei wählbare Datentyp „T“ heißt. Das „T“ hätte genauso gut „Datentyp“ heißen können, denn der Typname ist frei wählbar und die Namensgebung erfolgt nach den gleichen Regeln wir bei Variablen. Allerdings ist die Bezeichnung „T“ etwas wie ein Standard geworden und ich werde hier im Weiteren auch „T“ verwenden.

Die Implementierung der Methoden hat auch eine eigene Syntax.

// Konstruktor template < typename T > Classname <T>:: Classname (void) { } // Destruktror template < typename T > Classname <T>::~ Classname () { } // Setzt Daten template < typename T > void Classname <T>::setData(const T &data) { this->data = data; } // Liest Daten template < typename T > const T &Classname<T>::getData(void) const { return data; }

Die Schreibweise ist gewöhnungsbedürftig aber nicht weiter schwierig und erfolgt immer nach dem gleichen Schema.

template < typename T> Rückgabetyp KlassenName<T>::Methodenname(...)

Das Erstellen einer Instanz.

// eine Instanz für die Verwaltung von int-Variablen erstellen TemplateKlasseListe<int> listeFuerInt; // eine Instanz für die Verwaltung von float-Variablen erstellen TemplateKlasseListe<float> listeFuerFloat;

Und noch was sehr wichtiges. Normalerweise ist man in C++ gewöhnt, Klassendeklaration in *.h-Dateien und Klassenimplementierung in *.cpp-Dateien auszulagern. Dies geht mit Template-Klassen nicht. Alles muss in einer *.h-Datei liegen oder man lagert die Implementierung in *.inl-Dateien aus.
Ich werde alles in liste.h schreiben.

Mit diesem Wissen können wir die Listenimplementierung aus dem ersten Tutorial als eine Template-Klasse schreiben.

Einfach verkettete Liste als Template-Klasse

Wir schreiben die Klasse der einfach verketteten Liste als Template. Hier sollte für Sie nichts Neues zu finden sein, denn es handelt sich dabei um altbekannte Methoden und Attribute aus dem ersten Teil des Artikels.

// Grundgerüst template<typename T> class Liste { private: // Definition eines Listenelements class Listenelement { public: // Konstruktor Listenelement(T daten) { this->daten = daten; nachfolger = NULL; } // Zeiger auf den Nachfolger Listenelement *nachfolger; // Das sind die Daten die wir verwalten wollen ( Datenbereich) T daten; }; // Listenkopf Listenelement* kopf; // Listenende Listenelement* ende; public: // Konstruktor Liste(void); // Destruktor ~Liste(void); // einen Film in die Liste einfügen void hinzufuegen(T daten); // prüft ob die Liste leer ist bool istLeer(void) { return (kopf == NULL) ? true : false; } // Liste löschen void loeschen(void); }; // Konstruktor template<typename T> Liste<T>::Liste(void) { kopf = ende = NULL; } // Destruktor template<typename T> Liste<T>::~Liste() { // beim zerstören der instanz, die liste immer leeren loeschen(); } // einen Film in die Liste einfügen template<typename T> void Liste<T>::hinzufuegen(T daten) { // Ein neues Listenelement erstellen und mit 'daten' initialisieren Listenelement *neuesListenelement = new Listenelement(daten); // liste ist leer if(istLeer()) ende = kopf = neuesListenelement; else // am ende der Liste einfügen { // das letzte Element zeigt auf das neue Element ende->nachfolger = neuesListenelement; // das neue Element wird zum Letzten ende = neuesListenelement; } } // Liste löschen template<typename T> void Liste<T>::loeschen(void) { if(istLeer()) return; // solange der Zeiger nicht Null ist, also noch Elemente vorhanden sind... while(kopf->nachfolger != NULL) { // ...suche das vorletzte ELement Listenelement *vorletztesElement = kopf; while(vorletztesElement->nachfolger != ende) { vorletztesElement = vorletztesElement->nachfolger; } // lösche das letzte Element delete ende; // das vorletzte Element wird zum Letzten vorletztesElement->nachfolger = NULL; ende = vorletztesElement; } // zuletzt noch den Listenkopf löschen delete kopf; kopf = NULL; }

Die einzige Neuerung ist die Methode istLeer(), die überprüft ob die Liste leer ist oder nicht.

Wie man sieht besitzt die aktuelle Implementierung keine Methode um auf die Daten zuzugreifen. Im ersten Teil haben wir direkt auf die Datenstruktur zugegriffen. Jetzt können wir das nicht machen, da wir nicht wissen, welche Daten in der Liste verwaltet werden.
Unser Ziel ist es einige Methoden zu implementieren, so dass folgender Code funktioniert.

Liste<Film> filme; filme.hinzufuegen(film); filme.hinzufuegen(film1); filme.hinzufuegen(film2); for(Liste<Film>::Iterator it = filme.start(); it != filme.postende(); it++) { std::cout << "Film: " << it.gibDaten().titel.c_str() << std::endl; }

Dabei greifen wir auf das Konzept von Iteratoren zurück. Ein Iterator stellt ein Zeiger auf das aktuelle Listenelement dar und besitzt Methoden um sich in der Liste zu bewegen.

Der obere Code bedeutet also folgendes: Erstelle einen Iterator für eine Liste mit Film-Elementen. Initialisiere ihn mit dem ersten Listenelement. So lange der Iterator nicht auf das Element nach dem letzten Listenelement zeigt, bewege ihn ein Element weiter.
Da der Iterator in jedem Durchlauf auf ein anderes Element zeigt, können wir so die ganze Liste durchlaufen.

Die Implementierung der Iteratorklasse beschränkt sich auf die wichtigsten Methoden.
Der Iterator kommt als private Klasse in die Listenklasse rein.

// Iterator für die Liste class Iterator { protected: // Zeiger auf das aktuelle Listenelement Listenelement *iter; public: // der Listeklasse erlauben auf protected-Elemente zuzugreifen friend Liste; // Konstruktor Iterator(void) : iter(NULL) {} Iterator(Listenelement* le) : iter(le) {} // Zuweisungsoperator void operator=(Listenelement<T>* le) { iter = le; } // Vergleichsoperator bool operator!=(Listenelement<T>* le) { if(NULL != iter && iter!=le) return true; else return false; } // Inkrementierungsoperator void operator++ () { if(iter != NULL) iter = iter->nachfolger; } // Zugriff auf den Datenbereich T& gibDaten(void) { return iter->daten; } };

Ich habe hier die Operatorenüberladung benutzt. Genauso so gut könnte man normale Methoden verwenden und zum Beispiel den Inkrement-Operator als next()-Methode implementieren.

Als nächstes brauchen wir noch zwei kleine Methoden in der Listen-Klasse, die das erste Element und das Element nach dem Listenende zurückgeben.

// gibt Startknoten zurück Listenelement* start(void) { return kopf; } // gibt das Element nach dem Endelement zurück Listenelement* postende(void) { if(ende==NULL) return NULL; else return ende->nachfolger; }

Somit wäre unsere einfach verkettete Liste als Template-Implementierung komplett.
Das war ja hartes Stückchen Arbeit. Doch die Mühe hat sich gelohnt, denn jetzt haben wir eine ziemlich flexible Liste, die mit verschiedensten Datentypen zurechtkommt.

Ein Beispiel zur Verwendung der Liste.

// Liste für int-Werde erstellen Liste<int> int_liste; std::cout<<"Liste erstellt."<<std::endl; // Liste mit Daten füllen for(int i = 0; i<1000; i++) { int_liste.hinzufuegen(i); } std::cout<<"Liste gefuellt."<<std::endl; // Liste durchlaufen for(Liste<int>::Iterator it = int_liste.start(); it != int_liste.postende(); it++) { std::cout<<it.gibDaten()<<std::endl; } std::cout<<"Daten ausgegeben."<<std::endl; // Liste löschen (optional) int_liste.loeschen(); std::cout<<"Liste geloescht"<<std::endl;

Perfekt oder? Nicht ganz! Schon bei diesem einfachen Beispiel merkt man, dass die Geschwindigkeit nicht besonders rasant ist. Um sich einen Eindruck über die Geschwindigkeit der Liste zu verschaffen haben, habe ich folgenden Code verwendet.

unsigned int anzahl_elemente = 100000; unsigned int zeit = 0; // Liste - test // Wegen timeGetTime() muss winmm.lib eingebunden werden zeit = timeGetTime(); Liste<int> liste; for(unsigned int i = 0; i<anzahl_elemente; i++) liste.hinzufuegen(i); for(Liste<int>::Iterator iit = liste.start(); iit != liste.postende(); iit++) { int test = iit.gibDaten(); } liste.loeschen(); std::cout<<"zeit: "<< (timeGetTime()-zeit) << std::endl; // std::liste test zeit = timeGetTime(); std::list<int> std_liste; for(unsigned long i = 0; i<anzahl_elemente; i++) std_liste.push_back(i); std::list<int>::const_iterator sit; for(sit = std_liste.begin(); sit != std_liste.end(); sit++) int test = *sit; std_liste.clear(); std::cout<<"zeit: "<< (timeGetTime()-zeit) << std::endl; std::cout<<"ENDE"<<std::endl;

Die Liste wird also mit Werten gefüllt, dann durchgelaufen und zum Schluss geleert.
Der Test wurde mit 20000, 40000, 60000, 80000 und 1000000 Elementen ausgeführt. Das Ergebnis wurde in einem Plot dargestellt.

Im Gegensatz zur std::list, die eine lineare Laufzeitcharakteristik besitzt, skaliert unsere Liste in quadratischer Ordnung.

Den Flaschenhals haben wir schon im ersten Teil des Artikels ausgemacht – die Methode loeschen().
Ich habe die Anwendung durch einen Profiler überwachen lassen. Das Resultat ist äußerst beeindruckend.

Demnach ist das Programm über 99% der Ausführungszeit mit der Methode loeschen() beschäftigt. Eine Optimierung muss her.

An dieser Stelle erweitern wir unsere Listenelement-Klasse um einen Zeiger auf das Vorgänger-Element.

Doppelt verkettete Liste

Der Sprung von einfach zu doppelt verketteter Liste ist relativ einfach. Die einzige Neuerung besteht darin, dass ein Listenelement nicht nur einen Zeiger besitzt, sondern zwei. Der eine Zeiger zeigt wie gehabt auf das nächste Element und der zweite auf das Vorherige.

Eine schematische Darstellung einer doppelt verketteten Liste mit vier Elementen.

Diese kleine Datenstrukturerweiterung bringt Vorteile beim Durchlaufen der Liste.
Man kann sich jetzt nicht nur vorwärts, sondern auch rückwärts in der Liste bewegen.
Genau das werden wir uns von Nutzen machen und die Methode loeschen() beschleunigen.
Aber zuerst müssen wir den zweiten Zeiger und damit verbundene Änderungen implementieren.

Die Klasse Listenelement wird um einen Zeiger erweitert.

// Zeiger auf den Vorgänger Listenelement* vorgaenger;

Damit wir mit diesem Zeiger auch arbeiten können, muss er auf ein gültiges Listenelement verweisen. Dafür sorgen wir in der Methode hizufuegen(..). Das Ganze beschränkt sich auf eine Zeile gleich nach der Erzeugen eines neuen Elements.

// das letzte Element zeigt auf das neue Element ende->nachfolger = neuesListenelement; // NEU: das aktuelle Ende wird zum Vorgänger des neuen Elements neuesListenelement->vorgaenger = ende; // das neue Element wird zum neuen Ende ende = neuesListenelement;

Da das neue Element an das Ende drangehängt wird, wird es das letzte Element in der Liste sein. Dadurch wird das momentan letzte Element automatisch zum Vorletzten.

Als nächstes werden wir die Methode loeschen() überarbeiten.

Dazu ändern wir den Algorithmus wie folgt ab. Der Codeabschnitt …

// ...suche das vorletzte ELement Listenelement *vorletztesElement = kopf; while(vorletztesElement->nachfolger != ende) { vorletztesElement = vorletztesElement->nachfolger; }

wird ersetzt durch

// Nimm das vorletzte Element Listenelement *vorletztesElement = ende->vorgaenger;

Die Suche nach dem vorletzten Element wird uns somit erspart, was dazu führt, dass das Löschen viel schneller geht.

Das war’s, alles andere bleibt unverändert.
Das Laufzeitverhalten sieht jetzt folgendermaßen aus.

Ein lineares Laufzeitverhalten und somit optimal. In O-Notation: Einfügen in O(1), Durchlaufen in O(n), Löschen in O(n).

Was jetzt noch fehlt ist etwas mehr Benutzerfreundlichkeit.

Zuerst erweitern wir die Iteratorklasse um einen Dekrement-Operator. Mit dieser Methode können wir uns dann in der Liste rückwärts bewegen.

// Dekrementierungsoperator void operator-- () { if(iter != NULL) iter = iter->vorgaenger; }

Als letzten Schritt schauen wir uns an, wie man Listenelemente löscht.

Listenelemente löschen

Es sind vier Fälle zu unterscheiden.
Wenn die Liste nur aus einem Element besteht, so löscht man dieses Element und setzt alle Zeiger auf null.

Besteht die Liste aus mehreren Elementen so ist zu unterscheiden, an welcher Position gelöscht wird.

Das erste Element löschen:

Das zweite Element wird zum Listenkopf.

Über den Vorgänger-Zeiger wird der alte Listenkopf gelöscht.

Anschließend wird der Vorgänger-Zeiger auf null gesetzt.

Das letzte Element löschen:

Die Vorgehensweise geht analog wie beim Entfernen des ersten Elements.

Das vorletzte Element wird zum Letzten erklärt.

Das letzte Element wird über den Nachfolger-Zeiger von Listenende gelöscht.

Der Nachfolger-Zeiger wird auf null gesetzt.

Listenelement in der Mitte löschen:

Angenommen es wird das zweite Element gelöscht.
Zuerst wird der Nachfolger-Zeiger des Vorgängers so umgeleitet, dass er auf den Nachfolger zeigt.

Danach wird der Vorgänger-Zeiger des Nachfolgers so umgeleitet, dass er auf den Vorgänger zeigt.

Da der Zeiger auf das zweite Element zwischengespeichert wurde, wissen wir wo es sich befindet. Das zweite Element wird gelöscht.

Diese vier Fälle werden nacheinander in der vorgestellten Reihenfolge abgearbeitet.

// Element löschen template<typename T> void Liste<T>::loeschen(Iterator& it) { // unterscheiden wo sich das zu löschende element befinden // das einzige element in der Liste if(kopf->nachfolger==NULL) { delete kopf; kopf = ende = NULL; } else if(it==kopf) // das erste element löschen { // das erste element wird zum ersten kopf = kopf->nachfolger; // lösche das alte erste element delete kopf->vorgaenger; kopf->vorgaenger = NULL; } else if(it==ende) // das letzte element löschen { // das vorletzte element wird zum letzten ende = ende->vorgaenger; // lösche das alte letzte element delete ende->nachfolger; ende->nachfolger = NULL; } else // ein element in der mitte der liste { // der vorgänger muss auf den nachfolger zeigen it.iter->vorgaenger->nachfolger = it.iter->nachfolger; // das nachfolger muss auf den vorgänger zeigen it.iter->nachfolger->vorgaenger = it.iter->vorgaenger; // das aktuelle element löschen delete it.iter; } }

Übergeben wird der aktuelle Iterator. Will man zum Beispiel das zweite Element löschen so geht man wie folgt vor.

it = filme.start(); it++; filme.loeschen(it);

Das Ändern von Elementen geht ähnlich.

it = filme.start(); it++; it.gibDaten().titel = "Bla bla";

Der ganze Code als Download: Doppelt verkettete Liste (880 Downloads)

Fazit

Im Laufe dieses Tutorials haben wir uns eine flexible und schnelle Liste geschrieben, die über die wichtigsten Funktionen verfügt. Das Erweitern und Ausbauen ist jedem selbst überlassen.

Die von mir vorgestellte Implementierung soll nur die Funktionsweise einer dynamischen Liste aufzeigen, so dass man eine Vorstellung bekommt, was darunter zu verstehen ist.
Für den produktiven Einsatz empfehle ich die Verwendung von std::list. Diese Implementierung ist nicht nur schnell, sondern auch besonders sicher.

Viel Spaß beim Programmieren =)

0 Thoughts to “Doppelt Verkettete Liste C++ Beispiel Essay

Leave a comment

L'indirizzo email non verrà pubblicato. I campi obbligatori sono contrassegnati *