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


zurück zu Informatik, Homepage


2. Hinweise zur Realisierung einer "Doppelt verketteten Liste"

Dieses Kapitel soll nun einen prinzipiellen Überblick darüber geben, wie man einen "Doppelt verketteten Liste" realisiert, unabhäängig von der verwendeten Programmiersprache.

Speziell die folgenden Punkte möchte ich hier näher betrachten:

Bei der Realisierung von Verketteten Listen spielen die Zeiger eine sehr wichtige Rolle. Daher ist der korrekte Umgang mit Zeigern eine Grundvoraussetzung.

nach oben

2.1. Einen Knoten hinzufügen

Beim Hinzufügen eines neuen Knotens muss zwischen 3 Fällen unterschieden werden:

a) FALL 1: Die Liste ist noch leer, es handelt sich hier also um den erste Knoten

Schritt 1:
Speicherplatz für den neuen Knoten (dynamisch) anfordern. In der Regel wird dazu ein Zeiger definiert. (Hier soll der Zeiger pNewNode heißen)
Ist noch genügend Arbeitsspeicher für den neuen Knoten vorhanden, so wird der Zeiger pNewNode mit der Adresse des Arbeitsspeichers, an welche dieser neue Knoten hinterlegt wurde geladen. Der Zeiger pNewNode zeigt somit auf jene Adresse im Arbeitsspeicher, wo sich dieser neue Knoten befindet. Ist jedoch nicht mehr ausreichend Arbeitsspeicher vorhanden so wird in der Regel der Zeiger pNewNode mit 0 (NULL) geladen.

Ersten Knoten einfügen (Schritt 1)

Schritt 2:
Die zu speichernden Daten eingeben und im neuen (ersten) Knoten (Zeiger pNewNode) speichern.

Ersten Knoten einfügen (Schritt 2)

Schritt 3:
Hier, beim ersten Knoten, die Zeiger auf den vorhergehenden Knoten und auf den folgenden Knoten mit dem Inhalt 0 (NULL) laden.

Ersten Knoten einfügen (Schritt 3)

Schritt 4:
Die Zeiger pRoot (für den ersten Knoten), pEnd (fü}r den letzten Knoten) und pActuell (für den aktuellen Knoten) auf diesen ersten Knoten zeigen lassen.

Ersten Knoten einfügen (Schritt 4)

b) FALL 2: Der neue Knoten befindet sich am Ende der Liste

Schritt 1:
Speicherplatz für den neuen Knoten anfordern. (wie im Fall 1)

Knoten am Ende der Liste hinzufügen (Schritt 1)

Schritt 2:
Die zu speichernden Daten eingeben und im neuen Knoten (Zeiger pNewNode) speichern (wie im Fall 1).

Knoten am Ende der Liste hinzufügen (Schritt 2)

Schritt 3:
Hier, beim letzten Knoten der Liste, die Zeiger auf den folgenden Knoten mit dem Inhalt 0 (NULL) laden.

Knoten am Ende der Liste hinzufügen (Schritt 3)

Schritt 4:
Die Knoten auf denen die Zeiger pActuell und pNewNode zeigen miteinander verketten.

Knoten am Ende der Liste hinzufügen (Schritt 4)

Schritt 5:
Die Zeiger pEnd (für den letzten Knoten) und pActuell (für den aktuellen Knoten) auf diesen letzten Knoten zeigen lassen.

Knoten am Ende der Liste hinzufügen (Schritt 5)

c) FALL 3: Der neue Eintrag befindet sich nicht am Ende der Liste, sondern mittendrin

Schritt 1:
Speicherplatz für den neuen Knoten anfordern. (wie im Fall 1)

Knoten innerhalb der Liste hinzufügen (Schritt 1)

Schritt 2:
Die zu speichernden Daten eingeben und im neuen Knoten (Zeiger pNewNode) speichern (wie im Fall 1).

Knoten innerhalb der Liste hinzufügen (Schritt 2)

Schritt 3:
Die Knoten auf denen die Zeiger pNewNode, pActuell und den auf pActuell folgenden miteinander verketten.

