11.3 Listen

Die Klassen ArrayList, LinkedList und Vector implementieren die Schnittstelle List und erlauben sequenziellen Zugriff auf die gespeicherten Elemente. Die genannten Klassen leiten sich von der abstrakten Klasse AbstractList ab, die schon grundlegende Funktionalität für Listen liefert. Eine Liste gibt über iterator() einen speziellen ListEnumerator zurück. LinkedList besitzt die zusätzliche Oberklasse AbstractSequentialList.

Speicherung als Feld oder verkettete Liste

ArrayList speichert Elemente in einem Array (so wie es auch Vector macht). LinkedList dagegen speichert die Elemente in einer verketteten Liste und realisiert die Verkettung mit einem eigenen Hilfsobjekt für jedes Listen-Element. Es ergeben sich Einsatzgebiete, die einmal für LinkedList und einmal für ArrayList sprechen. Da ArrayList intern ein Array benutzt, ist der Zugriff auf ein spezielles Element über die Position in der Liste sehr schnell. Eine LinkedList muss aufwändiger durchsucht werden, und dies kostet seine Zeit. Die verkettete Liste ist aber deutlich im Vorteil, wenn Elemente mitten in der Liste gelöscht oder eingefügt werden; hier muss einfach nur die Verkettung der Hilfsobjekte an einer Stelle verändert werden. Bei einem ArrayList-Objekt als Container bedeutet dies viel Arbeit, es sei denn, das Element muss am Ende gelöscht oder eingefügt werden. Zum einen müssen alle nachfolgenden Listen-Elemente beim Einfügen und Löschen im Array verschoben werden, zum anderen kann beim Einfügen das verwendete Array-Objekt zu klein werden. Dann bleibt, wie beim Vector, nichts anderes übrig, als ein neues Array-Objekt anzulegen und alle Elemente zu kopieren.

11.3.1 AbstractList

Da AbstractList viele wichtige Methoden für die beiden Listen-Klassen vorgibt, beginnen wir hier mit der Beschreibung. Dies erspart uns ein doppeltes Aufzählen bei den Unterklassen ArrayList und LinkedList. Einige Methoden kennen wir schon vom Collection-Interface, und zwar deshalb, da AbstractCollection die Schnittstelle Collection implementiert und AbstractList die Methoden aus AbstractCollection erbt.

abstract class java.util.AbstractList
extends AbstractCollection
implements List

void add( int index, Object element ) Optional. Fügt ein Objekt an der angegebenen Stelle in die Liste ein.

boolean add( Object o ) Optional. Fügt das Element am Ende der Liste an.

boolean addAll( int index, Collection c ) Optional. Fügt alle Elemente der Collection an der angegebenen Stelle in die Liste ein.

void clear() Optional. Löscht alle Elemente aus der Liste.

boolean equals( Object o ) Vergleicht die Liste mit dem Objekt. Zwei Listen-Objekte sind gleich, wenn ihre Elemente paarweise gleich sind.

abstract Object get( int index ) Wird das Element an dieser angegebenen Stelle der Liste liefern.

int indexOf( Object o ) Liefert die Position des ersten Vorkommens für o oder -1, wenn kein Listen-Element mit o inhaltlich übereinstimmt. Leider gibt es hier keine Methode, um ab einer bestimmten Stelle weiterzusuchen, so wie sie die Klasse String bietet. Dann lässt sich jedoch eine Teilliste einsetzen.

Iterator iterator() Liefert den Iterator. Überschreibt die Methode in AbstractCollection, obwohl wir auch listIterator() für die spezielle Liste haben. Die Methode ruft aber listIterator() auf und gibt ein ListIterator-Objekt zurück.

int lastIndexOf( Object o ) Sucht von hinten in der Liste nach dem ersten Vorkommen von o, liefert -1, wenn kein Listen-Element inhaltlich mit o übereinstimmt.

ListIterator listIterator() Liefert einen Listen-Iterator für die ganze Liste. Ein Listen-Iterator bietet gegenüber dem allgemeinen Iterator für Container zusätzliche Operationen.

ListIterator listIterator( int index ) Liefert einen Listen-Iterator, der die Liste ab der Position index durchläuft.

Object remove( int index ) Entfernt das Element an Position index aus der Liste.

