Liste (Datenstruktur)

Grundidee und Eigenschaften

Eine verkettete Liste ist eine dynamische Datenstruktur, in der Datenelemente in einer bestimmten Reihenfolge gespeichert werden. Dynamisch bedeutet hier: Bei der Erstellung muss die maximale Anzahl der Elemente nicht festgelegt werden, und die Anzahl der Elemente darf sich während der Laufzeit beliebig ändern.

Listen sind wichtig, wenn Daten häufig eingefügt oder gelöscht werden und eine feste Speichergröße, wie bei vielen Array-Anwendungen, unpraktisch wäre. Der Zugriff geschieht über Knoten. Ein Knoten enthält die eigentlichen Daten und mindestens einen Zeiger, also einen Verweis auf einen anderen Knoten. Dadurch entsteht eine Kette von Elementen.

Einfach verkettete Listen

Der Datentyp der einfach verketteten Listen mit Elementen vom Typ A wird rekursiv definiert als L = Nil | [A, L_A]. Das bedeutet: Eine Liste ist entweder leer, also Nil, oder sie besteht aus einem Element vom Typ A und einer weiteren Liste.

Technisch wird eine einfach verkettete Liste meist durch einzelne Knoten umgesetzt. Jeder Knoten enthält die Nettodaten und einen Verweis auf den Nachfolgeknoten. Im letzten Knoten steht als Nachfolger der Null-Zeiger, der ebenfalls Nil genannt wird.

Elementare Operationen sind das Erweitern der Liste um einen Knoten am Anfang und das Entfernen des ersten Knotens. Beide Operationen können in der Zeit O(1) erfolgen. Das heißt: Ihr Aufwand ist konstant und hängt nicht von der Länge der Liste ab.

Ein Vorteil ist, dass das Einfügen an jeder Stelle O(1) kostet, sobald der Einfügepunkt bereits gefunden wurde. Bei einem Array müssten dagegen im ungünstigen Fall Datensätze umkopiert werden, was O(n) kostet. Außerdem benötigt eine einfach verkettete Liste nur einen zusätzlichen Zeiger pro Knoten. Ein Nachteil ist das Suchen: Im ungünstigsten Fall muss über jeden Knoten iteriert werden, daher kostet das Suchen O(n).

Doppelt verkettete Listen

Bei einer doppelt verketteten Liste besitzt jedes Element zwei Zeiger: einen auf das nachfolgende Element und einen auf das vorhergehende Element. Der Vorgänger-Zeiger des ersten Elements und der Nachfolger-Zeiger des letzten Elements zeigen auf NULL. So lassen sich Anfang und Ende der Liste feststellen.

Der wichtigste Vorteil ist, dass ein Element in O(1) entfernt werden kann, auch wenn man nicht über eine der beiden Verkettungen zu ihm gelangt ist. Bei einer einfach verketteten Liste müsste man dafür erst den Vorgänger suchen. Außerdem kann man eine doppelt verkettete Liste auch von hinten nach vorne durchlaufen.

Nachteile sind der höhere Speicherbedarf durch die zusätzlichen Zeiger und der größere Aufwand beim Einfügen und Löschen, weil auch die Vorgänger-Zeiger der nachfolgenden Listenelemente angepasst werden müssen.

Weitere Listenformen

Ein Listenkopf, auch Listenanker genannt, ist ein Datenfeld mit zusätzlichen Informationen über die Liste, zum Beispiel der Anzahl der Knoten. Er zeigt auf das erste Element.

Eine Skip-Liste speichert Daten ebenfalls in Containern. Diese enthalten einen Schlüssel und einen Zeiger auf den nächsten Container. Zusätzlich können Container Zeiger auf weiter entfernte Container enthalten, sodass Schlüssel übersprungen werden können. Jeder Container hat eine Höhe h, die um 1 kleiner ist als die Anzahl seiner Zeiger. Die Zeiger werden von 0 bis h nummeriert. Grundsätzlich imitiert eine Skip-Liste die binäre Suche auf einem Feld.

