21.2 Doppelt verkettete Listen 
Im Gegensatz zu den einfach verketteten Listen haben doppelt verkettete Listen zusätzlich noch einen Zeiger auf den Vorgänger. Soll z. B. erst ein Element in der Liste gelöscht werden und wird gleich darauf auf den Vorgänger des gelöschten Elements zugegriffen, müsste bei der einfach verketteten Liste der vollständige Satz von Neuem durchlaufen werden. Mit der doppelt verketteten Liste kann hingegen sofort auf den Vorgänger zugegriffen werden.
Zur Realisierung doppelt verketteter Listen muss nur der Struktur bei der Deklaration ein weiterer Zeiger hinzugefügt werden:
struct angestellt{
char name[20];
char vorname[20];
struct datum alter;
struct datum eingest;
long gehalt;
struct angestellt *next; /* Nachfolger */
struct angestellt *previous; /* Vorgänger */
};Außerdem sollten Sie noch einen Zeiger auf das letzte Element definieren. Wird z. B. nach einem Namen mit dem Anfangsbuchstaben »Z« gesucht, wäre es doch reine Zeitverschwendung, die Liste von vorn zu durchlaufen. Also gäbe es noch folgende Angaben:
struct angestellt *anfang;
struct angestellt *ende;Die Initialisierung mit NULL soll gleich in eine Funktion verpackt werden:
void start(void) {
anfang = ende = NULL;
}So sieht die Struktur jetzt mit dem Extra-Zeiger auf seinen Vorgänger aus (siehe Abbildung 21.22).
Abbildung 21.22 Struktur einer doppelt verketteten Liste
Bevor all dies in die Praxis umgesetzt wird, noch schnell ein Bild dazu, wie Sie sich eine doppelt verkettete Liste vorstellen können (siehe Abbildung 21.23).
Abbildung 21.23 Doppelt verkettete Liste
Auf den kommenden Seiten werden die Funktionen, die im Abschnitt über die einfach verketteten Listen verwendet wurden, umgeschrieben, damit diese mit doppelt verketteten Listen eingesetzt werden können. Sie müssen dabei immer darauf achten, dass jetzt jedes Element in der Liste auch einen Vorgänger besitzt.
Wir beginnen mit der Funktion anhaengen():
void anhaengen(char *n, char *v, int at, int am, int aj,
int eint, int einm, int einj, long g) {
/* Zeiger zum Zugriff auf die einzelnen Elemente
* der Struktur */
struct angestellt *zeiger, *zeiger1;
/* Wurde schon Speicher für den ende-Zeiger bereitgestellt? */
if(ende == NULL) {
if((ende=malloc(sizeof(struct angestellt))) == NULL) {
printf("Konnte keinen Speicherplatz für ende "
"reservieren\n");
return;
}
}
/* Wir fragen ab, ob es schon ein Element in der Liste gibt.
* Wir suchen das Element, auf das unser Zeiger *anfang
* zeigt. Falls *anfang immer noch auf NULL zeigt, bekommt
* *anfang die Adresse unseres 1. Elements und ist somit der
* Kopf (Anfang) unserer Liste. */
if(anfang == NULL) {
/* Wir reservieren Speicherplatz für unsere
* Struktur für das erste Element der Liste. */
if((anfang =malloc(sizeof(struct angestellt))) == NULL) {
fprintf(stderr,"Kein Speicherplatz vorhanden "
"fuer anfang\n");
return;
}
strcpy(anfang->name,strtok(n, "\n"));
strcpy(anfang->vorname,strtok(v, "\n"));
anfang->alter.tag=at;
anfang->alter.monat=am;
anfang->alter.jahr=aj;
anfang->eingest.tag=eint;
anfang->eingest.monat=einm;
anfang->eingest.jahr=einj;
anfang->gehalt=g;Bis hierhin stellt diese Funktion nichts Neues dar. Es wird davon ausgegangen, dass sich noch kein Element in der Liste befindet, und Sie fügen nun das erste Element ein:
anfang->next=NULL;
ende=anfang;
ende->previous=NULL;
}Der next-Zeiger vom ersten Element zeigt zunächst auf gar nichts (NULL). Der ende-Zeiger, der auf das letzte Element verweist, zeigt am Anfang zunächst auf das erste Element, das gleichzeitig ja auch das letzte der Liste ist. Der previous-Zeiger, der auf den Vorgänger zeigen soll, verweist ebenso auf NULL. Genauso gut hätten Sie anstatt ende->previous=NULL auch anfang->previous=NULL schreiben können. Beides hätte denselben Effekt gehabt.
Kommen wir jetzt zur zweiten Möglichkeit – das neue Element wird hinten angehängt:
else {
zeiger=anfang; /* Wir zeigen auf das 1. Element. */
while(zeiger->next != NULL)
zeiger=zeiger->next;
/* Wir reservieren einen Speicherplatz für das letzte
* Element der Liste und hängen es an. */
if((zeiger->next =
malloc(sizeof(struct angestellt))) == NULL) {
fprintf(stderr, "Kein Speicherplatz fuer "
"letztes Element\n");
return;
}
zeiger1=zeiger;
zeiger=zeiger->next; /* zeiger auf neuen Speicherplatz */
strcpy(zeiger->name,strtok(n, "\n"));
strcpy(zeiger->vorname,strtok(v, "\n"));
zeiger->alter.tag=at;
zeiger->alter.monat=am;
zeiger->alter.jahr=aj;
zeiger->eingest.tag=eint;
zeiger->eingest.monat=einm;
zeiger->eingest.jahr=einj;
zeiger->gehalt=g;Auch am Anfang bleibt beim Hintenanhängen alles beim Alten – bis auf den zeiger1, der wie zeiger auf das momentan (noch) letzte Element zeigt. Anschließend verweist man den Zeiger zeiger auf den neuen Speicherplatz, der zuvor mit malloc() reserviert wurde (siehe Abbildung 21.24).
Abbildung 21.24 Ein neues Element wurde hinten mit einfacher Verkettung angefügt.
Die weiteren Schritte zum Einfügen des neuen Elements sind:
zeiger->next=NULL;
ende=zeiger;
zeiger->previous=zeiger1;
zeiger1->next=zeiger;
}Der next-Zeiger des neuen Elements bekommt den NULL-Zeiger. Der ende-Zeiger verweist auf das neue Element, da es das letzte Element in der Liste ist. Zusätzlich bekommt das neue Element auch die Adresse des Vorgängers, auf die zeiger1 verweist. Und zeiger1->next bekommt noch die Adresse des neuen Elements zeiger übergeben. Somit ergibt sich folgendes Bild:
Abbildung 21.25 Ein neues Element wurde hinten mit doppelter Verkettung angefügt.
Schwieriger wird die nächste Funktion, nämlich das Löschen eines Elements in der Liste:
void loesche(char *wen) {
struct angestellt *zeiger, *zeiger1, *zeiger2;
/* Ist überhaupt ein Element vorhanden? */
if(anfang != NULL) {
/* Ist unser 1. Element das von uns gesuchte (wen[])? */
if(strcmp(anfang->name,wen) == 0) {
zeiger=anfang->next;
if(zeiger == NULL) {
free(anfang);
anfang=NULL;
ende=NULL;
return;
}
zeiger->previous=NULL;
free(anfang);
anfang=zeiger;
}Die erste Möglichkeit: Das erste Element ist das gesuchte und soll gelöscht werden. Als Erstes lassen Sie einen Zeiger auf die zukünftige Anfangsdatei zeigen – natürlich vorausgesetzt, es ist mehr als ein Element vorhanden. Falls nicht (if(zeiger == NULL)), wird die Anweisung der if-Bedingung aktiv. Abbildung 21.26 zeigt den momentanen Stand.
Abbildung 21.26 Das erste Element in der Liste (»anfang«) soll gelöscht werden.
Es wird davon ausgegangen, dass bereits mehrere Elemente in der Liste vorhanden sind. Also folgt nur noch:
zeiger->previous=NULL; free(anfang); anfang=zeiger;
... und schon ist das erste Element in der Liste gelöscht:
Abbildung 21.27 Das erste Element in der Liste wurde gelöscht.
Die zweite Möglichkeit ist, dass das zu löschende Element das letzte in der Liste ist:
else if(strcmp(ende->name,wen) == 0) {
zeiger=ende->previous;
zeiger->next=NULL;
zeiger1=ende;
ende=zeiger;
free(zeiger1);
}Da der Vorgang ähnlich wie beim ersten Element abläuft, kann dieser auf einem Blatt Papier zur Übung selbst aufgezeichnet werden.
Weiter geht es mit der dritten Möglichkeit: Das zu löschende Element ist irgendwo zwischendrin:
zeiger=anfang;
while(zeiger->next != NULL) {
zeiger1=zeiger->next;
/* Ist die Adresse von zeiger1 der gesuchte Name? */
if(strcmp(zeiger1->name,wen) == 0) {
/* Falls ja, dann ... */
zeiger->next=zeiger1->next;
zeiger2=zeiger1->next;
zeiger2->previous=zeiger;
free(zeiger1);
break;
}
zeiger=zeiger1;
}Wir nehmen hier wieder an, dass das zu löschende Element gefunden wurde und dass es das zweite Element ist (im Bild mit del gekennzeichnet):
Abbildung 21.28 Das Element, auf das »zeiger1« verweist, soll gelöscht werden.
zeiger1 verweist auf das zu löschende Element. Dieses Element muss jetzt ausgehängt werden. Die weiteren Schritte sind somit:
zeiger->next=zeiger1->next;
Abbildung 21.29 Zu löschendes Element zum Teil aushängen
zeiger2=zeiger1->next;
Abbildung 21.30 Ein Zeiger auf den Vorgänger des zu löschenden Elements
zeiger2->previous=zeiger;
Abbildung 21.31 Das zu löschende Element wurde komplett ausgehängt.
free(zeiger1);
Abbildung 21.32 Speicherplatz freigegeben
Der Vorgang lässt sich anhand der Grafiken recht einfach nachvollziehen. Hier folgt die vollständige Funktion zur Übersicht:
/* Funktion zum Löschen einer Datei */
void loesche(char *wen) {
struct angestellt *zeiger, *zeiger1, *zeiger2;
/* Ist überhaupt ein Element vorhanden? */
if(anfang != NULL) {
/* Ist unser 1. Element das von uns gesuchte (wen[])? */
if(strcmp(anfang->name,wen) == 0) {
zeiger=anfang->next;
if(zeiger == NULL) {
free(anfang);
anfang=NULL;
ende=NULL;
return;
}
zeiger->previous=NULL;
free(anfang);
anfang=zeiger;
}
/* Ist das letzte Element das von uns gesuchte? */
else if(strcmp(ende->name,wen) == 0) {
zeiger=ende->previous;
zeiger->next=NULL;
zeiger1=ende;
ende=zeiger;
free(zeiger1);
}
else {
/* Es ist nicht das 1. Element zu löschen.
* Wir suchen in der weiteren Kette, ob das zu
* löschende Element vorhanden ist. */
zeiger=anfang;
while(zeiger->next != NULL) {
zeiger1=zeiger->next;
/* Ist die Adresse von zeiger1
* der gesuchte Name? */
if(strcmp(zeiger1->name,wen) == 0) {
/* Falls ja, dann ... */
zeiger->next=zeiger1->next;
zeiger2=zeiger1->next;
zeiger2->previous=zeiger;
free(zeiger1);
break;
}
zeiger=zeiger1;
}
}
}
else
printf("Es sind keine Daten zum Loeschen vorhanden!!!\n");
}Die Funktionen eingabe() und ausgabe() müssen nicht verändert werden.
Die Funktion loesche_alles() ist ebenfalls relativ einfach umzuschreiben. Es muss lediglich die ganze Liste durchlaufen werden, und dabei müssen alle bis auf das erste und letzte Element gelöscht werden:
void loesche_alles(void) {
struct angestellt *zeiger, *zeiger1;
/* Ist überhaupt eine Liste zum Löschen vorhanden? */
if(anfang != NULL) {
/* Es ist eine vorhanden ... */
zeiger=anfang->next;
while(zeiger != NULL) {
zeiger1=anfang->next->next;
if(zeiger1 == NULL)
break;
anfang->next=zeiger1;
zeiger1->previous=anfang;
free(zeiger);
zeiger=zeiger1;
}
Abbildung 21.33 Momentane Zeigerstellung der Funktion »loesche_alles()«
Die if-Abfrage, ob der Zeiger zeiger1 auf NULL zeigt, wird als Abbruchbedingung benutzt, da – falls das wahr sein sollte – nur noch zwei Elemente in der Liste vorhanden sind. Genauso gut hätten Sie dies mit der while-Abfrage vornehmen können: while(zeiger->next != NULL). Zu dieser Funktion sehen wir uns den Ablauf an. Zuerst wird das Element, auf das zeiger verweist, ausgehängt:
anfang->next=zeiger1;
zeiger1->previous=anfang;
Abbildung 21.34 Zu löschendes Element aushängen
Danach kann der Speicherplatz, auf den zeiger zeigt, mit free() freigegeben werden. Es ergibt sich in Abbildung 21.35.
Abbildung 21.35 Speicherplatz wurde freigegeben.
Hier endet die while-Schleife, da zeiger1=anfang->next->next jetzt auf NULL zeigt. Jetzt müssen nur noch die letzten beiden Elemente in der Liste gelöscht werden:
free(anfang);
free(ende);
anfang=NULL;
ende=NULL;Dazu müssen Sie den Speicherplatz freigeben, auf den anfang und ende zeigen. Anschließend bekommen die Zeiger anfang und ende den NULL-Zeiger. Die Funktion loesche_alles() sieht komplett so aus:
void loesche_alles(void) {
struct angestellt *zeiger, *zeiger1;
/* Ist überhaupt eine Liste zum Löschen vorhanden? */
if(anfang != NULL) {
/* Es ist eine vorhanden ... */
zeiger=anfang->next;
while(zeiger != NULL) {
zeiger1=anfang->next->next;
if(zeiger1 == NULL)
break;
anfang->next=zeiger1;
zeiger1->previous=anfang;
free(zeiger);
zeiger=zeiger1;
}
/* Jetzt löschen wir erst den Anfang der Liste und
* dann das Ende der Liste. */
free(anfang);
free(ende);
anfang=NULL;
ende=NULL;
printf("Liste erfolgreich geloescht!!\n");
}
else
fprintf(stderr, "Keine Liste zum Loeschen vorhanden!!\n");
}Als Nächstes soll die Funktion sortiert_eingeben() umgeschrieben werden, damit diese für doppelt verkettete Listen verwendet werden kann:
void sortiert_eingeben(char *n, char *v, int at, int am,
int aj, int et, int em, int ej,
long geh) {
struct angestellt *zeiger, *zeiger1;
/* Ist es das 1. Element der Liste? */
if(anfang==NULL)
anhaengen(n,v,at,am,aj,et,em,ej,geh);
/* Es ist nicht das 1. Element. Wir suchen nun so lange, bis
* das gesuchte Element gefunden wird oder wir auf NULL
* stoßen. */
else {
zeiger=anfang;
while(zeiger != NULL && (strcmp(zeiger->name,n) < 0 ) )
zeiger=zeiger->next;
/* Falls der Zeiger auf NULL zeigt, können wir
* unser Element hinten anhängen, da unser neues Element
* das "größte" zu sein scheint. */
if(zeiger==NULL)
anhaengen(n,v,at,am,aj,et,em,ej,geh);
/* Ist unser neues Element das kleinste und somit
* kleiner als das 1. Element, so müssen wir es an den
* Anfang hängen. */
else if(zeiger == anfang) {
anfang=malloc(sizeof(struct angestellt));
if(NULL == anfang) {
fprintf(stderr, "Kein Speicherplatz vorhanden!!!\n");
return;
}
strcpy(anfang->name,strtok(n, "\n") );
strcpy(anfang->vorname,strtok(v, "\n") );
anfang->alter.tag=at;
anfang->alter.monat=am;
anfang->alter.jahr=aj;
anfang->eingest.tag=et;
anfang->eingest.monat=em;
anfang->eingest.jahr=ej;
anfang->gehalt=geh;
anfang->next=zeiger;
anfang->previous=NULL;
}Die Erklärung dafür, ob es sich hier um das einzige, das erste oder das letzte Element der Liste handelt, können Sie bei der Funktion anhaengen() in Abschnitt 21.1, »Lineare Listen (einfach verkettete Listen)«, nachlesen. Viel interessanter ist es, wie ein Element irgendwo dazwischen eingefügt wird. Hier sehen Sie zunächst den weiteren Codeverlauf:
else {
zeiger1=anfang;
/* Wir suchen das Element, das vor dem
* Zeiger zeiger steht. */
while(zeiger1->next != zeiger)
zeiger1=zeiger1->next;
zeiger=malloc(sizeof(struct angestellt));
if(NULL == zeiger) {
fprintf(stderr, "Kein Speicherplatz vorhanden!!!\n");
return;
}
strcpy(zeiger->name, strtok(n, "\n") );
strcpy(zeiger->vorname, strtok(v, "\n") );
zeiger->alter.tag=at;
zeiger->alter.monat=am;
zeiger->alter.jahr=aj;
zeiger->eingest.tag=et;
zeiger->eingest.monat=em;
zeiger->eingest.jahr=ej;
zeiger->gehalt=geh;
/* Wir fügen das neue Element ein */
zeiger->next=zeiger1->next;
zeiger->previous=zeiger1;
zeiger1->next=zeiger;
zeiger1->next->previous=zeiger;
} /* Ende else */Wir gehen davon aus, dass die Position für das neue Element bereits ermittelt wurde und dass sich zeiger1 vor diesem Element befindet. Somit ergibt sich folgender Zustand:
Abbildung 21.36 Neues Element einfügen
Jetzt soll das neue Element, auf das zeiger verweist, zwischen dem zweiten und dem dritten Element eingefügt werden. Die weiteren Schritte sind:
zeiger->next=zeiger1->next;
Abbildung 21.37 Zeiger auf den Nachfolger des neuen Elements
zeiger->previous=zeiger1;
Abbildung 21.38 Zeiger auf den Vorgänger des neuen Elements
zeiger1->next=zeiger; zeiger1->next->previous=zeiger;
Abbildung 21.39 Zeiger vom Vorgänger und Nachfolger zum neuen Element
Das soll es vorerst mit dem Abschnitt »Doppelt verkettete Listen« gewesen sein. Wenn Sie folgende Ratschläge zu diesem Thema beherzigen, dürften keine Probleme zu erwarten sein:
- Wenn Sie Zeiger benutzen, müssen Sie immer darauf achten, dass diese auf einen gültigen Speicherbereich (Adresse) zeigen. Ein häufiges Missverständnis bei Zeigern ist es, dass z. B. mit zeiger1=zeiger kein Wert an zeiger1 übergeben wird, sondern die Adresse, auf die zeiger verweist. Daher empfiehlt es sich, so oft wie möglich Fehlerüberprüfungen einzubauen.
- Sie sollten aussagekräftige Namen für einen Zeiger verwenden. Beispiele: next, previous, anfang oder ende. Dies ist eine enorme Erleichterung, wenn das Programm Fehler hat und nach ihnen gesucht werden muss. Denn unter anfang->next=ende können Sie sich mehr vorstellen als unter a–>n=e.
- Einer der häufigsten Fehler ist ein Zeiger, der auf einen unerlaubten Speicherplatz zeigt. Daher lohnt es, sich die Zeit zu nehmen, den Ablauf des Programms auf einem Stück Papier zu zeichnen, um ihn besser nachvollziehen zu können. Gerade bei doppelt verketteten Listen passiert es ziemlich schnell, dass Sie ein Glied der Kette vergessen. Meist wird dieser Fehler am Anfang gar nicht bemerkt, denn der Compiler kann bei Übersetzung des Programms ja noch nicht wissen, ob ein Zeiger ins Nirwana verweist.
- And last but not least: Sie sollten immer den Rückgabewert überprüfen, wenn Speicherplatz reserviert wird. Denn alles, was schiefgehen kann, wird irgendwann einmal schiefgehen.
Das vollständige Listing (double_list.c) finden Sie selbstverständlich auf der Buch-CD. Dem Listing wurden noch einige Funktionen, unter anderem das Laden oder Speichern von Daten auf der Festplatte, hinzugefügt.
Ihre Meinung
Wie hat Ihnen das Openbook gefallen? Wir freuen uns immer über Ihre Rückmeldung. Schreiben Sie uns gerne Ihr Feedback als E-Mail an kommunikation@rheinwerk-verlag.de.
