16.2 Die Collection des Typs List
16.2.1 Abstrakte Eigenschaften
Eine Collection vom Typ List
ist eine geordnete Menge von Objekten, auf die entweder sequenziell
oder über ihren Index (ihre Position in der Liste) zugegriffen
werden kann. Wie bei Arrays hat das erste Element den Index 0 und
das letzte den Index size() - 1.
Es ist möglich, an einer beliebigen Stelle der Liste ein Element
einzufügen oder zu löschen. Die weiter hinten stehenden
Elemente werden dann entsprechend nach rechts bzw. links verschoben.
Des Weiteren gibt es Methoden, um Elemente in der Liste zu suchen.
Das Interface List
ist direkt aus Collection
abgeleitet und erbt somit dessen Methoden. Zusätzlich gibt es
einige neue Methoden, die zum wahlfreien Zugriff auf die Elemente
benötigt werden. Um Elemente in die Liste einzufügen, können
die Methoden add
und addAll
verwendet werden:
void add(int index, Object element)
boolean add(Object o)
boolean addAll(Collection c)
boolean addAll(int index, Collection c)
|
java.util.List |
Mit add
wird ein einfaches Element in die Liste eingefügt. Wenn die Methode
mit einem einzelnen Object
als Parameter aufgerufen wird, hängt sie das Element an das Ende
der Liste an. Wird zusätzlich der Index angegeben, so wird das
Element an der spezifizierten Position eingefügt und alle übrigen
Elemente werden um eine Position nach rechts geschoben. Mit addAll
kann eine komplette Collection in die Liste eingefügt werden.
Auch hier können die Elemente wahlweise an das Ende angehängt
oder an einer beliebigen Stelle in der Liste eingefügt werden.
Das Löschen von Elementen kann mit den Methoden remove,
removeAll
und retainAll
erfolgen:
Object remove(int index)
boolean remove(Object o)
boolean removeAll(Collection c)
boolean retainAll(Collection c)
|
java.util.List |
An remove
kann dabei wahlweise der Index des zu löschenden Objekts oder
das Objekt selbst übergeben werden. Mit removeAll
werden alle Elemente gelöscht, die auch in der als Argument übergebenen
Collection enthalten sind, und retainAll
löscht alle Elemente außer den in der Argument-Collection
enthaltenen.
16.2.2 Implementierungen
Das Interface List
wird seit dem JDK 1.2 von verschiedenen Klassen implementiert:
- Die Klasse AbstractList
ist eine abstrakte Basisklasse, bei der alle optionalen Methoden die
Ausnahme UnsupportedOperationException
auslösen und diverse obligatorische Methoden als abstract
deklariert wurden. Sie dient als Basisklasse für eigene List-Implementierungen.
- Die Klasse LinkedList
realisiert eine Liste, deren Elemente als doppelt verkettete lineare
Liste gehalten werden. Ihre Einfüge- und Löschoperationen
sind im Prinzip (viele Elemente vorausgesetzt) performanter als die
der ArrayList.
Der wahlfreie Zugriff ist dagegen normalerweise langsamer.
- Die Klasse ArrayList
implementiert die Liste als Array von Elementen, das bei Bedarf vergrößert
wird. Hier ist der wahlfreie Zugriff schneller, aber bei großen
Elementzahlen kann das Einfügen und Löschen länger
dauern als bei einer LinkedList.
- Aus Gründen der Vereinheitlichung implementiert seit dem
JDK 1.2 auch die Klasse Vector
das List-Interface.
Neben den bereits in Abschnitt 15.2
erwähnten Methoden besitzt ein 1.2-Vector
also auch die entsprechenden Methoden des List-Interface.
Soll im eigenen Programm eine Liste verwendet werden, stellt sich
die Frage, welche der genannten Implementierungen dafür am besten
geeignet ist. Während die Klasse AbstractList
nur als Basisklasse eigener Listenklassen sinnvoll verwendet werden
kann, ist die Entscheidung für eine der drei übrigen Klassen
von den Spezifika der jeweiligen Anwendung abhängig. Bleibt die
Liste klein, wird hauptsächlich wahlfrei darauf zugegriffen;
überwiegen die lesenden gegenüber den schreibenden Zugriffen
deutlich, so liefert die ArrayList
die besten Ergebnisse. Ist die Liste dagegen sehr groß und werden
häufig Einfügungen und Löschungen vorgenommen, ist
wahrscheinlich die LinkedList
die bessere Wahl. Wird von mehreren Threads gleichzeitig auf die Liste
zugegriffen, kann die Klasse Vector
verwendet werden, denn ihre Methoden sind bereits weitgehend als synchronized
deklariert. Weitere Untersuchungen zur Performance der Listentypen
sind in Abschnitt 52.2.3
zu finden.
Das folgende Beispiel zeigt das Anlegen und Bearbeiten zweier unterschiedlicher
Listen:
001 /* Listing1601.java */
002
003 import java.util.*;
004
005 public class Listing1601
006 {
007 static void fillList(List list)
008 {
009 for (int i = 0; i < 10; ++i) {
010 list.add("" + i);
011 }
012 list.remove(3);
013 list.remove("5");
014 }
015
016 static void printList(List list)
017 {
018 for (int i = 0; i < list.size(); ++i) {
019 System.out.println((String)list.get(i));
020 }
021 System.out.println("---");
022 }
023
024 public static void main(String[] args)
025 {
026 //Erzeugen der LinkedList
027 LinkedList list1 = new LinkedList();
028 fillList(list1);
029 printList(list1);
030 //Erzeugen der ArrayList
031 ArrayList list2 = new ArrayList();
032 fillList(list2);
033 printList(list2);
034 //Test von removeAll
035 list2.remove("0");
036 list1.removeAll(list2);
037 printList(list1);
038 }
039 }
|
Listing1601.java |
Listing 16.1: Anlegen und Bearbeiten zweier Listen
Hierbei wird zunächst je eine Liste des Typs LinkedList
und ArrayList
angelegt; beide werden durch Aufruf von fillList
identisch gefüllt. Der Parameter list
hat den Typ List
und akzeptiert damit beliebige Objekte, die dieses Interface implementieren.
Tatsächlich spielt es für fillList
keine Rolle, welche konkrete Listenklasse verwendet wurde, und die
nachfolgenden Ausgabemethoden geben jeweils genau dasselbe aus:
0
1
2
4
6
7
8
9
---
0
1
2
4
6
7
8
9
---
0
---
Anschließend wird aus list2
das Element »0« entfernt und aus list1
werden alle Elemente gelöscht, die noch in list2
enthalten sind. Nach dem Aufruf von removeAll
verbleibt also nur noch das (zu diesem Zeitpunkt nicht mehr in list2
enthaltene) Element »0« in list1
und es wird durch den folgenden Aufruf von printList
ausgegeben.