protected void removeRange( int fromIndex, int toIndex ) Löscht den Teil der Liste von Position fromIndex bis toIndex. Das Element an der Stelle fromIndex wird mit gelöscht und das bei toIndex nicht. Da diese Methode protected ist, lässt sie sich nur in Unterklassen benutzen. Der Autor der Unterklasse kann dann entscheiden, ob er die Methode mit einer öffentlichen Version überschreibt oder diese Operation unter einem anderen Methodennamen öffentlich anbieten will.

Object set( int index, Object element ) Optional. Ersetzt das Element an der Stelle index durch element.

List subList( int fromIndex, int toIndex ) Liefert den Ausschnitt dieser Liste von Position fromIndex (einschließlich) bis toIndex (nicht mit dabei). Die zurückgelieferte Liste stellt eine Sicht auf einen Ausschnitt der Originalliste dar. Änderungen an der Teilliste wirken sich auf die ganze Liste aus und umgekehrt (so weit sie den passenden Ausschnitt betreffen).

int hashCode() Liefert den Hashcode der Liste.

ListIterator

ListIterator ist eine Erweiterung von Iterator. Diese Schnittstelle fügt noch Methoden hinzu, damit an der aktuellen Stelle auch Elemente eingefügt werden können. Mit einem ListIterator lässt sich rückwärts laufen und auf das vorhergehende Element zugreifen.

public interface ListIterator
extends Iterator

boolean hasPrevious(), boolean hasNext(), Liefert true, wenn es ein vorhergehendes/nachfolgendes Element gibt.

Object previous(), Object next(), Liefert das vorangehende/nächste Element der Liste und NoSuchElementException, wenn es das Element nicht gibt.

int previousIndex(), int nextIndex() Liefert den Index des vorhergehenden/nachfolgenden Elements. Geht previousIndex() vor die Liste, so liefert die Funktion -1, geht nextIndex() hinter die Liste, liefert die Funktion die Länge der gesamten Liste.

void remove() Optional. Entfernt das letzte von next() oder previous() zurückgegebene Element.

void add( Object o ) Optional. Fügt ein neues Objekt in die Liste ein.

void set( Object o ) Optional. Ersetzt das von next() oder previous() gegebene Objekt.

11.3.2 Beispiel mit List-Methoden

Das nachfolgende Programm zeigt die wichtigsten Methoden und wie sie auf einem Exemplar einer konkreten Unterklasse zu AbstractList, wie ArrayList oder LinkedList, aussehen.

Listing 11.3 AbstractListDemo.java

import java.util.*;
public class AbstractListDemo
{
  public static void main( String args[] )
  {
//    List a = new LinkedList();
    List a = new ArrayList();
    // Hinzufügen
    a.add( "b" );
    a.add( 0, "a" );
    a.add( "i" );
    List ta = new ArrayList();
    ta.add( "I" );
    a.add( ta );
    a.addAll( 3, ta );
    a.add( "a" );
    System.out.println( a );  // [a, b, i, I, [I], a]
    // Abfrage- und Suchfunktionen
    boolean b = a.contains( "a" );
    System.out.println( b );  // true
    b = a.containsAll( ta );
    System.out.println( b );  // true
    ta.add( "I2" );
    b = a.containsAll( ta );
    System.out.println( b );  // false
    System.out.println( a );  // [a, b, i, I, [I, I2], a]
    Object o = a.get( 1 );
    System.out.println( o );  // b
    int i = a.indexOf( "i" );
    System.out.println( i );  // 2
    i = a.lastIndexOf( "a" );
    System.out.println( i );  // 5
    b = a.isEmpty();
    System.out.println( b );  // false
    b = new ArrayList().isEmpty();
    System.out.println( b );  // true
    // Teilfelder bilden
    Object array[] = a.toArray();
    System.out.println( array[3] ); // "I"
    ta = new ArrayList();     // Menge mit a bilden
    ta.add( "a" );
    List tb = new ArrayList();
    tb.addAll( a );           // tb enthält Elemente aus a
    tb.retainAll( ta );       // Schnitt bilden
    System.out.println( tb ); // [a, a]
    // Iteratoren besorgen
    ListIterator it = a.listIterator();
    it.add( "s" );    // Vorne ersetzen
    System.out.println( a );  // [s, a, b, i, I, [I, I2], a]
    it.next();
    it.remove();
    System.out.println( a );  // [s, b, i, [I, I2], a]
    it.next();
    it.set( "i" );
    System.out.println( a );  // [s, i, i, I, [I, I2], a]
    it = a.listIterator( a.size()/2 - 1 );
    it.add( "l" );
    it.add( "v" );
    System.out.println( a );  // [s, i, l, v, i, I, [I, I2], a]
    // Löschen und verändern
    it = a.listIterator( a.size() );
    it.previous();        // Liste rückwärts
    it.remove();
    System.out.println( a );  // [s, i, l, v, i, I, [I, I2]]
    a.remove( 6 );
    System.out.println( a );  // [s, i, l, v, i, I]
    a.remove( "v" );
    System.out.println( a );  // [s, i, l, i, I]
    a.set( 1, new ArrayList() );
    System.out.println( a );  // [s, [], l, i, I]
    System.out.println( a.size() );  // 5
    a.clear();
    System.out.println( a );  // []
    System.out.println( a.size() );  // 0
  }
}

