Verkettete Listen in C++ und Visual Basic (Informatik)


zurück zu Informatik, Homepage


1. Grundlegendes zu "Verketteten Listen" (engl. linked list)

1.1. Was ist eine "Verkettete Liste"

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.

nach oben

1.2. Aufbau einer "Verkettete Liste"

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.

nach oben

1.3. Arten von "Verkettete Liste"

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.

Einfach verkettete Liste mit drei Knoten

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.

Doppelt verkettete Liste mit drei Knoten

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.

nach oben


zurück zu Informatik, Homepage

Autor: Buchgeher Stefan
Erstellt: 10. März 2007
Letzte Änderung: