Weiterführende Themen zu Listen, Sets und Maps

1. For-EACH-Schleife

In vielen Fällen ist es in Schleifen über Arrays, Listen oder Sets nötig, Methoden am jeweils aktuellen Element auszuführen und der Array- oder Listen-Index ist unnötig oder gar nicht verfügbar (bei Sets, die ja keine definierte Ordnung haben!!).

Zu diesm Zweck worde eine weitere Form der FOR-Schleife eingeführt, die diese Anforderung sehr elegant erfült:

import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

public class Demo4ForEach {

    public void forEachDemo() {
        System.out.println("#### forEachDemo() ####");
        System.out.println("  Array of int:");
        int[] numbers = {5, -2, 3, 7};
        for (int n : numbers) {
            System.out.format("    %d%n", n);
        }
        System.out.println("  Array of String:");
        String[] words = {"Heute", "ist", "ein", "schöner", "Tag"};
        for (String wd : words) {
            System.out.format("    %s%n", wd);
        }
        System.out.println("  List<String>:");
        List<String> wordList = new ArrayList(Arrays.asList(words));
        for (String wd : wordList) {
            System.out.format("    %s%n", wd);
        }
    }
}

Für Arrays ist die Logik direkt implementiert, für Lists etc. basiert es auf der Implementation des Interfaxces java.lang.Iterable<ElementTyp>: siehe auch Iterable (Java SE 17 & JDK 17)

2. Iteratoren

Sets erlauben keinen index-basierten Zugriff auf einzelne Elemente, da in ihnen keine Ordnung definiert ist. Die einzige Möglichkeit, auf Elemente zuzugreifen, ist das "Durchiterieren".

Die Basis dafür bietet das Konzept der Iteratoren. Das Interface java.util.Collection<E> "extends" das Super-Interface java.lang.Iterable<E> und hat daher die Methode Iterator<E> iterator().

Im Interface Iterator<E> hat zwei für die Nutzbarkeit fundamentale Methoden:

  • boolean hasNext() gibt an, ob ein weiteres Element verfügbar ist und kann somit als Fortsetzungsbedingung z.B. in while-Schleifen verwendet werden.

  • E next() liefert das oben als verfügbar angekündigte nächste Element.
    Wenn keines vorhanden wäre, würde eine unchecked java.util.NoSuchElementException geworfen.

Ein kurzes Beispiel:

public class IteratorDemo1
{
    public void demo1() {
        Collection<String> words = Arrays.asList("Heute", "ist", "ein", "schöner", "Tag");
        Iterator<String> wordsIterator = words.iterator();
        System.out.format("=== All %d words: ===%n", words.size());
        while (wordsIterator.hasNext()) {
            String word = wordsIterator.next();
            System.out.format(" %s", word);
        }
    }
}

Be Verwendung des Iterators kann durch Hinzufügen oder vor allem Entfernen eines Elements während der Iteration die Bereitstellungslogik außer Tritt kommen. Das Iterator-Objekt wird ja VOR Beginn der Iteration von einem bestimmten Listen/Set-Zustand erzeugt und erfährt nichts von Änderungen.

Bei einem solchen Problem wird eine unchecked java.util.ConcurrentModificationException geworfen.

Wenn sofort nach dem Entfernen eines einzelnen Elements die Iteration gestoppt wird, tritt das Problem NICHT auf. Wenn die Fortsetzung der Iteration nötig ist, sollte keine for-ech-Schleife verwendet werden, sondern direkt wie oben gezeigt mit dem Iterator gearbeitet werden. Für das Entfernen gibt es eine eigene Methode in der Iterator-Klasse, die dem Iterator erlaubt, bei Entfernen die Bereitstellungslogik zu adaptieren, womit das Problem beseitigt ist.

    // Ergänzung zu obiger Klasse "IteratorDemo1":
    public void removeWithIteratorRemove(String toRemove) {
        System.out.println("#### removeWithIteratorRemove(..) ####");
        Iterator<String> wordsIterator = words.iterator();
        while (wordsIterator.hasNext()) {
            String wd = wordsIterator.next();
            if (wd.equals(toRemove)) {
                wordsIterator.remove();
            }
        }
        printListWithIteratorWhile();
    }

    public void printListWithIteratorWhile() {
        System.out.println("#### printSetWithIteratorWhile() ####");
        Iterator<String> wordsIterator = words.iterator();
        while (wordsIterator.hasNext()) {
            String wd = wordsIterator.next();
            System.out.println(String.format("  %s", wd));
        }
    }
