31 Abstrakte Datentypen
31.1 Was ist eine Liste?

Jedem der sich mit Informatik beschäftigt, werden irgendwann Begriffe wie Liste
oder Baum begegnen. Bei diesen Begriffen handelt es sich um sog. abstrakte Datentypen (ADT). Spezielle Listen wie z.B. ein 'Keller', ist so wichtig, dass er in Java unter dem Namen Stack als Klasse standardmäßig implementiert ist.  Wir wollen uns zunächst eine Vorstellung machen von dem was was wir unter einer Liste verstehen wollen.
 
ADT

Eine erste Vorstellung von Listen kann man sich machen, wenn man sie von dem abgrenzt, was wir als Felder kennen gelernt haben. Wir betrachten dazu zwei Zeilen aus einem beliebigen Programm

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 es zu großzügig angelegt hat. Von Listen verlangen wir, dass sie mit dem Bedarf wachsen und schrumpfen können1). In einem weiteren Punkt unterscheidet sich eine Liste von einem Feld. Während man bei einem Feld über Platznummern wahlfrei auf seine Eintragungen zugreifen kann, ist das bei Listen nicht möglich. Die Eintragungen in der Liste sind Elemente, die zum einen einen Wert tragen und zum anderen auf ein nächste Listenelement verweisen.  Das unten stehende Bild zeigt, wie man sich eine Liste aufgebaut vorstellen kann. Leicht ist zu erkennen, dass ein wahlfreier Zugriff auf einzelne Elemente ist nicht mehr möglich.

 

 

 

Wir modellieren zunächst ein Listenelement in Java; seinen Bauplan legen wir konsequenterweise in der Klasse Element an.

Wir erkennen, dass die Verkettung eines Elementes in der Liste mit seinem Nachfolger dadurch geschieht, dass ein Element neben dem eingetragenen Wert ein Attribut hat, dessen Typ selbst wieder ein Element ist. Erinnern wir uns: Die Werte von Java-Variablen sind, die primitiven Datentypen ausgenommen, immer Referenzen.
 

API der Klasse Element

  Der rekursive Aufbau der Klasse Element ist leicht zu erkennen: Ein Element-Objekt enthält eine Referenz auf ein anderes Element-Objekt.
 
Download:
Element.java

 

package listen;

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 besitzt zwei Konstruktoren. Mit Hilfe dieses Konstruktoren lassen sich Objekte der Klasse Element erzeugen. Mit dem ersten Konstruktor, Element() wird ein Element-Objekt erzeugt, das keinen Wert (genauer keine Referenz auf ein Object-Objekt) und keine Referenz auf ein weiteres Element-Objekt hat.  Ein Element-Objekt, das in diesem geschilderten Sinne erzeugt wird, stellt eine leere Liste dar. Wir werden das später benutzen. wir erzeugen mit ihm also eine leere Liste.2) Mit dem zweiten Konstruktor erzeugen wir ein Element, das einen Wert hat, aber auf kein anderes Element verweist.

  • Die implementierten Methoden sind selbsterklärend; nur die Methode setNaechster(Element naechster) bedarf einer Erläuterung. Ein Aufruf
    Element1.setNaechstes(Element2);
    veranlasst, dass das Objekt
    Element1 auf da Element2 verweist. Diese Methode wird demnach eine wesentliche Rolle bei der Konstruktion von Listen spielen.

  • Neu ist auch die erste Zeile
    package listen;
    Die beim Kompilieren dieses Quelltextes erzeugte Datei
    Element.class wird einem Paket mit dem Namen listen hinzugefügt. Wichtig ist, dass diese Datei in einem Ordner listen abgelegt ist. Benutzt man den Java-Editor, so legt man den Quelltext Element.java in einen Ordner listen. Das Kompilat liegt dann automatisch im richtigen Ordner.3)

Dokumentationskommentare zu der Klasse
 Element sind in den Quelltext
 im Download eingebunden.

  Im nächsten Schritt wollen wir eine erste Liste bauen.

Fußnoten

 

1)

Objekte der in Java implementierte Klasse Vector können das.
[zurück]

2)

Da die Werte von noch nicht referenziierten Objekten standardmäßig null sind, hätte man auf die Zeile wert = null; und naechstes = null; verzichten können; lediglich didaktische Gründe veranlassen uns, sie stehen zu lassen.
[zurück]

3)

Wenn das Projekt fertig ist, entfernen wir den Quelltext aus dem Ordner listen und archivieren es z.B. in einem Ordner src (Source).
[zurück]
 
zu 31.2 Die abstrakte Klasse Liste
zur Startseite www.pohlig.de  (C) MPohlig 2006