12.2 Mit einem Iterator durch die Daten wandern

Wenn wir mit einer ArrayList oder LinkedList arbeiten, so haben wir zumindest eine gemeinsame Schnittstelle List, um an die Daten zu kommen. Doch was vereinigt eine Menge (Set) und Liste, sodass sich die Elemente der Sammlungen mit immer der gleichen Technik erfragen lassen? Listen geben als Sequenz den Elementen zwar Positionen, aber in einer Menge hat kein Element eine Position. Hier bieten sich Iteratoren beziehungsweise Enumeratoren an, die unabhängig von der Datenstruktur alle Elemente auslesen – wir sagen dann, dass sie »über die Datenstruktur iterieren«.

12.2.1 Die Schnittstellen Enumeration und Iterator

Für Iteratoren deklariert 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, seit der Collection-API. Der Typ Iterator ist jedoch deutlich weiter verbreitet. Die Schnittstellen erweitern selbst keine weitere Schnittstelle. [Enumeratoren (und Iteratoren) können nicht serialisiert werden, da sie die Schnittstelle Serializable nicht implementieren. ]

Beiden Schnittstellen ist eine Funktion gemeinsam, die das nächste Element erfragt, und eine Funktion, die ermittelt, ob es überhaupt ein nächstes Element gibt. So wandert der Iterator einen Datengeber (in der Regel eine Datenstruktur) Element für Element ab. Die Namen der Operationen unterscheiden sich in den Schnittstellen ein wenig und sind beim Iterator kürzer.

Hast du mehr? Gib mir das nächste Iterator hasNext() next() Enumeration hasMoreElements() nextElement()

Bei jedem Aufruf von next()/nextElement() erhalten wir ein weiteres Element der Datenstruktur. Übergehen wir ein false von hasNext()/hasMoreElements(), bestraft uns eine NoSuchElementException.

Collection<String> set = new TreeSet<String>(); 
Collections.addAll( set, "Horst", "Schlämmer", "Hape" , "Kerkeling" ); 
for ( Iterator<String> iterator = set.iterator(); iterator.hasNext(); ) 
  System.out.println( iterator.next() );

Im Gegensatz zum Index eines Felds können wir ein Objekt nicht noch einmal auslesen, nicht vorlaufen beziehungsweise hin und her springen. Ein Iterator gleicht 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 Iterator/Enumeration-Objekt erzeugen oder uns die Elemente zwischendurch merken. Nur bei Listen und sortierten Datenstrukturen ist die Reihenfolge der Elemente vorhersehbar.

interface java.util.Enumeration<E>

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

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

Der Iterator kann löschen

Die Schnittstelle Iterator bietet eine Möglichkeit, die Enumeration nicht bietet. Das zuletzt aufgezählte Element lässt sich aus dem zugrunde liegenden Container mit remove() entfernen. Vor dem Aufruf muss jedoch next() das zu löschende Element als Ergebnis geliefert haben. Eine Enumeration kann die aufgezählte Datenstruktur grundsätzlich nicht verändern.

In der Dokumentation ist die Methode remove() als optional gekennzeichnet. Das heißt, dass ein konkreter Iterator kein remove() können muss – auch eine UnsupportedOperationException ist möglich. Das ist etwa dann der Fall, wenn ein Iterator von einem Feld abgeleitet wird und ein Löschen nicht wirklich möglich ist.

interface java.util.Iterator<E>

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

• E 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.

12.2.2 Iteratoren von Sammlungen und das erweiterte for

Jede Collection wie ArrayList oder HashSet liefert mit iterator() einen Iterator. Datenstrukturen laufen damit immer nach dem gleichen Muster ab:

for ( Iterator i = c.iterator(); i.hasNext(); ) 
{ 
  Object o = i.next(); 
  ... 
}

Steckt in der Datenstruktur ein spezieller Untertyp von Object – wenn eine Liste zum Beispiel Strings enthält –, kann eine explizite Typanpassung helfen. Da der Iterator aber mit Generics-Fähigkeiten deklariert wurde, geht es noch einfacher, wie der nächste Absatz zeigt.

interface java.util.Collection<E> 
extends Iterable<E>

• Iterator<E> iterator() Iterator der Datenstruktur.

Der typisierte Iterator

Von einer typisierten Collection liefert iterator() ebenfalls einen typisierten Iterator. Das heißt, die Datenstruktur überträgt den generischen Typ auf den Iterator. Nehmen wir eine mit String typisierte Sammlung an:

Collection<String> c = new LinkedList<String>();

Ein Aufruf von c.iterator() liefert nun Iterator<String> und beim Durchlaufen über den Iterator kann die explizite Typanpassung beim next() entfallen:

for ( Iterator<String> i = c.iterator(); i.hasNext(); ) 
{ 
  String s = i.next(); 
  ... 
}

Iterator und erweitertes for

Stößt der Compiler auf ein erweitertes for und erkennt er rechts vom Doppelpunkt den Typ Iterable, so erzeugt er Bytecode für eine Schleife, die den Iterator und seine bekannten Methoden hasNext() und next() nutzt. Nehmen wir eine Funktion totalStringLength(List) an, die ermitteln soll, wie viele Zeichen alle Strings zusammen besitzen. Aus

static int totalStringLength( List strings ) 
{ 
  int result = 0; 
 
  for ( Object s : strings ) 
    result += ((String)s).length(); 
 
  return result; 
}

erzeugt der Compiler:

static int totalStringLength( List strings ) 
{ 
  int result = 0; 
 
  for ( Iterator iter = strings.iterator(); iter.hasNext(); ) 
    result += ((String)iter.next()).length(); 
 
  return result; 
}

Mit einer generischen Datenstrukturen und einem damit abgeleiteten generischen Iterator vollzieht sich das Ablaufen noch einfacher.

static int totalStringLength( List<String> strings ) 
{ 
  int result = 0; 
 
  for ( String s : strings ) 
    result += s.length(); 
 
  return result; 
}

Da die erweiterte Schleife das Ablaufen einer Datenstruktur vereinfacht, wird ein explizit ausprogrammierter Iterator selten benötigt. Doch der Iterator kann ein Element über die remove()-Funktion des Iterators löschen, was über das erweiterte for nicht möglich ist.

12.2.3 Fail-Fast Iterator und die ConcurrentModificationException

Die Entwickler der Java-Bibliothek haben einen Entwurf gewählt, dass Änderungen über die Sammlung und den Iteratoren auffallen und zu einer ConcurrentModificationException führen:

Listing 12.5 com/tutego/insel/util/ConcurrentModificationExceptionDemo.java, main()

List<String> list = new ArrayList<String>( Arrays.asList( "Stunden", "der" ) ); 
Iterator<String> iterator = list.iterator(); 
System.out.println( list.get( 0 ) );  // Stunden 
list.add( "Entspannung" ); 
iterator.next(); // Exception in thread "main"  
                 // java.util.ConcurrentModificationException

Da nach dem Erfragen des Iterators die Datenstruktur für Veränderungen gesperrt ist, führt ein add() auf der Liste zu einer ConcurrentModificationException.

Ihr Kommentar