Die Collection Interfaces

Die Interfaces

Das Collection-API zerfällt in fünf grundlegende Interfaces und deren Implementierungen. Da die Verwendung und die wichtigsten Eigenschaften durch die Interfaces festgelegt werden, betrachten wir zuerst die Interfaces und dann in einem zweiten Schritt die dazugehörigen Klassen.

  • Collection
    • Sammlung von Objekten ohne besondere Ordnung
    • Duplikate sind zulässig
  • List
    • Geordnete Sammlung von Objekten
    • Duplikate sind zulässig
  • Set
    • Ungeordnete Sammlung von Objekten
    • Duplikate sind nicht zulässig
  • Queue
    • geordnet, Duplikate erlaubt
    • Warteschlange mit speziellen Methoden, die mit leeren oder überfüllten Warteschlangen ohne Ausnahmen umgehen können
  • Deque
    • geordnet, Duplikate erlaubt
    • Erweiterte Form der Queue mit Operationen an beiden Enden der Warteschlange

Die Basis aller Interfaces ist das Interface Collection, in dem die Methoden festgelegt werden, die allen Collections gemeinsam sind. Generell sind zwei Fragen bei allen Interfaces wichtig:

  1. Wird eine Ordnung gehalten? Ordnung bedeutet in diesem Zusammenhang, dass die Elemente innerhalb der Collection in einer festen Reihenfolge abgelegt sind, die sich aus der Reihenfolge des Einfügens ergibt. Wenn eine Ordnung vorhanden ist, kann man den gespeicherten Objekten stabile Indices zuordnen, jedes Objekt bekommt einen Index, der über die Zeit stabil bleibt. Hält die Collection keine Ordnung, können die Elemente nicht indiziert werden und bei aufeinanderfolgenden Durchläufen mit einem Iterator können die Objekte in unterschiedlicher Sequenz ausgegeben werden. Insbesondere kommen bei einer ungeordneten Collection die Elemente in einer anderen Reihenfolge heraus, als man sie hineingesteckt hat.
  2. Sind Duplikate zulässig? Duplikate sind Elemente gleichen Inhalts. Wenn Duplikate zulässig sind, können in einer Collection mehrere Objekte enthalten sein, bei denen ein equals()-Aufruf true ergeben würde. Sind Duplikate verboten, gibt es keine zwei Objekte in der Collection bei denen equals() true ergeben würde.

Collection trifft zu den beiden Fragen keine abschließende Aussage, d. h. es gibt keine Ordnung und Duplikate sind zulässig. Das genaue Verhalten wird erst auf der Ebene der Subinterfaces festgelegt.

List erlaubt Duplikate und hält eine Ordnung. Im Gegensatz dazu verbietet Set Duplikate und garantiert keine Ordnung. Queue stell eine Warteschlange dar und Deque erweitert diese um Operationen an beiden Enden, sodass man sowohl eine Queue als auch einen Stack damit realisieren kann. Sowohl Queue als auch Deque sind geordnet und erlauben Duplikate.

Beispiel: Set 

Set<String> set = new HashSet<>();

set.add("Element A");
set.add("Element B");
set.add("Element C");
set.add("Element A");
set.add("Element B");

for (String element : set) {
    System.out.println(element);
}

Element B
Element C
Element A

Im Beispiel kann man sehen, dass bei einem Set die Elemente keine Ordnung halten und dass die beiden Duplikate „Element A“ und „Element B“ nur jeweils einmal aufgenommen wurden.

Ein wichtiger Punkt ist, dass durch das Hinzufügen eines Objektes zu einer Collection (hier einem Set) keine Kopie des Objektes angelegt wird. Die Collection speichert nur eine Kopie der Referenz, d. h. der Inhalt des Objektes kann über eine weitere Referenz, so noch vorhanden, verändert werden. Das folgende Beispiel zeigt diesen Sachverhalt: 

public class A {
    public int wert;
    public String toString() {
        return "" + wert;
    }
}

A a = new A();
a.wert = 42;

Set<A> set = new HashSet<>();
set.add(a);
System.out.println(set); // -> [42]

a.wert = 23;
System.out.println(set); // -> [23]

Beispiel: List 

List<String> list = new ArrayList<>();

list.add("Element A");
list.add("Element B");
list.add("Element C");
list.add("Element A");
list.add("Element B");

for (String element : list) {
    System.out.println(element);
}

Element A
Element B
Element C
Element A
Element B

Die Liste hält im Gegensatz zum Set die Ordnung und erlaubt Duplikate. Deswegen gibt es „Element A“ und „Element B“ dann zweimal.

