liste-datenstruktur

List (Liste)

Kurz: Eine geordnete Datenstruktur, die Elemente in einer festen Reihenfolge hält und Duplikate erlaubt — jedes Element ist über seine Position (Index) ansprechbar.

Genauer: Anders als ein klassisches Array kann eine Liste in den meisten Sprachen dynamisch wachsen und schrumpfen. Gängige Implementierungen sind das dynamische Array (schneller Indexzugriff, langsameres Einfügen in der Mitte) und die verkettete Liste (schnelles Einfügen/Entfernen, langsamerer Indexzugriff).

Im Detail

Die Wahl der richtigen Listen-Implementierung ist ein klassisches Beispiel dafür, dass es DIE beste Datenstruktur nicht gibt — nur die beste für den konkreten Anwendungsfall:

# Dynamisches Array: gut für Lesezugriff per Index
liste[500]              # O(1) - direkter Sprung an die Speicherposition
 
# Verkettete Liste: gut für Einfügen/Entfernen in der Mitte
liste.einfuegen_an(500, neuesElement)  # O(1), sobald man an der Stelle ist

Beim dynamischen Array liegen alle Elemente hintereinander im Speicher, weshalb der Zugriff per Index blitzschnell ist (die Speicheradresse lässt sich direkt berechnen). Wird die Kapazität überschritten, muss intern ein größerer Speicherblock reserviert und ALLE bestehenden Elemente dorthin kopiert werden — das passiert selten, kostet dann aber kurzzeitig mehr Zeit.

Bei der verketteten Liste ist jedes Element ein eigenständiger “Knoten”, der zusätzlich einen Verweis auf den nächsten (und bei einer doppelt verketteten Liste auch den vorherigen) Knoten enthält. Ein neues Element einzufügen bedeutet nur, ein paar Verweise umzubiegen — kein Kopieren nötig. Der Nachteil: Um auf das 500. Element zuzugreifen, muss man ab dem Anfang JEDEN einzelnen Verweis nacheinander folgen, es gibt keinen direkten Sprung.

Faustregel für die Wahl: Wird hauptsächlich per Index gelesen und selten in der Mitte eingefügt/entfernt → dynamisches Array. Wird häufig an beliebigen Stellen eingefügt/entfernt und selten wahlfrei per Index gelesen → verkettete Liste. In der Praxis ist das dynamische Array (in den meisten Sprachen einfach “die Liste” schlechthin) der deutlich häufigere Standardfall.

Siehe auch: ArrayList, LinkedList, Collections