~~SLIDYSHOW~~
====== Verkettete Listen ======
Eine verkettete Liste besteht aus sogenannten **Knoten**, die Daten und einen Zeiger auf den nächsten Knoten enthalten.
===== Definition der Grundstruktur =====
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:
{{bck-292.jpg}}
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:
{{bck-293-1.jpg}}
===== Einhängen eines neuen Knotens =====
Als nächstes sollen Anweisungen gesucht werden, mit denen man vor einem Knoten, auf den ein Zeiger n0 zeigt,
{{bck-293-2.jpg}}
einen neuen Knoten einfügen kann, auf den n0 dann zeigt:
{{bck-293-3.jpg}}
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:
{{bck-293-4.jpg}}
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:
{{bck-294-1.jpg}}
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
{{bck-294-2.jpg}}
Die Werte in den Spalten //n1, n//2 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:
{{bck-296.jpg}}
Ein neuer Knoten //*tmp// soll dann der letzte Knoten in der Liste sein:
{{bck-297.jpg}}
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
{{bck-298-1.jpg}}
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
{{bck-298-2.jpg}}
hängt man diesen Knoten einfach mit einer Anweisung wie
pn = pn->next;
aus der Liste aus:
{{bck-299.jpg}}
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.
----
* [[.:verkettete_listen:Musterbeispiel]]