Knoten innerhalb der Liste hinzufügen (Schritt 3)

Schritt 4:
Den Zeiger pActuell (für den aktuellen Knoten) auf diesen neuen Knoten zeigen lassen.

Knoten innerhalb der Liste hinzufügen (Schritt 4)
nach oben

2.2. Daten eines Knoten ändern (editieren)

Das ändern (editieren) der Daten die in einem Knoten abgelegt sind ist besonders einfach. Es müssen einfach nur die Daten auf denen der Zeiger pActuell zeigt mit den "neuen" Werten (Daten) überschrieben werden.

Wichtig: Dieser Knoten muss natürlich "existieren", also im Speicher vorhanden sein. Dies erkennt man dadurch dass der Zeiger pActuell einen Wert besitzt der größer als Null ist.

nach oben

2.3. Einen Knoten löschen

Beim Löschen eines Knotens muss zwischen 4 Fällen unterschieden werden:

a) FALL 1: Die Liste besteht nur aus einem einzigen Knoten. Dieser Knoten soll nun gelöscht werden

Den einzigen Knoten löschen

Schritt 1:
Den Speicherplatz auf den der Zeiger pActuell zeigt freigeben. Dadurch wird dieser Knoten aus dem Speicher gelöscht.

Schritt 2:
Die Zeiger pRoot (für den ersten Knoten), pEnd (für den letzten Knoten) und pActuell (für den aktuellen Knoten) mit dem 0 bzw. NULL laden, da ja nun kein Knoten mehr vorhanden ist. Die Liste ist somit wieder leer.

b) FALL 2: Die Liste besteht aus mehreren Knoten, davon wird der erste Knoten gelöscht

Den ersten Knoten löschen

Schritt 1:
Den Zeiger pActuell auf den auf pActuell folgenden Knoten setzen.

Den ersten Knoten löschen (Schritt 1)

Schritt 2:
Den Speicherplatz für den ersten Knoten freigeben (z.B. mit Hilfe des Zeigers pRoot). Dadurch wird dieser (erste) Knoten aus dem Speicher gelöscht.

Den ersten Knoten löschen (Schritt 2)

Schritt 3:
Beim nun aktuellen Knoten den Zeiger, der auf den vorhergehenden Knoten zeigt mit dem Inhalt 0 bzw. NULL laden. Da es ja keinen vorhergehenden Knoten mehr gibt.

Den ersten Knoten löschen (Schritt 3)

Schritt 4:
Den Zeiger pRoot (für den ersten Knoten) auf den nun aktuellen Knoten setzen.

Den ersten Knoten löschen (Schritt 4)

c) FALL 3: Die Liste besteht aus mehreren Knoten, davon wird der letzte Knoten gelöscht

Den letzten Knoten löschen

Schritt 1:
Den Zeiger pActuell auf den auf pActuell vorhergehenden Knoten setzen.

Den letzten Knoten löschen (Schritt 1)

Schritt 2:
Den Speicherplatz für den letzten Knoten freigeben (z.B. mit Hilfe des Zeigers pEnd). Dadurch wird dieser (letzte) Knoten aus dem Speicher gelöscht.

Den letzten Knoten löschen (Schritt 2)

Schritt 3:
Beim nun aktuellen Knoten den Zeiger, der auf den nachfolgenden Knoten zeigt mit dem Inhalt 0 bzw. NULL laden. Da es ja keinen nachfolgenden Knoten mehr gibt.

Den letzten Knoten löschen (Schritt 3)

Schritt 4:
Den Zeiger pEnd (für den letzten Knoten) auf den nun aktuellen Knoten setzen.

Den letzten Knoten löschen (Schritt 4)

d) FALL 4: Die Liste besteht aus mehreren Knoten, davon wird weder der erste Knoten noch der letzte Knoten gelöscht. Sondern ein Knoten irgendwo zwischen Ersten und Letztem

Einen Knoten mittendrinn löschen

