Die Knoten einer verketteten Liste werden meist durch einen Datentyp wie CWaggon (in der einschlägigen Literatur meist aber Listnode genannt) dargestellt:

typedef AnsiString T;  // Datentyp der Nutzdaten
 
struct CWaggon 
{T data;               // die Nutzdaten
 CWaggon *next;        // Zeiger auf den nächsten Knoten
};

Die Verwendung eines Datentyps in seiner Definition ist nur mit Zeigern oder Referenzen möglich. Ein solcher Datentyp wird auch als rekursiver Datentyp bezeichnet.

Beispiel 1: Verwendet man einen Datentyp ohne Zeiger oder Referenz in seiner Definition, wird das vom Compiler als Fehler betrachtet:

struct CWaggon
{T data;
 CWaggon next;   // Fehler
};

Mit einem Datentyp wie CWaggon erhält man eine verkettete Liste, indem man mit new Variablen dieses Typs erzeugt und in jedem Knoten dem Zeiger next die Adresse des nächsten Knotens zuweist:

Ein Zeiger wie first zeigt auf den ersten Knoten der Liste:

 CWaggon *first; // Zeiger auf den ersten Knoten

Den letzten Knoten der Liste kennzeichnet man durch einen Zeiger next mit dem Wert 0. Grafisch wird dieser Wert oft durch einen schwarzen Punkt dargestellt.

Dann hat die verkettete Liste einen eindeutigen Anfang und ein eindeutiges Ende:

Einhängen eines neuen Knotens

Als nächstes sollen Anweisungen gesucht werden, mit denen man vor einem Knoten, auf den ein Zeiger n0 zeigt,

einen neuen Knoten einfügen kann, auf den n0 dann zeigt:

Das ist mit den Anweisungen unter 1. und 2. möglich:

1. Ein Zeiger tmp soll auf einen neuen Knoten zeigen, der mit new erzeugt wird

CWaggon *tmp = new CWaggon; // 1.1

und dem die Daten durch eine Anweisung wie

tmp->data = d2; // 1.2

zugewiesen werden. Dadurch ergibt sich:

2. Der neue Knoten *tmp wird dann mit den beiden Anweisungen

tmp->next = n0; // 2.1
n0 = tmp;       // 2.2

in die Liste eingehängt:

Diese Anweisungen werden mit der Funktion

CWaggon *newWaggon(T &data, CWaggon *next) // gibt Zeiger auf neuen Listenknoten{d0,nx0} zurück,  
{                                         // wobei d0 und nx0 die Argumente für data und next sind.
 CWaggon *n = new CWaggon;                // 1.1
 n->data = data;                          // 1.2
 n->next = next;                          // 2.2
 return n;                                // Nachbedingung: Der Rückgabewert zeigt auf 
}                                         // einen neuen Knoten {d0,nx0}

durch den Aufruf

 n0 = newWaggon(d2,n0);                   // 2.1

ausgeführt. n0 zeigt danach auf einen neu erzeugten Knoten, dessen Element next auf den Knoten zeigt, auf den das Argument für next zeigt. Falls das Argument für next den Wert 0 hat, zeigt der Funktionswert auf einen Knoten mit next==0.

Das Ergebnis der ersten drei Ausführungen der Anweisung

 first = newWaggon(di,first);

mit den Daten d1, d2 usw., wobei der Wert von first zuerst 0 sein soll, ist in dem folgenden Ablaufprotokoll dargestellt. Dabei sind die Zeiger auf die von newWaggon erzeugten Knoten mit n1, n2 usw. bezeichnet, und ein Knoten, auf den ein solcher Zeiger zeigt, mit →{di,nj}. Der Ausdruck →{d2,n1} in der Spalte n2 ist also nichts anderes als eine Kurzschreibweise für

Die Werte in den Spalten n1, n2 usw. erhält man einfach durch Einsetzen der Argumente in die Nachbedingung von newWaggon:

                                   // first         n1          n2        n3
