Galileo Computing < openbook > Galileo Computing - Professionelle Bücher. Auch für Einsteiger.
Professionelle Bücher. Auch für Einsteiger

 << zurück
Java ist auch eine Insel von Christian Ullenboom
Programmieren für die Java 2-Plattform in der Version 5
Java ist auch eine Insel

Java ist auch eine Insel
5., akt. und erw. Auflage
1454 S., mit CD, 49,90 Euro
Galileo Computing
ISBN 3-89842-747-1
gp Kapitel 11 Datenstrukturen und Algorithmen
  gp 11.1 Datenstrukturen und die Collection-API
    gp 11.1.1 Die Schnittstelle Collection
    gp 11.1.2 Das erste Programm mit Container-Klassen
    gp 11.1.3 Die Schnittstelle Iterable und das erweiterte for
    gp 11.1.4 Generische Datentypen in der Collection-API
    gp 11.1.5 Generischer Typ bei Iterable und konkreter Typ beim erweiterten for
    gp 11.1.6 Schnittstellen, die Collection erweitern, und Map
    gp 11.1.7 Konkrete Container-Klassen
  gp 11.2 Mit einem Iterator durch die Daten wandern
    gp 11.2.1 Die Schnittstellen Enumeration und Iterator
    gp 11.2.2 Der typisierte Iterator
  gp 11.3 Listen
    gp 11.3.1 Die Schnittstelle List
    gp 11.3.2 Beispiel mit List-Methoden
    gp 11.3.3 ArrayList
    gp 11.3.4 Arrays.asList() und die »echten« Listen
    gp 11.3.5 toArray() von Collection verstehen – die Gefahr einer Falle erkennen
    gp 11.3.6 Die interne Arbeitsweise von ArrayList und Vector
    gp 11.3.7 LinkedList
  gp 11.4 Stack (Kellerspeicher, Stapel)
    gp 11.4.1 Die Methoden von Stack
    gp 11.4.2 Ein Stack ist ein Vector – aha!
  gp 11.5 Queues (Schlangen)
    gp 11.5.1 Blockierende Queues und Prioritätswarteschlangen
  gp 11.6 Assoziative Speicher HashMap und TreeMap
    gp 11.6.1 Ein Objekt der Klasse HashMap erzeugen
    gp 11.6.2 Einfügen und Abfragen der Datenstruktur
    gp 11.6.3 Wichtige Eigenschaften von Assoziativspeichern
    gp 11.6.4 Elemente im Assoziativspeicher müssen unveränderbar bleiben
    gp 11.6.5 Aufzählen der Elemente
    gp 11.6.6 Der Gleichheitstest, Hash-Wert und Klon einer Hash-Tabelle
    gp 11.6.7 Die Arbeitsweise einer Hash-Tabelle
  gp 11.7 Die Properties-Klasse
    gp 11.7.1 Properties setzen und lesen
    gp 11.7.2 Properties verketten
    gp 11.7.3 Eigenschaften ausgeben
    gp 11.7.4 Hierarchische Eigenschaften
    gp 11.7.5 Properties speichern
    gp 11.7.6 Über die Beziehung Properties und Hashtable
  gp 11.8 Mengen (Sets)
    gp 11.8.1 HashSet
    gp 11.8.2 TreeSet – die Menge durch Bäume
    gp 11.8.3 LinkedHashSet
  gp 11.9 Algorithmen in Collections
    gp 11.9.1 Datenmanipulation: Umdrehen, Füllen, Kopieren
    gp 11.9.2 Vergleichen von Objekten mit Comparator und Comparable
    gp 11.9.3 Größten und kleinsten Wert einer Collection finden
    gp 11.9.4 Sortieren
    gp 11.9.5 Elemente in der Collection suchen
    gp 11.9.6 Nicht-änderbare Datenstrukturen
    gp 11.9.7 nCopies()
    gp 11.9.8 Singletons
  gp 11.10 Synchronisation der Datenstrukturen
    gp 11.10.1 Lock-Free-Algorithmen aus java.util.concurrent
    gp 11.10.2 Wrapper zur Synchronisation
    gp 11.10.3 CopyOnWriteArrayList und CopyOnWriteArraySet
  gp 11.11 Die abstrakten Basisklassen für Container
    gp 11.11.1 Optionale Methoden
  gp 11.12 Die Klasse BitSet für Bitmengen
    gp 11.12.1 Ein BitSet anlegen und füllen
    gp 11.12.2 Mengenorientierte Operationen
    gp 11.12.3 Funktionsübersicht
    gp 11.12.4 Primzahlen in einem BitSet verwalten
  gp 11.13 Ein Design-Pattern durch Beobachten von Änderungen
    gp 11.13.1 Design-Pattern
    gp 11.13.2 Das Beobachter-Pattern (Observer/Observable)


Galileo Computing

11.2 Mit einem Iterator durch die Daten wanderdowntop

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 und Liste, sodass sich die Elemente der Sammlungen mit immer der gleichen Technik erfragen lassen? Hier bieten sich Iteratoren beziehungsweise Enumeratoren an, die unabhängig von der Datenstruktur alle Elemente auslesen – wir sagen dann: »über die Datenstruktur iterieren«.