Schritt 1:
Die Adresse des auf den Zeiger pActuell folgenden Knoten in pTempNach sichern, und den zu pActuell vorherigen Knoten in pTempVor sichern.

Einen Knoten mittendrinn löschen (Schritt 1)

Schritt 2:
Den Knoten auf den der Zeiger pActuell zeigt entfernen (löschen) und den Speicherplatz für diesen Knoten wieder freigeben.

Einen Knoten mittendrinn löschen (Schritt 2)

Schritt 3:
Die beiden Knoten auf denen die Zeiger pTempVor und pTempNach zeigen miteinander verketten.

Einen Knoten mittendrinn löschen (Schritt 3)

Schritt 4:
Den Zeiger pActuell (für den aktuellen Knoten) auf den Knoten setzen auf den der Zeiger pTempVor zeigt. Dieser Knoten ist nun der "neue" aktuelle Knoten.

Einen Knoten mittendrinn löschen (Schritt 4)
nach oben

2.4. Gesamte Liste löschen

Beim Löschen der gesamten Liste ist darauf zu achten das jeder Knoten für sich gelöscht werden muss, und dass anschließend die Zeiger pRoot (für den ersten Knoten), pEnd (für den letzten Knoten) und pActuell (für den aktuellen Knoten) mit dem Wert 0 bzw. NULL geladen werden müssen, da ja nun kein Knoten mehr vorhanden ist.

Als Vorgehensweise empfiehlt sich folgende Methode: Mit Hilfe zweier Hilfszeiger (z.B. pDeleteNode und pDeleteNextNode) beginnend beim ersten Knoten diesen mit Hilfe einer Schleife Knoten für Knoten vom Speicher entfernen. Dabei zeigt der Zeiger pDeleteNode immer auf den zu entfernenden Knoten und der Zeiger pDeleteNextNode auf den darauf folgenden Knoten. Die Abbruchbediengung für die Schleife ist wenn der Zeiger pDeleteNextNode ein "Null-Zeiger" ist, d.h. der Zeiger den Wert Null beinhaltet. Denn dann ist er am Ende der Liste angekommen.

Die folgende Abbildung zeigt diesen Vorgang in Form eines Flussdiagramms.

Flussdiagramm (Löschen der gesamten Liste)
nach oben

2.5. In der Liste blättern (scrollen)

Unter "scrollen" versteht man das sich bewegen innerhalb der Liste. Also vom aktuellen Knoten zu dessen vorhergehenden Knoten, oder zum nachfolgenden Knoten.
Oft soll es auch möglich sein direkt zum ersten Knoten zu gelangen, und natürlich auch zum letzten Knoten.

Das "scrollen" ist notwendig um dem Benutzer die gewünschten Daten (in den Knoten) sichtbar z.B. am Bildschirm anzeigen zu können.

Bei einer doppelt verketteten Liste ist die Realisierung des "scrollen" sehr einfach. Aufgrund der Verkettung zeigt ja ein Zeiger immer auf den nachfolgenden Knoten und bei der doppelt verketteten Liste ein Zeiger auf den vorhergehenden Knoten. Weiters gibt es noch den Zeiger der auf den ersten Knoten der Liste zeigt (Zeiger pRoot) und in vielen Fällen (so wie in dieser Dokumentation) auch einen Zeiger auf den letzten Knoten der Liste (Zeiger pEnd).
Es ist daher nur notwendig den Zeiger, der auf den aktuellen Knoten zeigt (hier der Zeiger pActuell), mit dem je nach "Scrollart" (also einen Knoten nach vor oder zurück, zum Beginn der Liste, oder ans Ende der Liste) erforderlichen Zeiger zu laden. Die folgende Tabelle zeigt wie der Zeiger pActuell geladen werden muss.

Scrollart Symbol Zeigerzuweisung
Zum Beginn der Liste
<<
pActuell = pRoot
Zum vorhergehenden Knoten
<
pActuell = pActuel.pLast
Zum folgenden Knoten
>
pActuell = pActuel.pNext
Zum Ende der Liste
>>
pActuell = pEnd
nach oben


zurück zu Informatik, Homepage

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