11.3.3 ArrayList

Jedes Exemplar der Klasse ArrayList vertritt ein Array mit variabler Länge. Der Zugriff auf die Elemente erfolgt über Indizes, zwar nicht über den Operator [], aber doch über Methoden, die einen Index als Parameter annehmen. Da in einer ArrayList jedes Exemplar einer von Object abgeleiteten Klasse Platz findet, ist eine ArrayList nicht auf bestimmte Datentypen fixiert. Dies ist ein Problem, denn beim Zugriff auf Elemente der Liste muss der Entwickler wissen, welchen Typ die Vektorelemente haben werden. Die Datentypen müssen also später wieder mit expliziten Typanpassungen angepasst werden. Dasselbe Problem haben wir bei anderen Datenstrukturen auch. Bei Java 1.5 wird die Technik des Unboxing das unnötig machen.

Hier klicken, um das Bild zu Vergrößern

Eine ArrayList erzeugen

Um ein ArrayList-Objekt zu erzeugen, existieren drei Konstruktoren.

class java.util.ArrayList
extends AbstractList
implements List, RandomAccess, Cloneable, Serializable

ArrayList() Eine leere Liste mit einer Anfangskapazität von zehn Elementen wird angelegt. Werden mehr als zehn Elemente eingefügt, muss die Liste sich vergrößern.

ArrayList( int initialCapacity ) Eine Liste mit initialCapacity freien Elementen wird angelegt.

ArrayList( Collection c ) Kopiert alle Elemente der Collection c in das neue ArrayList-Objekt.

List v = new ArrayList();
v.add ( "ICE 924 Hildegard von Bingen" );
v.add ( new Integer(23) );

Primitive Elemente in den Collection-Datenstrukturen

Die eingefügte Zahl durch das Integer-Objekt macht deutlich, dass als Elemente nur Objekte akzeptiert werden und keine primitiven Datentypen. Eine Unterklasse könnte jedoch ArrayList erweitern und die Daten für den Benutzer unsichtbar in den Objekten kapseln. Für performante Anwendungen ist es jedoch sinnvoll, eine komplette eigene Klasse für den speziellen Datentyp einzusetzen. So etwas muss nicht mehr selbst programmiert werden - die Lösung ist etwas GNU Trove: high performance collections for Java, unter http://trove4j.sourceforge.net/.

Kopieren, Ausschneiden und Einfügen

Eine wichtige Methode, die ArrayList von AbstractList überschreibt, ist clone(). Damit lässt sich leicht eine Kopie der Liste erzeugen. Es entsteht so allerdings nur eine flache Kopie der Datenstruktur. Ein besonderer Witz ist removeRange(int, int). Die Methode wird zwar überschrieben, sie ist aber immer noch protected3¹. Die API-Dokumentation beschreibt dazu, dass removeRange() nicht zur offiziellen Schnittstelle von Listen gehört, sondern für die Autoren neuer Listenimplementierungen gedacht ist. Beispielsweise kann removeRange() für ArrayList-Objekte deutlich effizienter implementiert werden als in der Klasse AbstractList. Das offizielle Idiom für die Funktionalität von removeRange() ist subList(from, to).clear(). Die subList()-Technik erschlägt gleich noch ein paar andere Operationen, für die es keine speziellen Range-Varianten gibt, zum Beispiel indexOf(), also die Suche in einem Teil der Liste.

