Verkettete Listen in C++ und Visual Basic (Informatik)
Verkettete Listen in C++ und Visual Basic (Informatik)
linkedlist_doku.pdf (803 KB)
Eine "Verkettete Liste" (engl. linked list) ist eine sehr einfache
Möglichkeit zum Speichern einer umfangreichen Datenmenge und ist, im Sinne der Informatik,
eine grundlegende dynamischen Datenstruktur.
Unter einer dynamischen Datenstruktur versteht man eine Datenstruktur die zwar vom
Programmierer festgelegt wurde (z.B. ein Telefonbuch soll die Informationen Vorname,
Nachname, Telefonnummer usw. enthalten) aber wie viele solcher Telefonnummern gespeichert
werden soll ist zum Zeitpunkt der Programmerstellung nicht bekannt.
Die wesentliche Komponente einer verketteten Liste ist der so genannte Knoten (engl. node). Die folgende Abbildung zeigt den Aufbau eines solchen Knotens (Node).
Ein Knoten beinhaltet die zu speichernden Nutzdaten (im einfachsten Fall nur
eine bestimmte Zahl, oder bei einer Anwendung als Telefonbuch sämtliche Informationen
für eine Person, also Vorname, Nachname, Telefonnummer usw.) und zumindest einen
Zeiger auf den nächsten Knoten. Die Zeiger stellen somit das Bindeglied zwischen
den einzelnen Knoten dar, daher auch der Name "Verkettete Liste".
Wichtig ist, dass die Adresse des ersten Knoten an irgendeiner Stelle im Programm
bekannt sein muss.
Bei den "Verketteten Listen" unterscheidet man grundsätzlich zwei Arten:
Einfach verkettete Liste
Bei einer "Einfach verketteten Liste" entspricht der Aufbau eines Knotens der folgenden Abbildung. Die Verknüpfung der Knoten erfolgt dabei mit nur einem Zeiger. In der Regel zeigt dieser Zeiger immer auf den folgenden Knoten. Die Abbildung zeigt eine solche Liste mit drei Knoten. Die Nutzdaten sind in diesem Beispiel die Zahlen 27, 1234 und -89.
Wie schon erähnt, muss der erste Knoten der "Verketteten Liste" im Programm bekannt sein. In der oberen Abbildung übernimmt diese Aufgabe der Zeiger pRoot.
Bei den meisten Anwendungen ist es sehr hilfreich, wenn man einen Zeiger hat, der auf den Knoten zeigt, den man gerade bearbeiten möchte. (z.B. um den Inhalt dieses Knotens auszulesen, oder zu veändern, oder aber um an dieser Stelle einen neuen Knoten hinzufügen zu können). In der oberen Abbildung übernimmt diese Aufgabe der Zeiger pActuell.
Das Ende der "Verketteten Liste" erkennt man dadurch, dass der Zeiger des letzten Knotens den Wert NULL beinhaltet, da ja kein weiterer Knoten mehr vorhanden ist. Siehe obere Abbildung.
Bei der "Einfach verketteten Liste" ist es nur möglich in der Richtung vom ersten Knoten zum letzten Knoten zu gelangen. Eine "Rückwärtsbewegung" ist hier nicht möglich. Dies ist der Nachteil der "Einfach verketteten Liste" gegenüber der "Doppelt verketteten Liste".
Doppelt verkettete Liste
Bei der "Doppelt verketteten Liste" hat jeder Knoten einen zusätzlichen Zeiger. Dieser Zeiger zeigt immer auf den vorhergehenden Knoten. Somit kennt jeder Knoten seinen "Vorgänger-Knoten" und seinen "Nachfolger-Knoten". Die folgende Abbildung zeigt eine solche Liste mit drei Knoten. Die Nutzdaten sind in diesem Beispiel die Zahlen 27, 1234 und -89.
Der Vorteil der "Doppelt verketteten Liste", nämlich die Bewegung in beiden Richtungen, wird durch den zusätzlichen Zeiger, was einen zusätzlichen Speicherbedarf bedeutet, erkauft.
Auch bei der "Doppelt verketteten Liste" muss der erste Knoten der
"Verketteten Liste" im Programm bekannt sein. (Zeiger pRoot
in der oberen Abbildung)
Dieser Zeiger ist der einzig notwendige. Weitere Zeiger sind zwar manchmal sehr
hilfreich aber nicht unbedingt notwendig. Zum Beispiel könnte ein Zeiger hilfreich sein,
der immer auf den letzten Knoten zeigt. In der oberen Abbildung wäre dies der Zeiger
pEnd. Ein weiterer Zeiger pActuell,
der die selbe Funktion wie bei der "Einfach verketteten Liste" hat.
Dadurch, dass jeder Knoten auch einen Zeiger zu seinem Vorgänger-Knoten besitzt, muss
dafür gesorgt werden, dass dieser Zeiger beim ersten Knoten den Wert NULL
besitzt, so wie beim letzten Knoten der Zeiger auf den folgenden Knoten ebenfalls den
Wert NULL beinhalten muss, da es ja in beiden Fällen
keinen weiteren Knoten gibt.
Aus diesem Grund muss der Zeiger pRoot nicht
unbedingt auf den ersten Knoten zeigen. Es reicht wenn er auf irgend einen beliebigen
Knoten der "Verketteten Liste" zeigt.
Autor: Buchgeher Stefan