Galileo Computing < openbook > Galileo 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 Mathematisches
6 Eigene Klassen schreiben
7 Angewandte Objektorientierung
8 Exceptions
9 Generics, innere Klassen
10 Die Klassenbibliothek
11 Threads und nebenläufige Programmierung
12 Datenstrukturen und Algorithmen
13 Raum und Zeit
14 Dateien und Datenströme
15 Die eXtensible Markup Language (XML)
16 Grafische Oberflächen mit Swing
17 Grafikprogrammierung
18 Netzwerkprogrammierung
19 Verteilte Programmierung mit RMI und Web–Services
20 JavaServer Pages und Servlets
21 Applets
22 Midlets und die Java ME
23 Datenbankmanagement mit JDBC
24 Reflection und Annotationen
25 Logging und Monitoring
26 Sicherheitskonzepte
27 Java Native Interface (JNI)
28 Dienstprogramme für die Java-Umgebung
Stichwort

Download:
- ZIP, ca. 14,1 MB
Buch bestellen
Ihre Meinung?

Spacer
<< zurück
Java ist auch eine Insel (8. Auflage) von Christian Ullenboom
Programmieren mit der Java Standard Edition Version 6
Buch: Java ist auch eine Insel (8. Auflage)

Java ist auch eine Insel (8. Aufl.)
8., aktual. Auflage, geb., mit DVD
1.475 S., 49,90 Euro
Galileo Computing
ISBN 978-3-8362-1371-4
Pfeil 12 Datenstrukturen und Algorithmen
Pfeil 12.1 Datenstrukturen und die Collection-API
Pfeil 12.1.1 Designprinzip mit Schnittstellen, abstrakten und konkreten Klassen
Pfeil 12.1.2 Die Basis-Schnittstellen Collection und Map
Pfeil 12.1.3 Das erste Programm mit Container-Klassen
Pfeil 12.1.4 Die Schnittstelle Collection
Pfeil 12.1.5 Schnittstellen, die Collection erweitern, und Map
Pfeil 12.1.6 Konkrete Container-Klassen
Pfeil 12.1.7 Welche Klasse nehmen?
Pfeil 12.1.8 Generische Datentypen in der Collection-API
Pfeil 12.1.9 Die Schnittstelle Iterable und das erweiterte for
Pfeil 12.2 Mit einem Iterator durch die Daten wandern
Pfeil 12.2.1 Die Schnittstellen Enumeration und Iterator
Pfeil 12.2.2 Iteratoren von Sammlungen und das erweiterte for
Pfeil 12.2.3 Fail-Fast Iterator und die ConcurrentModificationException
Pfeil 12.3 Listen
Pfeil 12.3.1 Auswahlkriterium ArrayList oder LinkedList
Pfeil 12.3.2 Die Schnittstelle List
Pfeil 12.3.3 ArrayList
Pfeil 12.3.4 LinkedList
Pfeil 12.3.5 Der Feld-Adapter Arrays.asList()
Pfeil 12.3.6 toArray() von Collection verstehen – die Gefahr einer Falle erkennen
Pfeil 12.3.7 Primitive Elemente in den Collection-Datenstrukturen
Pfeil 12.4 Vergleichen von Objekten
Pfeil 12.4.1 Die Schnittstellen Comparator und Comparable
Pfeil 12.4.2 Algorithmen mit Such- und Sortiermöglichkeiten
Pfeil 12.4.3 Den größten und kleinsten Wert einer Collection finden
Pfeil 12.4.4 Sortieren
Pfeil 12.5 Mengen (Sets)
Pfeil 12.5.1 HashSet
Pfeil 12.5.2 TreeSet – die Menge durch Bäume
Pfeil 12.5.3 LinkedHashSet
Pfeil 12.6 Stack (Kellerspeicher, Stapel)
Pfeil 12.6.1 Die Methoden von Stack
Pfeil 12.6.2 Ein Stack ist ein Vector – aha!
Pfeil 12.7 Queues (Schlangen) und Deques
Pfeil 12.7.1 Die Schnittstelle Queue
Pfeil 12.7.2 Blockierende Queues und Prioritätswarteschlangen
Pfeil 12.7.3 Deque-Klassen
Pfeil 12.8 Assoziative Speicher
Pfeil 12.8.1 Die Klassen HashMap und TreeMap
Pfeil 12.8.2 Einfügen und Abfragen der Datenstruktur
Pfeil 12.8.3 equals(), hashCode() und IdentityHashMap
Pfeil 12.8.4 Das Problem von veränderbaren Elementen
Pfeil 12.8.5 Aufzählungen und Sichten auf den Assoziativspeicher
Pfeil 12.8.6 Der Gleichheitstest, Hash-Wert und Klon einer Hash-Tabelle
Pfeil 12.8.7 Die Arbeitsweise einer Hash-Tabelle
Pfeil 12.8.8 Multi-Maps
Pfeil 12.9 Die Properties-Klasse
Pfeil 12.9.1 Properties setzen und lesen
Pfeil 12.9.2 Properties verketten
Pfeil 12.9.3 Eigenschaften ausgeben
Pfeil 12.9.4 Hierarchische Eigenschaften
Pfeil 12.9.5 Properties speichern
Pfeil 12.9.6 Klassenbeziehungen: Properties und Hashtable
Pfeil 12.10 Algorithmen in Collections
Pfeil 12.10.1 Ersetzen, Kopieren, Füllen, Umdrehen, Rotieren, Durchmischen
Pfeil 12.10.2 Mit der Halbierungssuche nach Elementen fahnden
Pfeil 12.10.3 Nicht-änderbare Datenstrukturen
Pfeil 12.10.4 Häufigkeit eines Elements
Pfeil 12.10.5 nCopies()
Pfeil 12.10.6 Singletons
Pfeil 12.11 Synchronisation der Datenstrukturen
Pfeil 12.11.1 Lock-free-Algorithmen aus java.util.concurrent
Pfeil 12.11.2 Wrapper zur Synchronisation
Pfeil 12.11.3 CopyOnWriteArrayList und CopyOnWriteArraySet
Pfeil 12.12 Die Klasse BitSet für Bitmengen
Pfeil 12.12.1 Ein BitSet anlegen, füllen und erfragen
Pfeil 12.12.2 Mengenorientierte Operationen
Pfeil 12.12.3 Methodenübersicht
Pfeil 12.12.4 Primzahlen in einem BitSet verwalten


