Rheinwerk Computing < openbook >


 
Inhaltsverzeichnis
Materialien
Vorwort
1 Java ist auch eine Sprache
2 Imperative Sprachkonzepte
3 Klassen und Objekte
4 Arrays und ihre Anwendungen
5 Der Umgang mit Zeichenketten
6 Eigene Klassen schreiben
7 Objektorientierte Beziehungsfragen
8 Ausnahmen müssen sein
9 Geschachtelte Typen
10 Besondere Typen der Java SE
11 Generics<T>
12 Lambda-Ausdrücke und funktionale Programmierung
13 Architektur, Design und angewandte Objektorientierung
14 Java Platform Module System
15 Die Klassenbibliothek
16 Einführung in die nebenläufige Programmierung
17 Einführung in Datenstrukturen und Algorithmen
18 Einführung in grafische Oberflächen
19 Einführung in Dateien und Datenströme
20 Einführung ins Datenbankmanagement mit JDBC
21 Bits und Bytes, Mathematisches und Geld
22 Testen mit JUnit
23 Die Werkzeuge des JDK
A Java SE-Module und Paketübersicht
Stichwortverzeichnis


Download:

- Listings, ca. 2,7 MB


Buch bestellen
Ihre Meinung?



Spacer
<< zurück
Java ist auch eine Insel von Christian Ullenboom

Einführung, Ausbildung, Praxis
Buch: Java ist auch eine Insel


Java ist auch eine Insel

Pfeil 17 Einführung in Datenstrukturen und Algorithmen
Pfeil 17.1 Listen
Pfeil 17.1.1 Erstes Listen-Beispiel
Pfeil 17.1.2 Auswahlkriterium ArrayList oder LinkedList
Pfeil 17.1.3 Die Schnittstelle List
Pfeil 17.1.4 ArrayList
Pfeil 17.1.5 LinkedList
Pfeil 17.1.6 Der Array-Adapter Arrays.asList(…)
Pfeil 17.1.7 ListIterator *
Pfeil 17.1.8 toArray(…) von Collection verstehen – die Gefahr einer Falle erkennen
Pfeil 17.1.9 Primitive Elemente in Datenstrukturen verwalten
Pfeil 17.2 Mengen (Sets)
Pfeil 17.2.1 Ein erstes Mengen-Beispiel
Pfeil 17.2.2 Methoden der Schnittstelle Set
Pfeil 17.2.3 HashSet
Pfeil 17.2.4 TreeSet – die sortierte Menge
Pfeil 17.2.5 Die Schnittstellen NavigableSet und SortedSet
Pfeil 17.2.6 LinkedHashSet
Pfeil 17.3 Java Stream-API
Pfeil 17.3.1 Deklaratives Programmieren
Pfeil 17.3.2 Interne versus externe Iteration
Pfeil 17.3.3 Was ist ein Stream?
Pfeil 17.4 Einen Stream erzeugen
Pfeil 17.4.1 Parallele oder sequenzielle Streams
Pfeil 17.5 Terminale Operationen
Pfeil 17.5.1 Die Anzahl der Elemente
Pfeil 17.5.2 Und jetzt alle – forEachXXX(…)
Pfeil 17.5.3 Einzelne Elemente aus dem Strom holen
Pfeil 17.5.4 Existenz-Tests mit Prädikaten
Pfeil 17.5.5 Einen Strom auf sein kleinstes bzw. größtes Element reduzieren
Pfeil 17.5.6 Einen Strom mit eigenen Funktionen reduzieren
Pfeil 17.5.7 Ergebnisse in einen Container schreiben, Teil 1: collect(…)
Pfeil 17.5.8 Ergebnisse in einen Container schreiben, Teil 2: Collector und Collectors
Pfeil 17.5.9 Ergebnisse in einen Container schreiben, Teil 3: Gruppierungen
Pfeil 17.5.10 Stream-Elemente in ein Array oder einen Iterator übertragen
Pfeil 17.6 Intermediäre Operationen
Pfeil 17.6.1 Element-Vorschau
Pfeil 17.6.2 Filtern von Elementen
Pfeil 17.6.3 Statusbehaftete intermediäre Operationen
Pfeil 17.6.4 Präfix-Operation
Pfeil 17.6.5 Abbildungen
Pfeil 17.7 Zum Weiterlesen
 

Zum Seitenanfang

17    Einführung in Datenstrukturen und Algorithmen Zur vorigen ÜberschriftZur nächsten Überschrift

»Glück ist ganz einfach gute Gesundheit und ein schlechtes Gedächtnis.«

– Ernest Hemingway (1899–1961)

Algorithmen[ 251 ](Das Wort Algorithmus geht auf den Namen des persisch-arabischen Mathematikers Ibn Mûsâ Al-Chwârismî zurück, der im 9. Jahrhundert lebte. ) sind ein zentrales Thema der Informatik. Ihre Erforschung und Untersuchung nimmt dort einen bedeutenden Platz ein. Algorithmen operieren nur dann effektiv mit Daten, wenn diese geeignet strukturiert sind. Schon das Beispiel des Telefonbuchs zeigt, wie wichtig die Ordnung der Daten nach einem Schema ist. Die Suche nach einer Telefonnummer bei gegebenem Namen gelingt schnell, während die Suche nach einem Namen bei bekannter Telefonnummer ein mühseliges Unterfangen darstellt. Datenstrukturen und Algorithmen sind also eng miteinander verbunden, und die Wahl der richtigen Datenstruktur entscheidet über effiziente Laufzeiten; beide erfüllen allein nie ihren Zweck. Leider ist die Wahl der »richtigen« Datenstruktur nicht so einfach, wie es sich anhört, und eine Reihe von schwierigen Problemen in der Informatik ist wohl deswegen noch nicht gelöst, weil eine passende Datenorganisation bis jetzt nicht gefunden wurde.

Die wichtigsten Datenstrukturen, wie Listen, Mengen und Assoziativspeicher, sollen in diesem Kapitel vorgestellt werden.

 

Zum Seitenanfang

17.1    Listen Zur vorigen ÜberschriftZur nächsten Überschrift

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 Arrays

  • java.util.LinkedList: Liste durch verkettete Elemente

  • java.util.concurrent.CopyOnWriteArrayList: schnelle Liste, optimal für häufige nebenläufige Lesezugriffe

  • java.util.Vector: synchronisierte Liste seit Java 1.0, die der ArrayList wich. Die Klasse ist zwar nicht deprecated, sollte aber nicht mehr verwendet werden.

Die Methoden zum Zugriff über die gemeinsame Schnittstelle List sind immer die gleichen. So ermöglicht jede Liste einen Punktzugriff über get(index), und jede Liste kann alle gespeicherten Elemente sequenziell über einen Iterator herausgeben. Doch die Realisierungen einer Liste unterscheiden sich in Eigenschaften wie der Performance, dem Speicherplatzbedarf 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.

 

Zum Seitenanfang

17.1.1    Erstes Listen-Beispiel Zur vorigen ÜberschriftZur nächsten Überschrift

Listen haben die wichtige Eigenschaft, dass sie sich die Reihenfolge der eingefügten Elemente merken und dass Elemente auch doppelt vorkommen können. Wir wollen diese Listenfähigkeit für ein kleines Gedächtnisspiel nutzen. Der Anwender gibt Städte für eine Route vor, die sich das Programm in einer Liste merkt. Nach der Eingabe eines neuen Ziels auf der Route soll der Anwender alle Städte in der richtigen Reihenfolge wiedergeben. Hat er das geschafft, kommt eine neue Stadt hinzu. Im Prinzip ist das Spiel unendlich, doch da sich kein Mensch unendlich viele Städte in der Reihenfolge merken kann, wird es zu einer Falscheingabe kommen, die das Programm beendet.

Listing 17.1    src/main/java/com/tutego/insel/util/list/MemorizeYourRoadTripRoute.java

package com.tutego.insel.util.list;



import java.text.*;

import java.util.*;



public class MemorizeYourRoadTripRoute {

public static void main( String[] args ) {

List<String> cities = new ArrayList<>();



while ( true ) {

System.out.println( "Welche neue Stadt kommt hinzu?" );

String newCity = new Scanner( System.in ).nextLine();

cities.add( newCity );



System.out.printf( "Wie sieht die gesamte Route aus? (Tipp: %d %s)%n",

cities.size(), cities.size() == 1 ? "Stadt" : "Städte" );



for ( String city : cities ) {

String guess = new Scanner( System.in ).nextLine();

if ( ! city.equalsIgnoreCase( guess ) ) {

System.out.printf( "%s ist nicht richtig, %s wäre korrekt. Schade!%n",

guess, city );

return;

}

}

System.out.println( "Prima, alle Städte in der richtigen Reihenfolge!" );

}

}

}
 

Zum Seitenanfang

17.1.2    Auswahlkriterium ArrayList oder LinkedList Zur vorigen ÜberschriftZur nächsten Überschrift

Eine ArrayList (das Gleiche gilt für Vector) speichert Elemente in einem internen Array. Eine LinkedList hingegen speichert die Elemente in einer verketteten Liste und realisiert die Verkettung mit einem eigenen Hilfsobjekt für jedes Listenelement. Es gibt 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 aufwendiger 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 Listenelemente verschoben werden.

  • Bei einer ArrayList kann die Größe des internen Arrays zu klein werden. Dann bleibt der Laufzeitumgebung nichts anderes übrig, als ein neues, größeres Array-Objekt anzulegen und alle Elemente zu kopieren.

 

Zum Seitenanfang

17.1.3    Die Schnittstelle List Zur vorigen ÜberschriftZur nächsten Überschrift

Die Schnittstelle List schreibt das allgemeine Verhalten für Listen vor. Die allermeisten Methoden kennen wir schon vom Collection-Interface, und zwar deshalb, weil List die Schnittstelle Collection erweitert. Hinzugekommen sind Methoden, die einen Bezug zur Position eines Elements haben – Mengen, die auch Collection implementieren, kennen keinen Index.

Hinzufügen und Setzen von Elementen

Die add(…)-Methode fügt neue Elemente an die Liste an, wobei eine Position die Einfügestellen bestimmen kann. Die Methode addAll(…) fügt fremde Elemente einer anderen Sammlung in die Liste ein. set(…) setzt ein Element an eine bestimmte Stelle, überschreibt das ursprüngliche Element und verschiebt es auch nicht. Die Methode size() nennt die Anzahl der Elemente in der Datenstruktur:

Listing 17.2    src/main/java/com/tutego/insel/util/list/ListDemo.java. Ausschnitt

List<String> list1 = new ArrayList<>();

list1.add( "Eva" );

list1.add( 0, "Charisma" );

list1.add( "Pallas" );



List<String> list2 = Arrays.asList( "Tina", "Wilhelmine" );

list1.addAll( 3, list2 );

list1.add( "XXX" );

list1.set( 5, "Eva" );



System.out.println( list1 ); // [Charisma, Eva, Pallas, Tina, Wilhelmine, Eva]

System.out.println( list1.size() ); // 6

Positionsanfragen und Suchen

Ob die Sammlung leer ist, bestimmt isEmtpy(). Ein Element an einer speziellen Stelle erfragen kann get(int). Ob Elemente Teil der Sammlung sind, beantworten contains(…) und containsAll(…). Wie bei Strings liefern indexOf(…) und lastIndexOf(…) die Fundpositionen:

Listing 17.3    src/main/java/com/tutego/insel/util/list/ListDemo.java. Ausschnitt

boolean b = list1.contains( "Tina" );

System.out.println( b ); // true



b = list1.containsAll( Arrays.asList( "Tina", "Eva" ) );

System.out.println( b ); // true



Object o = list1.get( 1 );

System.out.println( o ); // Eva



int i = list1.indexOf( "Eva" );

System.out.println( i ); // 1



i = list1.lastIndexOf( "Eva" );

System.out.println( i ); // 5



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

Listen zu Arrays und neue Listen bilden

Von den Listen können Arrays abgeleitet werden. So lassen sich Schnittmengen bilden:

Listing 17.4    src/main/java/com/tutego/insel/util/list/ListDemo.java. Ausschnitt

String[] array = list1.toArray( new String[list1.size()] );

// alternativ: String[] array = list1.toArray( String[]::new );



System.out.println( array[3] ); // "Tina"



List<String> list3 = new LinkedList<>( list1 );

System.out.println( list3 ); // [Charisma, Eva, Pallas, Tina,

// Wilhelmine, Eva]

list3.retainAll( Arrays.asList( "Tina", "Eva" ) );

System.out.println( list3 ); // [Eva, Tina, Eva]

Löschen von Elementen

Außerdem gibt es Methoden zum Löschen von Elementen. Hier bietet die Liste überladene remove(…)-Methoden, removeIf(…) und removeAll(…). Den kürzesten Weg, alles aus der Liste zu löschen, bietet clear():

Listing 17.5    src/main/java/com/tutego/insel/util/list/ListDemo.java. Ausschnitt

System.out.println( list1 );     // [Charisma, Eva, Pallas, Tina, Wilhelmine, Eva]

list1.remove( 1 );

System.out.println( list1 ); // [Charisma, Pallas, Tina, Wilhelmine, Eva]



list1.remove( "Wilhelmine" );

System.out.println( list1 ); // [Charisma, Pallas, Tina, Eva]



list1.removeAll( Arrays.asList( "Pallas", "Eva" ) );

System.out.println( list1 ); // [Charisma, Tina]



list1.clear();

System.out.println( list1 ); // []
[»]  Hinweis

Die Methode remove(int) löscht ein Element an der gegebenen Stelle, remove(Object) sucht einmal nach einem equals-gleichen Objekt und löscht es dann, würde aber nicht nach anderen Vorkommen weitersuchen. removeIf(…) und removeAll(…) laufen immer komplett über die ganze Datenstruktur und schauen, ob ein Element dem Kriterium genügt, um es zu löschen, was mehrmals vorkommen kann.

[zB]  Beispiel

Lösche alle null-Referenzen und Weißraum-Strings aus der Liste:

List<String> list = new ArrayList<>();

Collections.addAll( list, "1", "", " ", "zwei", null, "Polizei" );

list.removeIf( e -> Objects.isNull( e ) || e.trim().isEmpty() );

System.out.println( list ); // [1, zwei, Polizei]

Zusammenfassung

Die Methoden der Schnittstelle List (inklusive der aus der erweiterten Schnittstelle Collection) sind:

interface java.util.List<E>

extends Collection<E>
  • boolean add(E o)

    Fügt das Element am Ende der Liste an. Eine optionale Operation.

  • void add(int index, E element)

    Fügt ein Objekt an der angegebenen Stelle in die Liste ein. Eine optionale Operation.

  • boolean addAll(int index, Collection<? extends E> c)

    Fügt alle Elemente der Collection an der angegebenen Stelle in die Liste ein. Eine optionale Operation.

  • void clear()

    Löscht alle Elemente aus der Liste. Eine 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.

  • static <E> List<E> copyOf (Collection<? extends E> coll)

    Erzeugt eine unmodifizierbare Kopie. Neu in Java 10.

  • E get(int index)

    Liefert das Element an der angegebenen Stelle der Liste.

  • int indexOf(Object o)

    Liefert die Position des ersten Vorkommens für o oder –1, wenn kein Listenelement mit o inhaltlich (also per equals(…) und nicht per Referenz) übereinstimmt. Leider gibt es keine Methode, die ab einer bestimmten Stelle weitersucht, so wie sie die Klasse String bietet. Dafür lässt sich jedoch eine Teilliste einsetzen, die subList(…) bildet – eine Methode, die später in der Aufzählung folgt.

  • boolean isEmpty()

    Liefert 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 Listenelement 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. Eine optionale Operation.

  • boolean removeAll(Collection<?> c)

    Löscht in der eigenen Liste die Elemente aus c. Eine optionale Operation.

  • default boolean removeIf(Predicate<? super E> filter)

    Entfernt alle Elemente aus der Liste, bei denen das Prädikat erfüllt ist.

  • boolean retainAll(Collection<?> c)

    Optional. Entfernt alle Objekte aus der Liste, die nicht in der Collection c vorkommen.

  • default void replaceAll(UnaryOperator<E> operator)

    Ruft auf jedem Element den Operator auf und schreibt das Ergebnis zurück.

  • E set(int index, E element)

    Ersetzt das Element an der Stelle index durch element. Eine 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 Ansicht eines Ausschnitts der Originalliste dar. Änderungen an der Teilliste wirken sich auf die ganze Liste aus und umgekehrt (soweit sie den passenden Ausschnitt betreffen).

  • default void sort(Comparator<? super E> c)

    Sortiert die Liste, entspricht Collections.sort(this, c).

  • boolean equals(Object o)

    Vergleicht die Liste mit einer anderen Liste. Zwei Listenobjekte sind gleich, wenn ihre Elemente paarweise gleich sind.

  • int hashCode()

    Liefert den Hashwert der Liste.

Was List der Collection hinzufügt, sind also die indexbasierten Methoden 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) und zudem die beiden Default-Methoden replaceAll(…) und sort(…).

[»]  Hinweis

Die remove(…)-Methode ist überschrieben und löscht

  • einmal ein Element, das mit equals(…) gesucht wird, und

  • mit remove(int) ein Element an der gegebenen Position.

Irritierend ist Folgendes:

List<Integer> list = new ArrayList<>( Arrays.asList( 9, 8, 1, 7 ) );

Integer index = 1;

list.remove( index );

System.out.println( list ); // [9, 8, 7]

Es wird remove(Object) aufgerufen, weil Object dem Argumenttyp Integer am ähnlichsten ist. Somit verschwindet das Element Integer.valueOf(1) aus der Liste. Ein Unboxing findet nicht statt. Das dürfte zu erwarten sein, und daher sind die Namensgebung index und der Objekttyp im Beispiel bewusst irreführend. Gemeint war natürlich:

list = new ArrayList<>( List.of( 9, 8, 1, 7 ) );

int realIndex = 1;

list.remove( realIndex );

System.out.println( list ); // [9, 1, 7]

Kopieren und Ausschneiden

Die Listen-Klassen implementieren clone() und erzeugen eine flache Kopie.

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.

[zB]  Beispiel

Baue eine Liste auf, kürze sie, und gib die Elemente rückwärts aus:

List<String> list = new ArrayList<>(

Arrays.asList( "0 1 2 3 4 5 6 7 8 9".split( " " ) ) );

list.subList( 2, list.size() - 2 ).clear();

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

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

it.hasPrevious(); )

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

subList(…) erzeugt wie viele andere Methoden der Collection-Datenstrukturen eine Ansicht auf die Liste, was bedeutet, dass Änderungen an dieser Teilliste zu Änderungen am Original führen. Das gilt auch für clear(), das dazu genutzt werden kann, einen Teilbereich der Originalliste zu löschen.

[»]  Hinweis

Die zum Löschen naheliegende Methode removeRange(int, int) kann nicht (direkt) eingesetzt werden, da sie protected[ 252 ](In AbstractList ist removeRange(int, int) 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 zum Beispiel wie folgt beheben:

List<gewünschterTyp> list = new ArrayList<gewünschterTyp>() {

@Override public void removeRange( int fromIndex, int toIndex ) {

super.removeRange( fromIndex, toIndex );

}

};
 

Zum Seitenanfang

17.1.4    ArrayList Zur vorigen ÜberschriftZur nächsten Überschrift

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 sich die Liste vergrößern.

  • ArrayList(int initialCapacity)

    Eine Liste mit der internen Größe von initialCapacity-vielen Elementen wird angelegt.

  • ArrayList(Collection<? extends E> c)

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

Die interne Arbeitsweise von ArrayList und Vector *

Die Klassen ArrayList und Vector verwalten zwei Größen: zum einen die Anzahl der gespeicherten Elemente nach außen, zum anderen die interne Größe des Arrays. Ist die Kapazität des Arrays 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, also die Größe, liefert die Methode size(); die Kapazität des darunterliegenden 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 Arrays in das neue kopieren. Das kostet Zeit. Schon aus diesem Grund sollte der Konstruktor ArrayList(int initialCapacity) oder 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 Array angelegt wird und die Elemente kopiert werden, wir haben aber nichts über die Größe des neuen Arrays gesagt. Hier gibt es Strategien wie die »Verdopplungsmethode« beim Vector. Wird er vergrößert, so ist das neue Array doppelt so groß wie das alte. Dies ist eine Vorgehensweise, die für kleine und schnell wachsende Arrays eine clevere Lösung darstellt, großen Arrays 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 nicht das capacityIncrement im Konstruktor.

Die Größe eines Arrays *

Die interne Größe des Arrays kann mit ensureCapacity(int) 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 Weißraum, 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.

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.[ 253 ](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().

 

Zum Seitenanfang

17.1.5    LinkedList Zur vorigen ÜberschriftZur nächsten Überschrift

Die Klasse LinkedList (siehe Zweidimensionale Arrays mit ineinander verschachtelten Schleifen ablaufen) realisiert die Schnittstelle List als verkettete Liste und bildet die Elemente nicht auf ein Array 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.)

Klassendiagramm von »LinkedList« mit Vererbungsbeziehungen

Abbildung 17.1    Klassendiagramm von »LinkedList« mit Vererbungsbeziehungen

Eine LinkedList hat neben den gegebenen Operationen aus der Schnittstelle List weitere Hilfsmethoden: Dabei handelt es sich um die Methoden addFirst(…), addLast(…), getFirst(), getLast(), removeFirst() und removeLast(). Die implementierten Schnittstellen Queue und Deque sind nicht ganz unschuldig an diesen Methoden.

class java.util.LinkedList<E>

extends AbstractSequentialList<E>

implements List<E>, Deque<E>, Cloneable, Serializable
  • LinkedList()

    Erzeugt eine neue leere Liste.

  • LinkedList(Collection<? extends E> c)

    Kopiert alle Elemente der Collection c in die neue verkettete Liste.

 

Zum Seitenanfang

17.1.6    Der Array-Adapter Arrays.asList(…) Zur vorigen ÜberschriftZur nächsten Überschrift

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 statischen Methode Arrays.asList(…) an, ein existierendes Array als java.util.List zu behandeln. Der Parametertyp ist ein Vararg – das ja intern auf ein Array abgebildet wird –, sodass sich asList(…) auf zwei Arten verwenden lässt:

  • Arrays.asList(array): Die Variable array ist eine Referenz auf ein Array, und das Ergebnis ist eine Liste, die die gleichen Elemente wie das Array enthält.

  • Arrays.asList(e1, e2, e3): Die Elemente e1, e2, e3 sind Elemente der Liste.

Das Entwurfsmuster, das die Java-Bibliothek bei der statischen Methode anwendet, nennt sich Adapter. Er passt die Schnittstelle eines Typs an eine andere Schnittstelle eines anderen Typs an.

[zB]  Beispiel

Ermittle die Anzahl der »:-)«-Smileys im String.

String s = "Oten :-) Bilat :-) Iyot";

int i = Collections.frequency( Arrays.asList(s.split("\\s")), ":-)" );

System.out.println( i ); // 2

In String gibt es keine Methode zum Zählen von Teil-Strings.

[zB]  Beispiel

Gib das größte Element eines Arrays aus:

Integer[] ints = { 3, 9, -1, 0 };

System.out.println( Collections.max( Arrays.asList( ints ) ) );

Zum Ermitteln des Maximums bietet die Utility-Klasse Arrays keine Methode, daher bietet sich die max(…)-Methode von Collections an. Auch etwa zum Ersetzen von Array-Elementen bietet Arrays nichts, aber Collections. Sortieren und füllen kann Arrays aber schon. Hier muss asList() nicht einspringen.

class java.util.Arrays
  • public static <T> List<T> asList(T... a)

    Ermöglicht es, über die Schnittstelle List Zugriff auf ein Array zu erhalten. Die variablen Argumente sind sehr praktisch.

[»]  Hinweis

Wegen der Generics ist der Parametertyp von asList(…) ein Objekt-Array, aber niemals ein primitives Array. In unserem Beispiel von eben würde so etwas wie

int[] ints = { 3, 9, -1, 0 };

Arrays.asList( ints );

zwar compilieren, aber die Rückgabe von Arrays.asList(ints) ist vom Typ List<int[]>, was bedeutet, die gesamte Liste besteht aus genau einem Element, und dieses Element ist das primitive Array. Zum Glück führt Collections.max(Arrays.asList(ints)) zu einem Compilerfehler, denn von einer List<int[]>, also einer Liste von Arrays, kann max(Collection<? extends T>) kein Maximum ermitteln. Anders wäre das bei Arrays.asList(3, 9, -1, 0), denn hier konvertiert der Compiler die Varargs-Argumente über Autoboxing schon direkt in Wrapper-Objekte, und es kommt eine Liste von Integer-Objekten heraus.

Internes

Die Rückgabe von asList(…) ist kein konkreter Klassentyp wie ArrayList oder LinkedList, sondern irgendetwas Unbekanntes, was asList(…) als List herausgibt. Diese Liste ist nur eine andere Ansicht des Arrays.

Jetzt gibt es allerdings einen Interpretationsspielraum, was genau mit der Rückgabe möglich ist. Zudem ist es nicht ganz uninteressant, zu wissen, ob die Liste einen schnellen Punktzugriff zulässt (RandomAccess implementiert) bzw. ob optionale Operationen wie Veränderungen oder sogar totale Reorganisationen denkbar sind. Ein Blick auf die Implementierung verrät mehr. Das Ergebnis ist ein Adapter, der Listen-Methoden wie get(index) oder set(index, element) direkt auf das Array umleitet. Da Array-Längen final sind, führen Modifikationsmethoden wie remove(…) oder add(…) zu einer UnsupportedOperationException.

[»]  Hinweis

Sind Veränderungen an der asList(…)-Rückgabe erwünscht, so muss das Ergebnis in eine neue Datenstruktur kopiert werden, etwa so:

List<String> list = new ArrayList<>( Arrays.asList( "A", "B" ) );

list.add( "C" );
 

Zum Seitenanfang

17.1.7    ListIterator * Zur vorigen ÜberschriftZur nächsten Überschrift

Die Schnittstelle 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. Die Stelle wird auch Cursor genannt. Es ist zu berücksichtigen, dass der Cursor vom Iterator immer zwischen den Elementen steht; am Anfang steht er vor dem ersten Element. Die Methoden remove() und set(e) sind nicht mit Cursor-Positionen verbunden; sie operieren auf dem letzten Element, das next() oder previous() geliefert hat.

Listing 17.6    src/main/java/com/tutego/insel/util/list/ListIteratorDemo.java, main()

List<String> list = new ArrayList<>();

Collections.addAll( list, "b", "c", "d" );



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



it.add( "a" ); // Vorne anfügen

System.out.println( list ); // [a, b, c, d]



it.next(); // Position vor

it.remove(); // Element löschen

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



it.next(); // Position vor

it.set( "C" ); // Element ersetzen

System.out.println( list ); // [a, C, d]



it = list.listIterator( 1 ); // Neuen Iterator mit Startpos. 1

it.add( "B" ); // B hinzufügen

System.out.println( list ); // [a, B, C, d]



it = list.listIterator( list.size() );



it.previous(); // Eine Stelle nach vorne

it.remove(); // Letztes Element löschen

System.out.println( list ); // [a, B, C]
[+]  Tipp

Ein ListIterator kann die Elemente auch rückwärts verarbeiten:

List<String> list = new ArrayList<String>();

Collections.addAll( list, "1", "2", "3", "4" );

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

it.hasPrevious(); )

System.out.print( it.previous() + " " ); // 4 3 2 1
interface ListIterator<E>

extends Iterator<E>
  • boolean hasPrevious()

  • boolean hasNext()

    Liefern true, wenn es ein vorhergehendes bzw. nachfolgendes Element gibt.

  • E previous()

  • E next()

    Liefern das vorangehende bzw. nächste Element der Liste oder NoSuchElementException, wenn es das Element nicht gibt. Setzt dann die Cursorposition zurück bzw. weiter.

  • int previousIndex()

  • int nextIndex()

    Liefern den Index des vorhergehenden bzw. nachfolgenden Elements. Geht previousIndex() vor die Liste, so liefert die Methode die Rückgabe –1. Geht nextIndex() hinter die Liste, liefert die Methode 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 vor der aktuellen Position in die Liste ein.

  • void set(E o)

    Optional. Ersetzt das Element, das next() oder previous() als Letztes zurückgegeben haben.

 

Zum Seitenanfang

17.1.8    toArray(…) von Collection verstehen – die Gefahr einer Falle erkennen Zur vorigen ÜberschriftZur nächsten Überschrift

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.

[zB]  Beispiel

Diese Anwendung von toArray() überträgt alle Punkte der Sammlung in ein neues Array:

ArrayList<Point> list = new ArrayList<>();

list.add( new Point(13, 43) );

list.add( new Point(9, 4) );

Object[] points = list.toArray();

Wir erhalten ein Array mit Referenzen auf Point-Objekte, können jedoch 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.

Vielleicht kommen wir spontan auf die Idee, einfach den Typ des Arrays auf Point[] zu ändern; in dem Array befinden sich ja schließlich Point-Exemplare:

Point[] points = list.toArray();             // inline image Compilerfehler

Doch damit meldet der Compiler den Fehler »Type mismatch: cannot convert from Object[] to Point[]«, weil der Rückgabewert von toArray() ein Object[] ist und kein Point[]. Jetzt könnten wir auf die Idee kommen, das mit einer Typumwandlung auf ein Point[] zu reparieren:

Point[] points = (Point[]) list.toArray();   // inline image Problem zur Laufzeit

