|
Hauptseite - Welches System? - Hardware - Software - Emulatoren - |
Internet MausNet Programmieren Verweise Über |
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:
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.
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.
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
English version not yet available. |