Listing 11.4 ArrayListDemo.java

import java.util.*;
public class ArrayListDemo
{
  public static void main( String args[] )
  {
    ArrayList a = new ArrayList();
    for ( int i = 1; i <= 20; i++ )
      a.add( "" + i );
    a.subList( a.size()/2-3, a.size()/2+3 ).clear();
    System.out.println( a );
    // Iterator besorgen und Reihe ausgeben
    ListIterator it = a.listIterator( a.size() );
    while( it.hasPrevious() )
      System.out.print( it.previous() + " " );
    System.out.println();
    // Datenstruktur kürzen und klonen
    a.subList( 4, a.size() ).clear();
    System.out.println( a );
  }
}

Zusätzlich sehen wir hier noch einen ganz normalen ListIterator im Einsatz. Dann ist die Ausgabe Folgende:

[1, 2, 3, 4, 5, 6, 7, 14, 15, 16, 17, 18, 19, 20]
20 19 18 17 16 15 14 7 6 5 4 3 2 1
[1, 2, 3, 4]

11.3.4 asList() und die »echten« Listen

Arrays von Objektreferenzen und dynamische Datenstrukturen passen nicht so richtig zusammen. Die Java-Bibliothek bietet mit der Methode asList() der Hilfsklasse Arrays an, die Felder als Listen anzusprechen.

Bei den uns bekannten Unterklassen ArrayList und LinkedList stellt sich die Frage, ob asList() damit etwas zu tun hat. Die Antwort ist nein. Arrays implementiert eine eigene interne Listen-Klasse, die mit ArrayList oder LinkedList von der Implementierung her nichts gemeinsam hat, bis auf die Tatsache, dass sie die Schnittstelle List implementiert, obwohl die interne Klasse auch ArrayList heißt. Die Unterscheidung ist wichtig, da ArrayList aus Arrays eine Mini-Implementierung des Vorbilds ist. Daher lässt sich mit ihr auch nicht alles machen, was spätestens dann klar wird, wenn über einen Iterator Elemente in der Liste gelöscht werden sollen. Dann folgt eine UnsupportedOperationException(), die aus AbstractList kommt. Die kleine ArrayList-Implementierung in Arrays erweitert nämlich AbstractList und implementiert nur das Notwendigste. Damit wir jetzt dennoch Elemente löschen können, müssen wir die einfache Liste in eine spezielle LinkedList oder ArrayList umbauen. Das sieht dann wie folgt aus:

List l = new ArrayList( Arrays.asList( new String[]{"Purzelchen", "Hässchen"} ) );
Iterator i = l.iterator();
i.next();
i.remove();

11.3.5 toArray() von Collection verstehen - die Gefahr einer Falle erkennen

Die toArray()-Methode aus der Schnittstelle Collection gibt laut Definition ein Array von Objekten zurück. Es ist wichtig zu verstehen, welchen Typ die Einträge und das Array selbst haben. Eine Implementierung der Collection-Schnittstelle ist ArrayList.

ArrayList l = new ArrayList();
l.add( new Point(13,43) );
l.add( new Point(9,4) );
Object points[] = l.toArray();

Wir erhalten nun ein Feld mit Referenzen auf Point-Objekte. Doch wir können zum Beispiel nicht einfach points[1].x schreiben, um auf das Attribut des Point-Exemplars zuzugreifen, denn das Array points hat den deklarierten Elementtyp Object. Es fehlt die explizite Typumwandlung, und erst ((Point)points[1]).x ist korrekt. Doch spontan kommen wir sicherlich auf die Idee, einfach den Typ des Arrays auf Point zu ändern. In dem Array befinden sich ja nur Referenzen auf Point-Exemplare.

Point points[] = l.toArray();            // Vorsicht!

Jetzt wird der Compiler einen Fehler melden, da der Rückgabewert von toArray() ein Object[] ist. Spontan reparieren wir dies, indem wir eine Typumwandlung auf ein Point-Array an die rechte Seite setzen.

