Collections (Java)

Vector, ArrayList und die anderen Collection

Zitat:
A collection represents a group of objects, known as its elements. Some collections allow duplicate elements and others do not. Some are ordered and others unordered.
(Eine Collection stellt eine Gruppe von Objekten dar, bekannt als ihr Element. Einige Collections erlauben doppelte Elemente, andere nicht. Manche sind geordnet, manche ungeordnet)

Eine Collection ist somit vorstellbar als eine Tasche in die man mehrere Objekte hinein tun kann und wieder rausholen kann. Das Interface Collection ist das oberste Elemente der Hierarchie und bietet keine direkten Implementationen an.

Um eine solche Tasche nutzen zu können muss man sich erst überlegen, welche Art von Tasche man überhaupt haben will. Wie oben erwähnt gibt es verschiedene Arten davon (mit Dupilkaten, ohne Duplikaten, geordnet oder nicht geordnet). Alle haben aber gemeinsam, dass sie eine Tasche zum aufbewahren von Objekten sind.

Dieser Beitrag soll eine kleine Übersicht über diese enorme Hierarchie darstellen und die Vor- bzw. Nachteile einiger Collection Klassen zeigen. Der Beitrag gewährt keinen Anspruch auf Vollständigkeit und ist angeleht an dem Tutorial zu Collections von Oracle (früher Sun).

Betrachten wir zuerst einmal die Hierarchie der Interfaces die uns Oracle bietet:

List

Eine geordnete Collection (bekannt auch als Sequenz). Der Benutzer hat die genau Kontrolle darüber, an welcher Stelle in der Liste jedes Element eingefügt werden soll. 
Der Benutzer kann über den Index (die Position in der Liste) auf die Elemente zugreifen und nach Elementen in der Liste suchen.

Die drei bekanntesten Implementationen des List Interfaces sind Vector, ArrayList und LinkedList. Alle diese Elemente werden im Folgenden betrachtet. Sie bieten eine geordnete Struktur (geordnet im Sinne von Ordnung nach der Einfügereihenfolge) und erlauben doppelte Elemente.

Vector

Der Vector ist im Grunde nichts anderes als ein Array mit ein paar Methoden außenrum. Intern werden die Objekte in einem Array gespeichert. Aufgrund des Arrays ist der Vector schnell beim indexbasierten Zugriff auf seine Elemente. D.h. das Iterieren über die Elemente kann schnell und einfach per for-Schleife realisiert werden.

for(int i = 0, j = vector.size(); i < j; i++) {
   System.out.println(vector.get(i));
}

Des Weiteren sind alle Methoden des Vectors synchronisiert, d.h. geschützt vor Multihread-Zugriffen. Der Nachteil macht sich aber bei "normalen" Programmen bemerkbar, die nur einen Thread besitzen, da das Synchronisieren in diesem Falle mehr nachteilig ist, da unnötig. Weiterhin hat der Vector Probleme, falls oft Elemente hinzugefügt bzw. gelöscht werden.
Da der Vector ein Array ist, tritt irgendwann die Situation auf, dass der Array voll ist. Wird nun ein weiteres Element hinzufügt, muss intern ein neuer, größerer Array angelegt werden und alle Elemente des alten Arrays hinüberkopiert werden.
Beim Löschen eines Index muss der Array-Rest größer des Index jeweils um eine Stelle nach links kopiert werden, um die entstandene Lücke zu füllen.
Diese beiden Operationen benötigen natürlich "etwas Zeit".

ArrayList

Die ArrayList ist im Grunde nichts anderes als ein nichtsynchronisierter Vector. D.h. alle Eigenschaften außer den synchronisierten Methoden, die oben aufgeführt sind, treffen auch auf die ArrayList zu.

Allgemeine Regel
Wenn man eine indexbasierte Collection haben will, muss man sich überlegen, ob man mit einem oder mehreren Threads arbeitet: 

Ein Thread ===> ArrayList (99% der Fälle)

