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. Bis auf die Assoziativspeicher implementieren die Datenstrukturen 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( E 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<? extends E> 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<E> 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.

<T> T[] toArray(T[] a) Gibt ein Array mit allen Elementen des Containers zurück. Verwendet das als Argument übergebene Array als Zielcontainer, 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.1   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 Generische Datentypen in der Collection-API 

Ein großes Problem mit Datenstrukturen bis Java 5 ist, dass sie prinzipiell offen für jeden Typ sind, da sie Objekte vom allgemeinsten Typ Object beim Speichern entgegennehmen und diesen auch als Rückgabe liefern. Wenn eine Liste zum Beispiel Diskothek-Objekte aufnimmt, sind dort keine Strings, Flummis und Firseurläden-Objekte gewünscht – doch mit einen allgemeinen Typ Object kann das nicht verhindert werden. Eine Anweisung wie

Disko ü30Disko = new Disko();
ArrayList diskos = new ArrayList();
  diskos.add( ü30Disko );  

fügt ein Element in die Liste ein, es hätte aber auch diskos.add("ätsch") sein können. Der Fehler fällt beim Einfügen auch nicht auf, doch beim Wiederholen der Daten und anschließender Typanpassung folgt die gefürchtete ClassCastException.

Seit Java 5 macht die Collection-API massiven Gebrauch der Generics. Erst dadurch wird bessere Typsicherheit gewährleistet, denn nur ganz spezielle Objekte kommen in die Datenstruktur. Mit den Generics lässt sich bei der Konstruktion einer Collection-Datenstruktur angeben, welche Objekte in die Liste aufgenommen werden dürfen. In unserem Beispiel wird die Diskoliste diskos definiert als:

ArrayList<Disko> diskos = new ArrayList<Disko>();

So lässt die Liste nur den Typ Disko beim Hinzufügen und Anfragen zu, nicht aber andere Typen, wie Zeichenketten. Das ist zum einen eine schöne Sicherheit für den Programmierer, hat aber noch einen anderen Vorteil: Zum Beispiel können die Typanpassungen weggelassen werden. Wird die Liste ohne den Typ Disko angelegt, muss für den Zugriff auf das erste Element die explizite Typanpassung von Object auf Disko eingesetzt werden:

Disko ü30Disko = (Disko) diskos.get( 0 );

Mit den Generics kann diese Anpassung entfallen, und es wird kurz

Disko ü30Disko = diskos.get( 0 );

Geschachtelte Generics

Eine ArrayList von Strings ist etwa so zu nutzen:

ArrayList<String> als;

Deklarationen dieser Art lassen sich auch zusammenführen, um etwa eine verkettete Liste aus ArrayList-Objekten, die String-Objekte aufnehmen, aufzubauen¹  :

LinkedList<ArrayList<String>> las = new LinkedList<ArrayList<String>>();

11.2.4 Der Iterator, die Schnittstelle Iterable und das erweiterte for 

Praktisch ist, dass alle java.util.Collection-Klassen die Schnittstelle java.lang.Iterable implementieren, sodass mit dem erweiteren for komfortabel alle Datenstrukturen abgelaufen werden können. So wird das bekannte Programmier-Idiom

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

durch das erweitere for erfolgreich abgekürzt:

for ( Typ elem : c )

Für den Typ gilt, dass er zur Collection passen muss. Anderfalls muss der Typ Object sein und eine explizite Typanpasssung ist nötig. Schreiben wir

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

dann ist sie ausdrücklich vom Typ String und folgende Iteration ist möglich:

for (   String   s : c )
  System.out.println( s );

Ist die Collection nicht typisiert, also definiert als

Collection c = new LinkedList();

wird das erweiterte for natürlich nicht mit String möglich sein, denn die Collection ist lediglich mit Object typisiert.

Der typisierte Iterator

Da das erweiterte for jedoch nicht für alle Fälle den Iterator ersetzt – etwa dann, wenn ein Element über die remove()-Funktion des Iterators gelöscht werden soll – muss wieder zum klassischen Iterator gegriffen werden. Ohne Typangabe liefert next() vom Iterator nur den Basistyp Object. Nehmen wir wieder unsere Collection c.

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 d = (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 auch ohne typisierte Collection ein Iterator typisiert werden, doch dann wird der Compiler einen Hinweis geben. Eclipe 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«.

int gesamtLänge( List strings )
{
  int gesamt = 0;

  for ( Object s : strings )
  gesamt += ((String)s).length();

  return gesamt;
}

int gesamtLänge( List<String> strings )
{
  int gesamt = 0;

  for ( String s : strings )
  gesamt += s.length();

  return gesamt;
}

11.2.5 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. 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 LinkedList sowie ArrayList implementiert auch Vector die Schnittstelle List.

Hier klicken, um das Bild zu Vergrößern

Die Schnittstelle Set für Mengen

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. Die wichtigste konkrete Mengen-Klasse ist HashSet.

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

Die Schnittstelle Queues für Schlangen

Eine Queue arbeitet nach dem FIFO-Prinzip (First-In-First-Out). Elemente, die zuerst eingefügt wurden, werden zuerst wieder herausgegeben, getreu dem Motto: »Wer zuerst kommt, malt zuerst.« Die Schnittstelle Queue definiert Operationen für alle Schlagen.

Die Schnittstelle Map

Eine Datenstruktur, die einen Schlüssel (engl. key) mit einem Wert (engl. value) verbindet, nennt sich assoziativer Speicher. Sie erinnert an ein Gedächtnis und ist vergleichbar mit einem Wörterbuch oder Nachschlagewerk. Betrachten wir beispielsweise ein Telefonbuch. Dort sind Namen (Schlüssel) mit Nummern (Werten) verbunden. In Java schreibt die Schnittstelle Map Verhalten vor. Im Gegensatz zu List ist eine Map unsortiert, und die Reihenfolge, in der die Elemente eingefügt werden, spielt keine Rolle.

Die Schnittstelle Map implementiert Collection nicht. Das liegt daran, dass bei einem Assoziativspeicher Schlüssel und Wert immer zusammen vorkommen müssen und die Datenstruktur eine Operation wie add(Object) nicht unterstützen kann.

Die Schlüssel einer Map können mit Hilfe eines Kriteriums sortiert werden. Ist das der Fall, so implementieren diese speziellen Klassen die Schnittstelle SortedMap, die Map direkt erweitert. Das Sortierkriterium entweder über eine externes Comparator-Objekts festgelegt oder die Elemente in der Map sind vom Typ Comparable. 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.6 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:

¹  Das erinnert mich immer unangenehm an C: Ein Feld von Pointern, die auf Strukturen zeigen, die Pointer enthalten.