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

Inhaltsverzeichnis
Vorwort
1 Java ist auch eine Sprache
2 Sprachbeschreibung
3 Klassen und Objekte
4 Der Umgang mit Zeichenketten
5 Eigene Klassen schreiben
6 Exceptions
7 Generics<T>
8 Äußere.innere Klassen
9 Besondere Klassen der Java SE
10 Architektur, Design und angewandte Objektorientierung
11 Die Klassenbibliothek
12 Bits und Bytes und Mathematisches
13 Datenstrukturen und Algorithmen
14 Threads und nebenläufige Programmierung
15 Raum und Zeit
16 Dateien, Verzeichnisse und Dateizugriffe
17 Datenströme
18 Die eXtensible Markup Language (XML)
19 Grafische Oberflächen mit Swing
20 Grafikprogrammierung
21 Netzwerkprogrammierung
22 Verteilte Programmierung mit RMI
23 JavaServer Pages und Servlets
24 Datenbankmanagement mit JDBC
25 Reflection und Annotationen
26 Dienstprogramme für die Java-Umgebung
A Die Begleit-DVD
Stichwort
Ihre Meinung?

Spacer
 <<   zurück
Java ist auch eine Insel von Christian Ullenboom
Das umfassende Handbuch
Buch: Java ist auch eine Insel

Java ist auch eine Insel
geb., mit DVD
1482 S., 49,90 Euro
Rheinwerk Computing
ISBN 978-3-8362-1506-0
Pfeil 13 Datenstrukturen und Algorithmen
  Pfeil 13.1 Datenstrukturen und die Collection-API
    Pfeil 13.1.1 Designprinzip mit Schnittstellen, abstrakten und konkreten Klassen
    Pfeil 13.1.2 Die Basis-Schnittstellen Collection und Map
    Pfeil 13.1.3 Das erste Programm mit Container-Klassen
    Pfeil 13.1.4 Die Schnittstelle Collection und Kernkonzepte
    Pfeil 13.1.5 Schnittstellen, die Collection erweitern, und Map
    Pfeil 13.1.6 Konkrete Container-Klassen
    Pfeil 13.1.7 Welche Container-Klasse nehmen?
    Pfeil 13.1.8 Generische Datentypen in der Collection-API
    Pfeil 13.1.9 Die Schnittstelle »Iterable« und das erweiterte »for«
  Pfeil 13.2 Mit einem Iterator durch die Daten wandern
    Pfeil 13.2.1 Die Schnittstellen Enumeration und Iterator
    Pfeil 13.2.2 Iteratoren von Sammlungen und das erweiterte »for«
    Pfeil 13.2.3 Fail-Fast-Iterator und die ConcurrentModificationException
  Pfeil 13.3 Listen
    Pfeil 13.3.1 Auswahlkriterium ArrayList oder LinkedList
    Pfeil 13.3.2 Die Schnittstelle List
    Pfeil 13.3.3 ListIterator *
    Pfeil 13.3.4 ArrayList
    Pfeil 13.3.5 LinkedList
    Pfeil 13.3.6 Der Feld-Adapter »Arrays.asList()«
    Pfeil 13.3.7 »toArray()« von Collection verstehen – die Gefahr einer Falle erkennen
    Pfeil 13.3.8 Primitive Elemente in den Collection-Datenstrukturen
  Pfeil 13.4 Datenstrukturen mit Ordnung
    Pfeil 13.4.1 Algorithmen mit Such- und Sortiermöglichkeiten
    Pfeil 13.4.2 Den größten und kleinsten Wert einer Collection finden
    Pfeil 13.4.3 Sortieren
  Pfeil 13.5 Mengen (Sets)
    Pfeil 13.5.1 HashSet
    Pfeil 13.5.2 TreeSet – die Menge durch Bäume
    Pfeil 13.5.3 LinkedHashSet
  Pfeil 13.6 Stack (Kellerspeicher, Stapel)
    Pfeil 13.6.1 Die Methoden von »Stack«
    Pfeil 13.6.2 Ein »Stack« ist ein »Vector« – aha!
  Pfeil 13.7 Queues (Schlangen) und Deques
    Pfeil 13.7.1 Die Schnittstelle »Queue«
    Pfeil 13.7.2 Blockierende Queues und Prioritätswarteschlangen
    Pfeil 13.7.3 »Deque«-Klassen
  Pfeil 13.8 Assoziative Speicher
    Pfeil 13.8.1 Die Klassen »HashMap« und »TreeMap«
    Pfeil 13.8.2 Einfügen und Abfragen der Datenstruktur
    Pfeil 13.8.3 Über die Bedeutung von »equals()«, »hashCode()«
    Pfeil 13.8.4 IdentityHashMap
    Pfeil 13.8.5 Das Problem von veränderten Elementen
    Pfeil 13.8.6 Aufzählungen und Ansichten des Assoziativspeichers
    Pfeil 13.8.7 Der Gleichheitstest, Hash-Wert und Klon einer Hash-Tabelle*
    Pfeil 13.8.8 Die Arbeitsweise einer Hash-Tabelle *
  Pfeil 13.9 Die Properties-Klasse
    Pfeil 13.9.1 Properties setzen und lesen
    Pfeil 13.9.2 Properties verketten
    Pfeil 13.9.3 Hierarchische Eigenschaften
    Pfeil 13.9.4 Eigenschaften ausgeben *
    Pfeil 13.9.5 Properties laden und speichern
  Pfeil 13.10 Algorithmen in Collections
    Pfeil 13.10.1 Nicht-änderbare Datenstrukturen
    Pfeil 13.10.2 Null Object Pattern und leere Sammlungen zurückgeben
    Pfeil 13.10.3 Mit der Halbierungssuche nach Elementen fahnden
    Pfeil 13.10.4 Ersetzen, Kopieren, Füllen, Umdrehen, Rotieren, Durchmischen *
    Pfeil 13.10.5 Häufigkeit eines Elements *
    Pfeil 13.10.6 nCopies() *
    Pfeil 13.10.7 Singletons *
  Pfeil 13.11 Synchronisation der Datenstrukturen
    Pfeil 13.11.1 Lock-free-Algorithmen aus java.util.concurrent
    Pfeil 13.11.2 Wrapper zur Synchronisation
    Pfeil 13.11.3 »CopyOnWriteArrayList« und »CopyOnWriteArraySet«
  Pfeil 13.12 Die Klasse »BitSet« für Bitmengen *
    Pfeil 13.12.1 Ein »BitSet« anlegen, füllen und erfragen
    Pfeil 13.12.2 Mengenorientierte Operationen
    Pfeil 13.12.3 Methodenübersicht
    Pfeil 13.12.4 Primzahlen in einem BitSet verwalten
  Pfeil 13.13 Zum Weiterlesen


Rheinwerk Computing - Zum Seitenanfang

13.2 Mit einem Iterator durch die Daten wandern  Zur nächsten ÜberschriftZur vorigen Überschrift

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 eine 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«.


Rheinwerk Computing - Zum Seitenanfang

13.2.1 Die Schnittstellen Enumeration und Iterator  Zur nächsten ÜberschriftZur vorigen Überschrift

Für Iteratoren deklariert die Java-Bibliothek zwei unterschiedliche Schnittstellen. Das hat historische Gründe: Die Schnittstelle Enumeration [Nicht Enumerable! ] 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 Iterable und Enumeration erweitern selbst keine weitere Schnittstelle. [Konkrete Enumeratoren (und Iteratoren) können nicht automatisch serialisiert werden; die realisierenden Klassen müssen hierzu die Schnittstelle Serializable implementieren. ]

Beide Schnittstellen haben eine gemeinsame Methode, die das nächste Element erfragt, und eine Methode, 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.


Beispiel Die Aufzählung erfolgt meistens über einen Zweizeiler. Da jede Collection eine Methode iterator() besitzt, lassen sich alle Elemente wie folgt auf dem Bildschirm ausgeben:

Listing 13.4  com/tutego/insel/util/IteratorDemo.java, main()

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() );

Das erweiterte for macht das Ablaufen aber noch einfacher, und der gleiche Iterator steckt dahinter.


Im Gegensatz zum Index eines Felds können wir beim Iterator ein Objekt nicht noch einmal auslesen (next() geht automatisch zum nächsten Element), nicht vorspringen beziehungsweise hin und her springen. Ein Iterator gleicht anschaulich einem Datenstrom; wollten wir ein Element zweimal besuchen, zum Beispiel eine Datenstruktur 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.