von einem bestimmten Listen-Zusatnd

TODO: remove

import java.util.Set;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Arrays;

public class Demo4Iterator {
    private Set<String> words = new HashSet<>(Arrays.asList("aa", "cc", "bb", "dd"));

    public void printSetWithIteratorWhile() {
        System.out.println("#### printSetWithIteratorWhile() ####");
        Iterator<String> wordsIterator = words.iterator();
        while (wordsIterator.hasNext()) {
            String wd = wordsIterator.next();
            System.out.println(String.format("  %s", wd));
        }
    }

    public void printSetWithForeach() {
        System.out.println("#### printSetWithForeach() ####");
        for (String wd : words) {
            System.out.println("  %s".formatted(wd));
        }
    }

    public void removeWithWhileRemove(String toRemove) {
        System.out.println("#### removeWithWhileRemove(..) ####");
        Iterator<String> wordsIterator = words.iterator();
        while (wordsIterator.hasNext()) {
            String wd = wordsIterator.next();
            if (wd.equals(toRemove)) {
                words.remove(wd);
            }
        }
    }


    public void removeWithIteratorRemove(String toRemove) {
        System.out.println("#### removeWithIteratorRemove(..) ####");
        Iterator<String> wordsIterator = words.iterator();
        while (wordsIterator.hasNext()) {
            String wd = wordsIterator.next();
            if (wd.equals(toRemove)) {
                wordsIterator.remove();
            }
        }
        printSetWithForeach();
    }

    public void removeDirectly(String toRemove) {
        System.out.println("#### removeOne(..) ####");
        words.remove(toRemove);
        printSetWithForeach();
    }
}

3. Sortierte Listen und zugehörige Interfaces

Sortieren größerer Anzahlen gleichartiger Elemente ist eine vermutlich schon Jahrtausende betriebene Aktivität. Im Prinzip beruht Sortieren auf dem (mitunter sehr oft durchzuführenden) Vergleich je zweier Elemente, sodass man schließlich das größte, kleinste, zweitkleinste, etc. passend zueinander angeordnet hat.

Die grundlegende Operation ist also der Vergleich zweier Elemente. Der Algorithmus des Sortierens basiert auf einer systematischen Abfolge von Vergleichen und darauf basierenden Austausch-Operationen (oder Platzieren in einer neuen Sammlung).

Aus diesem Grund ist es möglich, Sortieralgorithmen zu schreiben, die als "Werkzeug" eine Zwei-Element-Vergleichsfunktion (oder -methode) nutzen. Diese wird – vom Algorithmus gesteuert – mit den jeweils benötigten Elementen aufgerufen und liefert 3 mögliche Ergebnisse des 2-Element-Vergleichs zurück: erstes kleiner, beide gleich, erstes größer.

Die Entwicklung, Analyse und Optimierung von Sortieralgorithmen ist eine wichtige Disziplin der Informatik, da sortierte Sammlungen eine fundamentale Basis für effizientes Finden und Zugriff in großen Sammlungen (für Menschen schon ab weniger als 10 Elemente, für Computer Tausende bis Milliarden Elemente) bilden.

Beispiele: Schülerliste, Bankkonten-Verwaltung, Domain-Name-System (=DNS)-Verwaltung, etc.

Java stellt im JDK fertige, effiziente und sehr gründlich getestete Sortieralgorithmen bereit – sowohl für Arrays (in Klasse java.util.Arrays) als auch für Lists (in Klasse java.util.Collections). Seit "kurzem" (ab Java 8) gibt es eine direkte Methode im Interface (seit Java 8 gibt es in Interfaces die Möglichkeit, mit Schlüsselwort default Default-Implementationen zu implementieren).

Für die Vergleichsfunktion gibt es 2 Optionen:

  • die Element-Klasse (oder das Element-Interface!!) selbst definiert eine Vergleichslogik, indem das Interface java.lang.Comparable<ItemClass> mit der einzigen Methode compareTo( …​ ) implementiert wird (Details siehe unten).

  • es wird ein externes Objekt übergeben, dessen Klasse das Interface java.util.Comparator<ItemClass> implementiert und das damit in der Lage ist, mittels der so bereitgestellten Methode int compare​(ItemClass item1, ItemClass item2) die Entscheidung für beliebige Elemente der ItemClass vorzunehmen.

Wichtig ist noch zu wissen, dass ItemClass genauso gut ein Interface sein kann – man kann also – wie auch bei Listenelementen und sogar wie bei Java-Arrays, die erlaubten Elemente nicht nur über Klassenzugeörigkeit, sondern auch per implementiertem Interface festlegen!

fehlt noch: Beispiel

3.1. Interface Comparable<ItemClass>

Die schon oben erwähnte Möglichkeit, eine "natürliche" Ordnung für Klassen zu definieren, beruht auf der Implementation des Interfaces java.lang.Comparable<ItemClass>.
Dieses enthält nur eine einzige Methode:
int compareTo(ItemClass item),
nutzbar als int cmp = thisItem.compareTo(otherItem).
Dabei bedeutet cmp < 0: thisItem ist kleiner, cmp == 0: beide gleich, und cmp > 0: thisItem größer als otherItem.

3.2. Interface Comparator<ItemClass>

Oft besteht der Bedarf, nach einer anderen als der "natürlichen" Ordnung zu sortieren. Für diesen Fall stellt das JDK das Interface Comparator<ItemClass> bereit. Ein Objekt dieser Klasse wird der Sortiermethode als Parameter übergeben, um die benötigten Vergleichsoperationen zu ermöglichen.

Das Interface hat einen generic Parameter <SomeClassOrIface> und enthält nur eine einzige Methode: int compare(ItemClassOrIface o1, ItemClassOrIface o2). Beim Rückgabewert gilt wie beim obigen compareTo(…​): 0 bei Gleichheit, negativ wenn o1 kleiner als o2, positiv wenn o1 größer.

3.3. Vergleichsdurchführung

Hier ein Beispielfür eine

4. Geordnete und sortierte Sets

Sets (deutsch: Mengen) sind mathematische Konzepte, die im Prinzip ungeordnete Sammlungen von eindeutigen Elementen (also ohne Doubletten) darstellen.

Abseits der Mathematik ist dieses Konzept ebenfalls bedeutsam, hier ist jedoch oft eine definierte Reihenfolge wichtig. Daher gibt es neben dem "nackten" Set auch 2 weitere Varianten.

  • nach Einfüge-Reihenfolge geordnet – die bekannteste Implementation ist das java.util.LinkedHashSet<ItemClass>. Die Reihenfolge der mit add(…​) aufgenommenen Elemente wird beibehalten, sodass der Iterator die Elemente in genau dieser Reihenfolge bereitstellt (die ForEach-Schleife daher auch).

  • sortiert – hierfür gibt es sogar das Sub-Interface SortedSet (Details siehe SortedSet (Oracle API-Doc Java SE 17 & JDK 17)), bekannteste Implementation: TreeSet (Details siehe TreeSet (Oracle API-Doc Java SE 17 & JDK 17) …​ 2021-11-19 ).

5. Sortierte Listen und Sets bei Objekt-Änderung

5.1. xxx

5.2. Probleme beim Ändern von Elementen

Für viele Arten von Collections hat das Ändern von Elementen, solange sie Teil der Collection sind, fundamentale Auswirkungen.

5.2.1. Erster, eher harmloser Fall: Feststellung des Enthalten-Seins

Für den Fall, dass die Methode equals(someObj) nicht auf Identität prüft, sondern auf semantische Übereinstimmung (z.B. den DB-Primary-Key oder bei Personen die Sozialversicherungsnummer), führt die Änderung dieses Attributs trivialerweise dazu, dass das Objekt mit dem alten Wert nicht mehr ansprechbar ist.

Da equals(someObj) für die Methode contains(someObj) und damit in weiterer Folge auch für remove(someObj) verwendet wird, kann das bei Nicht-Beachtung zu Problemen führen.

5.2.2. Zweiter Fall: sortierte Listen

Wenn in einer sortierten Liste ein enthaltenes Objekt so geändert wird, dass eines der Sortierkriterien (enthalten je nach Sortierart in der Methode compareTo(someObj) oder compare(obj1, obj2)) betroffen ist, bricht in diesem Augenblick die korrekte Sortierung zusammen, ohne dass dies in komplexeren Konstellationen zwingend auffällt. Ein Objekt weiß ja nicht, in welchen Listen es enthalten ist und ein Programmierer in einem größeren Team weiß nicht, ob ein Kollege ein Objekt "seiner Klasse" in einer sortierten Liste aufnimmt. Die Sortierung einer Liste ist aber fundamental z.B. beim Suchen.

5.2.3. Dritter Fall: Sets

sets sind Keys für Maps!!!!!

5.2.4. Elegante, allgemeine Lösung

PropertyChangeEvent

Für tieferes Verständnis siehe dazu auch z.B. artima - How to Write an Equality Method in Java