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.

Listen in der objektorientierten Programmierung

In der objektorientierten Programmierung werden Listen häufig auch durch kompliziertere Datenstrukturen, wie binäre Bäume realisiert, nach aussen sind aber hauptsächlich normale Listenoperationen sichtbar, die aufgrund der komplizerteren Datenstruktur um einige weitere Funktionen, wie z.B. Sortieren, sortiertes Einfügen, Entfernen des größten Elementes erweitert werden können. Streng genommen handelt es sich dabei also garnicht um Listen, auch wenn die Namen, die in der konkreten Implementierung diesen Datenstrukturen gegeben werden dies suggerieren. Der Vorteil ist, dass man häufig auch komplizierte Datenstrukturen als Listen "misbrauchen" kann und nicht extra eine Datenstruktur Liste implementieren muss.