Galileo Computing - Zum Seitenanfang

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


Galileo Computing - Zum Seitenanfang

12.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 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. [Enumeratoren (und Iteratoren) können nicht serialisiert werden, da sie die Schnittstelle Serializable nicht implementieren.]

Beide Schnittstellen haben eine gemeinsame Methode, 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.


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 12.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.

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



Galileo Computing - Zum Seitenanfang

12.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 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 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.


Galileo Computing - Zum Seitenanfang

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

Die Entwickler der Java-Bibliothek haben einen Entwurf gewählt, bei dem Ä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();

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



Ihr Kommentar

Wie hat Ihnen das <openbook> gefallen? Wir freuen uns immer über Ihre freundlichen und kritischen Rückmeldungen.






<< zurück
  Zum Katalog
Zum Katalog: Java ist auch eine Insel





Java ist auch eine Insel
Jetzt bestellen


 Ihre Meinung?
Wie hat Ihnen das <openbook> gefallen?
Ihre Meinung

 Tipp
Zum Katalog: Coding for Fun





 Coding for Fun


 Buchempfehlungen
Zum Katalog: Objektorientierte Programmierung





 Objektorientierte
 Programmierung


Zum Katalog: Einstieg in Eclipse 3.4






 Einstieg in
 Eclipse 3.4


Zum Katalog: Java 6 lernen mit Eclipse






 Java 6 lernen
 mit Eclipse


Zum Katalog: NetBeans Platform 6






 NetBeans
 Platform 6


Zum Katalog: Java und XML






 Java und XML


Zum Katalog: Visual C# 2008






 Visual C# 2008


Zum Katalog: IT-Handbuch für Fachinformatiker






 IT-Handbuch für
 Fachinformatiker


Zum Katalog: C++ von A bis Z






 C++ von A bis Z


 Shopping
Versandkostenfrei bestellen in Deutschland und Österreich
InfoInfo




Copyright © Galileo Press 2009
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, Rheinwerkallee 4, 53227 Bonn, Tel.: 0228.42150.0, Fax 0228.42150.77, info@galileo-press.de