Galileo Computing

11.2.1 Die Schnittstellen Enumeration und Iterator  downtop

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, seit der Collection-API. Der Typ Iterator ist jedoch deutlich weiter verbreitet.

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.

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.

Abbildung
Hier klicken, um das Bild zu Vergrößern


interface java.util.Enumeration<E>

gp  boolean hasMoreElements() Testet, ob noch ein weiteres Element aufgezählt werden kann.
gp  E 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.

Beispiel   Die Aufzählung erfolgt meistens über einen Zweizeiler: Nehmen wir an, die Datenstruktur ds besitzt eine Methode elements(), die ein Enumeration-Objekt zurückgibt.
for ( Enumeration e = ds.elements(); e.hasMoreElements(); )
 System.out.println( e.nextElement() );

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 Löschen nicht wirklich möglich ist.

Abbildung
Hier klicken, um das Bild zu Vergrößern


interface java.util.  Iterator<E>  

gp  boolean hasNext() Liefert true, falls die Iteration weitere Elemente bietet.
gp  E next() Liefert das nächste Element in der Aufzählung oder NoSuchElementException, wenn keine weiteren Elemente mehr vorhanden sind.
gp  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.

Hinweis   Es ist eine interessante Frage, warum es die Methode remove() im Iterator gibt. Die Erklärung dafür ist, dass der Iterator die Stelle kennt, an der sich die Daten befinden (eine Art Cursor). Darum können die Daten dort auch effizient und direkt gelöscht werden. Das erklärt jedoch nicht unbedingt, warum es keine Einfüge-Methode gibt. Ein allgemeiner Grund mag sein, dass bei vielen Container-Typen das Einfügen an einer bestimmten Stelle keinen Sinn ergibt, etwa bei SortedSet, SortedMap, Set und Map. Dort ist die Einfügeposition durch die Sortierung vorgegeben oder belanglos (beziehungsweise bei HashSet durch die interne Realisierung bestimmt), also kein Fall für einen Iterator. Dazu wirft Einfügen weitere Fragen auf: Vor oder nach dem zuletzt per next() gelieferten Element? Soll das neue Element mit aufgezählt werden oder nicht? Auch dann nicht, wenn es in der Sortierung erst später an die Reihe käme? Eine Löschen-Methode ist problemloser und universell anwendbar.


Galileo Computing

11.2.2 Der typisierte Iterator  toptop

Die Collection liefert mit iterator() einen typisierten Iterator und überträgt somit den generischen Typ der Datenstruktur auf den Iterator.


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

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

Nehmen wir wieder eine Collection c. Sie ist mit String typisiert:

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

Soll diese Liste mit einem Iterator abgelaufen werden, so ist herkömmlich zu schreiben:

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

Mit Generics wird der Typ des Iterators vorgeschrieben, und die Typanpassung kann entfallen.

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

Zwar kann ein Iterator auch ohne typisierte Collection typisiert werden, doch wird der Compiler dann einen Hinweis geben. Eclipse gibt hier den Hinweis »Unsafe type operation: Should not assign expression of raw type Iterator to type Iterator<String>. References to generic type Iterator<E> should be parameterized.«

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 hashNext() und next() nutzt.

Aus

for ( Typ elem : c )

folgt

for ( Iterator i = c.iterator(); i.hasNext(); )
{
  Typ elem = (Typ) i.next();
}

Dass der Iterator typisiert ist, ist auch der Grund für den möglichen konkreten Typ beim erweiterten for.


Beispiel   Eine konkrete Klasse, die java.util.List implementiert, enthält String-Objekte. Eine Funktion gesamtLänge() soll ermitteln, wie viele Zeichen alle Strings zusammen besitzen.
int gesamtLänge( List strings )
{
  int gesamt = 0;
  for ( Object s : strings )
    gesamt += ((String)s).length();
  return gesamt;
}
Es ist verführerisch, in for an Stelle von Object String zu schreiben, doch das funktioniert nicht. Wir haben gesehen, dass das intern eingeführte next() vom Iterator nur den Typ Object liefert, also nicht den konkreten Typ String. Doch mit Generics fordert die Funktion gesamtLänge() einfach eine Liste vom Typ String an – intern wird dann auch ein Iterator<String> zurückgegeben.
int gesamtLänge( List<String> strings )
{
  int gesamt = 0;
  for ( String s : strings )
    gesamt += s.length();
  return gesamt;
}

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 und lässt sich während des Ablaufens einfach stoppen.




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

 << zurück




Copyright © Galileo Press GmbH 2005
Für Ihren privaten Gebrauch dürfen Sie die Online-Version natürlich ausdrucken. Ansonsten unterliegt das <openbook> denselben Bestimmungen, wie die gebundene Ausgabe: Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Alle Rechte vorbehalten einschließlich der Vervielfältigung, Übersetzung, Mikroverfilmung sowie Einspeicherung und Verarbeitung in elektronischen Systemen.


[Galileo Computing]

Galileo Press GmbH, Rheinwerkallee 4, 53227 Bonn, Tel.: 0228.42150.0, Fax 0228.42150.77, info@galileo-press.de