Point points[] = (Point[])l.toArray();   // Gefährlich!

Jetzt haben wir zur Übersetzungszeit kein Problem mehr, aber zur Laufzeit wird es immer knallen, auch wenn sich im Array tatsächlich nur Point-Objekte befinden.

Diesen Programmierfehler müssen wir verstehen. Was wir falsch gemacht haben, ist einfach: Wir haben den Typ des Arrays mit den Typen der Array-Elemente durcheinander gebracht. Einem Array von Objekt-Referenzen können wir alles zuweisen.

Object os[] = new Object[3];
os[0] = new Point();
os[1] = "Trecker fahr'n";
os[2] = new Date();

Wir merken, dass der Typ des Arrays Object[] ist, und die Array-Elemente sind ebenfalls vom Typ Object. Hinter dem new-Operator, der das Array-Objekt erzeugt, steht der gemeinsame Obertyp für zulässige Array-Elemente. Bei Object[]-Arrays dürfen die Elemente Referenzen für beliebige Objekte sein. Klar ist, dass ein Array nur Objektreferenzen aufnehmen kann, die mit dem Typ für das Array selbst kompatibel sind, also sich auf Exemplare der angegebenen Klasse beziehen oder auf Exemplare von Unterklassen dieser Klasse.

/* 1 */  Object os[] = new Point[3];
/* 2 */  os[0] = new Point();
/* 3 */  os[1] = new Date();           // !!
/* 4 */  os[2] = "Trecker fahr'n";     // !!

Zeile 3 und 4 sind vom Compiler erlaubt, führen aber zur Laufzeit zu einer java.lang.ArrayStoreException.

Kommen wir wieder zurück zur Methode toArray(). Da die auszulesende Datenstruktur alles Mögliche enthalten kann, muss also der Typ der Elemente Object sein. Wir haben gerade festgestellt, dass der Elementtyp des Array-Objekts, das die Methode toArray() als Ergebnis liefert, mindestens so umfassend sein muss. Da es einen allgemeineren (umfassenderen) Typ als Object nicht gibt, ist auch der Typ des Arrays Object[]. Dies muss so sein, auch wenn die Elemente einer Datenstruktur im Einzelfall einen spezielleren Typ haben. Einer allgemein gültigen Implementierung von toArray() bleibt gar nichts anderes übrig, als das Array vom Typ Object[] und die Elemente vom Typ Object zu erzeugen.

public Object[] toArray() {
  Object[] objs = new Object[size()];
  Iterator it = iterator();
  for (int i = 0; i < objs.length; i++) {
    objs[i] = it.next();
  }
  return objs;
}

Wenn sich auch die Elemente wieder auf einen spezielleren Typ konvertieren lassen, ist das jedoch bei dem Array-Objekt selbst nicht der Fall. Ein Array-Objekt mit Elementen vom Typ X ist nicht automatisch auch selbst vom Typ X[], sondern von einem Typ Y[], wobei Y eine (echte) Oberklasse von X ist.

Die Lösung für das Problem

Bevor wir nun eine Schleife mit einer Typumwandlung für jedes einzelne Array-Element schreiben oder eine Typumwandlung bei jedem Zugriff auf die Elemente vornehmen, sollten wir einen Blick auf die zweite toArray()-Funktion werfen. Sie akzeptiert als Parameter ein vorgefertigtes Array für das Ergebnis. Mit dieser Funktion lässt sich erreichen, dass das Ergebnis-Array von einem spezielleren Typ als Object[] ist.

ArrayList l = new ArrayList();
l.add( new Point(13,43) );
l.add( new Point(9,4) );
Point points[] = (Point[])l.toArray( new Point[0]);

Jetzt bekommen wir die Listen-Elemente in ein Array kopiert, und der Typ des Arrays ist, passend zu den aktuell vorhandenen Listen-Elementen, Point[].

Spannend ist die Frage, wie so etwas funktionieren kann. Dazu verwendet die Methode toArray(Object[]) die Technik Reflection, um dynamisch ein Array vom gleichen Typ wie das Parameter-Array zu erzeugen. Wollten wir ein Array b vom Typ des Arrays a mit Platz für len Elemente anlegen, so schreiben wir