Es gibt ausgeglichene SkipLists, unausgeglichene SkipLists und randomisierte SkipLists. Bei allen Typen darf derselbe Inhalt mehrfach auftreten. Ausgeglichene und unausgeglichene SkipLists sind geordnet, randomisierte SkipLists müssen nicht notwendigerweise geordnet sein. Einfügen, Suchen und Löschen haben jeweils eine erwartete Laufzeit von O(log n).

Bei randomisierten Skiplisten wird die Höhe h nach dem Zufallsprinzip bestimmt. Die Wahrscheinlichkeit, dass eine bestimmte Höhe erreicht wird, beträgt 1/(2 · 2^h). Bei nicht randomisierten Skiplisten wird die Höhe so gewählt, dass jeder Zeiger mit Zeigerhöhe z auf einen Container 2^z Positionen weiter hinten zeigen kann.

Adaptive Listen versuchen, die mittlere Zugriffszeit zu verringern. Dazu werden Elemente nach ihrer Zugriffshäufigkeit angeordnet. Die Strategie MoveToFront verschiebt ein Element bei jedem Zugriff an den Anfang. Transpose vertauscht ein Element bei jedem Zugriff mit seinem Vorgänger, außer beim ersten Element. Gratification speichert die Zugriffshäufigkeit jedes Elements und sortiert die Liste in bestimmten Intervallen danach neu.

Listen als abstrakter Datentyp und in OOP

Als abstrakter Datentyp beschreibt eine Liste nicht nur eine konkrete Speicherform, sondern auch die Struktur und Operationen, mit denen Daten verwaltet werden. Die Daten werden in einer Sequenz von Schlüsseln gespeichert. Eine Listenstruktur kann aus einem Zähler, einem Zeiger und der Adresse zu einer Vergleichsfunktion bestehen. Ein Datenknoten enthält einen Zeiger auf eine Datenstruktur und einen selbstreferenzierenden Zeiger auf den nächsten Knoten.

In der objektorientierten Programmierung werden Listen nach dem Prinzip der Datenkapselung über Listenoperationen beschrieben. Die innere Umsetzung kann unterschiedlich sein und muss von außen nicht sichtbar sein. Intern können auch andere Datenstrukturen wie binäre Bäume verwendet werden. Dadurch können zusätzliche Funktionen angeboten werden, etwa Sortierung, sortiertes Einfügen oder das Entfernen des größten Elements.

Welche konkrete Listenimplementierung sinnvoll ist, hängt vom Einsatzzweck ab. Wenn häufig wahlfrei über einen Index zugegriffen wird, ist eine verkettete Liste eine schlechte Wahl, weil n Operationen nötig sind, um das n-te Element zu adressieren. Objektorientierte Bibliotheken bieten daher oft eine Schnittstelle und mehrere Implementierungen an. In Java gibt es zum Beispiel die Schnittstelle java.util.List sowie konkrete Implementierungen wie java.util.LinkedList und java.util.ArrayList. In C++ werden Listen und Vektoren in der Standardbibliothek implementiert.

Typische Operationen und Beispiele

Die Beispiele im Artikel zeigen Listenoperationen in C# und C++. In C# wird zunächst ein Knoten definiert, der eine Zahl und einen Nachfolgeknoten speichern kann. Der Knoten besitzt ein Feld element vom Typ int und ein Feld folgeknoten, das auf den nächsten Knoten verweist.

Beim Einfügen eines neuen Elements wird die Liste bis zum letzten Knoten durchlaufen. Dort wird ein neuer Knoten angelegt und sein element-Wert gesetzt. Beim Suchen wird jeder Knoten geprüft: Wenn das gesuchte Element gefunden wird, liefert die Funktion true, sonst nach dem Ende der Liste false.

Beim Löschen wird zuerst bis zu einem Knoten mit dem gesuchten Wert gelaufen. Danach wird über die Liste iteriert; wenn der Folgeknoten das zu löschende Element enthält, wird dieser Folgeknoten übersprungen, indem der Verweis auf dessen Nachfolger gesetzt wird.

Das C++-Beispiel verwendet die Standardbibliothek mit list<int>. Es zeigt das Einfügen am Anfang mit push_front, das Anfügen am Ende mit push_back, das Durchlaufen der Liste mit einer for-Schleife, das Entfernen aller Zahlen größer als 4 mit erase und remove_if, das Sortieren mit sort und das vollständige Löschen mit clear.