Zwar haben wir zur Übersetzungszeit kein Problem mehr, aber zur Laufzeit wird es immer knallen, und zwar mit einer »java.lang.ClassCastException: class [Ljava.lang.Object; cannot be cast to class [Ljava.awt.Point;«, 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 verwechselt. Einem Array von Objektreferenzen können wir alles zuweisen:

Object[] os = new Object[ 3 ];

os[0] = new Point();

os[1] = "Trecker fahr'n";

os[2] = LocalDate.now();

Wir merken, dass der Typ des Arrays Object[] ist, und die Array-Elemente sind ebenfalls vom Typ Object. Hinter dem Schlüsselwort new, das 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] = LocalDate.now(); // inline image ArrayStoreException

/* 4 */ os[2] = "Trecker fahr'n"; // inline image ArrayStoreException

Die Zeilen 3 und 4 sind vom Compiler erlaubt, führen aber zur Laufzeit zu einer 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 allgemeingültigen Implementierung von toArray() bleibt gar nichts anderes übrig, als das Array vom Typ Object[] und die Elemente vom Typ Object zu erzeugen.

Fassen wir zusammen: Wir haben vorher Object[] os = new Point[3]; geschrieben und gesehen, dass Object[] ein Basistyp von Point[] ist. Das geht, weil Object auch ein Basityp von Point ist. Die Vererbungsbeziehung von Typen überträgt sich auf die Vererbungsbeziehung der Arrays dieser Typen. Das nennt sich kovariant. Wenn allerdings – wie durch das parameterlose toArray() – nur ein Object[]-Array aufgebaut ist, lässt es sich nicht auf den Typ Point[] bringen, auch wenn jedes Element ein Point 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(T[])-Methode werfen. Sie akzeptiert als Parameter ein vorgefertigtes Array für das Ergebnis. Mit dieser Methode lässt sich erreichen, dass das Ergebnis-Array von einem spezielleren Typ als Object[] ist.

[zB]  Beispiel

Wir fordern von der toArray()-Methode ein Array vom Typ Point:

List<Point> list = new ArrayList<>();

list.add( new Point(13,43) );

list.add( new Point(9,4) );

Point[] points = (Point[]) list.toArray( new Point[0] );

Die Listenelemente bekommen wir in ein Array kopiert, und der Typ des Arrays ist Point[] – passend zu den aktuell vorhandenen Listenelementen. Der Parameter zeigt dabei den Wunschtyp an, der hier das Point-Array ist.

[+]  Performance-Tipp

Am besten ist es, bei toArray(T[]) ein Array anzugeben, das so groß ist wie das Ergebnis-Array, also so groß wie die Liste. Dann füllt nämlich toArray(T[]) genau dieses Array und gibt es zurück, anstatt ein neues Array aufzubauen:

ArrayList<Point> list = new ArrayList<>();

list.add( new Point(13,43) );

list.add( new Point(9,4) );

Point[] points = list.toArray( new Point[list.size()] );

// alternative Point[] points = list.toArray( Point[]::new );

Arrays mit Reflection anlegen *

Intern verwendet die Methode toArray(T[]) Reflection, um dynamisch ein Array vom gleichen Typ wie das übergebene Array zu erzeugen. Dabei kommt eine Methode aus java.lang.reflect.Array zum Einsatz:

  • public static Object newInstance(Class<?> componentType, int length)

[zB]  Beispiel

Lege ein neues Array an, das den gleichen Typ wie array hat. Das neue leere Feld soll Platz für len Elemente haben:

Object[] array = { new Point(-1, -1), new Point( 1, 1 ) };

int len = 100;

Object[] b = (Object[]) Array.newInstance(

array.getClass().getComponentType(), len);

Der Aufruf array.getClass() liefert ein Class-Objekt für das Array array, etwa ein Objekt, das den Typ Point[] repräsentiert. Mit array.getClass().getComponentType() erhalten wir ein Class-Objekt für den Elementtyp des Arrays, also Point.

Wir machen also dynamisch das, was new TYP[len] macht, wobei bei new 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 Sammlung aufnehmen kann, kopiert toArray(T[]) die Elemente aus der Collection in das Array. Im Übrigen entspricht toArray(new Object[0]) dem Aufruf von toArray().

 

Zum Seitenanfang

17.1.9    Primitive Elemente in Datenstrukturen verwalten Zur vorigen ÜberschriftZur nächsten Überschrift

Jede Datenstruktur der Collection-API akzeptiert, auch wenn sie generisch verwendet wird, nur Referenzen. Primitive Datentypen nehmen die Sammlungen nicht auf, was zur Konsequenz hat, dass Wrapper-Objekte nötig sind (über das Boxing fügt Java scheinbar primitive Elemente ein, doch in Wahrheit sind es Wrapper-Objekte). Auch wenn es also

List<Double> list = new ArrayList<>();

list.add( 1.1 );

list.add( 2.2 );

heißt, sind es zwei neue Double-Objekte, die aufgebaut werden und in die Liste wandern. Wenn dies anders und klarer geschrieben wird, sehen wir, was wirklich passiert:

List<Double> list = new ArrayList<>();

list.add( Double.valueOf(1.1) );

list.add( new Double(2.2) );

Aus dem Aufruf von Double.valueOf(…) ist die new-Nutzung nicht abzulesen, doch die Methode ist implementiert als Double valueOf(double d){ return new Double(d); }.

Spezialbibliotheken

Für performante Anwendungen und große Mengen von primitiven Elementen ist es sinnvoll, eine Klasse für den speziellen Datentyp einzusetzen. Anstatt so etwas selbst zu programmieren, kann der Entwickler auf drei Implementierungen zurückgreifen:

 


Ihre Meinung?

Wie hat Ihnen das Openbook gefallen? Wir freuen uns immer über Ihre Rückmeldung. Schreiben Sie uns gerne Ihr Feedback als E-Mail an kommunikation@rheinwerk-verlag.de

<< zurück
 Zum Rheinwerk-Shop
Zum Rheinwerk-Shop: Java ist auch eine Insel Java ist auch eine Insel

Jetzt Buch bestellen


 Buchempfehlungen
Zum Rheinwerk-Shop: Captain CiaoCiao erobert Java

Captain CiaoCiao erobert Java




Zum Rheinwerk-Shop: Java SE 9 Standard-Bibliothek

Java SE 9 Standard-Bibliothek




Zum Rheinwerk-Shop: Algorithmen in Java

Algorithmen in Java




Zum Rheinwerk-Shop: Objektorientierte Programmierung

Objektorientierte Programmierung




 Lieferung
Versandkostenfrei bestellen in Deutschland, Österreich und in die Schweiz

InfoInfo



 

 


Copyright © Rheinwerk Verlag GmbH 2021

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.

 

[Rheinwerk Computing]



Rheinwerk Verlag GmbH, Rheinwerkallee 4, 53227 Bonn, Tel.: 0228.42150.0, Fax 0228.42150.77, service@rheinwerk-verlag.de



Cookie-Einstellungen ändern