Methoden auf Collection

  • boolean add(E e) – Fügt ein Element e hinzu
  • boolean addAll(Collection<? extends E> c) – Fügt alle Elemente aus c hinzu
  • boolean remove(Object o) – Entfernt das gegebene Objekt o falls vorhanden
  • boolean removeAll(Collection<?> c) – Entfernt alle Elemente, die in der gegebenen Collection c enthalten sind
  • boolean retainAll(Collection<?> c) – Entfernt alle Elemente, die nicht in der gegebenen Collection c enthalten sind
  • void clear() – Entfernt alle Elemente
  • boolean contains(Object o) – Prüft, ob das gegebene Objekt in der Collection enthalten ist
  • boolean containsAll(Collection<?> c) – Prüft ob alle Elemente der gegebenen Collection enthalten sind
  • int size() – Gibt Anzahl der Elemente zurück
  • boolean isEmpty() – (size() == 0)
  • Object[] toArray() – Konvertiert die Collection in ein Object-Array
  • T[] toArray(T[] a) – Konvertiert die Collection in ein Array

Die Methoden aus dem Interface Collection sind weitgehend selbsterklärend. Die Konvertierung in ein Array ist allerdings etwas ungewöhnlich, da es hier zwei Varianten gibt:

  • Object[] toArray() – Die Elemente der Collection werden in ein Array vom Typ Object[] konvertiert. Das Array hat dabei so viele Elemente, wie die Collection (size()). Da man bei einem Object-Array jedes Element einzeln casten muss, wenn man damit etwas anfangen möchte, kommt diese Methode selten zum Einsatz.
  • T[] toArray(T[] a) – Konvertiert die Collection in ein Array vom Typ, der durch den Typ-Parameter T der Collection festgelegt wurde. Bei diese Methode muss man ein Array vom richtigen Typ übergeben. Ist dieses Array groß genug für alle Elemente der Collection, so werden diese einfach in das Array umkopiert und eine Referenz auf das übergebene Array wird zurückgegeben. Ist das übergebene Array zu klein, wird ein neues, hinreichend großes Array angelegt und mit den Elementen befüllt. Zurückgegeben wird dann eine Referenz auf das neu erzeugte Array.

Üblicherweise ruft man die toArray-Methode mit folgender Konstruktion auf (angenommen die Collection sei vom Typ Collection<String>: 

String[] array = collection.toArray(new String[collection.size()]);

Beispiel: Collection 

Collection<String> col1 = new ArrayList<>();

col1.add("Element 1");
col1.add("Element 2");
col1.add("Element 3");
col1.add("Element 4");

System.out.println(col1.size());  // --> 4
System.out.println(col1.contains("Element 3"));  // --> true

col1.remove("Element 3");
System.out.println(col1.size());  // --> 3

Collection<String> col2 = new ArrayList<>();
col2.addAll(col1);

System.out.println(col2); // --> [Element 1, Element 2, Element 4]

col1.clear();
System.out.println(col1.size());  // --> 0

col1.add("Element 2");
col2.removeAll(col1);

System.out.println(col2); // --> [Element 1, Element 4]

String[] str1 = col1.toArray(new String[0]);

Object[] str2 = col2.toArray();

System.out.println(Arrays.asList(str1)); // --> [Element 2]
System.out.println(Arrays.asList(str2)); // --> [Element 1, Element 4]

Methoden auf List

Zusätzlich zu den Methoden aus Collection hat List noch

  • boolean addAll(int index, Collection<? extends E> c) – Fügt alle Elemente von c an der gegebenen Stelle ein und verschiebt die existierenden Elemente
  • E get(int index) – Gibt das Element an der gegebenen Position zurück
  • E set(int index, E element) – Ersetze das Element an der gegebenen Position
  • void add(int index, E element) – Füge an der gegebenen Position ein Element ein
  • E remove(int index) – Entferne das Element an der Position
  • int indexOf(Object o) – Position des gegebenen Objekts (erster Treffer)
  • int lastIndexOf(Object o) – Position des gegebenen Objekts (letzter Treffer)
  • ListIterator<E> listIterator() – Liefert einen ListIterator
  • ListIterator<E> listIterator(int index) – Liefert einen ListIterator ab der gegebenen Position
  • List<E> subList(int fromIndex, int toIndex) – Erzeugt eine Sub-Liste beginnend bei fromIndex (inklusive) und endend bei toIndex (exklusive)

List erweitert die Methoden von Collection um Methoden, die ausnutzen, dass in einer List alle Elemente einen eindeutigen Index haben.

Beispiel: List 

List<String> list1 = new ArrayList<String>();

list1.add("Element 1"); list1.add("Element 2");
list1.add("Element 3"); list1.add("Element 4");

System.out.println(list1.get(3)); // --> Element 4
list1.remove(0);
System.out.println(list1);  // --> [Element 2, Element 3, Element 4]

list1.add(2, "Eingefuegt");
System.out.println(list1);  // --> [Element 2, Element 3, Eingefuegt,
                                   // Element 4]

List<String> list2 = list1.subList(1, 3);
System.out.println(list2);  // --> [Element 3, Eigefuegt]

list2.set(1, "Ausgetauscht");
System.out.println(list2);  // --> [Element 3, Ausgetauscht]

list2.add(2, "Eingefuegt");
System.out.println(list2);  // --> [Element 3, Ausgetauscht, Eingefuegt]

System.out.println(list2.indexOf("Element 3"));  // --> 0

Methoden auf Set

Set fügt zur Schnittstelle von Collection keine weiteren Methoden hinzu, sondern definiert nur die Semantik

  • ungeordnet
  • keine Duplikate zulässig

Set hat keine eigenen Methoden, weil Collection schon alles definiert hat, was möglich ist.

Vorsicht: Veränderbare Objekte im Set

  • Das Verhalten hash-basierter Sets ist undefiniert, wenn der Wert nach dem Hinzufügen verändert wird
  • Schlimmstenfalls werden die Objekte nie mehr wiedergefunden
  • Daher sollte man vorsichtig bei veränderbaren Objekte (mutuable objects) in Sets sein
  • Eine Set darf sich nicht selbst enthalten

Sets werden normalerweise mithilfe von Hash-Tabellen implementiert. Diese sind aber empfindlich gegen Veränderungen des Inhalts von Objekten, nachdem diese einmal hinzugefügt wurden. Deshalb darf man Objekte nach dem Speichern in einem Set nicht mehr verändern. Will man sie doch manipulieren muss man

  1. das Objekt aus dem Set entfernen (remove())
  2. das Objekt verändern
  3. das Objekt dem Set wieder hinzufügen (add())

Der Grund liegt darin, dass bei einer Hash-Tabelle die Speicherposition anhand des Hash-Wertes (hashCode()) bestimmt wird. Der Hash-Wert berechnet sich aus dem Inhalt des Objekts. Ändert sich der Inhalt, so ändert sich der Hash-Wert. Verändert man den Inhalt und damit den Hash-Wert, so ist das Objekt in der Hash-Tabelle noch immer an der Stelle gespeichert, die seinem alten Hash-Wert entspricht – die Position wird nur einmalig beim Einfügen bestimmt. Damit entspricht die Speicherposition nicht mehr dem aktuellen Hash-Wert und das Objekt kann in der Tabelle nicht wiedergefunden werden.

Verändert man Objekte nachträglich kommt es zu der paradoxen Situation, dass die contains()-Methode meldet, dass das Objekt nicht vorhanden ist, beim Iterieren wird es aber ausgegeben.

Methoden auf Queue

Zusätzlich zu den Methoden aus Collection hat Queue noch

  • boolean offer(E e) – Versucht ein Element am Ende der Warteschlange anzufügen. Wirft keine Ausnahme wenn das nicht klappt, sondern gibt dann einfach false zurück
  • E poll() – Holt das erste Element der Warteschlange und entfernt es. Wenn die Queue leer ist, gibt die Methode null zurück
  • E peek() – Holt das erste Element der Warteschlange, entfernt es aber nicht. Wenn die Queue leer ist, gibt die Methode null zurück
  • E element() – Holt das erste Element der Warteschlange, entfernt es aber nicht. Wenn die Queue leer ist, wirft die Methode eine NoSuchElementException

Mit dem Interface Queue wird eine Warteschlange (Ringpuffer) zur Verfügung gestellt.

Das Deque

Deque (sprich „deck“) steht für double ended queue

Man kann Elemente am Anfang und am Ende hinzufügen und entfernen

  • void addFirst(E e), void addLast(E e)
  • Iterator<E> descendingIterator()
  • E getFirst(), E getLast()
  • boolean offerFirst(E e), boolean offerLast(E e)
  • E peekFirst(), E peekLast()
  • E pollFirst(), E pollLast()
  • E removeFirst(), E removeLast()

Man kann ein Deque sowohl als Queue als auch als Stack verwenden. Insofern ist java.util.Stack überflüssig und kann durch ein Deque ersetzt werden.

Als Queue

  • Queue-Methode → Deque-Methode
  • add(e) → addLast(e)
  • offer(e) → offerLast(e)
  • remove() → removeFirst()
  • poll() → pollFirst()
  • element() → getFirst()
  • peek() → peekFirst()

Als Stack

  • Stack-Methode → Deque-Methode
  • push(e) → addFirst(e)
  • pop() → removeFirst()
  • peek() → peekFirst()

Copyright © 2025 Thomas Smits