23.2 Doppelt verkettete Listen 

Im Gegensatz zu den einfach verketteten Listen haben doppelt verkettete zusätzlich noch einen Zeiger auf den Vorgänger. Soll z.B. erst ein Element in der Liste gelöscht werden, und gleich darauf wird 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:

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.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:

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.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. Es muss dabei immer darauf geachtet werden, dass jetzt jedes Element in der Liste auch einen Vorgänger besitzt. Es soll mit der Funktion anhaengen() angefangen werden:

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=(struct angestellt *)
        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 =(struct angestellt *)
        malloc(sizeof(struct angestellt))) == NULL) {
         fprintf(stderr,"Kein Speicherplatz vorhanden "
                        "für 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.

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 =(struct angestellt *)
        malloc(sizeof(struct angestellt))) == NULL) {
         fprintf(stderr, "Kein Speicherplatz für "
                         "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 hinten Anhä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:

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.24   Neues Element wurde hinten angefügt mit einfacher Verkettung

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:

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.25   Neues Element wurde hinten angefügt mit doppelter Verkettung

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. Der momentane Stand:

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.26   Erstes 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:

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.27   Erstes 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;
   }

Es sei hier wieder angenommen, das zu löschende Element wurde gefunden, und es ist das zweite Element (im Bild mit del gekennzeichnet):

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.28   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;

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.29   Zu löschendes Element zum Teil aushängen

zeiger2=zeiger1->next;

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.30   Ein Zeiger auf den Vorgänger des zu löschenden Elements

zeiger2->previous=zeiger;

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.31   Zu löschendes Element komplett ausgehängt

free(zeiger1);

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.32   Speicherplatz freigegeben

Der Vorgang lässt sich anhand der Grafiken recht einfach nachvollziehen. Hier nochmals 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 Löschen 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;
      }

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.33   Momentane Zeigerstellung der Funktion loesche_alles()

Die if-Abrage, 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 noch ein kleiner bildlicher Ablauf. Zuerst wird das Element, auf das zeiger verweist, ausgehängt:

      anfang->next=zeiger1;
      zeiger1->previous=anfang;

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.34   Zu löschendes Element aushängen

Danach kann der Speicherplatz, auf den zeiger zeigt, mit free() freigegeben werden. Es ergibt sich folgendes Bild:

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.35   Speicherplatz 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, auf den anfang und ende zeigen, freigeben. Anschließend bekommen die Zeiger anfang und ende den NULL-Zeiger. Die Funktion loesche_alles() komplett:

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
       * das Ende der Liste */
      free(anfang);
      free(ende);
      anfang=NULL;
      ende=NULL;
      printf("Liste erfolgreich gelöscht!!\n");
   }
   else
      fprintf(stderr, "Keine Liste zum Löschen 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össte" 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=(struct angestellt *)
           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, ob es sich hier um das einzige, das erste oder das letzte Element der Liste handelt, kann bei der Funktion anhaengen() in Abschnitt 23.1, Lineare Listen (einfach verkettete Listen), nachgelesen werden. Viel interessanter ist es, wie ein Element irgendwo dazwischen eingefügt wird. Hierzu zunächst der weitere Codeverlauf:

      else {
         zeiger1=anfang;
         /* Wir suchen das Element, das vor dem
          * Zeiger zeiger steht */
         while(zeiger1->next != zeiger)
            zeiger1=zeiger1->next;
         zeiger=(struct angestellt *)
           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*/

Es wird davon ausgegangen, dass die Position für das neue Element bereits ermittelt wurde, und sich zeiger1 vor diesem Element befindet. Somit ergibt sich folgender Zustand:

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.36   Neues Element einfügen

Jetzt soll das neue Element, auf welches zeiger verweist, zwischen dem zweiten und dem dritten Element eingefügt werden. Hierzu die weiteren Schritte:

zeiger->next=zeiger1->next;

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.37   Zeiger auf den Nachfolger des neuen Elements

zeiger->previous=zeiger1;

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.38   Zeiger auf den Vorgänger des neuen Elements

zeiger1->next=zeiger;
zeiger1->next->previous=zeiger;

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.39   Zeiger vom Vorgänger und Nachfolger zum neuen Element

Das soll es vorerst mit dem Abschnitt »Doppelt verkettete Listen« gewesen sein. Wenn folgende Ratschläge zu diesem Thema beherzigt werden, dürften keine Probleme zu erwarten sein:

Wenn Sie Zeiger benutzen, ist immer darauf zu 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 ist es ziemlich schnell passiert, 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 schief gehen kann, wird irgendwann einmal schief gehen.

Das vollständige Listing (double_list.c) kann unter der Adresse http://www.pronix.de/ heruntergeladen werden. Dem Listing wurden noch einige Funktionen, u.a. das Laden oder Speichern von Daten auf der Festplatte, hinzugefügt.