first = 0;                               0
first = newWaggon(d1,first);             n1        ->{d1,0}
first = newWaggon(d2,first);             n2                    ->{d2,n1}
first = newWaggon(d3,first);             n3                              ->{d3,n2}

Dieses Ablaufprotokoll illustriert, wie der erste dieser Aufrufe einen ersten Knoten mit next==0 erzeugt, auf den first dann zeigt, und wie jeder weitere Aufruf einen neuen Knoten am Anfang in die verkettete Liste einhängt, auf die first zeigt.

Die Funktionsweise von newWaggon beruht insbesondere darauf, dass eine mit new erzeugte Variable bis zum Aufruf von delete existiert. Im Unterschied zu einer gewöhnlichen Variablen wird ihr Speicherplatz nicht mit dem Verlassen des Blocks wieder freigegeben, in dem sie erzeugt wurde.

– Deshalb existiert die Variable *tmp, die mit CWaggon *tmp=new CWaggon; erzeugt wurde, auch noch nach dem Verlassen der Funktion newWaggon.

– Der Zeiger tmp ist dagegen eine „gewöhnliche“ lokale Variable, deren Speicherplatz mit dem Verlassen des Blocks wieder freigegeben wird. Da der Wert von tmp dem Element next des Funktionswerts zugewiesen wird, kann man die lokal erzeugte Variable *tmp über den Funktionswert auch außerhalb der Funktion verwenden, in der sie erzeugt wurde.

Aufbau einer Liste von vorne

Listen, bei denen neue Elemente am Anfang eingehängt werden, bezeichnet man auch als „Last-in-first-out“-Listen (LIFO), da das zuletzt eingefügte Element am Anfang steht. Eine LIFO-Liste erhält man mit einem Zeiger first, der am Anfang den Wert 0 hat, und wiederholte Aufrufe der Funktion newWaggon:

CWaggon *first=0;
 
void LIFOInsert(T &data)
{first=newWaggon(data,first);
}

Durchlaufen einer Liste

Um alle Elemente einer Liste zu durchlaufen, kann man sich mit einer Hilfsvariablen tmp vom Anfang bis zum Ende durchhangeln:

void showList(CWaggon *start) // Gibt alle Daten der Liste ab der Position start aus
{CWaggon *tmp=start;
 while (tmp != 0)
 {Form1->Memo1->Lines->Add(tmp->data);
  tmp = tmp->next;
 }
}

Da start als Werteparameter übergeben wird, kann man auch start als Laufvariable verwenden. Wäre start ein Referenzparameter, würde das Argument verändert:

while (start != 0)
{Form1->Memo1->Lines->Add(start->data);
 start = start->next;
}

Anstelle einer while-Schleife kann man auch eine for-Schleife verwenden:

for (CWaggon *tmp= start; tmp != 0; tmp = tmp->next)
 Form1->Memo1->Lines->Add(tmp->data);

Durch diese Schleifen werden die Listenelemente in der Reihenfolge ausgegeben, in der sie sich in der Liste befinden. Falls sie durch eine Funktion wie LIFOInsert immer am Anfang eingehängt werden, werden sie in der umgekehrten Reihenfolge ausgegeben, in der sie eingehängt wurden.

Suchen in der Liste

Einen Zeiger auf den ersten Knoten mit den Daten x erhält man mit der Funktion findData. Falls kein solcher Knoten gefunden wird, ist der Funktionswert 0:

CWaggon *findData(CWaggon *start, T &x)
{CWaggon *found=0;
 CWaggon *tmp = start;
 while (tmp != 0 && found==0)
 {if(tmp->data==x) found=tmp;
  tmp = tmp->next;
 }
 return found;
}

Oft will man die Knoten einer Liste nicht in der umgekehrten Reihenfolge durchlaufen, in der sie eingefügt wurden, sondern in derselben. Das kann man dadurch erreichen, dass man einen neuen Knoten immer am Ende der Liste einhängt. Damit man sich dann aber nicht bei jedem Einfügen zeitaufwendig bis zum Ende der Liste durchhangeln muss, kann man einen Zeiger last einführen, der immer auf das letzte Element der Liste zeigt:

Ein neuer Knoten *tmp soll dann der letzte Knoten in der Liste sein:

Das wird dadurch erreicht, dass man sein Element next auf 0 setzt:

CWaggon *tmp = newWaggon(data,0);

In eine nichtleere Liste (last!=0) wird der neue Knoten dann durch

 last->next = tmp; // 1.

nach dem bisherigen letzten Element eingehängt. Falls die Liste dagegen leer ist (last==0), ist der neue Knoten der erste in der Liste:

 first = tmp;

Mit

 last = tmp; // 2.

zeigt last dann auf den neuen letzten Knoten. Diese Anweisungen werden durch die folgende Funktion zusammengefasst:

CWaggon *first = 0;
CWaggon *last  = 0;
 
void insertLastWaggon(T &data)
{                                   // Erzeugt einen neuen Listen-Knoten und fügt diesen
                                    // nach last ein. last zeigt anschließend auf den
                                    // letzten und first auf den ersten Knoten der Liste.
 CWaggon *n = newWaggon(data,0);    // n->{d0,0}
 if (last==0) first=n;
 else last->next=n;                 // 1.
 last=n;                            // 2.
                                    // Nachbedingung: Bezeichnet man den Wert von last vor
                                    // dem Aufruf dieser Funktion mit l0, gilt
                                    // Fall I, l0==0: first==n && last==n
                                    // Fall II, l0!=0: l0->next==n && last==n
}

Beim ersten Aufruf dieser Funktion gilt last==0, was zur Ausführung des then-Zweigs der if-Anweisung und zu der als Fall I bezeichneten Nachbedingung führt.

Bei jedem weiteren Aufruf gilt last!=0: Dann wird der else-Zweig ausgeführt, und es gilt die als Fall II bezeichnete Nachbedingung.

Das Ergebnis der ersten drei Ausführungen der Anweisung

 insertLastWaggon(di);

mit den Daten d1, d2 usw. ist in dem folgenden Ablaufprotokoll dargestellt. Dabei sind die Zeiger auf die in insertLastWaggon erzeugten Knoten wieder wie im letzten Ablaufprotokoll mit n1, n2 usw. bezeichnet, und ein Knoten, auf den ein solcher Zeiger zeigt, mit →{di,nj}. Die Werte in den Spalten n1, n2 usw. erhält man durch Einsetzen der Argumente in die Nachbedingung von insertLastListnode:

                             // first    last          n1         n2         n3
first == 0                               0
last  == 0                                             0
insertLastWaggon(d1);           n1       n1         ->{d1,0}
insertLastWaggon(d2);                    n2         ->{d1,n2}  ->{d2,0}
insertLastWaggon(d3);                    n3                    ->{d2,n3}  ->{d3,0}

Das entspricht nach dem ersten Aufruf der Konstellation

und nach dem zweiten und dritten Aufruf den oben dargestellten Konstellationen. Offensichtlich hängt ein Aufruf von insertLastWaggon einen neuen Knoten auch in eine Liste mit n Elementen am Ende ein.

Eine Liste, bei der Knoten am Ende eingehängt und am Anfang entnommen werden, bezeichnet man auch als „First-in-first-out“-Liste (FIFO) oder als Queue. FIFO-Listen werden oft zur Simulation von Warteschlangen verwendet. Solche Warteschlangen können sich bilden, wenn Ereignisse in der Reihenfolge ihres Eintreffens bearbeitet werden (Fahrkartenausgabe, Bankschalter, Kasse in einem Supermarkt usw.).

Entfernen eines Knotens

Um den Knoten, auf den ein Zeiger pn zeigt, aus einer Liste zu entfernen

hängt man diesen Knoten einfach mit einer Anweisung wie

 pn = pn->next;

aus der Liste aus:

Den vom ausgehängten Knoten belegten Speicher gibt man wie in eraseWaggon gezeigt mit delete wieder frei. Dazu muss man den Zeiger auf den Knoten vor dem Aushängen speichern:

void eraseWaggon(CWaggon *&pn)  // entfernt *p aus der Liste
{if (pn != 0)                   //falls pn==0, nichts machen oder Fehlermeldung
 { CWaggon *tmp = pn;
   pn = pn->next;
   delete tmp;
 }
}

Gesamte Liste löschen

Alle Knoten einer verketteten Liste können durch eine Funktion wie clearList ausgehängt und gelöscht werden. Falls ein Zeiger last auf das letzte Element zeigen soll, muss last auf 0 gesetzt werden.

void clearList()   // löscht alle Knoten der Liste
{while (first!=0) eraseWaggon(first);
 last=0;
}

Resumee

Dieser Abschnitt sollte nur einen ersten Einblick in den Aufbau und die Arbeit mit verketteten Listen geben. Dabei hat sich insbesondere gezeigt, dass verkettete Listen eine Alternative zu Arrays sein können, wenn ein Container zur Speicherung von Daten benötigt wird. Vergleichen wir zum Schluss die wichtigsten Vor- und Nachteile dieser beiden Alternativen. Diese Vor- und Nachteile gelten auch für die Container-Datentypen vector und list der C++-Standardbibliothek, die mit dynamisch erzeugten Arrays und doppelt verketteten Listen implementiert sind:

Die Größe eines gewöhnlichen Arrays muss zum Zeitpunkt der Kompilation festgelegt werden. Wenn man zu diesem Zeitpunkt aber noch nicht weiß, wie viele Daten zur Laufzeit anfallen, reserviert man eventuell zu viel oder zu wenig.
Bei einem dynamisch erzeugten Array kann man mit Funktionen wie ReAllocate bei Bedarf auch noch weiteren Speicher reservieren. Wenn man einen Zeiger p auf eine Position in einem dynamischen Array hat und die Speicherbereiche mit einer Funktion wie ReAllocate verschoben werden, ist p anschließend ungültig. Bei einer verketteten Liste werden die Elemente dagegen nie verschoben. Ein Zeiger auf einen Listenknoten wird nur ungültig, wenn der Knoten gelöscht wird.
Für eine mit new erzeugte Variable (wie z.B. ein Knoten einer Liste) ist neben dem Speicherplatz für die eigentlichen Nutzdaten“ noch Speicherplatz für die Adresse (im Zeiger) notwendig. Speichert man eine Folge von kleinen Datensätzen (z.B. einzelne Zeichen) in einer verketteten Liste, kann das mit einem beträchtlichen Overhead verbunden sein. Die Adresse eines Arrayelements wird dagegen über den Index berechnet und belegt keinen Speicherplatz.
Der Zugriff auf das n-te Element eines Arrays ist einfach über den Index möglich. Da man auf das n-te Element einer verketteten Liste in der Regel keinen direkten Zugriff hat, muss man sich zu diesem meist relativ zeitaufwendig durchhangeln.
Will man in eine sortierte Folge von Daten neue Elemente einfügen bzw. entfernen, ohne die Sortierfolge zu zerstören, muss man in einer verketteten Liste nur die entsprechenden Zeiger umhängen. In einem Array müssen dagegen alle folgenden Elemente verschoben werden.

Offensichtlich kann man nicht generell sagen, dass einer dieser Container besser ist als der andere. Vielmehr muss man die Vor- und Nachteile in jedem Einzelfall abwägen.

Bemerkung: Normalerweise brauchen und sollen Sie (außer in den folgenden Übungsaufgaben) keine eigenen verketteten Listen und dynamischen Arrays schreiben. Die Containerklassen list und vector der C++-Standardbibliothek sind für die allermeisten Anwendungen besser geeignet als selbstgestrickte Listen und Arrays. Da sich die wesentlichen Unterschiede zwischen diesen Containerklassen aus den zugrundeliegenden Datenstrukturen ergeben, ist ein Grundverständnis dieser Datenstrukturen wichtig, auch wenn sie nicht selbst geschrieben werden sollen.

Musterbeispiel

Verkettete Listen