Mehrere Threads ===> Vector bzw. eine synchronisierte List ( Collections#syncronizedList(java.util.List) )

LinkedList

Die LinkedList unterscheidet sich von den anderen beiden oben genannten. Sie ist intern kein Array sondern eine doppelt verkette Liste. D.h. die Objekte in der Collection haben jeweils einen Verweis auf ihren Vorgänger, sowie ihren Nachfolger.
Der große Vorteil der Liste ist es, dass Einfüge- bzw. Löschoperationen extrem günstig sind, da hier nur ein paar Zeiger verschoben werden müssen, nie aber Elemente kopiert oder verschoben werden.

Verheerend wäre es aber, bei einer LinkedList über einen Index auf die Elemente zuzugreifen. Da LinkedList intern kein Array benutzt und man somit ein Element nicht per Index holen kann, würde bei jedem Indexzugriff vom Startelement über alle Element sich gehangelt, bis der gegebene Index erreicht wurde. Das führt zu einer enormen Laufzeit für einen Zugriff. Somit ist ein direktes "Herausholen" eines Elements nicht möglich, nur das Iterieren über die Liste ist zu empfehlen. <code=java> Iterator iter = linkedList.iterator(); while(iter.hasNext()) {

 System.out.println(iter.next());

} </code=java>

Allgemeine Regel
LinkedList bieten den Vorteil, dass sie bei vielen Einfüge- bzw Löschoperationen effizienter ist, benötigt aber mehr Speicher (wg. zusätzlicher Referenzen) und keinen direkten Zugriff auf ein Element.

Set

Ein Set speichert Objekte, ohne dabei Duplikate zuzulassen.

Das bekannteste Set ist das HashSet, in dem die Objekte je nach ihrem HashCode eingefügt werden. D.h. Java stellt sich intern die Objekte anders dar, als wir sie erzeugen, um sie effizient in das Set einfügen zu können. Das hat zur Folge, dass die Einfügereihenfolge nicht der Reihenfolge entspricht, wenn wir es wieder auslesen.

Auch hier ist kein indexbasierter Zugriff möglich, da auch hier wieder intern kein Array zum Speichern verwendet wird. Der Zugriff erfolgt wie bei der LinkedList über den Iterator.

Allgemeine Regel
Wenn ihr eine Tasche haben wollt, in der ihr sicher gehen wollt, dass keine doppelten Elemente vorhanden sind, die Reihenfolge der Elemente, die in der Tasche liegen egal für das Programm ist, so ist ein Set zu verwenden.

Ein Spezialfall des Sets ist das sog. SortedSet, mit seinem Vertreter TreeSet. Hier werden die Objekte nach ihrer natürlichen Ordnung gespeichert. Die zu speichernden Elemente müssen das Interface Comparable implementieren, so dass eine solche Ordnung gegeben ist.

Allgemeine Regel
Will man die Vorzüge eines Sets nutzen und zusätzlich die Element geordnet haben, so ist ein TreeSet zu verwenden.

Es gibt noch einige Collection mehr, doch sind die eben vorgestellten Klassen die meist benutzten. Man kann mehr über die Collection Klassen in der API finden und in dem oben verlinkten Tutorial.

Map

Klassen, die das Interface Map implementieren gehören nicht zu den Collections. Dennoch möchten wir sie hier im Rahmen dieses Artikels vorstellen.

Maps speichern ebenso, wie die Klassen aus dem oben vorgestellten Collection Framework Objekte. Eine Map speichert aber pro Zeile nicht nur ein Objekt, sondern ein Schlüssel-Wert-Paar.
Dieses Schlüssel-Wert-Paar besteht aus zwei Objekten: Einem Schlüssel und einem Wert, dem eigentlichen Nutzobjekt, welches in der Map mit dem Schlüssel eindeutig identifiziert werden kann. So sind auch Duplikate möglich, wenn verschiedene Schlüssel eingesetzt werden.

Dieser Beitrag wird derzeit noch bearbeitet. Der Text ist deshalb unvollständig und kann Fehler oder ungeprüfte Aussagen enthalten.

Weiterführendes Material

• Oracle - The Collections Framework

-- bygones 29.06.2005 | L-ectron-X (Update 30.08.2013)