Professionelle Bücher. Auch für Einsteiger.

Inhaltsverzeichnis
Vorwort
1 Java ist auch eine Sprache
2 Sprachbeschreibung
3 Klassen und Objekte
4 Der Umgang mit Zeichenketten
5 Mathematisches
6 Eigene Klassen schreiben
7 Angewandte Objektorientierung
8 Exceptions
9 Die Funktionsbibliothek
10 Threads und nebenläufige Programmierung
11 Raum und Zeit
12 Datenstrukturen und Algorithmen
13 Dateien und Datenströme
14 Die eXtensible Markup Language (XML)
15 Grafische Oberflächen mit Swing
16 Grafikprogrammierung
17 Netzwerkprogrammierung
18 Verteilte Programmierung mit RMI und Web-Services
19 JavaServer Pages und Servlets
20 Applets
21 Midlets und die Java ME
22 Datenbankmanagement mit JDBC
23 Reflection und Annotationen
24 Logging und Monitoring
25 Sicherheitskonzepte
26 Java Native Interface (JNI)
27 Dienstprogramme für die Java-Umgebung
A Die Begleit-DVD
Stichwort
Download: - ZIP, ca. 12,5 MB
Buch bestellen
Ihre Meinung?
<< zurück | Galileo Computing / <openbook> /Java-Insel | vor >>
Java ist auch eine Insel von Christian Ullenboom Programmieren mit der Java Standard Edition Version 6
Java ist auch eine Insel 7., aktualisierte Auflage geb., mit DVD (November 2007) 1.492 S., 49,90 Euro Galileo Computing ISBN 978-3-8362-1146-8 |
| 12 Datenstrukturen und Algorithmen
|  | 12.1 Datenstrukturen und die Collection-API
|  |  | 12.1.1 Designprinzip mit Schnittstellen, abstrakten Klassen, konkreten Klassen
|  |  | 12.1.2 Die Basis-Schnittstellen Collection und Map
|  |  | 12.1.3 Das erste Programm mit Container-Klassen
|  |  | 12.1.4 Die Schnittstelle Collection
|  |  | 12.1.5 Schnittstellen, die Collection erweitern, und Map
|  |  | 12.1.6 Konkrete Container-Klassen
|  |  | 12.1.7 Welche Klasse nehmen?
|  |  | 12.1.8 Generische Datentypen in der Collection-API
|  |  | 12.1.9 Die Schnittstelle Iterable und das erweiterte for
|  | 12.2 Mit einem Iterator durch die Daten wandern
|  |  | 12.2.1 Die Schnittstellen Enumeration und Iterator
|  |  | 12.2.2 Iteratoren von Sammlungen und das erweiterte for
|  |  | 12.2.3 Fail-Fast Iterator und die ConcurrentModificationException
|  | 12.3 Listen
|  |  | 12.3.1 ArrayList oder LinkedList? Speicherung im Feld oder in einer verketteten Liste
|  |  | 12.3.2 Die Schnittstelle List
|  |  | 12.3.3 ArrayList
|  |  | 12.3.4 LinkedList
|  |  | 12.3.5 Der Feld-Adapter Arrays.asList()
|  |  | 12.3.6 toArray() von Collection verstehen – die Gefahr einer Falle erkennen
|  |  | 12.3.7 Primitive Elemente in den Collection-Datenstrukturen
|  | 12.4 Vergleichen von Objekten
|  |  | 12.4.1 Die Schnittstellen Comparator und Comparable
|  |  | 12.4.2 Algorithmen mit Such- und Sortiermöglichkeiten
|  |  | 12.4.3 Den größten und kleinsten Wert einer Collection finden
|  |  | 12.4.4 Sortieren
|  | 12.5 Mengen (Sets)
|  |  | 12.5.1 HashSet
|  |  | 12.5.2 TreeSet – die Menge durch Bäume
|  |  | 12.5.3 LinkedHashSet
|  | 12.6 Stack (Kellerspeicher, Stapel)
|  |  | 12.6.1 Die Methoden von Stack
|  |  | 12.6.2 Ein Stack ist ein Vector – aha!
|  | 12.7 Queues (Schlangen) und Deques
|  |  | 12.7.1 Die Schnittstelle Queue
|  |  | 12.7.2 Blockierende Queues und Prioritätswarteschlangen
|  |  | 12.7.3 Deque-Klassen
|  | 12.8 Assoziative Speicher
|  |  | 12.8.1 Die Klassen HashMap und TreeMap
|  |  | 12.8.2 Einfügen und Abfragen der Datenstruktur
|  |  | 12.8.3 Die Bedeutung von equals(), hashCode() und IdentityHashMap
|  |  | 12.8.4 Elemente im Assoziativspeicher müssen unveränderbar bleiben
|  |  | 12.8.5 Aufzählungen und Sichten auf den Assoziativspeicher
|  |  | 12.8.6 Der Gleichheitstest, Hash-Wert und Klon einer Hash-Tabelle
|  |  | 12.8.7 Die Arbeitsweise einer Hash-Tabelle
|  |  | 12.8.8 Multi-Maps
|  | 12.9 Die Properties-Klasse
|  |  | 12.9.1 Properties setzen und lesen
|  |  | 12.9.2 Properties verketten
|  |  | 12.9.3 Eigenschaften ausgeben
|  |  | 12.9.4 Hierarchische Eigenschaften
|  |  | 12.9.5 Properties speichern
|  |  | 12.9.6 Klassenbeziehungen: Properties und Hashtable
|  | 12.10 Algorithmen in Collections
|  |  | 12.10.1 Listenoperationen: Ersetzen, Kopieren, Füllen, Umdrehen, Rotieren, Durchmischen
|  |  | 12.10.2 Mit der Halbierungssuche nach Elementen fahnden
|  |  | 12.10.3 Nicht-änderbare Datenstrukturen
|  |  | 12.10.4 Häufigkeit eines Elements
|  |  | 12.10.5 nCopies()
|  |  | 12.10.6 Singletons
|  | 12.11 Synchronisation der Datenstrukturen
|  |  | 12.11.1 Lock-Free-Algorithmen aus java.util.concurrent
|  |  | 12.11.2 Wrapper zur Synchronisation
|  |  | 12.11.3 CopyOnWriteArrayList und CopyOnWriteArraySet
|  | 12.12 Die Klasse BitSet für Bitmengen
|  |  | 12.12.1 Ein BitSet anlegen, füllen und erfragen
|  |  | 12.12.2 Mengenorientierte Operationen
|  |  | 12.12.3 Funktionsübersicht
|  |  | 12.12.4 Primzahlen in einem BitSet verwalten
## 12.3 Listen Eine Liste steht für eine Sequenz von Daten, bei der die Elemente eine feste Reihenfolge besitzen. Die Schnittstelle java.util.List schreibt Verhalten vor, die alle konkreten Listen implementieren müssen. Interessante Realisierungen der List-Schnittstelle sind: java.util.ArrayList. Liste auf der Basis eines Feldes. java.util.Vector. Synchronisierte Liste seit Java 1.0, die der ArrayList wich. java.util.LinkedList. Liste durch verkettete Elemente. java.util.concurrent.CopyOnWriteArrayList. Schnelle Liste optimal für häufige nebenläufige Lesezugriffe. Die Funktionen zum Zugriff über die gemeinsame Schnittstelle List sind immer die gleichen. So ermöglicht jede Liste einen Punktzugriff über get(index) oder kann alle gespeicherten Elemente sequenziell über einen Iterator geben. Die Realisierungen einer Liste unterschieden sich in Eigenschaften wie der Performance oder der Möglichkeit der sicheren Nebenläufigkeit. Da in allen Datenstrukturen jedes Exemplar einer von Object abgeleiteten Klasse Platz findet, sind die Listen grundsätzlich nicht auf bestimmte Datentypen fixiert, doch Generics spezifizieren diese Typen genauer. ### 12.3.1 ArrayList oder LinkedList? Speicherung im Feld oder in einer verketteten Liste Eine ArrayList (das Gleiche gilt für Vector) speichert Elemente in einem internen Array. 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 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 einer ArrayList bedeutet dies viel Arbeit, es sei denn, das Element kann am Ende gelöscht oder – bei ausreichender Puffergröße – eingefügt werden. Soll ein Element nicht am Ende eingefügt oder gelöscht werden, müssen alle nachfolgenden Listen-Elemente verschoben werden. Bei einer ArrayList kann die Größe des internen Feldes zu klein werden. Dann bleibt der Laufzeitumgebung nichts anderes übrig, als ein neues größeres Feld-Objekt anzulegen und alle Elemente zu kopieren. ### 12.3.2 Die Schnittstelle List Die Schnittstelle List schreibt das allgemeine Verhalten für Listen vor. Viele Methoden kennen wir schon vom Collection-Interface, und zwar deshalb, weil List die Schnittstelle Collection erweitert. Hinzugekommen sind Funktionen, die einen Bezug zur Position eines Elements haben – Mengen, die auch Collection implementieren, nutzen keinen Index. Hier klicken, um das Bild zu vergrößern
    interface java.util.List<E>
    extends Collection<E>