Hinweis In Java steht der Iterator nicht auf einem Element, sondern zwischen Elementen.



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 Methode kann später eine NoSuchElementException (eine RuntimeException) auslösen, wenn nextElement() aufgerufen und das Ergebnis false beim Aufruf von hasMoreElements() ignoriert wird.

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.

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 zugrundeliegenden 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()
  • E next()
  • void remove() Entfernt das Element, das der Iterator zuletzt bei next() geliefert hat. Kann ein Iterator keine Elemente löschen, so löst er eine UnsupportedOperationException aus.

Hinweis Warum es die Methode remove() im Iterator gibt, ist eine interessante Frage. Die Erklärung dafür: Der Iterator kennt die Stelle, 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 sortierten NavigableSet oder NavigableMap. 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 das Einfügen weitere Fragen auf: vor oder nach dem zuletzt per next() gelieferten Element? Soll das neue Element mit aufgezählt werden oder nicht? Soll es auch dann nicht aufgezählt werden, wenn es in der Sortierung erst später an die Reihe käme? Eine Löschen-Methode ist problemloser und universell anwendbar.


Konvertieren von Enumeration, Iterator, Iterable

Es gibt keine direkte Methode, die ein Enumeration in ein Iterator oder ein Iterator in ein Enumeration konvertiert. Nur über Umwege lässt sich das erreichen. Es helfen dabei zwei Methoden in der Utility-Klasse Collections:


class java.util.Collections

  • static <T> Enumeration<T> enumeration( Collection<T> c )
  • static <T> ArrayList<T> list( Enumeration<T> e )

Es liefert enumeration() zu einer Collection eine Aufzählung vom Typ Enumeration. (Für einen gewünschten Iterator ist keine Hilfsmethode nötig, da jede Collection die Methode iterator() besitzt.) Ist eine Collection gegeben, so bleibt nichts anderes übrig, eine temporäre Datenstruktur aufzubauen, Element für Element den Iterator abzulaufen und diese Elemente in die temporäre Datenstruktur zu setzen, die dann Argument der Methode enumeration() wird.

Der zweite Fall ist einfacher. Ist eine Enumeration gegeben, liefert list() eine ArrayList – der Rückgabetyp ist wirklich sehr erstaunlich, da er ungewöhnlich konkret ist. Die ArrayList ist eine Collection und somit Iterable, kann also rechts vom Doppelpunkt beim erweiterten for stehen bzw. liefert mit iterator() einen Iterator.


Rheinwerk Computing - Zum Seitenanfang

13.2.2 Iteratoren von Sammlungen und das erweiterte »for«  Zur nächsten ÜberschriftZur vorigen Überschrift

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 statische Methode 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 Datenstruktur 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()-Methode des Iterators löschen, was über das erweiterte for nicht möglich ist.


Rheinwerk Computing - Zum Seitenanfang

13.2.3 Fail-Fast-Iterator und die ConcurrentModificationException  topZur vorigen Überschrift

Beackern zwei Programmstellen gleichzeitig eine Datenstruktur, kann es zu Schwierigkeiten kommen, wenn sich die Datenstruktur strukturell verändert, also neue Elemente hinzukommen oder wegfallen. Probleme treten leicht auf, wenn ein Verweis auf die Datenstruktur im Programm an verschiedenen Stellen weitergegeben wird. Führt nun eine Stelle strukturelle Änderungen mit Methoden wie remove() oder add() durch, und die Größe der Liste verändert sich damit, kann das zu Zugriffsfehlern führen, wenn die andere Stelle von der Änderung nichts mitbekommt.

Nehmen wir an, zwei Programmteile greifen auf eine gemeinsame Liste zurück. Ein Programmteil merkt sich eine Suchstelle und will anschießend auf das gefundene Element zurückgreifen. Zwischen diesen beiden Operationen verändert jedoch ein anderer Programmteil die Liste und die Position des Elements verschiebt sich:

Listing 13.5  com/tutego/insel/util/ConcurrentModification.java, main()

List<String> list = new ArrayList<String>( Arrays.asList( "Trullo", "Zippus" ) );
int posOfZippus = list.indexOf( "Zippus" );
System.out.println( list.get( posOfZippus ) );  // Zippus
list.add( 0, "Apulien" );
System.out.println( list.get( posOfZippus ) );  // Trullo

Nach dem Einfügen von »Apulien« ist posOfZippus also veraltet. Es wäre eine Hilfe, wenn get() die strukturelle Veränderung bemerken würde.

