Kapitel 11 Datenstrukturen und Algorithmen

Einen Rat befolgen heißt,
die Verantwortung verschieben.
- Urzidil

Algorithmen¹ sind ein zentrales Thema der Informatik. Ihre Erforschung und Untersuchung nimmt dort einen bedeutenden Platz ein. Algorithmen operieren nur dann effektiv mit Daten, wenn diese geeignet strukturiert sind. Schon das Beispiel Telefonbuch zeigt, wie wichtig die Ordnung der Daten nach einem Schema ist. Die Suche nach einer Telefonnummer bei gegebenem Namen gelingt schnell, jedoch ist die Suche nach einem Namen bei bekannter Telefonnummer ein mühseliges Unterfangen. Datenstrukturen und Algorithmen sind also eng miteinander verbunden, und die Wahl der richtigen Datenstruktur entscheidet über effiziente Laufzeiten; beide erfüllen alleine nie ihren Zweck. Leider ist die Wahl der »richtigen« Datenstruktur nicht so einfach, wie es sich anhört, und eine Reihe von schwierigen Problemen in der Informatik sind wohl noch nicht gelöst, da eine passende Datenorganisation bis jetzt nicht gefunden wurde.

Die wichtigsten Datenstrukturen wie Listen, Mengen und Assoziativspeicher sollen in diesem Kapitel vorgestellt werden. In der zweiten Hälfte des Kapitels wollen wir uns dann stärker den Algorithmen widmen, die auf diesen Datenstrukturen operieren.

11.1 Mit einem Iterator durch die Daten wandern 

Wir wollen bei den Datenstrukturen eine Möglichkeit kennen lernen, wie sich die gespeicherten Daten unabhängig von der Implementierung immer mit derselben Technik abfragen lassen. Bei den Datenstrukturen handelt es sich meistens um Daten in Arrays, Bäumen oder Ähnlichem. Oft wird nur die Frage nach der Zugehörigkeit eines Werts zum Datenbestand gestellt, also: »Gehört das Wort dazu?«. Dieses Wortproblem ist durchaus wichtig, aber die Möglichkeit, die Daten in irgendeiner Weise aufzuzählen, ist nicht minder bedeutend. Bei Arrays können wir über den Index auf die Elemente zuzugreifen. Da wir jedoch nicht immer ein Array als Datenspeicher haben und uns auch die objektorientierte Programmierung verbietet, hinter die Kulisse zu sehen, benötigen wir möglichst einen allgemeineren Weg. Hier bieten sich Enumeratoren beziehungsweise Iteratoren an.

11.1.1 Die Schnittstellen Enumeration und Iterator 

Für Iteratoren definiert die Java-Bibliothek zwei unterschiedliche Schnittstellen. Das hat historische Gründe. Die Schnittstelle Enumeration gibt es seit den ersten Java-Tagen; die Schnittstelle Iterator gibt es seit Java 1.2.

Die Schnittstelle Enumeration

Enumeration schreibt zwei Funktionen hasMoreElements() und nextElement() vor, mit denen durch einen Datengeber (in der Regel eine Datenstruktur) iteriert werden kann - wir sprechen in diesem Fall auch von einem Iterator. Bei jedem Aufruf von nextElement() erhalten wir ein weiteres Element der Datenstruktur. Im Gegensatz zum Index eines Felds können wir ein Objekt nicht noch einmal auslesen oder vorlaufen beziehungsweise hin und her springen. Ein Iterator geleicht anschaulich einem Datenstrom; wollten wir ein Element zweimal besuchen, zum Beispiel von rechts nach links noch einmal durchwandern, dann müssen wir wieder ein neues Enumeration-Objekt erzeugen oder uns die Elemente zwischendurch merken.

boolean hasMoreElements() Testet, ob noch ein weiteres Element aufgezählt werden kann.2

Object nextElement()

Liefert das nächste Element der Enumeration zurück. Diese Funktion kann eine NoSuchElementException auslösen, wenn nextElement() aufgerufen wird und das Ergebnis false beim Aufruf von hasMoreElements() ignoriert wird.

for ( Enumeration e = ds.elements(); e.hasMoreElements(); )
 System.out.println( e.nextElement() );

Die Schnittstelle Iterator

