Möglichkeiten zum Durchlaufen einer Liste in Java

576

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.)

iX3
quelle
1
Dies sind die nicht pathologischen, obwohl Sie möglicherweise auch eine von mehreren Bibliotheken im funktionalen Stil verwenden, um Sammlungen zu verarbeiten.
Dave Newton
Ist die Frage nach der ListSchnittstelle spezifisch?
Sotirios Delimanolis
@SotiriosDelimanolis, in jeder Hinsicht ist es spezifisch für <code> List </ code>, aber wenn es andere interessante Möglichkeiten gibt, beispielsweise mit einer <code> Collection </ code> zu arbeiten, wäre ich es interessiert, sie zu kennen.
iX3
@ DaveNewton, danke für die Idee. Ich habe so etwas noch nie benutzt. Bitte werfen Sie einen Blick auf meine bearbeitete Frage und lassen Sie mich wissen, ob ich verstanden habe, was Sie meinten.
iX3
2
@sdasdadas, fertig: stackoverflow.com/questions/18410035/…
iX3

Antworten:

265

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).

Ted Hopp
quelle
OK, danke, aber wenn der Iterator tatsächlich einen Verweis auf das reale Element zurückgibt (keine Kopie), wie kann ich ihn dann verwenden, um den Wert in der Liste zu ändern? Ich nehme an, wenn ich ein verwende e = iterator.next(), e = somethingElseändert sich nur, worauf sich das Objekt ebezieht, anstatt den tatsächlichen Speicher zu ändern, aus dem iterator.next()der Wert abgerufen wurde.
iX3
@ iX3 - Das würde auch für eine indexbasierte Iteration gelten; Durch das Zuweisen eines neuen Objekts ewird nicht geändert, was in der Liste enthalten ist. du musst anrufen list.set(index, thing). Sie können den Inhalt von e(z. B. e.setSomething(newValue)) ändern. Um jedoch zu ändern, welches Element in der Liste gespeichert ist, während Sie es iterieren, müssen Sie sich an eine indexbasierte Iteration halten.
Ted Hopp
Vielen Dank für diese Erklärung; Ich denke, ich verstehe, was Sie jetzt sagen, und werde meine Frage / Kommentare entsprechend aktualisieren. Es gibt kein "Kopieren" an sich, aber wegen des Sprachdesigns emüsste ich eine der eMethoden aufrufen , um Änderungen am Inhalt von vorzunehmen, da die Zuweisung nur den Zeiger ändert (entschuldigen Sie mein C).
iX3
Also für Listen unveränderlicher Typen wie Integerund Stringes wäre nicht möglich, den Inhalt mit for-eachoder IteratorMethoden zu ändern - müsste das Listenobjekt selbst manipulieren, um es durch Elemente zu ersetzen. Ist das richtig?
iX3
@ iX3 - Richtig. Sie können Elemente mit der dritten Form (expliziter Iterator) entfernen, aber Sie können Elemente nur dann zu Elementen in der Liste hinzufügen oder diese ersetzen, wenn Sie eine indexbasierte Iteration verwenden.
Ted Hopp
46

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());
     }
}
iX3
quelle
23

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.

Amarseillan
quelle
1
Richtig; Das ist ein guter Punkt, und ich werde das Beispiel in der Frage aktualisieren.
iX3
Laut diesem Beitrag ist Ihre Aussage nicht korrekt: Was ist effizienter, eine for-each-Schleife oder ein Iterator?
Hibbem
5
Was ich in diesem Beitrag gelesen habe, ist genau das, was ich gesagt habe ... Welchen Teil lesen Sie genau?
Amarseillan
20

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));
    }
}
eugene82
quelle
Vielen Dank, ich beabsichtige, die Liste oben mit Java 8-Lösungen zu aktualisieren.
iX3
1
@ eugene82 ist dieser Ansatz viel effizienter?
Nazar_art
1
@nazar_art Sie werden keine großen Verbesserungen gegenüber anderen sehen, es sei denn, Sie haben parallelStream für eine sehr große Sammlung verwendet. Eigentlich ist es nur im Sinne einer heilenden Ausführlichkeit effizienter.
Schurke
7

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);
akhil_mittal
quelle
5

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.