Object b[] = (Object[])Array.newInstance(
               a.getClass().getComponentType(), len );

Mit a.getClass().getComponentType() erhalten wir ein Class-Objekt für den Elementtyp des Arrays, zum Beispiel das Class-Objekt Point.class für die Klasse Point. a.getClass() allein liefert ein Class-Objekt für das Array a, etwa ein Objekt, das den Typ Point[] repräsentiert. Array.newInstance(), eine statische Methode von java.lang.reflect.Array, konstruiert ein neues Array mit dem Elementtyp aus dem Class-Objekt und der angegebenen Länge. Nichts anderes macht auch ein new X[len], nur dass hier der Elementtyp zur Übersetzungszeit festgelegt werden muss. Da der Rückgabewert von newInstance() Object ist, muss letztendlich noch die Konvertierung in ein passendes Array stattfinden.

Passt der Inhalt der Collection in das als Parameter übergebene Array, so wird er dort hineinkopiert. Oft wird aber dort ein new X[0] anzeigen, dass wir ein neu erzeugtes Array-Objekt wünschen. Im Übrigen entspricht natürlich toArray(new Object[0]) dem Aufruf von toArray(). Die Java-Bibliothek gibt aber zwei völlig getrennte Implementierungen an, da ja die parametrisierte Methode auch in das Parameter-Array kopieren kann. Das ist komisch, denn toArray() könnte toArray(new Object[0]) aufrufen oder effizienter auch toArray(new Object[size()]).

11.3.6 Die interne Arbeitsweise von ArrayList und Vector

Eine ArrayList beziehungsweise Vector muss zwei Größen verwalten: zum einen die Anzahl der gespeicherten Elemente nach außen, zum anderen die interne Größe des Felds. Ist die Kapazität des Felds größer als die Anzahl der Elemente, so können noch Elemente aufgenommen werden, ohne dass die Liste etwas unternehmen muss. Die Anzahl der Elemente in der Liste, die Größe, liefert die Methode size(), und die Kapazität des darunter liegenden Arrays liefert capacity().

Die Liste vergrößert sich automatisch, falls mehr Elemente aufgenommen werden als ursprünglich am Platz vorgesehen waren. Diese Operation heißt Resizing. Dabei spielt die Größe initialCapacity für effizientes Arbeiten eine wichtige Rolle. Sie sollte passend gewählt sein. Betrachten wir daher zunächst die Funktionsweise der Liste, falls das interne Array zu klein ist.

Wenn das Array zehn Elemente fasst, nun aber ein Elftes eingefügt werden soll, so muss das Laufzeitsystem einen neuen Speicherbereich reservieren und jedes Element des alten Felds in das neue kopieren. Dies kostet Zeit. Schon aus diesem Grund sollte der Konstruktor ArrayList(int initialCapacity)/Vector(int initialCapacity) gewählt werden, da dieser eine Initialgröße festsetzt. Das Wissen über unsere Daten hilft dann der Datenstruktur. Falls kein Wert voreingestellt wurde, so werden zehn Elemente angenommen. In vielen Fällen ist dieser Wert zu klein.

Nun haben wir zwar darüber gesprochen, dass ein neues Feld angelegt wird und die Elemente kopiert werden, haben aber nichts über die Größe des neuen Felds gesagt. Hier gibt es Strategien wie die »Verdopplungsmethode« beim Vector. Wird er vergrößert, so ist das neue Feld doppelt so groß wie das Alte. Dies ist eine Vorgehensweise, die für kleine und schnell wachsende Felder eine clevere Lösung darstellt, für große Felder aber schnell zum Verhängnis werden kann. Für den Fall, dass wir die Vergrößerung selbst bestimmen wollen, nutzen wir den Konstruktor Vector(int initialCapacity, int capacityIncrement), der die Verdopplung ausschaltet und eine fixe Vergrößerung befiehlt. Die ArrayList verdoppelt nicht, sie nimmt die neue Größe mal 1,5. Bei ihr gibt es leider auch den capacityIncrement im Konstruktor nicht.

Die Größe eines Felds

