====== Doppelt verkettete Listen ======

Doppelt verkettete Listen (oder doubly linked lists) sind häufig benutze Datenstrukturen und eine Verallgemeinerung der einfach verketteten Listen, die ich hier anhand von Beispielen in der Programmiersprache C++ vorstellen will.

Sie funktioniert in jeder Programmiersprache genauso, die Zeiger oder Referenzen und so etwas wie Klassen oder Structs zur Verfügung stellt.

===== Wozu? =====

Doppelt verkettete Listen, oder "double linked lists" braucht man immer dann, wenn man sich in einer Liste leicht vorwärts und rückwärts bewegen können muss, und wenn man schnell und einfach Elemente der Liste an beliebigen Positionen löschen und neue einfügen muss.

Denn einfach verkettete Listen haben den Nachteil, dass man sie nur in einer Richtung durchlaufen kann.

Darüber hinaus kann man ein referenziertes Listenelement nicht unmittelbar löschen, da man von diesem Element keinen Zugriff auf das Vorgängerelement hat.

Doppelt verkettete Listen umgehen dieses Problem, indem sie in jedem Knoten zusätzlich noch eine Referenz auf den Vorgängerknoten speichern.

===== Die Grundidee ===== 

Im Gegensatz zu einfach verketteten Listen haben doppelt verkettete Listen in den Knoten eine zusätzliche Instanzvariable für die Referenz auf den Vorgängerknoten

Die Idee einer doppelt verketteten Liste ist es also, für jedes Element zwei Zeiger zu speichern, einen nach links und einen nach rechts:

<code c++>

struct DList{
	DList*left;
	DList *right;
	int data;
};

</code>


Die eigentlichen Daten, die in der Liste gespeichert werden sollen, stehen in data, das hier als int definiert ist. Jeder andere Datentyp, z.B. ein Zeiger auf beliebige andere Strukturen, funktioniert genau so.


{{:inf:inf8bi_201819:3:pasted:20190325-152508.png}}

===== Einfügen, Löschen und Ausgeben von Elementen =====


<code c++>

#include <iostream>

using namespace std;

struct DListe{
	DListe *next;
	DListe *prev;
	int zahl;
};


int main(int argc, char** argv) {
	
	DListe *head=NULL;		//Anlegen des Head-Pointers
	DListe *tail=NULL;		//Anlegen des Tail-Pointers
	DListe *help=NULL;		//Anlegen des Help-Pointers (für das Löschen und Ausgeben)
	

	//Einfügen von 10 Elementen in eine doppelt verkettete Liste
	for(int i=0;i<10;i++)
	{
		DListe *elem=new DListe();		//Element erzeugen
		elem->zahl=i;					//Attribut zahl befüllen
		if(head==NULL && tail==NULL)	//noch kein Element in der Liste
		{
			head=elem;					//Head zeigt auf das neue Element
			tail=elem;					//Tail zeigt auf das neue Element
			elem->next=NULL;			//Next zeigt auf NULL
			elem->prev=NULL;			//Prev zeigt auf NULL
		}
		else							//Elemente sind bereits vorhanden & Element wird am Ende eingefügt
		{
			tail->next=elem;			//tail->next auf das neue Element
			elem->prev=tail;			//elem->prev zeigt auf das ursprünglich letzte Element
			elem->next=NULL;			//elem->next zeigt auf NULL
			tail=elem;					//tail zeigt auf das neue letzte Element
		}	
	}
	
	cout << "Geben Sie an, welches Element (0-9) Sie loeschen wollen!" << endl;
	int loesche=0;
	cin >> loesche; //zB. Element mit der zahl=2 wird gelöscht 
	
	help=head;					//help zeigt auf head (Anfang der Liste)
	while(help->zahl!=loesche)	//Wenn help->zahl!=loesche, dann wandert help in der Liste weiter
	{
		help=help->next;		
	}
	//Überprüfe nochmals mit Ausgabe, ob beim richtigen Element (=2) angekommen?
	cout << help->zahl;
	//Sonderfall 1. Element soll gelöscht werden (zahl=0)	
	if(help==head)
	{
		head->next->prev=NULL;
		head=head->next;
		head->prev=NULL;
	}
	else if(help==tail)  //Sonderfall letztes Element soll gelöscht werden
	{
		tail=help->prev;
		help->prev->next=help->next;	
	}
	else	//Element ist zwischen 2 anderen Elementen
	{
		help->prev->next=help->next;
		help->next->prev=help->prev;
	}

	//Ausgabe der doppelt verketteten Liste
	cout << endl << endl;
	help=head;
	while(help!=NULL)
	{
		cout << help->zahl << " -> ";
		help=help->next;
	}
	
	return 0;
}

</code>


===== Sortiertes Einfügen =====

<code c++>
      do{
		DListe *elem=new DListe();
		cout << endl << "Geben Sie ein Element ein, das sie einfuegen wollen!" << endl;
		cin >> elem->zahl;
		elem->next=NULL;
		elem->prev=NULL;
		help=head;
		
		while((elem->zahl>help->zahl) && (help->next!=NULL))
		{
			help=help->next;
		}
		
		if(head==help)	//1. Fall => Element wird an erster Stelle eingefügt
		{
			elem->next=help;
			help->prev=elem;
			head=elem;	
		}
		else if(tail==help) //2. Fall => Element wird an letzter Stelle eingefügt
		{
			elem->prev=help;
			help->next=elem;
			tail=elem;
		}
		else	//3. Fall => Element wird in der Mitte, also zwischen 2 anderen Elemente eingefügt
		{
			elem->next=help;
			help->prev->next=elem;
			elem->prev=help->prev;
			help->prev=elem;
		}
		
		//Ausgabe der Doppelt verketteten Liste
		ausgabe(head);
		
		cout << "Wollen Sie noch ein Element einfuegen (j/n)" << endl;
	}while(getch()=='j');

</code>