Vector, ArrayList und die anderen Collection - ein HowTo

[bygones]

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 hineintun kann und wieder rausholen kann. Das Interface Collection ist das oberste Elemente der Hierarchie und bietet keine direten 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 Klasse zeigen. Der Beitrag gewährt keinen Anspruch auf Vollständigkeit und ist angeleht an dem Tutorial von Sun (hier).

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

Wir betrachten hier nur die Zweige Set und List, da sie wohl die meiste Benutzung haben.

Zuerst betrachten wir uns das Interface List.

1. List

An ordered collection (also known as a sequence). The user of this interface has precise control over where in the list each element is inserted. The user can access elements by their integer index (position in the list), and search for elements in the list.
Eine geordnete Collection (bekannt auch als Sequenz). Der User hat die genau Kontrolle darueber, an welcher Stelle in der Liste jedes Element eingefuegt werden soll. Der User kann ueber 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 erlaube doppelte Elemente.

i) 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 Element kann schnell und einfach per for schleife realisiert werden

for(int i = 0; i < vector.size(); 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 sie 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 ArrayRest größer des Index jeweils um eine Stelle nach links kopiert werden, um die entstandenen Lücke zufüllen.
Diese beiden Operationen sind natürlich zeitspielig.

ii) 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

iii) 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.

Verherrend aber bei einer LinkedList wäre es über einen Index auf die Element zuzugreifen. Da sie intern kein Array ist und man somit ein Element nicht per Index holen kann, würde bei jedem Indexzugriff vom Startelement über alle Element sich gehangelt, bis der gegeben Index erreicht wurde. Das führt zu einer enormen Laufzeit für einen Zugriff.
Somit ist ein direktes "Rausholen" eines Elements nicht möglich, nur das Iterieren über die Liste ist zu empfehlen

Iterator iter = linkedList.iterator();
while(iter.hasNext()) {
  System.out.println(iter.next());
}

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

2. Set

A collection that contains no duplicate elements.
Eine Collection die keine Duplikate enthaelt

Somit ist ein Set eine einfache Collection ohne doppelte Elemente.

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 da 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 Element vorhanden sind, die Reihenfolge wie die Elemente in der Tasche liegen egal für das Programm ist, so ist ein Set zu nehmen.

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

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

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