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) Knoten oder Speicherzellen des Arbeitsspeichers realisiert.
| Inhaltsverzeichnis |
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.
Knoten
Ein Knoten (engl. node) bezeichnet ein Element der Liste, welches die Daten und einen Zeiger auf seinen Nachfolger enthält.
Bild: Knoten _(Informatik).png
Typen
Man unterscheidet grundsätzlich zwischen einfach und mehrfach oder doppelt verketteten Listen.
Einfach verkettete Liste
Sie ist die einfachste Form der verketteten Liste, da sie neben den einzelnen Knoten nur einen "Start"-Zeiger besitzt. Letzterer zeigt auf den ersten Knoten in der Liste (roter Pfeil). Der letzte Knoten in der Liste zeigt auf den Nullwert (hier NIL).
Verbale Definition: Eine Liste ist entweder leer oder sie besteht aus einem Kopf und einem Zeiger, der wiederum eine Liste ist.
Bild: Einfach_verkettete_Liste.png
Vorteile
- Sehr geringer Speicherbedarf
Nachteile
- Es ist aufwändig nach Daten zu suchen, Knoten einzufügen, zu löschen und die Liste zu sortieren da über jedes einzelnen Element gegangen (iteriert) werden und viele Sonderfälle (wie z.B. das Einfügen an der letzten Stelle) behandelt werden müssen.
Erweiterungen Da sich die zuvor erwähnte Variante als zu umständlich (siehe Nachteile) erwiesen hat, wird oft eine der hier nachstehenden Erweiterungen verwendet.
- Liste mit "Ende"-Zeiger: Führt einen Zeiger Ende ein, der auf das letzte Element der Liste zeigt.
- Vorteile:
- Über die Liste kann von hinten nach vorne iteriert werden; es gibt weniger Sonderfälle beim einfügen, entfernen und sortieren.
- Nachteile:
- Unbedeutend mehr Speicherbedarf
Doppelt (mehrfach) verkettete Liste
thumb|Verkettete Liste Hier hat jedes Element der Liste nicht nur einen Zeiger auf das nachfolgende, sondern auch einen zusätzlichen zweiten auf das Vorgänger-Element.
Der Vorgänger-Zeiger des ersten Elementes zeigt auf ein Dummy-Element, wie auch der Nachfolger-Zeiger des letzten Elementes. Dieses besondere Element dient zum Auffinden des Anfangs und des Endes der doppelt verketteten Liste.
Nachteile
- Etwas mehr Speicherbedarf
Vorteile
- Man kann problemlos Elemente aus der Liste löschen und einfügen
- Die Elemente in der zweiten Hälfte der Liste sind schneller aufzufinden
Weitere Formen
Liste mit Listenkopf: Der Listenkopf ist ein spezieller Knoten am Anfang der Liste, der zusätzliche Informationen, wie z.B. die Anzahl der Knoten in der Liste, enthält. Der wesentlichste Vorteil ist, dass es wie bei der Liste mit Ende'-Zeiger weniger Sonderfälle wie z.B. beim Einfügen des 1. Elements gibt.
Listen in der objektorientierten Programmierung
In der objektorientierten Programmierung zeichnen sich Listen gemäß dem Prinzip der Kapselung durch eine Menge von Listenoperationen aus. Intern können dabei unterschiedliche und durchaus auch kompliziertere Datenstrukturen, wie binäre Bäume zum Einsatz kommen. Aufgrund der internen Datenstruktur können dabei oft auch weitere Funktionen, wie z.B. Sortierung, sortiertes Einfügen, Entfernen des größten Elementes, etc. angeboten werden.
Je nach Einsatzzweck kann es sinnvoll sein, zwischen konkreten Implementierungen der Schnittstelle Liste zu wählen. Wird beispielsweise hauptsächlich wahlfrei über Index auf die List zugegriffen, wäre eine verkettete Liste eine schlechte Wahl, da dort n Operation nötig sind, um das nte Element zu adressieren.
Daher werden in objektorientierten Bibliotheken oft neben der Schnittstelle verschiedene konkrete Implementierungen angeboten. Beipielsweise gibt es in der Progammiersprache Java als Schnittstelle java.util.List und als konkrete Implementierungen java.util.LinkedList und java.util.ArrayList.
Listen in der Programmiersprache LISP
Listen sind neben den Einzelwerten (Atomen) die Basisdatenstruktur der Programmiersprache LISP. Programme sind Listen von Listen.