Java ist auch eine Insel von Christian Ullenboom

Buch: Java ist auch eine Insel (Galileo Computing)

Kapitel 11 Datenstrukturen und Algorithmen
	11.1 Mit einem Iterator durch die Daten wandern
		11.1.1 Die Schnittstellen Enumeration und Iterator
		11.1.2 Arrays mit Iteratoren durchlaufen
	11.2 Datenstrukturen und die Collection-API
		11.2.1 Die Schnittstelle Collection
		11.2.2 Das erste Programm mit Container-Klassen
		11.2.3 Schnittstellen, die Collection erweitern, und Map
		11.2.4 Konkrete Container-Klassen
	11.3 Listen
		11.3.1 AbstractList
		11.3.2 Beispiel mit List-Methoden
		11.3.3 ArrayList
		11.3.4 asList() und die »echten« Listen
		11.3.5 toArray() von Collection verstehen - die Gefahr einer Falle erkennen
		11.3.6 Die interne Arbeitsweise von ArrayList und Vector
		11.3.7 LinkedList
		11.3.8 Queue, die Schlange
	11.4 Stack (Kellerspeicher, Stapel)
		11.4.1 Die Methoden von Stack
		11.4.2 Ein Stack ist ein Vector - aha!
	11.5 Die Klasse HashMap und assoziative Speicher
		11.5.1 Ein Objekt der Klasse HashMap erzeugen
		11.5.2 Einfügen und Abfragen der Datenstruktur
		11.5.3 Wichtige Eigenschaften von Assoziativspeichern
		11.5.4 Elemente im Assoziativspeicher müssen unveränderbar bleiben
		11.5.5 Die Arbeitsweise einer Hash-Tabelle
		11.5.6 Aufzählen der Elemente
		11.5.7 Der Gleichheitstest und der Hash-Wert einer Hash-Tabelle
		11.5.8 Klonen
	11.6 Die abstrakte Klasse Dictionary
	11.7 Die Properties-Klasse
		11.7.1 Über die Klasse Properties
		11.7.2 put(), get() und getProperties()
		11.7.3 Eigenschaften ausgeben
		11.7.4 Systemeigenschaften der Java-Umgebung
		11.7.5 Browser-Version abfragen
		11.7.6 Properties von der Konsole aus setzen
		11.7.7 Windows-typische INI-Dateien
	11.8 Algorithmen in Collections
		11.8.1 Datenmanipulation: Umdrehen, Füllen, Kopieren
		11.8.2 Vergleichen von Objekten mit Comparator und Comparable
		11.8.3 Größten und kleinsten Wert einer Collection finden
		11.8.4 Sortieren
		11.8.5 nCopies()
		11.8.6 Singletons
		11.8.7 Elemente in der Collection suchen
	11.9 Synchronisation der Datenstrukturen
	11.10 Typsichere Datenstrukturen
	11.11 Die abstrakten Basisklassen für Container
		11.11.1 Optionale Methoden
	11.12 Die Klasse BitSet für Bitmengen
		11.12.1 Ein BitSet anlegen und füllen
		11.12.2 Mengenorientierte Operationen
		11.12.3 Funktionsübersicht
		11.12.4 Primzahlen in einem BitSet verwalten
	11.13 Ein Design-Pattern durch Beobachten von Änderungen
		11.13.1 Design-Pattern
		11.13.2 Das Beobachter-Pattern (Observer/Observable)

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.

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

<< zurück

<top>

vor >>