Dynamische Datenstrukturen – Doppelt verkettete Liste

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

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