Liste

Eine Liste (engl. List) ist eine dynamische Datenstruktur, die über Verweise linear verkettet ist.

Aufbau

Eine Liste kannst du dir wie eine Menschenkette vorstellen:

Eine Liste besteht aus Knoten, in denen Daten gespeichert sind.

Der erste Knoten wird manchmal auch Kopf der Liste genannt.

Die Knoten sind mit Zeigern verkettet.

Der erste und letzte Knoten zeigen beide zusätzlich auf NULL:

Arten von Listen

Die drei wichtigsten Listen sind:

• Einfach verkettete Liste
• Doppelt verkettete Liste
• Kreisförmig verkettete Liste

Einfach verkettete Liste

Eine einfach verkettete Liste funktioniert wie eine Polonaise bei einer Party: die hintere Person berührt die nächste.

Die letzte Person weiß also, wer vor ihr steht, aber nicht, wer danach kommt.

Auch weiß sie nicht, wer hinter ihr steht (in diesem Fall wäre das natürlich niemand).

Genau so ist das auch bei der Datenstruktur:

Bei der einfach verketteten Liste zeigt ein Knoten auf den nächsten, hat aber keinen Zeiger auf einen möglichen vorhergehenden oder weitere nachfolgende Knoten.

Hier siehst du ein Beispiel einer einfach verketteten Liste:

Doppelt verkettete Liste

Eine doppelt verkettete Liste kannst du dir wieder wie die Menschenkette von vorhin vorstellen:

Hier weiß also eine Person, wer links von ihr steht, aber auch, wer rechts von ihr steht.

So ist es auch bei der Datenstruktur, da jeder Knoten auf seinen Vorgänger und Nachfolger zeigt:

Kreisförmig verkettete Liste

Eine kreisförmig verkettete Liste kannst du dir auch wieder wie eine Menschenkette vorstellen, nur dass hier die letzte Person die Hand der ersten Person hält:

Auch hier weiß eine Person, wer links und rechts von ihr steht, auch die Personen, die vorher am Ende und am Anfang der Menschenkette standen.

Bei der Datenstruktur ist es genauso:

Dadurch brauchst du auch keine NULL-Zeiger mehr. Der Kopf bleibt bestehen, damit klar bleibt, wo der Anfang deiner Liste ist.

Operationen

Auf einer Liste kannst du folgende Operationen aufrufen:

• Einfügen
• Löschen
• Suchen

Der Vorteil einer Liste ist, dass sie in ihrer Größe variabel ist. Sie kann also beliebig vergrößert werden.

Auch kann in Listen an jeder Stelle eingefügt und gelöscht werden.

Diese Operationen werden im Folgenden an der einfach verketteten Liste gezeigt:

Einfügen

Schau dir das an dieser Liste an:

Wenn du an die zweite Stelle einen neuen Knoten einfügen möchtest, muss zuerst der Zeiger des neuen Knotens auf den zweiten Knoten zeigen. Danach lässt du den Zeiger des ersten Knotens auf deinen neuen Knoten zeigen.

Danach sollte deine Liste so aussehen:

Beim Einfügen gibt es jedoch zwei Sonderfälle:

• Einfügen am Anfang der Liste: Es gibt keinen vorherigen Knoten, der auf den neuen Knoten zeigen muss.
• Einfügen am Ende der Liste: Es gibt keinen nachfolgenden Knoten, auf den der neue Knoten zeigen muss.

Diese Sonderfälle können abgefangen werden, indem du Wächterknoten einführst. Diese haben keinen Inhalt. Ihr einziger Job besteht darin, das Einfügen und Löschen einfacher zu gestalten.

Diese stehen am Anfang und am Ende deiner Liste:

Dadurch musst du beim Einfügen am Anfang der Liste den neuen Knoten auf den ersten Knoten (nicht den Wächterknoten) zeigen lassen und den Wächterknoten auf den neuen Knoten.

Ähnlich ist es beim Einfügen am Ende der Liste. Du lässt deinen neuen Knoten auf den Wächterknoten zeigen und den letzten Knoten auf den neuen.

Löschen

Schau dir die mit Wächterknoten modifizierte Liste an:

Wenn du den zweiten Knoten aus der Liste löschen möchtest, lässt du den ersten Knoten auf den dritten zeigen.

Dadurch zeigt kein Knoten mehr auf diesen Knoten. Er ist also gelöscht.

Auch hier helfen dir die Wächterknoten dabei, die Sonderfälle beim Löschen am Anfang und am Ende zu umgehen.

Suchen

Um den gesuchten Knoten zu finden, gehst du einfach die gesamte Liste von vorne nach hinten durch, bis du den Knoten findest, oder beim Wächterknoten landest.

Wenn du keine Wächterknoten verwendest und der gesuchte Knoten nicht in der Liste ist, wird NULL-Knoten erreicht.

Diese drei Operationen lassen sich auch auf alle anderen Arten von Listen anwenden. Dabei muss man nur das Umändern der Zeiger anpassen.

Beispiele

Das Einfügen und Löschen bei der doppelt verketteten Liste beinhaltet einen Schritt mehr:

Einfügen

Um den neuen Knoten 8 zwischen 5 und 4 einzufügen, müssen nun zwei Zeiger pro Knoten umgeändert werden:

1. Zeiger von 8 zeigen auf 5 und 4.
2. Zeiger von 5 und 4 zeigen auf 8.

Löschen

Wenn du nun aus dieser Liste die 5 löschen möchtest, muss 7 auf 8 und 8 auf 7 zeigen:

Die 5 ist nun gelöscht, da kein Knoten der Liste auf sie zeigt.

Suchen

Wenn du schauen möchtest, ob der Knoten mit dem Wert 1 in der Liste ist, läufst du wie bei der einfach verketteten Liste von vorne nach hinten die Liste durch:

1 ist nicht in der Liste enthalten.