Die interne Größe des Arrays kann mit ensureCapacity() geändert werden. Ein Aufruf von ensureCapacity(int minimumCapacity) bewirkt, dass die Liste insgesamt mindestens minimumCapacity Elemente aufnehmen kann, ohne dass ein Resizing nötig wird. Ist die aktuelle Kapazität der Liste kleiner als minimumCapacity, so wird mehr Speicher angefordert. Der Vektor verkleinert die aktuelle Kapazität nicht, falls sie schon höher als minimumCapacity ist. Um aber auch diese Größe zu ändern und somit ein nicht mehr wachsendes Vektor-Array so groß wie nötig zu machen, gibt es, ähnlich wie beim String mit Leerzeichen, die Methode trimToSize(). Sie reduziert die Kapazität des Vektors auf die Anzahl der Elemente, die gerade in der Liste sind. Mit size() lässt sich die Anzahl der Elemente in der Liste erfragen. Sie gibt die wirkliche Anzahl der Elemente zurück.

Hier klicken, um das Bild zu Vergrößern

Bei der Klasse Vector lässt sich mit setSize(int newSize) auch die Größe der Liste verändern. Ist die neue Größe kleiner als die Alte, werden die Elemente am Ende des Vektors abgeschnitten. Ist newSize größer als die alte Größe, werden die neu angelegten Elemente mit null initialisiert.² Vorsicht ist bei newSize=0 geboten, denn setSize(0) bewirkt das Gleiche wie removeAllElements().

11.3.7 LinkedList

Eine verkettete Liste hat neben den normalen Funktionen aus AbstractList noch weitere Hilfsmethoden, um leicht einen Stack oder eine Schlange zu programmieren. Es handelt sich dabei um die Funktionen addFirst(), addLast(), getFirst(), getLast(), removeFirst() und removeLast().

11.3.8 Queue, die Schlange

Eine Queue arbeitet nach dem FIFO-Prinzip (First-In-First-Out) und unterscheidet sich von einem Stack durch den Zugriff auf die Elemente. Bei einer Queue werden die Elemente, die zuerst eingefügt wurden, zuerst herausgegeben, getreu dem Motto: »Wer zuerst kommt, malt zuerst.«

In der Klassenbibliothek von Java gibt es bisher keine extra Queue-Klasse, doch eine LinkedList bietet alle nötigen Methoden für eine Implementierung mit verketteten Listen an.

Listing 11.5 QueueTest.java, Teil 1

import java.util.LinkedList;
class Queue
{
  private LinkedList queue = new LinkedList();
  
  public void enqueue( Object newElement )
  {
    queue.addLast( newElement );
  }
  public synchronized Object dequeue()
  {
    return isEmpty() ? null : queue.removeFirst();
  }
  
  public boolean isEmpty()
  {
    return queue.isEmpty();
  }
}

dequeue() ist so implementiert, dass null als Endelement zurückgegeben wird. Eine Exception ist sicherlich eine gute, wenn nicht sogar bessere Lösung, denn das Dilemma ist, dass ja auch mit enqueue(null) die null, die als normales Element erlaubt ist, in die Liste kommt. Es bleibt als Übung den Lesern überlassen, die Klasse so zu erweitern, dass die dequeue()-Methode eine Exception auslöst.

Nun benötigen wir nur noch eine kleine Klasse zum Testen. Sie füllt die Schlange mit einigen Werten und liest sie dann wieder aus. Hier ist es wichtig, mit empty() nachzufragen, ob noch Elemente in der Queue sind. Es wurde eine Implementierung gewählt, die bei leerer Queue statt des nicht vorhandenen Elements einfach null liefert.

Listing 11.6 QueueTest.java, Teil 2

public class QueueTest
{
  public static void main( String args[] )
  {
    Queue queue = new Queue();
    
    queue.enqueue( "Fischers" );
    queue.enqueue( "Fritze" );
    queue.enqueue( "fischt" );
    queue.enqueue( "frische" );
    queue.enqueue( "Fische" );
    
    queue.dequeue();
    
    queue.enqueue( "Nein, es war Paul!" );
    
    while( !queue.isEmpty() )
      System.out.println( queue.dequeue() );
  }
}

¹ In AbstractList ist removeRange() gültig mit einem ListIterator implementiert.

² Zudem können null-Referenzen ganz normal als Elemente eines Vektors auftreten, bei den anderen Datenstrukturen gibt es Einschränkungen