In diesem Beitrag versuche ich mal ganz unkompliziert eine der elementaren Datenstrukturen – die „Liste“ zu erklären.
Eine Liste ist eine dynamische Datenstruktur, was bedeutet, dass sie sich im Gegensatz z. B. zu einem Array im Laufe des Programms anpassen kann. Das heißt es können ihr im Verlauf noch weitere Elemente hinzugefügt werden, ausgetauscht oder entfernt werden. Ihr Speicher ist nicht vorher festgelegt und definiert. Auch die Anzahl der Elemente sind vorher nicht wie bei einem Array definiert.
Benutze die Gliederung, um im Beitrag zu navigieren, falls du nur ein bestimmtes Thema suchst.
Inhaltsverzeichnis
Die Listen
Es gibt zwei grundlegende Arten von Listen:
- Einfache verkettete Liste
- Doppelt verkettete Liste
Es kann sein, dass du in deinen Unterlagen oder in deinem Script auch „Lineare Liste“ stehen hast. Das ist nur ein anderes Wort für die ganz normale Liste. Beide Listen bestehen aus einem Speicher für die einzelnen Elemente und aus Zeigern, die auf das nächste Element zeigen. Es gibt natürlich noch andere Listen wie die adaptive Liste zum Beispiel oder die Skip-List. Im Studium arbeitet man, zumindest war das bei uns so, mit den zwei hier vorgestellten Listen.
Für eine doppelt verkettete Liste musst du dir bei jedem Knoten noch einen Zeiger dazu denken, der auch noch von der anderen Seite auf seinen Vorgänger zeigt.
Mögliche Operationen einer Liste
- Initialisieren der Liste
- die Länge bestimmen
- Nach Element suchen
- Einfügen eines Elements
- Entfernen eines Elements
- Verketten, Liste ausgeben, eine Teilliste bilden, die Liste umkehren
Einfügen eines Elements
Anhang der Grafik unten kannst du dir jetzt denken, wie ein Element in eine bestehende Liste eingefügt wird. Die Elemente rechts vom neu eingefügten Element werden nach rechts geschoben und die linken nach links. Die Zeiger des linken Knotens zeigen nun auf das neue Element und die Zeiger des neuen Elements zeigen nun auf das Element rechts davon.
Element aus Liste entfernen
Auf dieser Grafik siehst du, wie ein Element entfernt wird. Der ganze Knoten samt seiner Verweise und der Zeiger wird entfernt und ein neuer Verweis zu seinem Nachfolger gebildet.
Liste Regeln:
- Jeder Knoten (außer der letzte) hat genau einen Nachfolger
- Jeder Knoten (außer der erste) hat genau einen Vorgänger
- Haben die Knoten einen Zeiger nur auf den Nachfolger, so handelt es sich um eine einfach verkette Liste.
Die Komplexität von Listen
| Array | Einfach verkette Liste | doppelt verkette Liste | |
|---|---|---|---|
| Einfügen am Listenanfang | O(n) | O(1) | O(1) |
| Einfügen an Position | O(n) | O(n) | O(n) |
| Einfügen am Listenende | O(1) | O(n) | O(n) |
| Element entfernen an Position | O(n) | O(n) | O(n) |
| Zugriff auf Position | O(1) | O(n) | O(n) |
In dieser Tabelle siehst du die Komplexität bzw. Laufzeit der einzelnen Operationen in einer einfach & doppelt verketteten Liste. Zum Vergleich daneben habe ich noch die Laufzeit eines Arrays hinzugeschrieben. Daran sieht man, dass die Liste gegenüber dem Array nicht überall Vorteile hat.
Falls du übrigens nicht weißt, was die Komplexität aussagt, so kannst du das in meinem Beitrag „Komplexität – O-Notation – Laufzeit“ nachlesen.
Vor- und Nachteile von Listen
Die Vor-& Nachteile lassen sich aus diesem Beitrag ganz gut ableiten, aber ich schreibe sie hier mal trotzdem in kurz auf:
Vorteile:
- Listen können beliebige Datentypen enthalten. Egal ob es Integer sind oder sogar andere Listen.
- Eine Liste kann beliebig erweitert werden
Nachteile:
- Der Zugriff auf ein Element an einer bestimmten Position ist langsamer als z. B. bei einem Array
Ich hoffe, du weißt jetzt etwas mehr über Listen in der Informatik und dieser Beitrag hat dir weiter geholfen. Wenn du gerade Informatik studierst und Algorithmen schreibst, so kannst du dir auf Studydrive kostenlos meine Zusammenfassung über Listen runterladen. (Damit supportest du mich mit 2 Cent.) Außerdem findest du hier noch als gratis Download Java Beispiel Code für Listen.
