Verkettete Liste
Eine verkettete Liste (engl. linked list) ist eine Datenstruktur, die beliebig viele Elemente in linearer Form speichern kann, d.h. zu jedem Element außer dem letzten existiert genau ein Nachfolger und zu jedem Element außer dem ersten existiert genau ein Vorgänger.
Verkettete Listen sind rekursiv definiert und bestehen aus zwei Teilen:
- einem Objekt, genannt
head; das ist das erste Element der (Teil-)Liste - einer verketteten Liste, genannt
tail; das ist der gesamte Rest der Liste
Die einfachsten Fälle sind die leere Liste:
... und eine einelementige Liste:
An diese Liste können nun weitere Elemente angefügt werden, indem schrittweise neue Listen erzeugt werden:
Ein Element nach dem anderen:
Operationen
Suchen
Selbst wenn die Liste sortiert ist, kann nur dadurch nach Elementen suchen, dass man die ganze Liste von vorn nach hinten durchgeht. Da jedes Element nur mit seinem direkten Nachfolger verbunden ist, können auch keine Algorithmen wie die Binäre Suche eingesetzt werden. Die Suche in einer verketteten Liste hat damit eine Laufzeit in .
Einfügen
Am Ende einer Liste kann man einfach ein neues Element anfügen, indem man ein neues Listen-Objekt mit einem Eintrag erzeugt:
... und dann den tail des letzten Listenelements darauf zeigen lässt.
In der Mitte einer Liste kann man einfach ein neues Element anfügen, indem man ein neues Listen-Objekt mit einem Eintrag erzeugt:
... und dann den tail des vorhergehenden Listenelements darauf zeigen lässt. Damit das Ende der alten Liste nicht verloren geht, muss auch der tail des neu eingefügten Elements entsprechend gesetzt werden.
Entfernen
Ein Element entfernt man einfach, indem man den tail von dessen Vorgänger auf dessen Nachfolger zeigen lässt. Für die Liste ist dieses Element dann nicht mehr existent. In den meisten modernen Programmiersprachen springt außerdem, sobald keine Referenzen mehr auf ein Objekt zeigen, ein Mechanismus namens Garbage Collection an. Dieses Objekt, auf das nun nicht mehr aus dem Programm heraus zugegriffen werden kann, wird dann aus dem Speicher gelöscht.
Dass der tail von Element 2 weiterhin auf Element 3 zeigt, ist nicht weiter tragisch. Element 2 ist trotzdem aus der Liste verschwunden, weil es keinen Weg mehr gibt, zu Element 2 hin zu navigieren. Dem Verweis von Element 2 auf Element 3 kann man nicht rückwärts folgen.
