Aufbau und Funktionsweise
Stapel und Warteschlange können jeweils genau eine Sache. Für einen Nachrichtenverlauf reicht das nicht: Dort will man durchblättern, eine bestimmte Nachricht löschen und eine neue an einer beliebigen Stelle einfügen.
Ein Feld könnte das – 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.
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 ...
Auflösung zu a)
Die Grenzfälle ergeben sich aus zwei Fragen.
Wie groß ist die Liste?
| Fall | Was ist heikel |
|---|---|
| leer | first ist null. Jeder Zugriff auf first.getContent() bricht ab. |
| genau ein Knoten | Er ist gleichzeitig erster und letzter. Wer ihn entfernt, muss first und last auf null setzen. |
| mehrere Knoten | der bequeme Fall |
An welcher Stelle wird gearbeitet?
| Fall | Was ist heikel |
|---|---|
| am Anfang | Es gibt keinen Vorgänger, dessen Verweis man umhängen könnte – first muss direkt geändert werden. |
| in der Mitte | der bequeme Fall |
| am Ende | last muss auf den neuen letzten Knoten nachgezogen werden. |
current zeigt auf null |
Es gibt kein aktuelles Objekt; remove und getContent dürfen dann nichts tun bzw. null liefern. |
Das Muster dahinter ist allgemein und kommt in 7.1 Systematisch testen wieder: Grenzfälle sind die kleinstmögliche Eingabe und die Ränder des Bereichs, auf dem man arbeitet.