Beim Erfragen über Listen-Iteratoren ist das anders. Die Entwickler der Java-Bibliothek haben einen Entwurf gewählt, bei dem konfliktträchtige Änderungen über die Listen-Iteratoren auffallen und zu einer ConcurrentModificationException führen. Das funktioniert so, dass sich die Liste die Anzahl struktureller Änderungen merkt – bei der Standardimplementierung vom JDK intern in der Variablen modCount:

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

List<String> list = new ArrayList<String>( Arrays.asList( "Stunden", "der" ) );
Iterator<String> iterator = list.iterator();  // modCount = 0, Umbruch
                                              // expectedModCount = 0
list.get( 0 );                                // Anfragen ändert modCount nicht
list.add( "Entspannung" );                    // modCount = 1, Umbruch
                                              // expectedModCount = 0
iterator.next();                              // modCount != Umbruch
                                              // expectedModCount => CME

Der Iterator registriert die Änderungen, da sich der modCount in der Zwischenzeit verändert hat. Wird der Iterator initialisiert, erfragt er den modCount der Liste und speichert den Wert in expectedModCount. Jede strukturelle Änderung in der Liste führt zum Inkrement vom modCount. Wird später eine Operation über den Iterator durchgeführt, testet er, ob der gemerkte expectedModCount mit dem aktuellen modCount übereinstimmt. In unserem Fall tut er das nicht, denn add() ist eine strukturelle Änderung und modCount wird 1. Beim nachfolgendem next() kommt es zu einer ConcurrentModificationException.


Tellerrandblick Unter C++ ist die Standard Template Library (STL) eine Bibliothek, die Datenstrukturen und Algorithmen implementiert. Ein Vergleich der STL mit der Collection-API ist schwierig, obwohl beide Konzepte wie Listen, Mengen und Iteratoren besitzen. So gibt es in Java nur eine Klasse pro Datenstruktur (auch durch Generics), was die STL durch Templateklassen (daher Template Library) realisiert, die auch primitive Werte (ohne die lästigen Java-Wrapper) speichert. Während Java über den globalen Basistyp Object jedes Objekt in jeder Datenstruktur erlaubt und sich auf die Prüfung zur Laufzeit verlässt, ist C++ da viel strenger. Die Java-Datenstrukturen referenzieren die Objekte und speichern nicht ihre Zustände an sich, wie es bei der STL üblich ist – hier steht Referenz-Semantik gegen Wert-Semantik. Fehler werden von der Collection-API über Exceptions angezeigt, während die STL kaum Ausnahmen auslöst und oft undefinierte Zustände hinterlässt; Entwickler müssen eben korrekte Anfragen stellen. STL nutzt überladene Operatoren wie == statt des Java-equals(), < für die Ordnung in sortierten Sammlungen, [] beim Zugriff und Überschreiben und den Operator ++ für Iteratoren. Iteratoren spielen bei der STL eine sehr große Rolle – es gibt auch einen Random-Access-Iterator, der Indexierung durch [] erlaubt. Die STL-Algorithmen sind von den Datenstrukturen abgetrennt – anders als in Java – und bekommen die Elemente über Iteratoren. Zudem ist die STL reichhaltiger und bietet beispielsweise Funktionsobjekte; hier gibt es Ansätze wie http://jga.sourceforge.net/, um die STL bestmöglich auf Java zu übertragen.




Ihr Kommentar

Wie hat Ihnen das <openbook> gefallen? Wir freuen uns immer über Ihre freundlichen und kritischen Rückmeldungen. >> Zum Feedback-Formular
 <<   zurück
 Ihre Meinung?
Wie hat Ihnen das <openbook> gefallen?
Ihre Meinung

 Buchempfehlungen
Zum Katalog: Java ist auch eine Insel






 Java ist auch
 eine Insel


Zum Katalog: Java SE Bibliotheken






 Java SE Bibliotheken


Zum Katalog: Professionell entwickeln mit Java EE 7






 Professionell
 entwickeln mit
 Java EE 7


Zum Katalog: Einstieg in Eclipse






 Einstieg in
 Eclipse


Zum Katalog: Einstieg in Java






 Einstieg in
 Java


 Shopping
Versandkostenfrei bestellen in Deutschland und Österreich
InfoInfo




Copyright © Rheinwerk Verlag GmbH 2011
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.


Nutzungsbestimmungen | Datenschutz | Impressum

Rheinwerk Verlag GmbH, Rheinwerkallee 4, 53227 Bonn, Tel.: 0228.42150.0, Fax 0228.42150.77, service@rheinwerk-verlag.de