Möglichkeiten zum Durchlaufen einer Liste in Java

Da ich etwas neu in der Java-Sprache bin, versuche ich mich mit allen (oder zumindest nicht pathologischen) Möglichkeiten vertraut zu machen, wie man eine Liste (oder vielleicht andere Sammlungen) durchläuft, sowie mit den Vor- oder Nachteilen der einzelnen.

Bei einem bestimmten List<E> listObjekt kenne ich die folgenden Möglichkeiten, um alle Elemente zu durchlaufen:

Grundlegend für Schleife (natürlich gibt es auch Äquivalente while/ do whileSchleifen)

// Not recommended (see below)!
for (int i = 0; i < list.size(); i++) {
    E element = list.get(i);
    // 1 - can call methods of element
    // 2 - can use 'i' to make index-based calls to methods of list

    // ...
}

Hinweis: Wie @amarseillan hervorhob, ist dieses Formular eine schlechte Wahl für die Iteration über Lists, da die tatsächliche Implementierung der getMethode möglicherweise nicht so effizient ist wie bei Verwendung von a Iterator. Beispielsweise müssen LinkedListImplementierungen alle Elemente vor i durchlaufen, um das i-te Element zu erhalten.

Im obigen Beispiel gibt es keine Möglichkeit für die ListImplementierung, "ihren Platz zu speichern", um zukünftige Iterationen effizienter zu gestalten. Für a spielt ArrayListes keine Rolle, denn die Komplexität / Kosten von getsind konstante Zeit (O (1)), während sie für a LinkedListproportional zur Größe der Liste (O (n)) sind.

Weitere Informationen zur rechnerischen Komplexität der integrierten CollectionsImplementierungen finden Sie in dieser Frage .

Verbesserte for-Schleife ( in dieser Frage gut erklärt )

for (E element : list) {
    // 1 - can call methods of element

    // ...
}

Iterator

for (Iterator<E> iter = list.iterator(); iter.hasNext(); ) {
    E element = iter.next();
    // 1 - can call methods of element
    // 2 - can use iter.remove() to remove the current element from the list

    // ...
}

ListIterator

for (ListIterator<E> iter = list.listIterator(); iter.hasNext(); ) {
    E element = iter.next();
    // 1 - can call methods of element
    // 2 - can use iter.remove() to remove the current element from the list
    // 3 - can use iter.add(...) to insert a new element into the list
    //     between element and iter->next()
    // 4 - can use iter.set(...) to replace the current element

    // ...
}

Funktionelles Java

list.stream().map(e -> e + 1); // Can apply a transformation function for e

Iterable.forEach , Stream.forEach , ...

(Eine Kartenmethode aus der Stream-API von Java 8 (siehe Antwort von @ i_am_zero).)

In Java 8-Auflistungsklassen, die Iterable(z. B. alle Lists) implementieren , gibt es jetzt eine forEachMethode, die anstelle der oben gezeigten for-Schleifenanweisung verwendet werden kann . (Hier ist eine andere Frage , die einen guten Vergleich bietet.)

Arrays.asList(1,2,3,4).forEach(System.out::println);
// 1 - can call methods of an element
// 2 - would need reference to containing object to remove an item
//     (TODO: someone please confirm / deny this)
// 3 - functionally separates iteration from the action
//     being performed with each item.

Arrays.asList(1,2,3,4).stream().forEach(System.out::println);
// Same capabilities as above plus potentially greater
// utilization of parallelism
// (caution: consequently, order of execution is not guaranteed,
// see [Stream.forEachOrdered][stream-foreach-ordered] for more
// information about this).

Welche anderen Möglichkeiten gibt es, wenn überhaupt?

(Übrigens, mein Interesse beruht überhaupt nicht auf dem Wunsch, die Leistung zu optimieren . Ich möchte nur wissen, welche Formulare mir als Entwickler zur Verfügung stehen.)

Die drei Formen der Schleife sind nahezu identisch. Die erweiterte forSchleife:

for (E element : list) {
    . . .
}

die gemäß ist, Java Language Specification , identisch in der Tat auf die explizite Verwendung eines Iterators mit einem traditionellen forSchleife. Im dritten Fall können Sie den Listeninhalt nur ändern, indem Sie das aktuelle Element entfernen, und zwar nur dann, wenn Sie dies über die removeMethode des Iterators selbst tun . Mit der indexbasierten Iteration können Sie die Liste auf beliebige Weise ändern. Wenn Sie jedoch Elemente hinzufügen oder entfernen, die vor dem aktuellen Index stehen, besteht die Gefahr, dass Ihre Schleife Elemente überspringt oder dasselbe Element mehrmals verarbeitet. Sie müssen den Schleifenindex richtig anpassen, wenn Sie solche Änderungen vornehmen.

