28 Abstrakte Datentypen 28.1 Was ist eine Liste? Jedem der sich mit Informatik beschäftigt, werden irgendwann Begriffe wie Liste, Stack oder Baum begegnen. Bei diesen Begriffen handelt es sich um sog. abstrakte Datentypen (ADT). Der Stack, oder auch Keller genannt, ist so wichtig, dass er in Java unter dem Namen Stack als Klasse standardmäßig implementiert ist. Wir wollen uns zunächst den Datentyp 'Liste' genauer anschauen, implementieren und dabei Listenarten wie LIFO und FIFO kennen lernen. |
|
ADT |
Eine erste Vorstellung von Listen kann man sich machen, wenn man sie von den Feldern abgrenzt.
int
n = (int)(100*Math.random()); Die beiden Zeilen zeigen, wie vielfältig Felder in Java verwendet werden können. Sie können alle Arten Daten aufnehmen und ihre Größe ist insofern flexibel, dass erst zur Laufzeit bestimmt wird, wie viele Eintragungen in das Feld vorgenommen werden können. Ist die Länge aber mal gesetzt, wird das ‚Gebilde’ eher starr. Man kann das Feld nicht weiter wachsen lassen, wenn man erkennt, dass noch einige Plätze nötig sind und man kann es nicht schrumpfen lassen, wenn man zu großzügig angelegt hat. Von Listen als abstrakte Datentypen verlangt man aber, dass sie mit dem Bedarf wachsen und schrumpfen1). Ein weiterer Unterschied zu den Feldern, bei denen man auf die einzelnen Plätze mittels Platznummern zugreifen kann, besteht darin, dass ‚Elemente’ einer Liste anders angeordnet sind. Es sind Gebilde, die zum einen einen Wert tragen und zum anderen auf das nächste Listenelement verweisen. Ein wahlfreier Zugriff auf einzelne Elemente ist nicht mehr möglich. Das unten stehende Bild vermittelt einen Eindruck, wie man sich eine Liste aufgebaut vorstellen kann.
|
Wir modellieren zunächst ein Listenelement in Java; seinen Bauplan legen wir konsequenterweise in der Klasse Element an. An der Modellierung erkennt man,
dass die Verkettung eines Elementes in der Liste mit seinem Nachfolger
dadurch geschieht, dass Element ein Attribut hat, dessen Typ selbst wieder
ein Element ist und sein Wert nichts anderes ist, als eine Referenz auf
ein neues Element-Objekt. Erinnern wir uns: Die Werte von Java-Variablen
sind, die primitiven Datentypen ausgenommen, immer Referenzen. Ein Verzeigern, wie man
sie von anderen Sprachen her kennt, entfällt, ja sie
ist nicht einmal möglich. Aus Sicherheitsgründen haben die Entwickler von
Java ein explizites Referenziieren von Beginn an ausgeschlossen. |
|
Die rekursive Konstruktion des
Elementes erkennt man an dem Aggregations-pfeil, der von der Klasse auf
sich selbst verweist. Ein Element-Objekt enthält also eine Referenz auf
ein anderes Element-Objekt.
Aber das ist genau das was wir wollen, um eine Liste zu bauen. |
|
Download: Element.java
|
|
Bemerkung |
Die Klasse hat zwei Konstruktoren. Mit Hilfe des ersten Konstruktors lassen sich Objekte der Klasse Element erzeugen, die weder Werte und noch Referenzen auf Nachfolger haben. Der zweite Konstruktor dagegen erlaubt es, Element-Objekte zu erzeugen, die Werte haben. Referenzen auf Nachfolger gibt es auch hier nicht. In beiden Fällen sind die Attributs-Werte von naechstes die ‚Referenz’ null, sie ‚zeigen’ demnach auf kein konkretes Objekt2). [Dokumentationskommentare sind in den Quelltext im Download eingebunden.] |
Fußnoten |
|
Der in
Java implementierte Datentyp Vector bietet hier größere Flexibilität [zurück] |
|
Da die
Werte von noch nicht referenziierten Objekten standardmäßig
null
sind, hätte man auf die Zeile
naechstes =
null;
verzichten können; lediglich didaktische Gründe veranlassen uns, sie
stehen zu lassen. [zurück] |
|
zu | 28.2 Die abstrakte Klasse Liste |
zur Startseite | www.pohlig.de (C) MPohlig 2004 |