Bevor wir weitermodellieren und weiterprogrammieren können, müssen wir uns
zunächst Gedanken machen, wie eine Liste im Computer denn funktionieren
könnte / sollte / müsste ...
Unsere Klassen Liste und Link haben wir schon
identifiziert, davon können wir während der Programmausführung Objekte
erzeugen:
Wir werden genau ein Objekt Liste der Klasse Liste benötigen, aber etliche Objekte Link der Klasse Link - bei unserer Umsetzung mindestens zwei. Achtung: Klassennamen sind nicht unterstrichen, Objektnamen sind unterstrichen! Der gestrichelte Pfeil gibt an, zu welcher Klasse die jeweiligen Objekte gehören.
Die Objekte Link sind also unsere einzelnen
Listenelemente - aber wie entsteht daraus eine Liste? Die Lösung ist
ganz einfach: Jedes Listenelement muss seinen Vorgänger und seinen
Nachfolger kennen; eine solche Kette heißt doppelt verkettete Liste, weil
man sich darin mühelos vorwärts und rückwärts bewegen kann. (Im Grunde
würde eine einfach verkettete Liste, z.B. nur mit Kenntnis des jeweiligen
Nachfolgers, genügen und es würde auch etwas Speicherplatz gespart, dafür
wird das Handling umständlicher, weil man immer nur in einer Richtung,
nämlich vorwärts, die Liste durchschreiten kann.)
Wir verpassen daher unserer Klasse Link Attribute: einmal die
Attribute Vorgaenger und Nachfolger, die natürlich vom
Typ Link sind, denn sie zeigen ja auf ebensolche. Zum andern
noch das Attribut Datensatz, denn wir wollen in unserer Liste ja
Informationen ablegen. Der Einfachheit halber wählen wir hier
String als Typ und können dann nachher Zeichenketten in unserer
Liste ablegen.
Nicht nur die Klasse Link hat Attribute, auch die Klasse Liste müssen wir versorgen: Anfang soll auf das Link-Objekt, das den Anfang der Liste bildet zeigen, Ende soll auf das Link-Objekt, das das Ende der Liste bildet zeigen und Position soll auf die aktuelle Position, an der wir uns in der Liste befinden, zeigen.
Mit diesen Informationen können wir eine Liste aufbauen:
Der Zusammenhang der Link-Objekte untereinander ist klar: jedes Link-Objekt verweist auf seinen Vorgänger und seinen Nachfolger. Eine besondere Behandlung erfordern Anfang und Ende der Liste, dort zeigen die Verweise auf den Wert null, um kenntlich zu machen, dass die Liste dort endet.
Das Attribut Anfang des Objektes Liste zeigt auf das erste Link-Objekt der Liste, das Attribut Ende verweist auf das letzte Objekt der Liste. Das Attribut Position zeigt auf die momentane Position in der Liste, die in dieser Abbildung nicht näher spezifiziert ist.
Aus bestimmten Gründen ist es praktisch, wenn auch eine leere Liste schon aus zwei Link-Objekten besteht. Eine leere, neu erzeugte Liste hat damit die folgende Struktur:
Damit haben wir schon genug gelernt, um weiter modellieren zu können, denn neben den oben genannten Attributen können wir auch die ersten Methoden modellieren:
- Konstruktor Link()der Klasse Link
- neueListe() der Klasse Liste
- gibListeaus() der Klasse Liste
- naechstes() der Klasse Liste
- main() der Klasse Liste
Weiter mit Teil 3.