Impressum
< Queue Inhalt Baum >

Verkettete Listen

Was ist eine Liste?

Eine verkettete Liste ist eine Datenstruktur, welche aus Knoten besteht.
Jeder Knoten enthält einen Wert und einem Zeiger auf den Folgeknoten.
Der erste Knoten einer Liste heiĂźt Listenkopf.
Der letzte Listenknoten enthält als Zeiger den Wert none als Endmarkierung.
Um auf eine Liste zugreifen zu können benötigt man noch eine Variable, welche auf den Listenkopf verweist. Diese heißt Anker.
In eine Liste können an beliebigen Positionen Knoten eingefügt oder gelöscht werden.

Liste durchlaufen

Um eine Liste zu Druchlaufen erstellt man sich eine Kopie des Ankers, nennen wir sie Läufer.
  1. Zeigt Läufer auf none brechen wir ab
  2. Ausgabe des Inhalts von Läufer
  3. Setzen wir Läufer auf den Next-Zeiger von Läufer
  4. weiter bei 1.)


EinfĂĽgen

Beim EinfĂĽgen eines neuen Knotens Kneu zwischen Kn und Kn+1 wird zuerst der Zeiger von Kneu auf den Zeiger von Kn gesetzt.
Somit zeigen Kneu und Kn beide auf Kn+1.
Dann wird der Nachfolge-Zeiger von Kn auf Kneu gesetzt.
Jetzt zeigt Kn auf Kneu und Kneu zeigt auf Kn+1.
Alles ist gut.


Speziallfälle:

Löschen

Um einen Knoten zu Löschen, muss nur der Zeiger auf diesen Knoten auf dessen Nachfolger gesetzt werden.
Da nichts mehr auf den gelöschten Knoten verweist, wird er automatisch aus dem Speicher entfernt (Garbage Collection).
Ist der zu löschende Knoten der letzte Knoten der Liste, so hat dieser als Zeiger auf seinen Nachfolger den Wert none. Da dieser Wert als Zeiger in den Vorgänger übernommen wird funktioniert, das Löschen hier gleich.



Ein Spezialfall ist das Löschen des ersten Knotens: Hier muss zuerst der Anker auf den zweiten Knoten zeigen und danach der Nachfolger des ersten Knotens auf none gesetzt werden.


Aufgaben

  1. Beim Lösen einer Aufgabe druchläuft man die Schritte folgender verketteter Liste:
    Liste zum Aufgabenlösen
    1. Geben Sie die Schritte an, welche man zum druchlaufen der Liste benötigt.
    2. Vollkommen zu Recht wird bemängelt, das zu Beginn der Punkt nachdenken fehlt.
      Da dieser aber erst nach dem Lesen der Aufgabe Sinn macht soller er zwischen „Aufgabe lesen” und „Ansatz finden” eingefĂĽgt werden.
      Geben Sie die nötigen Schritte an um den neuen Knoten an der korrekten Position einzufügen.

    3. Der unempathische Lehrer hat mal wieder vergessen, dass man sich nach dem Lösen einer Aufgabe freut.
      Geben Sie die Schritte an, die es braucht um diesen Knotem am Ende der Liste einzufĂĽgen.