Aufbau und Funktionsweise
Wie Schlange und Stapel besteht auch die Liste innen aus Knoten. Sie braucht aber mehr Verweise: einen auf den Anfang, einen auf das Ende und einen auf das aktuelle Element. Auf dieser Seite schaust du hinein. Als Beispiel dient wieder der Messenger, diesmal mit einem Nachrichtenverlauf zum Durchblättern.
Warum nicht einfach ein Feld? Ein Feld könnte das auch – aber schlecht. Seine Größe steht beim Anlegen fest, und wer vorne etwas entfernt, muss alles Übrige aufrücken lassen.
Eine verkettete Liste besteht aus Knoten. Jeder Knoten enthält
- ein Inhaltsobjekt und
- eine Referenz auf den nächsten Knoten.
Der letzte Knoten verweist auf null; daran erkennt man das Ende. Die Liste selbst merkt sich den ersten Knoten – und in der Abiturklasse zusätzlich den letzten sowie einen beweglichen Verweis current auf den gerade betrachteten Knoten.
Der Unterschied zum Feld in einem Satz: Ein Feld liegt am Stück, eine Liste hängt aneinander.
| Feld | verkettete Liste | |
|---|---|---|
| Größe | beim Anlegen festgelegt | wächst beliebig mit |
| Zugriff auf das n-te Element | sofort über den Index | n Schritte vom Anfang aus |
| Einfügen in der Mitte | alles Dahinterliegende aufrücken | zwei Verweise umhängen |
| Speicher pro Element | nur der Inhalt | Inhalt und ein Verweis |
Keine der beiden Strukturen ist besser. Sie sind an verschiedenen Stellen gut – und genau das ist die Frage, die du in Kapitel 7 beurteilen lernst.
Im Messenger-Beispiel stehen Nachrichten in der Liste. Das Klassendiagramm zeigt alle drei beteiligten Klassen, die Pfeile tragen die Namen der Verweise aus den Objektdiagrammen.
classDiagram
direction LR
class List {
+toFirst()
+next()
+append(pContent: Message)
+remove()
}
class ListNode {
+getNextNode() ListNode
+setNextNode(pNext: ListNode)
+getContentObject() Message
+setContentObject(pContent: Message)
}
class Message {
+getUsername() String
+getText() String
+getDate() String
}
List --> ListNode : first
List --> ListNode : last
List --> ListNode : current
ListNode --> ListNode : next
ListNode --> Message : contentObject
Gezeigt sind nur die Methoden, die auf dieser Seite vorkommen. Die vollständige Abiturklasse steht in der Dokumentation.
Nachrichten anhängen
Die Methode append soll eine neue Nachricht ans Ende der Liste anhängen.
- Setze die Schritte im Objektdiagramm um.
- Entwerfe zur Methode append der Klasse List einen Algorithmus im Pseudocode.
- Tausche deinen Algorithmus mit jemand anders und lasse ihn überprüfen. Überarbeite ihn gegebenenfalls.
- Bereite dich darauf vor deinen Algorithmus anhand des Objektdiagramms präsentieren zu können.
Formulierungshilfe: Pseudocode
- Erzeuge ...
- Setze das Attribut / die Variable ... auf die Referenz ...
Erste Nachricht entfernen
Die Methode remove soll den ersten Knoten der Liste entfernen.
Unter dem Diagramm stehen vier Zuweisungen. Nur eine davon entfernt den ersten Knoten – die anderen drei zerstören die Liste auf je eigene Weise.
- Sage für jede der vier Zuweisungen voraus, was sie am Diagramm ändern würde.
- Führe sie aus und prüfe deine Vorhersage. Mit Von vorn setzt du das Diagramm zurück.
- Entwerfe zur Methode remove der Klasse List einen Algorithmus im Pseudocode.
- Tausche deinen Algorithmus mit jemand anders und lasse ihn überprüfen. Überarbeite ihn gegebenenfalls.
- Bereite dich darauf vor deinen Algorithmus anhand des Objektdiagramms präsentieren zu können.
Formulierungshilfe: Pseudocode
- Setze das Attribut / die Variable ... auf die Referenz ...
Aktuelle Nachricht entfernen
Die Methode remove soll erweitert werden, sodass der aktuelle Knoten (current) der Liste entfernt wird.
Hier kommt es nicht nur darauf an, welche Zuweisungen du ausführst, sondern in welcher Reihenfolge. Die Zuweisungen werden in dem Moment ausgewertet, in dem du sie anklickst – ein Ausdruck wie messages.current.next liefert also das, worauf current gerade jetzt zeigt.
- Führe die Zuweisungen so aus, dass der aktuelle Knoten aus der Liste verschwindet, und prüfe.
- Setze zurück und führe dieselben Zuweisungen in einer anderen Reihenfolge aus. Beschreibe, was schiefgeht und warum.
- Formuliere daraus eine Regel: Welche Referenz muss man zuerst lesen, bevor man sie überschreibt?
- Erweitere deinen Algorithmus zum Entfernen von Nachrichten, sodass der aktuelle Knoten (current) entfernt wird.
- Bereite dich darauf vor deinen Algorithmus anhand des Objektdiagramms präsentieren zu können.
Formulierungshilfe: Pseudocode
- Gehe so lange ... bis ...
- Setze das Attribut / die Variable ... auf die Referenz ...
Hilfe: Vorgehen
Um den aktuellen (current) Knoten zu löschen, muss man den vorherigen Knoten kennen. Doch wie kommt man an den vorherigen Knoten?
Grenzfälle erkunden
Bis hierher hast du Knoten aus der Mitte entfernt und eine Nachricht ans Ende einer bereits gefüllten Liste angehängt – beides der bequeme Fall. Ein Algorithmus ist aber erst fertig, wenn er auch an den Rändern stimmt.
a) Ermittle, welche Grenzfälle es bei der Liste gibt. Geh dafür systematisch vor: Welche Größen kann eine Liste haben, und an welchen Stellen kann man arbeiten?
b) Prüfe jeden deiner Algorithmen an jedem Grenzfall und notiere, wo er fehlschlägt.
c) Modifiziere die Algorithmen so, dass die Grenzfälle beachtet werden.
Tipp: Grenzfälle finden
- Funktionieren deine Algorithmen z.B. für eine leere Liste?
- Funktioniert dein Algorithmus z.B. beim Entfernen des letzten Knotens?
Formulierungshilfe: Pseudocode
- Setze das Attribut / die Variable ... auf die Referenz ...
- Wenn ..., dann ...
- Gehe so lange ... bis ...
Abgrenzung zur Warteschlange
Eine Liste kann alles, was eine Warteschlange kann – und mehr. Auf den ersten Blick wirkt die Warteschlange deshalb wie ein Rückschritt.
a) Beschreibe die Unterschiede zwischen Warteschlange und Liste. Nimm dazu beide Dokumentationen nebeneinander: Welche Operationen hat die eine, die die andere nicht hat?
b) Begründe, warum es trotzdem spezialisierte Strukturen wie die Warteschlange gibt. Denk dabei an zwei verschiedene Arten von Vorteil – einen für den, der die Struktur benutzt, und einen für den, der sie baut.