boolean add( E o ) Fügt das Element am Ende der Liste an. Optionale Operation. void add( int index, E element ) Fügt ein Objekt an der angegebenen Stelle in die Liste ein. Optionale Operation. boolean addAll( int index, Collection<? extends E> c ) Fügt alle Elemente der Collection an der angegebenen Stelle in die Liste ein. Optionale Operation. void clear() Löscht alle Elemente aus der Liste. Optionale Operation. boolean contains( Object o ) Liefert true, wenn das Element o in der Liste ist. Den Vergleich übernimmt equals(), und es ist kein Referenz-Vergleich. boolean containsAll( Collection<?> c ) Liefert true, wenn alle Elemente der Sammlung c in der aktuellen Liste sind. E 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 – also per equals() und nicht per Referenz – übereinstimmt. Leider gibt es keine Methode, um ab einer bestimmten Stelle weiterzusuchen, so wie sie die Klasse String bietet. Dafür lässt sich jedoch eine Teilliste einsetzen, die subList() bildet – eine Funktion, die später in der Aufzählung folgt. boolean isEmpty() true, wenn die Liste leer ist. Iterator<E> iterator() Liefert den Iterator. 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 und liefert –1, wenn kein Listen-Element inhaltlich mit o übereinstimmt. ListIterator<E> 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<E> listIterator( int index ) Liefert einen Listen-Iterator, der die Liste ab der Position index durchläuft. E remove( int index ) Entfernt das Element an der Position index aus der Liste. boolean remove( Object o ) Entfernt das erste Objekt in der Liste, das equals()-gleich mit o ist. Liefert true, wenn ein Element entfernt wurde. Optionale Operation. boolean removeAll( Collection<?> c ) Löscht in der eigenen Liste die Elemente aus c. Optionale Operation. boolean retainAll( Collection<?> c ) Optional. Entfernt alle Objekte aus der Liste, die nicht in der Collection c vorkommen. E set( int index, E element ) Ersetzt das Element an der Stelle index durch element. Optionale Operation. List<E> 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). boolean equals( Object o ) Vergleicht die Liste mit einer anderen Liste. Zwei Listen-Objekte sind gleich, wenn ihre Elemente paarweise gleich sind. int hashCode() Liefert den Hashcode der Liste. Was List der Collection hinzufügt, sind also die Index-basierten Funktionen add(int index, E element), addAll(int index, Collection<? extends E> c), get(int index), indexOf(Object o), lastIndexOf(Object o), listIterator(), listIterator(int index), remove(int index), set(int index, E element) und subList(int fromIndex, int toIndex). #### Beispiel mit den wichtigsten List-Funktionen Das folgende Programm zeigt die wichtigsten Methoden der List-Schnittstelle. Listing 12.6 com/tutego/insel/util/list/ListDemo.java. main()
    List<Object> list1 = new ArrayList<Object>();

    // Hinzufügen

    list1.add( "b" );
    list1.add( 0, "a" );
    list1.add( "i" );

    List<String> list2 = new ArrayList<String>();
    list2.add( "I" );

    list1.add( list2 );
    list1.addAll( 3, list2 );
    list1.add( "a" );

    System.out.println( list1 );        // [a, b, i, I, [I], a]

    // Abfrage-und Suchfunktionen

    boolean b = list1.contains( "a" );
    System.out.println( b );            // true

    b = list1.containsAll( list2 );
    System.out.println( b );            // true

    list2.add( "I2" );
    b = list1.containsAll( list2 );
    System.out.println( b );            // false
    System.out.println( list1 );        // [a, b, i, I, [I, I2], a]

    Object o = list1.get( 1 );
    System.out.println( o );            // b

    int i = list1.indexOf( "i" );
    System.out.println( i );            // 2

    i = list1.lastIndexOf( "a" );
    System.out.println( i );            // 5

    b = list1.isEmpty();
    System.out.println( b );            // false

    b = new ArrayList().isEmpty();
    System.out.println( b );            // true

    // Teilfelder bilden

    Object array[] = list1.toArray();
    System.out.println( array[3] );     // "I"

    list2 = new ArrayList<String>();    // Menge mit a bilden
    list2.add( "a" );

    List<Object> list3 = new ArrayList<Object>();
    list3.addAll( list1 );              // tb enthält Elemente aus a
    list3.retainAll( list2 );           // Schnitt bilden
    System.out.println( list3 );        // [a, a]

    // Löschen und verändern

        list1.remove( 4 );
        System.out.println( list1 );    // [a, b, i, I, a]

    list1.remove( "I" );
    System.out.println( list1 );        // [a, b, i, a]

    list1.set( 1, new ArrayList() );
    System.out.println( list1 );        // [a, [], i, a]
    System.out.println( list1.size() ); // 4

    list1.clear();
    System.out.println( list1 );        // []
    System.out.println( list1.size() ); // 0
#### 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. Hier klicken, um das Bild zu vergrößern
    interface ListIterator<E>
    extends Iterator<E>
boolean hasPrevious(), boolean hasNext() Liefert true, wenn es ein vorhergehendes/nachfolgendes Element gibt. E previous(), E 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( E o ) Optional. Fügt ein neues Objekt in die Liste ein. void set( E o ) Optional. Setzt das Element, das next() oder previous() als letztes zurückgaben. Listing 12.7 com/tutego/insel/util/list/ListIteratorDemo.java, main()
    List<Object> list = new ArrayList<Object>();
    Collections.addAll( list, "b", "c", "d" );

    ListIterator<Object> it = list.listIterator();

    it.add( "a" );                     // Vorne anfügen
    System.out.println( list );        // [s, a, b, c, d]

    it.next();
    it.remove();
    System.out.println( list );        // [a, c, d]

    it.next();
    it.set( "i" );
    System.out.println( list );        // [a, i, d]
    it = list.listIterator( list.size()/2 – 1 );
    it.add( "l" );
    it.add( "v" );
    System.out.println( list );        // [l, v, a, i, d]

    it = list.listIterator( 1 );

    it.previous();                     // Eine Stelle nach vorne
    it.remove();
    System.out.println( list );        // [v, a, i, d]
#### Nach Elementen suchen und ihre Position ausgeben Ein zweites Beispiel zeigt die Möglichkeit von index() und subList(), um alle Positionen eines Elements in einer Liste zu finden. Die Code-Kompression gewinnt sicherlich keinen Preis. Arrays.asList() erzeugt aus einer Aufzählung eine Liste. Listing 12.8 com/tutego/insel/util/list/IndexOfSubList.java, main()
    List<Integer> list = Arrays.asList( 1, 3, 4, 1 );
    Integer o = 1;

    for ( int i = list.indexOf( o ), j = –1;
          i > j;
          j = i, i += list.subList( i + 1, list.size() ).indexOf( o ) + 1 )
    {
      System.out.println( i );
    }
#### Kopieren, Ausschneiden und Einfügen Die Listen-Klassen implementieren clone() und erzeugen eine flache Kopie der Liste. Um einen Bereich zu löschen, nutzen wir subList(from, to).clear(). Die subList()-Technik deckt gleich noch einige andere Operationen ab, für die es keine speziellen Range-Varianten gibt, zum Beispiel indexOf(), also die Suche in einem Teil der Liste. Die zum Löschen nahe liegende Funktion removeRange(int, int) kann nicht (direkt) eingesetzt werden, da sie protected [In AbstractList ist removeRange() gültig mit einem ListIterator implementiert, also nicht abstrakt. Die API-Dokumentation begründet das damit, dass removeRange() nicht zur offiziellen Schnittstelle von Listen gehört, sondern für die Autoren neuer Listenimplementierungen gedacht ist. ] ist. Das lässt sich aber schnell mit
    List list = new ArrayList() {
      @Override public void removeRange( int fromIndex, int toIndex ) {
        super.removeRange( fromIndex, toIndex );
      }
    };
beheben. Ein Beispiel zeigt den Aufbau einer Liste, die Kürzung und den Einsatz vom List-Iterator: Listing 12.9 com/tutego/insel/util/list/CutCopyPasteList.java, main()
    List<String> a = new ArrayList<String>(
        Arrays.asList( "0 1 2 3 4 5 6 7 8 9".split( " " ) ));
    a.subList( a.size() / 2 – 3, a.size() / 2 + 3 ).clear();

    System.out.println( a );                   // [0, 1, 8, 9]

    // Iterator besorgen und Reihe ausgeben

    ListIterator<String> it = a.listIterator( a.size() );

    while ( it.hasPrevious() )
      System.out.print( it.previous() + " " ); // 9 8 1 0

    // Datenstruktur kürzen und klonen

    a.subList( 2, a.size() ).clear();

    System.out.printf( "%n%s", a );            // [0, 1]
### 12.3.3 ArrayList Jedes Exemplar der Klasse ArrayList vertritt ein Array mit variabler Länge. Der Zugriff auf die Elemente erfolgt effizient über Indizes, was ArrayList über die Implementierung der Markierungsschnittstelle RandomAccess andeutet. #### Eine ArrayList erzeugen Um ein ArrayList-Objekt zu erzeugen, existieren drei Konstruktoren:
    class java.util.ArrayList<E>
    extends AbstractList<E>
    implements List<E>, 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<? extends E> c ) Kopiert alle Elemente der Collection c in das neue ArrayList-Objekt. Hier klicken, um das Bild zu vergrößern
Beispiel Erstelle eine Liste list, und fülle die Datenstruktur mit einer Zeichenkette und einer Ganzzahl:
    List<Object> list = new ArrayList<Object>();
    list.add( "ICE 924 Hildegard von Bingen" );
    list.add( 23 );  // oder list.add(new Integer(23)) ohne Boxing
#### Die interne Arbeitsweise von ArrayList und Vector Die Klassen ArrayList und Vector verwalteten zwei Größen: 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(); 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. Das kostet Zeit. Schon aus diesem Grund sollte der Konstruktor ArrayList(int initialCapacity)/Vector(int initialCapacity) gewählt werden, weil 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 Feldes 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, großen Feldern jedoch 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 Feldes 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. 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. [Zudem können null-Referenzen ganz normal als Elemente eines Vektors auftreten, bei den anderen Datenstrukturen gibt es Einschränkungen. ] Vorsicht ist bei newSize=0 geboten, denn setSize(0) bewirkt das Gleiche wie removeAllElements(). ### 12.3.4 LinkedList Die Klasse LinkedList realisiert die Schnittstelle List als verkettete Liste und bildet die Elemente nicht auf ein Feld ab. Die Implementierung realisiert die LinkedList als doppelt verkettete Liste, in der jedes Element – die Ränder lassen wir außen vor – einen Vorgänger und Nachfolger hat. (Einfach verkettete Listen haben nur einen Nachfolger, was die Navigation in beide Richtungen schwierig macht.) Eine LinkedList hat neben den gegebenen Operationen aus der Schnittstelle List weitere Hilfsmethoden: Dabei handelt es sich um die Funktionen addFirst(), addLast(), getFirst(), getLast(), removeFirst() und removeLast(). Die implementierten Schnittstellen Queue und Deque sind nicht ganz unschuldig an diesen neuen Funktionen. Hier klicken, um das Bild zu vergrößern
    class java.util.LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, Serializable
LinkedList() Eine neue leere Liste. LinkedList( Collection<? extends E> c ) Kopiert alle Elemente der Collection c in die neue verkettete Liste. ### 12.3.5 Der Feld-Adapter Arrays.asList() Arrays von Objektreferenzen und dynamische Datenstrukturen passen nicht so richtig zusammen, obwohl sie schon häufiger zusammen benötigt werden. Die Java-Bibliothek bietet mit der Methode Arrays.asList() an, ein existierendes Feld als java.util.List zu behandeln. Der Parametertyp ist ein Vararg – was ja intern auf ein Feld abgebildet wird –, so dass sich asList() auf zwei Arten verwenden lässt: Arrays.asList(array). Die Variable array ist eine Referenz auf ein Feld, und das Ergebnis ist eine Liste, die die gleichen Elemente wie das Feld enthält. Arrays.asList(e1, e2, e3). Die Elemente e1, e2, e3 sind Elemente der Liste. Das Entwurfsmuster, das die Java-Bibliothek bei der Methode anwendet, nennt sich Adapter. Es löst das Problem, die Schnittstellen eines Typs auf eine andere Schnittstelle eines anderen Typs anzupassen.
Beispiel Wie viele Integer(1)-Objekte gibt es im Feld ints? Listing 12.10 com/tutego/insel/util/list/AsListDemo.java, Ausschnitt
    Integer[] ints = { 1, 2, 1, 2, 3 };
    List<Integer> intList = Arrays.asList( ints );
    System.out.println( Collections.frequency( intList, 1 ));     // 2