Mario Rossi
quelle
1
Danke, dass du es erwähnt hast. Ich hatte mir die SubList-Methode noch nie angesehen. Ja, ich würde es als pathologisch betrachten, da ich keinen Umstand kenne, unter dem es jemals vorteilhaft wäre, dies abgesehen von vielleicht Verschleierungswettbewerben zu verwenden.
iX3
3
OK. Ich mag es nicht, als "pathologisch" bezeichnet zu werden, daher hier eine Erklärung: Ich habe sie verwendet, um Pfade in Bäumen zu verfolgen oder ihnen zu folgen. Einer noch? Während ich einige Lisp-Programme nach Java übersetzte, wollte ich nicht, dass sie ihren Lisp-Geist verlieren, und tat dasselbe. Stimmen Sie dem Kommentar zu, wenn Sie der Meinung sind, dass dies gültige, nicht pathologische Verwendungen sind. Ich brauche eine Gruppenumarmung !!! :-)
Mario Rossi
Sind Pfade in Bäumen nicht anders als Listen? Übrigens wollte ich Sie oder eine Person nicht als "pathologisch" bezeichnen. Ich meine nur, dass einige Antworten auf meine Frage verständlicherweise unpraktisch sind oder in einer guten Softwareentwicklungspraxis kaum einen Wert haben.
iX3
@ iX3 Mach dir keine Sorgen; Ich hab nur Spass gemacht. Pfade sind Listen: "an der Wurzel beginnen" (offensichtlich), "zum 2. Kind bewegen", "zum 1. Kind bewegen", "zum 4. Kind bewegen". "Halt". Oder kurz [2,1,4]. Dies ist eine Liste.
Mario Rossi
Ich würde es vorziehen, eine Kopie der Liste zu erstellen und zu verwenden while(!copyList.isEmpty()){ E e = copyList.remove(0); ... }. Das ist effektiver als die erste Version;).
AxelH
2

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));
Sudip Bhandari
quelle
0

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).

CoolMind
quelle
0

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
}
Yu Chen
quelle
3
Er fragt, ob es außer den in der Frage beschriebenen noch andere Möglichkeiten gibt (einschließlich der von Ihnen erwähnten)!
Ericbn
0

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);
                }
        );
    }
}
Suchergebnisse Web-Ergebnisse Pi
quelle
Cool. Können Sie erklären, wie sich dies von eugene82der Antwort und i_am_zeroder Antwort unterscheidet ?
iX3
@ iX3 ahh. Ich habe nicht die gesamte Antwortliste gelesen. Ich habe versucht, hilfreich zu sein. Soll ich die Antwort entfernen?
Suchergebnisse Web-Ergebnisse Pi
Ist mir egal, obwohl Sie es vielleicht verbessern könnten, indem Sie es mit anderen Techniken vergleichen und kontrastieren. Oder wenn Sie der Meinung sind, dass es keine neue Technik demonstriert, aber dennoch als Referenz für andere nützlich sein könnte, können Sie möglicherweise einen Hinweis hinzufügen, der dies erklärt.
iX3
-2

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

Schildgenerator7
quelle
Stimmt ... Ich denke, das ist technisch anders, aber das Verhalten ist nur anders, wenn die Liste leer ist, oder?
iX3
@ ix3 ja, und in diesem Fall ist das Verhalten schlechter. Ich würde das nicht als gute Alternative bezeichnen.
CPerkins
Sicher, aber fairerweise geht es bei dieser Frage weniger darum, was "gut" ist, als vielmehr darum, was "möglich" ist. Deshalb schätze ich diese Antwort immer noch.
iX3