13.2    Doppelt verkettete Listen

Benötigen Sie eine Liste, die in beiden Richtungen durchlaufen werden kann, also von vorne nach hinten und umgekehrt, können Sie eine doppelt verkettete Liste verwenden. Im Vergleich zu einer einfach verketteten Liste ändert sich hierbei nur, dass im Strukturtyp ein weiterer Zeiger auf das vorherige Element hinzugefügt werden muss. Natürlich müssen Sie diesen weiteren Zeiger auch zusätzlich in Ihrem Code verwalten, was den Aufwand bei der Programmierung etwas erhöht. Bezogen auf das Listing in diesem Kapitel sieht die Struktur nun wie folgt aus:

struct knoten {
  int wert;
  struct knoten *next;     // Zeiger auf nächstes Element
  struct knoten *previous; // Zeiger auf vorheriges Element
};

Durch den zusätzlichen Zeiger wird zwar ein Zeiger mehr und somit auch mehr Speicherplatz für diesen Zeiger benötigt, aber dies kann, richtig implementiert, durch ein effizienteres Einfügen, Auffinden und Löschen von Elementen in der Liste wieder wettgemacht werden.

Abbildung 13.10    Doppelt verkettete Liste

Dies sind natürlich nicht die einzigen Formen von verketteten Listen. Es können daraus, wie Sie schon in der Einführung gesehen haben, beispielsweise Stacks nach dem LIFO-Prinzip (Last In First Out) oder Queues (Warteschlangen) nach dem FIFO-Prinzip als abstrakte Datenstrukturen erstellt werden. Auch binäre Suchbäume werden zunächst nur als Struktur mit zwei Zeigern auf dem linken und dem rechten Ast implementiert. Die Implementierung ist dann allerdings etwas komplexer als bei verketteten Listen. Hier gibt es noch viele weitere spezielle Formen, die alle die verketteten Listen als Grundlage haben. Darauf soll hier allerdings nicht weiter eingegangen werden, weil dies einen Grundkurs bei weitem übersteigt. Wenn Sie wirklich mehr erfahren und bei Listen und Bäumen in die Tiefe gehen wollen, finden Sie z. B. in dem Buch »C von A bis Z« die entsprechenden Antworten.