11.2 Datenstrukturen und die Collection-API

Dynamische Datenstrukturen passen ihre Größe der Anzahl der Daten an, die sie aufnehmen. Die meisten Datenstrukturen sind dynamisch, haben aber dadurch den Nachteil, dass zur Laufzeit Speicher angefordert werden muss, wenn Daten eingefügt werden. Dieses Problem wurde mittlerweile in der Informatik erkannt, und der Trend geht wieder zu festen, nicht dynamischen Datenstrukturen - natürlich nur dort, wo dies möglich ist. Nicht dynamische Datenstrukturen sind beispielsweise Arrays, die einmal fest in einer bestimmten Größe erzeugt sind.

Eine der größten Neuerungen, die die Java-2-Plattform eingeführt hat, ist die Collection-API. Ein Container ist ein Objekt, welches wiederum Objekte aufnimmt und die Verantwortung für die Elemente übernimmt. Wir werden die Begriffe »Container« und »Collection« synonym verwenden.

11.2.1 Die Schnittstelle Collection

Collection ist die Basis der Hierarchie. Alle Container-Klassen - bis auf die Assoziativspeicher - implementieren die Schnittstelle Collection und erhalten damit einen gemeinsamen, äußeren Rahmen. Mit den dort definierten Operationen lassen sich Elemente hinzufügen, löschen, selektieren und finden.

Die Collection-Schnittstelle wird von mehreren Schnittstellen erweitert. Abgeleitete Schnittstellen schreiben Verhalten vor, ob etwa der Container Werte doppelt beinhalten darf oder die Werte sortiert hält; List, Set und SortedSet sind dabei die wichtigsten. AbstractCollection implementiert Basisfunktionalität und belässt nur noch zwei abstrakte Funktionen.

Hier klicken, um das Bild zu Vergrößern

boolean add( Object o ) Optional. Fügt dem Container ein Element hinzu und gibt true zurück, falls sich das Element einfügen lässt. Gibt false zurück, falls schon ein Objekt gleichen Werts vorhanden ist und doppelte Werte nicht erlaubt sind. Erlaubt der Container das Hinzufügen nicht, muss eine UnsupportedOperationException ausgeworfen werden.

boolean addAll( Collection c ) Fügt alle Elemente der Collection c dem Container hinzu.

void clear() Optional. Löscht alle Elemente im Container. Wird dies vom Container nicht unterstützt, wird eine UnsupportedOperationException ausgeworfen.

boolean contains( Object o ) Liefert true, falls der Container ein inhaltlich gleiches Element enthält.

boolean containsAll( Collection c ) Liefert true, falls der Container alle Elemente der Collection c enthält.

boolean isEmpty() Liefert true, falls der Container keine Elemente enthält.

Iterator iterator() Liefert ein Iterator-Objekt über alle Elemente des Containers.

boolean remove( Object o ) Optional. Entfernt das angegebene Objekt aus dem Container, falls es vorhanden ist.

boolean removeAll( Collection c ) Optional. Entfernt alle Objekte der Collection c aus dem Container.

boolean retainAll( Collection c ) Optional. Entfernt alle Objekte, die nicht in der Collection c vorkommen.

int size() Gibt die Anzahl der Elemente im Container zurück.

Object[] toArray() Gibt ein Array mit allen Elementen des Containers zurück.

Object[] toArray( Object a[] ) Gibt ein Array mit allen Elementen des Containers zurück. Verwendet das als Parameter übergebene Array, wenn es groß genug ist. Sonst wird ein Array passender Größe angelegt, dessen Laufzeittyp a entspricht.

boolean equals( Object o ) Prüft, ob das angegebene Objekt ebenfalls ein Container ist und die gleichen Elemente enthält wie dieser Container.

int hashCode() Liefert den Hash-Wert des Containers. Dies ist interessant, wenn der Container als Schlüssel in Hash-Tabellen verwendet wird. Dann darf der Inhalt aber nicht mehr geändert werden, da der Hash-Wert von allen Elementen des Containers abhängt.

11.2.2 Das erste Programm mit Container-Klassen

Wie wir schon gesehen haben, implementieren alle Container-Klassen das Interface Collection und haben dadurch schon wichtige Funktionen, um Daten aufzunehmen, zu manipulieren und auszulesen. Das folgende Programm erzeugt als Datenstruktur eine verkettete Liste und fügt zehn String-Elemente ein. Diese werden mit einem Iterator wieder ausgelesen.

Listing 11.2 ErsteSammlung.java

import java.util.*;
class ErsteSammlung
{
  public static void main( String args[] )
  {
    Collection c = new LinkedList();
    for ( int i = 0; i < 10; i++ )
      c.add( "" + i );
    for ( Iterator it = c.iterator(); it.hasNext(); )
      System.out.println( it.next() );
  }
}

Besonders leicht - unter softwaretechnischen Gesichtspunkten - lässt sich die Datenstruktur ändern. Wir müssen nur

Collection c = new LinkedList();

etwa in

Collection c = new ArrayList();

ändern, und schon ist die Liste intern nicht mehr mit verketteten Elementen implementiert, sondern als Array. Es ist immer schön, wenn wir, etwa aus Gründen der Geschwindigkeit, so leicht die Datenstruktur ändern können. Der Rest des Programms bleibt unverändert.

Sich selbst in einer Liste haben

Die Implementierung der Listen-Klasse hat ein Problem, wenn ein Listen-Objekt sich selbst als Element enthält.

Die folgenden Zeilen provozieren einen StackOverflowError:

List l = new ArrayList();
l.add( "Hübsch" );
l.add( l );
System.out.println( l );   // hier ist das Problem

Das Phänomen tritt erst bei der Ausgabe mit println() auf, denn die Methode toString() auf der Liste l ruft wiederum toString() auf l auf, was wiederum toString() auf l aufruft und so weiter.

11.2.3 Schnittstellen, die Collection erweitern, und Map

Es gibt einige elementare Schnittstellen, die einen Container weiter untergliedern, etwa in der Art, wie Elemente gespeichert werden.

Die Schnittstelle List

Die Schnittstelle List, die die Collection-Schnittstelle erweitert, enthält zusätzliche Operationen für eine geordnete Liste (auch Sequenz genannt) von Elementen. Seit Java 1.2 implementiert auch die Klasse Vector die Schnittstelle List. Auf die Elemente einer Liste lässt sich über einen ganzzahligen Index zugreifen, und es kann linear nach Elementen gesucht werden. Doppelte Elemente sind erlaubt. Da das AWT-Paket ebenfalls eine Klasse mit dem Namen »List« definiert, sollte bei Namenskonflikten der voll qualifizierte Name, also java.util.List oder java.awt.List verwendet werden. Neben Vector implementieren die Klassen AbstractList, LinkedList sowie ArrayList die List-Schnittstelle.

Hier klicken, um das Bild zu Vergrößern

Die Schnittstelle Set

Ein Set ist eine im mathematischen Sinne definierte Menge von Objekten. Wie von mathematischen Mengen bekannt, darf ein Set keine doppelten Elemente enthalten. Für zwei nicht identische Elemente e1 und e2 eines Set-Objekts liefert der Vergleich e1.equals(e2) also immer false. Genauer gesagt: Aus e1.equals(e2) folgt, dass e1 und e2 identische Objektreferenzen sind, sich also auf dasselbe Mengenelement beziehen.

Besondere Beachtung muss Objekten geschenkt werden, die ihren Wert nachträglich ändern, da so zunächst ungleiche Mengenelemente inhaltlich gleich werden können. Dies kann ein Set nicht kontrollieren. Als weitere Einschränkung gilt, dass eine Menge sich selbst nicht als Element enthalten darf.

Zwei Klassen implementieren die Schnittstelle Set: die abstrakte Klasse AbstractSet und die konkrete Klasse HashSet.

Die Schnittstelle SortedSet

SortedSet erweitert Set um die Eigenschaft, Elemente sortiert auslesen zu können. Das Sortierkriterium wird durch ein Exemplar der Hilfsklasse Comparator bestimmt. TreeMap ist die einzige Klasse, die SortedMap implementiert.

Die Schnittstelle Map

Eine Klasse, die Map implementiert, realisiert einen assoziativen Speicher. Dieser verbindet einen Schlüssel mit einem Wert, etwa einen Namen mit einer E-Mail-Adresse. Im Gegensatz zu List ist eine Map unsortiert, und die Reihenfolge, in der die Elemente eingefügt werden, spielt keine Rolle. Ebenso wie Vector nun eine Implementierung von List ist, implementiert die Klasse Hashtable seit Java 1.2 die Schnittstelle Map.

Die Schnittstelle Map implementiert Collection nicht. Das liegt daran, dass nicht nur ein Element mit add() dem Container hinzugeführt wird, sondern zwei: Schlüssel und Wert. Darauf ist die allgemeine Collection nicht vorbereitet.

Die Schnittstelle SortedMap

Eine Map kann mit Hilfe eines Kriteriums sortiert werden und nennt sich dann SortedMap, es ist also eine Schnittstelle, die Map direkt erweitert. Das Sortierkriterium wird mittels eines Comparator-Objekts festgelegt. Damit kann auf einen assoziativen Speicher über einen Iterator in einer definierten Reihenfolge iteriert werden. Bisher implementiert nur die konkrete Klasse TreeMap die Schnittstelle SortedMap.

11.2.4 Konkrete Container-Klassen

Werden wir nun ein wenig konkreter. Alle bisher vorgestellten Schnittstellen und Klassen dienen der Modellierung und dem Programmierer nur als Basis. Folgende Klassen sind konkrete Klassen und können von uns benutzt werden: