3.2 doppelt verkettete Liste

Um in der Liste leicht in beide Richtungen suchen zu können, z.B. um von einem Element den Vorgänger zu suchen, kann der Knoten zwei Zeiger bekommen. Ein Zeiger zeigt auf das nachfolgende Element, der zweite zeigt auf das Element vor dem Knoten in der Liste. Damit werden allerdings Einfüge- und Löschoperationen komplizierter.

Das Einfügen am Anfang der Liste ist noch recht einfach und ähnelt dem Einfügen für die einfach verkettete Liste.

1. Der Nachfolger-Zeiger des neuen Elements wird auf den Wert gesetzt, den die Wurzel hat, zeigt also auf das erste Element der Liste.
2. Der Vorgänger-Zeiger des ersten Elements zeigt auf das neue Element.
3. Jetzt wird die Wurzel auf das neue Element gesetzt.

Das Einfügen in der Mitte oder am Ende der Liste ähnelt auch dem Einfügen in die einfach verkettete Liste, es müssen zusätzlich die Vorgänger-Zeiger mit umgesetzt werden.

1. Der Nachfolger-Zeiger des einzufügenden Elements wird auf den Wert gesetzt, den der Zeiger des Elements hat, auf den der Suchzeiger zeigt.
2. Der Vorgänger-Zeiger des Elements, vor dem eingefügt wird, wird auf das neue Element gesetzt.
3. Der Vorgänger-Zeiger des neuen Elements wird auf den Wert gesetzt, auf den der Suchzeiger zeigt. Er zeigt also auf das Element, hinter dem eingefügt wird.
4. Der Nachfolger-Zeiger des Elements, auf den der Suchzeiger zeigt, wird auf das neue Element gesetzt.

Das Entfernen eines Elements ähnelt auch wieder dem Entfernen aus einer einfach verketteten Liste. Es müssen aber wieder zwei Zeiger verändert werden.

1. Der Suchzeiger durchläuft die Liste bis zu dem Element, das direkt vor dem zu entfernenden Element steht. Ein weiterer Zeiger wird auf das zu löschende Element gesetzt, damit es nicht verlorengeht.
2. Der Nachfolger-Zeiger des Elements, auf den der Suchzeiger zeigt, wird auf den Wert gesetzt, auf den das zu löschende Element zeigt.
3. Der Vorgänger-Zeiger des Elements hinter dem zu löschenden Element wird auf das Element gesetzt, auf den der Suchzeiger zeigt.
4. Damit ist das Element aus der Liste entfernt.

Auch hier kann die Sonderbehandlung durch ein zusätzliches Dummy-Element, dem Wächter, vermieden werden.

English version not yet available.