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 oder zusammengesetzter Datentypen erlauben. Sie werden durch Zeiger auf die jeweils folgende(n) Speicherzellen realisiert.
Table of contents |
2 Typen 3 Listen in der objektorientierten Programmierung 4 Listen in der Programmiersprache LISP |
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 Adress-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.
Listen sind neben den Einzelwerten (Atomen) die Basisdatenstruktur der Programmiersprache LISP. Programme sind Listen von Listen.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/vorwärts, b - backward/rückwärts). 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 außen sind aber hauptsächlich normale Listenoperationen sichtbar, die aufgrund der komplizierteren 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 gar nicht 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 "missbrauchen" kann und nicht extra eine Datenstruktur Liste implementieren muss.Listen in der Programmiersprache LISP