Boxing macht sich in diesem Beispiel natürlich sehr gut.
Die Rückgabe von asList() ist keine bekannte Klasse wie ArrayList oder LinkedList, sondern irgendetwas Internes, was die Klasse Arrays als java.util.List herausgibt. Diese Liste ist nur eine andere Sicht auf das Feld. Modifikationsfunktionen wie remove() oder add() führen zu einer UnsupportedOperationException – im Hintergrund steht immer noch das Feld – da kann nicht plötzlich ein Element gelöscht oder hinten angehängt werden. Listen-Methoden wie get(index) oder set(index,element) funktionieren aber und gehen direkt auf das Feld.
Beispiel Um dennoch Elemente löschen und einfügen zu können, lässt sich die Rückgabeliste von asList() in eine neue spezielle LinkedList oder ArrayList kopieren:
Listing 12.11 com/tutego/insel/util/list/AsListDemo.java, Ausschnitt
    List<String> list = new ArrayList<String>(
                         Arrays.asList( "Purzelchen",
                         "Häschen" ) );
    list.remove( 0 );
    System.out.println( list );    // [Häschen]
    class java.util.Arrays
public static <T> List<T> asList( T... a ) Ermöglicht mit der Schnittstelle einer Liste Zugriff auf ein Feld. Die variablen Argumente sind sehr praktisch. ### 12.3.6 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.
Beispiel Eine Anwendung von toArray(), die Punkte in ein Feld kopiert:
    ArrayList<Point> list = new ArrayList<Point>();
    list.add( new Point(13, 43) );
    list.add( new Point(9, 4) );
    Object[] points = list.toArray();
Wir erhalten nun ein Feld mit Referenzen auf Point-Objekte, können jedoch 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 = list.toArray();             // Vorsicht!
Jetzt wird der Compiler einen Fehler melden, weil 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[]) list.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, sich also 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 Methode toArray() zurück. Weil die auszulesende Datenstruktur alles Mögliche enthalten kann, muss der Typ der Elemente also 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 keinen allgemeineren (umfassenderen) Typ als Object 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 bei dem Array-Objekt selbst jedoch 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.
Beispiel Wir fordern von der toArray()-Funktion ein Feld vom Typ Point:
    ArrayList<Point> list = new ArrayList<Point>();
    list.add( new Point(13,43) );
    list.add( new Point(9,4) );
    Point[] points = (Point[]) list.toArray( new Point[0] );
Jetzt bekommen wir die Listen-Elemente in ein Array kopiert, und der Typ des Arrays ist Point[] – passend zu den aktuell vorhandenen Listen-Elementen. 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 übergebene 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() ein allgemeines Object ist, muss letztendlich noch die Konvertierung in ein passendes Array stattfinden. Ist das übergebene Array so groß, dass es alle Elemente der Collection aufnehmen kann, kopiert toArray() die Elemente aus der Collection in das Feld. Oft wird dort aber 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(). Dennoch gibt die Java-Bibliothek zwei völlig getrennte Implementierungen an, da toArray() einfacher und effizienter zu implementieren ist. ### 12.3.7 Primitive Elemente in den Collection-Datenstrukturen Jede Datenstruktur der Collection-API akzeptiert, auch wenn sie generisch verwendet wird, nur Objekte. Primitive Datentypen nehmen die Sammlungen nicht auf, was zur Konsequenz hat, dass Wrapper-Objekte nötig sind. (Über das Boxing fügt Java 5 scheinbar primitive Elemente ein, doch in Wahrheit sind es Wrapper-Objekte.) Für performante Anwendungen ist es sinnvoll, eine Klasse für den speziellen Datentyp einzusetzen. Statt so etwas selbst zu programmieren, kann der Entwickler sich an zwei Implementierungen halten: GNU Trove (http://trove4j.sourceforge.net/) Apache Commons Primitives (http://jakarta.apache.org/commons/primitives/) ### Ihr Kommentar Wie hat Ihnen das <openbook> gefallen? Wir freuen uns immer über Ihre freundlichen und kritischen Rückmeldungen.
Name |
E-Mail |
Ihr Kommentar |
<< zurück | <top> | vor >>

Copyright © Galileo Press 2008
Für Ihren privaten Gebrauch dürfen Sie die Online-Version natürlich ausdrucken. Ansonsten unterliegt das <openbook> denselben Bestimmungen, wie die gebundene Ausgabe: Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Alle Rechte vorbehalten einschließlich der Vervielfältigung, Übersetzung, Mikroverfilmung sowie Einspeicherung und Verarbeitung in elektronischen Systemen.

[Galileo Computing]
Galileo Press, Rheinwerkallee 4, 53227 Bonn, Tel.: 0228.42150.0, Fax 0228.42150.77, info@galileo-press.de