Implementierung

Nur Leistungskurs. Die Operationen einer dynamischen Datenstruktur selbst zu implementieren, gehört zu den zusätzlichen Anforderungen des Leistungskurses. Im Grundkurs genügt es, den Aufbau der Liste zu erläutern (Aufbau und Funktionsweise) und sie über ihre Dokumentation zu benutzen – so, wie es auch im Zentralabitur vorausgesetzt wird.

Aufgaben

Aufgabe 1: die Liste implementieren

a) Implementiere die Methode next. Sie soll das Attribut current auf den nächsten Knoten setzen.

b) Implementiere die Methode removeFirst. Sie soll den ersten Knoten der Liste entfernen.

c) Implementiere die Methode append. Sie soll das Nachrichten-Objekt (pMessage) ans Ende der Liste anhängen.

d) Implementiere die Methode remove. Sie soll den aktuellen (current) Knoten der Liste entfernen.

Halte dich an die Dokumentation: next rückt nur weiter, wenn es ein aktuelles Objekt gibt, und remove tut nichts, wenn current auf null zeigt. Sag vor jedem Testlauf voraus, was die Ausgabe zeigen wird.

Da in der Online-IDE bereits eine Klasse List existiert, benennen wir die Klasse in NRWList um.

Hilfe: Code-Puzzle und Schreibtischtest

Die Puzzles zeigen dieselben Methoden, die du oben schreiben sollst – in Einzelteilen. Der Schreibtischtest am Ende prüft, ob du den Ablauf im Kopf hast.

Tipp 1: Die Grenzfälle zuerst

Schreib dir für jede Methode auf, was in diesen drei Fällen passieren muss: leere Liste, Liste mit genau einem Knoten, letzter Knoten. Genau dort stehen die zusätzlichen if-Abfragen – der Normalfall ist meist eine Zeile.

Tipp 2: Den Vorgänger suchen

Für remove brauchst du den Knoten vor current. Eine einfach verkettete Liste kennt nur den Weg nach vorne, also läufst du von first aus los:

ListNode vorgaenger = first;
while (vorgaenger.getNextNode() != current) {
    vorgaenger = vorgaenger.getNextNode();
}

Danach hängst du den Verweis von vorgaenger um – und denkst daran, dass last neu gesetzt werden muss, wenn current der letzte Knoten war.

Lösung. Erfrage das Passwort bei deiner Lehrkraft.

Selbsttest

1. Welche Verweise braucht eine verkettete Liste mindestens?

{r1{nur einen auf das erste Element}}

{r1{!je einen auf das erste, das letzte und das aktuelle Element}}

{r1{einen auf jedes Element}}

{h{Ohne den Verweis auf das letzte Element müsste append jedes Mal durchlaufen.}} {H{Richtig!}}

2. Was muss man beim Einfügen in eine leere Liste besonders beachten?

{r2{nichts}}

{r2{!dass sowohl first als auch last auf den neuen Knoten zeigen müssen}}

{r2{dass zuerst toFirst aufgerufen werden muss}}

{h{Der einzige Knoten ist gleichzeitig der erste und der letzte.}} {H{Richtig! Das ist der häufigste Sonderfall bei der Implementierung.}}

3. Warum braucht das Entfernen eines Knotens den Vorgänger?

{r3{um den Inhalt zu sichern}}

{r3{!weil dessen Verweis auf den übernächsten Knoten umgehängt werden muss}}

{r3{um die Länge zu aktualisieren}}

{h{Eine einfach verkettete Liste kennt nur den Weg nach vorne.}} {H{Richtig! Deshalb muss man ihn von vorne suchen.}}

4. Welche Sonderfälle gehören in jede Testliste einer Liste? (Mehrfachauswahl)

{c1{!die leere Liste}}

{c1{!die Liste mit genau einem Element}}

{c1{!Entfernen ohne aktuelles Objekt}}

{c1{eine Liste mit genau 100 Elementen}}

{h{Die Zahl 100 ist kein Sonderfall, sondern ein Normalfall.}} {H{Richtig!}}