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());
Object[] feld = new Object[n];

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

 

package adt;

public class Element {
    protected Object wert;
    protected Element naechstes;
    
    public Element() {
        wert = null;
        naechstes = null;
    }
    
    public Element(Object wert) {
        setWert(wert);
        naechstes = null;
    }

    public Object getWert() {
        return wert;
    }

    public void setWert(Object wert) {
        this.wert = wert;
    }

    public Element getNaechstes() {
        return naechstes;
    }
    
    public void setNaechstes(Element naechstes) {
        this.naechstes = naechstes;
    }
}
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

 

1)

Der in Java implementierte Datentyp Vector bietet hier größere Flexibilität
[zurück]

2)

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