Atari Logo
Atari Computer

Hauptseite -
Welches System? -
Hardware -
Software -
Emulatoren -
Internet
MausNet
Programmieren
Verweise
Über

Algorithmen

Home Botanik: Basisalgorithmen für Container Botanik: Basisalgorithmen für Container doppelt verkettete Liste

3.1 einfach verkettete Liste

Bei einer einfach verketteten Liste enthält jeder Knoten einen Zeiger, so daß jeder Knoten einen Nachfolger hat. Um auf die Liste zugreifen zu können, muß ein Zeiger auf das erste Element, die Wurzel, gespeichert werden.

Soll ein Element in eine leere Liste eingefügt werden (die Wurzel zeigt auf kein Element), ist dies einfach. Es wird einfach die Wurzel auf die Adresse des neuen Elements gesetzt.

Ist die Liste nicht leer, müssen beim Einfügen zwei Fälle unterschieden werden. Muß das neue Element vor dem ersten in der Liste eingefügt werden, muß die Wurzel verändert werden. Das Einfügen läuft wie folgt ab:


  1. Dies ist der Zustand vor dem Einfügen: eine Liste und das neue Element.
  2. Zuerst wird der Zeiger des neuen Elements auf den Wert gesetzt, auf den die Wurzel zeigt.
  3. Jetzt wird die Wurzel auf das neue Element gesetzt. Wird zuerst die Wurzel umgesetzt, würde man nicht mehr auf die Liste zugreifen können.
  4. und das neue Element ist eingefügt.

Muß das neue Element in der Mitte oder am Ende der Liste eingefügt werden, wird ein weiterer Zeiger benötigt. Dieser Zeiger dient dazu, der Reihe nach auf jedes Element der Liste zuzugreifen.


  1. Der Suchzeiger wird auf den Wert gesetzt, den die Wurzel hat. Anschließend wird die Liste durchwandert. Für jeden Schritt zu dem nächsten Element wird der Zeiger auf den Wert gesetzt, den der Zeiger des Elements hat, auf den er zeigt. Dies wird solange durchgeführt, bis der Zeiger des Knoten auf ein Element zeigt, daß größer als das einzufügende ist. Der Suchzeiger wandert also der Liste entlang, bis die Position gefunden wurde, hinter der das neue Element eingefügt werden soll.
  2. Der Zeiger des einzufügenden Elements wird auf den Wert gesetzt, den der Zeiger des Elements hat, auf den der Suchzeiger zeigt.
  3. Der Zeiger des Elements, auf den der Suchzeiger zeigt, wird auf das einzufügende Element gesetzt.
  4. und das neue Element ist eingefügt.

Auch beim Entfernen eines Elements aus der Liste muß der Fall, das das erste Element entfernt wird, gesondert behandelt werden. Dies ist aber einfach, es wird einfach die Wurzel auf das Element gesetzt, auf das auch auch das erste Element verweist. Achtung: zuerst sollte ein Zeiger auf das erste Element gesetzt werden, damit das Element nicht verlorengeht.

Wird mitten in der Liste ein Element entfernt, muß wieder ein Zeiger so lange die Liste durchwandern, bis das Element vor dem zu entfernenden Element gefunden ist.


  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 Zeiger des Elements, auf den der Suchzeiger zeigt, wird auf den Wert gesetzt, auf den das zu löschende Element zeigt.
  3. Jetzt zeigt kein Element der Liste auf das zu löschende Element. Und mit dem zu löschenden Element kann beliebig weiter verfahren werden.
  4. und das Element ist gelöscht.

Das Ende der Liste muß nicht gesondert behandelt werden. Wenn ein Element auf den Nachfolger eines anderen gesetzt wird ist es egal, ob der Nachfolger ein Element oder NULL bzw. NIL ist.

Wird zusätzlich eine Dummyknoten bzw. Wächter an die Wurzel gehängt, kann die Sonderbehandlung für das Einfügen nach der Wurzel bzw. Löschen des ersten Elements nach der Wurzel entfallen. Es muß nur garantiert sein, daß dieser Dummy auch immer das kleinste Element ist bzw. muß der Algorithmus die Vergleiche erst mt den Nachfolgern des Wächters durchführen. Dazu kann der Wächter auch vor jeder Operation auf der Liste auf einen geeigneten Wert gesetzt werden.

Beispielcode
Home Botanik: Basisalgorithmen für Container Botanik: Basisalgorithmen für Container doppelt verkettete Liste


Best viewed with any browser English version not yet available.

Änderungen und Irrtümer vorbehalten. Letzte Änderung:
14 September 2001.
Home - Mail an den Webmaster - Impressum