Einfache & Doppelt verkettete Listen erklärt

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 Programm 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.

Die Listen

Es gibt zwei grundlegende Arten von Listen:

  1. Einfache verkettete Liste
  2. Doppelt verkettete Liste

Es kann sein das 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.

Einfach verkette Liste

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 Elemente und die Zeiger des neuen Elements zeigen nun auf das Element rechts davon.

einfach verkette Liste Element einfügen

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.

Einfach verkette Liste Element löschen

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

ArrayEinfach verkette Listedoppelt verkette Liste
Einfügen am ListenanfangO(n)O(1)O(1)
Einfügen an PositionO(n)O(n)O(n)
Einfügen am ListenendeO(1)O(n)O(n)
Element entfernen an PositionO(n)O(n)O(n)
Zugriff auf PositionO(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, das 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 entahlten. 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.

 

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.