In allen Fällen elementwird auf das eigentliche Listenelement verwiesen. Keine der Iterationsmethoden erstellt eine Kopie von irgendetwas in der Liste. Änderungen am internen Status von elementwerden immer im internen Status des entsprechenden Elements in der Liste angezeigt.

Grundsätzlich gibt es nur zwei Möglichkeiten, eine Liste zu durchlaufen: mithilfe eines Index oder mithilfe eines Iterators. Die erweiterte for-Schleife ist nur eine syntaktische Verknüpfung, die in Java 5 eingeführt wurde, um die mühsame explizite Definition eines Iterators zu vermeiden. Für beide Arten können Sie mit im Wesentlichen banale Varianten kommen mit for, whileoder do whileBlöcke, aber sie alle laufen auf die gleiche Sache (oder, besser gesagt, zwei Dinge).

BEARBEITEN: Wie @ iX3 in einem Kommentar hervorhebt, können Sie mit a ListIteratordas aktuelle Element einer Liste festlegen, während Sie iterieren. Sie müssten List#listIterator()stattdessen verwenden List#iterator(), um die Schleifenvariable zu initialisieren (die natürlich als a ListIteratorund nicht als deklariert werden müsste Iterator).

Beispiel für jede in der Frage aufgeführte Art:

ListIterationExample.java

import java.util.*;

public class ListIterationExample {

     public static void main(String []args){
        List<Integer> numbers = new ArrayList<Integer>();

        // populates list with initial values
        for (Integer i : Arrays.asList(0,1,2,3,4,5,6,7))
            numbers.add(i);
        printList(numbers);         // 0,1,2,3,4,5,6,7

        // replaces each element with twice its value
        for (int index=0; index < numbers.size(); index++) {
            numbers.set(index, numbers.get(index)*2); 
        }
        printList(numbers);         // 0,2,4,6,8,10,12,14

        // does nothing because list is not being changed
        for (Integer number : numbers) {
            number++; // number = new Integer(number+1);
        }
        printList(numbers);         // 0,2,4,6,8,10,12,14  

        // same as above -- just different syntax
        for (Iterator<Integer> iter = numbers.iterator(); iter.hasNext(); ) {
            Integer number = iter.next();
            number++;
        }
        printList(numbers);         // 0,2,4,6,8,10,12,14

        // ListIterator<?> provides an "add" method to insert elements
        // between the current element and the cursor
        for (ListIterator<Integer> iter = numbers.listIterator(); iter.hasNext(); ) {
            Integer number = iter.next();
            iter.add(number+1);     // insert a number right before this
        }
        printList(numbers);         // 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15

        // Iterator<?> provides a "remove" method to delete elements
        // between the current element and the cursor
        for (Iterator<Integer> iter = numbers.iterator(); iter.hasNext(); ) {
            Integer number = iter.next();
            if (number % 2 == 0)    // if number is even 
                iter.remove();      // remove it from the collection
        }
        printList(numbers);         // 1,3,5,7,9,11,13,15

        // ListIterator<?> provides a "set" method to replace elements
        for (ListIterator<Integer> iter = numbers.listIterator(); iter.hasNext(); ) {
            Integer number = iter.next();
            iter.set(number/2);     // divide each element by 2
        }
        printList(numbers);         // 0,1,2,3,4,5,6,7
     }

     public static void printList(List<Integer> numbers) {
        StringBuilder sb = new StringBuilder();
        for (Integer number : numbers) {
            sb.append(number);
            sb.append(",");
        }
        sb.deleteCharAt(sb.length()-1); // remove trailing comma
        System.out.println(sb.toString());
     }
}

Die Basisschleife wird nicht empfohlen, da Sie die Implementierung der Liste nicht kennen.

Wenn das eine LinkedList war, jeder Aufruf von

list.get(i)

würde über die Liste iterieren, was zu N ^ 2 Zeitkomplexität führen würde.

Eine Iteration im JDK8-Stil:

public class IterationDemo {

    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(1, 2, 3);
        list.stream().forEach(elem -> System.out.println("element " + elem));
    }
}

In Java 8 gibt es mehrere Möglichkeiten, Sammlungsklassen zu durchlaufen.

Verwenden von Iterable forEach

Die implementierten Sammlungen Iterable(z. B. alle Listen) verfügen jetzt über eine forEachMethode. Wir können die in Java 8 eingeführte Methodenreferenz verwenden .

Arrays.asList(1,2,3,4).forEach(System.out::println);

Verwenden von Streams forEach und forEachOrdered

Wir können eine Liste auch mit Stream wie folgt durchlaufen :

Arrays.asList(1,2,3,4).stream().forEach(System.out::println);
Arrays.asList(1,2,3,4).stream().forEachOrdered(System.out::println);

Wir sollen lieber forEachOrderedüber , forEachweil das Verhalten forEachausdrücklich nicht deterministisch ist , wo als forEachOrderedeine Aktion für jedes Element dieses Stroms, in der Begegnung Reihenfolge des Stroms , wenn der Strom eine definierte Begegnung Ordnung hat. ForEach garantiert daher nicht, dass die Bestellung beibehalten wird.

Der Vorteil von Streams ist, dass wir bei Bedarf auch parallele Streams verwenden können. Wenn das Ziel nur darin besteht, die Artikel unabhängig von der Bestellung zu drucken, können wir den parallelen Stream wie folgt verwenden:

Arrays.asList(1,2,3,4).parallelStream().forEach(System.out::println);

Ich weiß nicht, was Sie für pathologisch halten, aber lassen Sie mich einige Alternativen nennen, die Sie vorher nicht gesehen haben könnten:

List<E> sl= list ;
while( ! sl.empty() ) {
    E element= sl.get(0) ;
    .....
    sl= sl.subList(1,sl.size());
}

Oder seine rekursive Version:

void visit(List<E> list) {
    if( list.isEmpty() ) return;
    E element= list.get(0) ;
    ....
    visit(list.subList(1,list.size()));
}

Auch eine rekursive Version des Klassikers for(int i=0...:

void visit(List<E> list,int pos) {
    if( pos >= list.size() ) return;
    E element= list.get(pos) ;
    ....
    visit(list,pos+1);
}

Ich erwähne sie, weil Sie "etwas neu in Java" sind und dies interessant sein könnte.

Sie können forEach ab Java 8 verwenden:

 List<String> nameList   = new ArrayList<>(
            Arrays.asList("USA", "USSR", "UK"));

 nameList.forEach((v) -> System.out.println(v));

Für eine Rückwärtssuche sollten Sie Folgendes verwenden:

for (ListIterator<SomeClass> iterator = list.listIterator(list.size()); iterator.hasPrevious();) {
    SomeClass item = iterator.previous();
    ...
    item.remove(); // For instance.
}

Wenn Sie eine Position wissen möchten, verwenden Sie iterator.previousIndex (). Es ist auch hilfreich, eine innere Schleife zu schreiben, die zwei Positionen in der Liste vergleicht (Iteratoren sind nicht gleich).

Richtig, viele Alternativen sind aufgelistet. Am einfachsten und saubersten wäre es, die erweiterte forAnweisung wie folgt zu verwenden. Das Expressionist von einem Typ, der iterierbar ist.

for ( FormalParameter : Expression ) Statement

Um beispielsweise die IDs von List <String> zu durchlaufen, können wir dies einfach tun:

for (String str : ids) {
    // Do something
}

In können java 8Sie die List.forEach()Methode mit verwenden lambda expression, um eine Liste zu durchlaufen.

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

public class TestA {
    public static void main(String[] args) {
        List<String> list = new ArrayList<String>();
        list.add("Apple");
        list.add("Orange");
        list.add("Banana");
        list.forEach(
                (name) -> {
                    System.out.println(name);
                }
        );
    }
}

Sie können das erste und dritte Beispiel jederzeit mit einer while-Schleife und etwas mehr Code austauschen. Dies gibt Ihnen den Vorteil, dass Sie das Do-While verwenden können:

int i = 0;
do{
 E element = list.get(i);
 i++;
}
while (i < list.size());

Natürlich kann dies zu einer NullPointerException führen, wenn list.size () 0 zurückgibt, da es immer mindestens einmal ausgeführt wird. Dies kann behoben werden, indem getestet wird, ob das Element null ist, bevor seine Attribute / Methoden verwendet werden. Trotzdem ist es viel einfacher und einfacher, die for-Schleife zu verwenden