Datenstrukturen: Liste / Linked List

Bei einem Array gibt es ein Nachteil. Man muss im Vorfeld wissen, wieviele Elemente man benötigt. Dieses Problem wird mit der Datenstruktur einer Liste behoben.

Die (einfach verkettete) Liste

Das Konzept einer einfach verketteten Liste besteht darin, dass man beliebig viele Elemente einfügen aber auch entfernen kann.
Damit Daten gespeichert werden, wird im Hauptspeicher jeweils ein Block angelegt. So ein Block enthält zum einen die Daten als Datentyp und zum anderen einen Zeiger (Pointer) auf den nächsten Block.
Gibt es keinen Nachfolger, so zeigt der Zeiger nirgendwo hin (NIL oder nullpointer).
In diesem Fall handelt es sich um das letzte Listenelement

Pseudocode: Block einer einfach verketteten Liste

Node {
    datatype : data
    pointer* : next
}

Wird ein Element an das Listenende eingefügt, so muss der neu entstandene Block mit dem letzten Block aus der Liste verbunden werden. Der next-pointer des letzten Blocks zeigt nun auf den neu eingefügten Block.
Nun hat der neu eingefügte Block einen nullpointer, da er jetzt das letzte Listenelement ist.

Abbildung 1: Einfach verkettete Liste

Schwieriger ist es, wenn ein Block aus der Liste entfernt werden soll. Zunächst muss der zu entfernende Block gefunden werden. Dazu druchwandert man die Liste.
Wird der zu entfernende Block gefunden, so muss der Pointer des Vorgängerblocks mit dem Nachfolgerblock verbunden werden. Erst dann darf das gewünschte Element entfernt werden. Andernfalls entsteht ein "loch" in der Liste oder auch memory leak genannt, da man die Nachfolger nicht mehr erreichen kann.

Abbildung 2: Entfernen eines Blocks

Weiterhin gibt es noch die zweifach verkettete Liste. Die Funktionsweise ist dieselbe wie mit einer einfach verketteten Liste. Der Unterschied ist, dass jeder Block zusätzlich noch einen zweiten Zeiger hat, nämlich zu seinem Vorgängerblock.

Pseudocode: Block einer zweifach verketteten Liste

Node {
    datatype : data
    pointer* : next
    pointer* : prev
}

Der Vorteil ist, dass man die Liste in beiden Richtungen durchlaufen kann. Bei der einfach verketteten Liste kann man nur von "vorne nach hinten" laufen. Dadurch das jeder Block einen zweiten Pointer hat, verbrauchen zweifach verkettete Listen mehr Speicherplatz.

Anwendungsbeispiel

Listen sollten immer dann verwendet werden, wenn man im Vorfeld nicht weiss wieviele Elemente man benötigt.

• Man möchte eine Textdatei einlesen und alle Wörter speichern. Ein Array wäre nicht geeignet, da man die Anzahl der Wörter nicht kennt.
• Listen unterstützen Generics, Arrays nicht immer (Java)

Quellen
cslibrary.stanford.edu/103/LinkedListBasics.pdf
www.cs.usfca.edu/~srollins/courses/cs112-f07/web/notes/linkedlists/ll2.gif
www.basicsbehind.com/wp-content/uploads/2014/07/Singly-Linked-List-delete.jpg