Ein Iterator ist für die neuen Collection-Klassen das, was Enumeration für die herkömmlichen Datenstruktur-Klassen ist. Die Schnittstelle Iterator besitzt kürzere Methodennamen als Enumeration. Nun heißt es hasNext() an Stelle von hasMoreElements() und next() an Stelle von nextElement(). Übergehen wir ein false von hasNext(), so erhalten wir wiederum eine NoSuchElementException. Zudem besitzt ein Iterator auch die Möglichkeit, das zuletzt aufgezählte Element aus dem zugrunde liegenden Container zu löschen. Dazu dient die optionale Methode remove(); sie lässt sich allerdings nur unmittelbar aufrufen, nachdem next() das zu löschende Element als Ergebnis geliefert hat. Eine Enumeration kann die aufgezählte Datenstruktur grundsätzlich nicht verändern. 

boolean hasNext() Liefert true, falls die Iteration weitere Elemente bietet.

Object next() Liefert das nächste Element in der Aufzählung oder NoSuchElementException, wenn keine weiteren Elemente mehr vorhanden sind.

void remove() Entfernt das Element, das der Iterator zuletzt bei next() geliefert hat. Implementiert ein Iterator diese Funktion nicht, so löst er eine UnsupportedOperationException aus.

Hier klicken, um das Bild zu Vergrößern

11.1.2 Arrays mit Iteratoren durchlaufen

Die Konzepte Array und Container-Objekte passen oft nicht genau zusammen, da zwischen ihnen ein Bruch in der Programmierung liegt. Beide werden unterschiedlich angesprochen: ein Container häufig mittels Iteratoren, ein Array direkt über einen ganzzahligen Index. Wenn es nicht auf Geschwindigkeit ankommt, sollten wir als Container besser eine Datenstruktur verwenden und kein »rohes« Array. Bei einem Array müssen wir uns immer selbst um Strategien zum Durchlaufen der Array-Elemente kümmern, bei Datenstrukturen haben wir das Konzept der Enumeratoren und Iteratoren. Gut ist es, ein Array nachträglich mit derselben Abstraktion auszustatten wie eine Datenstruktur, also mit einem Iterator. Folgende Implementierung soll uns dabei helfen, von den Vorteilen eines Iterators zu profitieren. Dadurch kann zum Beispiel ein Array leichter gegen eine mächtigere Datenstruktur ausgetauscht werden. Wir müssen dazu nur für drei Methoden Programmcode bereitstellen: hasNext(), next() und remove(). Für Letztere wollen wir keine Implementierung bieten und eine UnsupportedOperationException auslösen, da beim Löschen eigentlich auch das Feld kleiner werden muss.

Damit sieht die Klasse ArrayIterator wie folgt aus:

Listing 11.1 ArrayIterator.java

import java.util.*;

public class ArrayIterator implements Iterator
{
  private Object array[];
  private int    pos = 0;
   public ArrayIterator( Object anArray[] )
  {
    array = anArray;
  }
   public boolean hasNext()
  {
    return pos < array.length;
  }
  public Object next() throws NoSuchElementException
  {
    if ( hasNext() )
      return array[pos++];
    else
      throw new NoSuchElementException();
  }
  public void remove()
  {
    throw new UnsupportedOperationException();
  }
}

Ein ArrayIterator wird über einen parametrisierten Konstruktor für ein bestimmtes Array-Objekt erzeugt. Die Funktion nextElement() löst eine NoSuchElementException aus, wenn das Ergebnis false von hasMoreElements() ignoriert wird. NoSuchElementException ist eine RuntimeException, so dass sie nicht ausdrücklich aufgefangen werden muss.

Das Array kann parallel im Hintergrund noch verändert werden. Da sich die Größe allerdings nicht mehr ändern kann, müssen wir die ersten beiden kritischen Zeilen in next() nicht synchronisieren.

Praktisch bei dem ArrayIterator ist nun, dass er an alle Funktionen weitergegeben werden kann, die einen Iterator als Parameter erwarten und kein remove() verwenden. Sonst hätten wir eine andere Datenstruktur wählen müssen.

Folgendes Beispiel zeigt unseren neuen Iterator im Einsatz beim Aufzählen der Kommandozeilen-Argumente:

static public void main( String arg[] )
{
  Iterator i = new ArrayIterator( arg );
  while ( i.hasNext() )
    System.out.println( "Eintrag: " + i.next() );
}

¹Das Wort »Algorithmus« geht auf den persisch-arabischen Mathematiker Ibn Mûsâ Al-Chwârismî zurück, der im 9. Jahrhundert lebte.

²Enumeratoren (und Iteratoren) können nicht serialisiert werden, da sie die Schnittstelle Serializable nicht implementieren.