Liste (Datenstruktur)

Verkettete Listen gehören zu den dynamischen Datenstrukturen, die eine Speicherung von einer im Vorhinein nicht bestimmten Anzahl von miteinander in Beziehung stehenden Werten einfacher Datentypen erlauben. Sie werden durch Zeiger auf die jeweils folgende(n) Speicherzellen realisiert.

Vergleich mit anderen Datenstrukturen

Im Gegensatz zu Arrays müssen die einzelnen Speicherzellen nicht nacheinander im Speicher abgelegt sein, es kann also nicht mit einfacher Address-Arithmetik gearbeitet werden, sondern die Speicherorte müssen absolut referenziert werden. Im Gegensatz zu Bäumen sind Listen linear, d.h. ein Element hat genau einen Nachfolger und einen Vorgänger.

Typen

Man unterscheidet grundsätzlich zwischen einfach und doppelt verketteten Listen. Letztere ermöglichen das Durchlaufen der Liste nicht nur vom Anfang bis zum Ende, sondern auch rückwärts. Im Schaubild bedeuten Vi -- Wert i, Pid -- Zeiger i in Richtung d (f - forward, b - backward). Ohne die in Grau gehaltenen backward Zeiger handelt es sich um eine einfach verkettete Liste.