11.11 Listen 

Die Schnittstelle List, die in den Klassen ArrayList und LinkedList implementiert ist, erlaubt sequenziellen Zugriff auf die gespeicherten Elemente. Beide 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.

ArrayList speichert Elemente in einem Array (so wie es Vector macht). LinkedList dagegen speichert die Elemente in einer verketteten Liste und realisiert die Verkettung mit einem eigenen Hilfsobjekt für jedes Listenelement. Somit 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 nur einfach 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 Listenelemente 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.11.1 AbstractList 

Da AbstractList viele wichtige Methoden für die beiden Listen-Klassen vorgibt, beginnen wir hier mit der Beschreibung. Dies erspart uns doppeltes Aufzählen bei den speziellen Unterklassen. 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 hashCode() Liefert den Hashcode der Liste.

int indexOf( Object o ) Liefert die Position des ersten Vorkommens für o oder -1, wenn kein Listenelement 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 Listenelement 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 (soweit sie den passenden Ausschnitt betreffen).

11.11.2 Optionale Methoden 

Rufen wir eine optionale Methode auf, die von der Unterklasse nicht implementiert wird, erhalten wir eine UnsupportedOperationException. Die vielen Optional-Anmerkungen erschrecken zunächst und lassen die Klassen beziehungsweise Schnittstellen irgendwie unzuverlässig oder nutzlos wirken. Die konkreten Standard-Implementierungen der Collection-API bieten diese Operationen jedoch vollständig an; nur die Spezial-Wrapper für nur Lese-Container lassen sie weg. Das Konzept der optionalen Operationen ist umstritten, wenn Methoden zur Laufzeit eine Exception auslösen. Besser wären natürlich separate kleinere Schnittstellen, die nur die Leseoperationen enthalten und zur Übersetzungszeit überprüft werden können; doch dann würde es noch deutlich mehr Schnittstellen im Util-Paket geben.

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.12   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.11.3 ArrayList 

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 protected¹  . 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.13   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.11.4 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().

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