Einstieg: Jeder kann drankommen

Schlange und Stapel können jeweils genau eine Sache: vorne beziehungsweise oben herausnehmen. 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.

Dafür gibt es die Liste. Bei ihr kommt nicht der Erste oder der Letzte dran, sondern der, den man gerade ausgewählt hat.

Eine Liste (englisch list) ist eine lineare Datenstruktur, bei der man an jeder Stelle lesen, einfügen und entfernen kann.

Dazu gibt es ein aktuelles Element, auf das die Liste gerade zeigt. Man bewegt es mit

toFirst an den Anfang, toLast ans Ende,
next um ein Element weiter.

hasAccess sagt, ob es gerade ein aktuelles Element gibt. getContent, setContent, insert und remove beziehen sich immer auf das aktuelle Element. Nur append hängt unabhängig davon ans Ende an.

Die Liste hat keine Nummern wie ein Feld. Wer an das dritte Element will, geht vom ersten aus zweimal weiter – so wie man in einem Fotoalbum blättert, statt eine Seitenzahl aufzuschlagen.

Von außen zeigt die Abiturklasse List diese Methoden:

classDiagram
    class List~ContentType~ {
        +List()
        +isEmpty() boolean
        +hasAccess() boolean
        +toFirst()
        +toLast()
        +next()
        +getContent() ContentType
        +setContent(pContent: ContentType)
        +insert(pContent: ContentType)
        +append(pContent: ContentType)
        +remove()
        +concat(pList: List~ContentType~)
    }

Erst einmal ausprobieren

a) Sage voraus, was das Programm ausgibt. Notiere nach jeder Zeile, welche Namen in der Liste stehen und welcher davon das aktuelle Element ist. Führe das Programm dann aus.

b) Welche Namen stehen am Ende in der Liste? Ergänze am Ende des Programms eine Schleife, die sie alle ausgibt.

Weiterdenken: Nach dem letzten next() gibt es kein aktuelles Element mehr. Was liefert getContent() jetzt? Und was passiert bei insert("Emil")? Schlag in der Dokumentation nach, bevor du es ausprobierst.

Auflösung. Erfrage das Passwort bei deiner Lehrkraft.

Wer kommt als Nächstes dran?

Wähle für jeden Fall die passende Struktur – Schlange, Stapel oder Liste – und begründe.

a) Die Teilnehmerliste einer AG, in die jederzeit an beliebiger Stelle jemand eingefügt werden soll.

b) Die Rückgängig-Funktion eines Zeichenprogramms.

c) Eine Playlist, in der man Lieder überspringen, löschen und umsortieren kann.

d) Nachrichten, die ein Server in der Reihenfolge ihres Eintreffens beantwortet.

Auflösung. Erfrage das Passwort bei deiner Lehrkraft.

Selbsttest

1. Worauf beziehen sich getContent, insert und remove?

{r1{auf das erste Element}}

{r1{!auf das aktuelle Element}}

{r1{auf das letzte Element}}

{h{Die Liste merkt sich, wo man gerade steht.}} {H{Richtig!}}

2. Wo fügt insert ein?

{r2{hinter dem aktuellen Element}}

{r2{!vor dem aktuellen Element}}

{r2{am Ende der Liste}}

{h{Ans Ende hängt eine andere Methode an.}} {H{Richtig! Das aktuelle Element bleibt dabei dasselbe.}}

3. Welches Element ist nach remove das aktuelle?

{r3{das erste der Liste}}

{r3{das vorherige}}

{r3{!der Nachfolger des entfernten}}

{h{Die Dokumentation legt das genau fest.}} {H{Richtig! Gibt es keinen Nachfolger, liefert hasAccess danach false.}}

4. Wie kommt man an das dritte Element einer Liste?

{r4{über den Index 2}}

{r4{!mit toFirst und zweimal next}}

{r4{mit toLast}}

{h{Die Liste hat keine Nummern.}} {H{Richtig!}}