Façons d'itérer sur une liste en Java

576

Étant un peu nouveau dans le langage Java, j'essaie de me familiariser avec toutes les façons (ou au moins celles non pathologiques) que l'on pourrait parcourir à travers une liste (ou peut-être d'autres collections) et les avantages ou les inconvénients de chacun.

Étant donné un List<E> listobjet, je connais les façons suivantes de parcourir tous les éléments:

De base pour la boucle (bien sûr, il existe également des boucles while/ équivalentes do while)

// 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

    // ...
}

Remarque: Comme @amarseillan l'a souligné, ce formulaire est un mauvais choix pour itérer sur Lists, car l'implémentation réelle de la getméthode peut ne pas être aussi efficace que lors de l'utilisation d'un Iterator. Par exemple, les LinkedListimplémentations doivent traverser tous les éléments précédant i pour obtenir le i-ème élément.

Dans l'exemple ci-dessus, l' Listimplémentation n'a aucun moyen de "sauver sa place" pour rendre les futures itérations plus efficaces. Pour un, ArrayListcela n'a pas vraiment d'importance, car la complexité / le coût de getest un temps constant (O (1)) tandis que pour un LinkedListil est proportionnel à la taille de la liste (O (n)).

Pour plus d'informations sur la complexité de calcul des Collectionsimplémentations intégrées , consultez cette question .

Amélioré pour la boucle (bien expliqué dans cette question )

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

    // ...
}

Itérateur

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

    // ...
}

Java fonctionnel

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

Iterable.forEach , Stream.forEach , ...

(Une méthode de carte de l'API Stream de Java 8 (voir la réponse de @ i_am_zero).)

Dans Java 8, les classes de collection qui implémentent Iterable(par exemple, tous les Lists) ont désormais une forEachméthode, qui peut être utilisée à la place de l' instruction for loop illustrée ci-dessus. (Voici une autre question qui fournit une bonne comparaison.)

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

Quels autres moyens existe-t-il, le cas échéant?

(BTW, mon intérêt ne découle pas du tout d'un désir d' optimiser les performances ; je veux juste savoir quelles formes sont à ma disposition en tant que développeur.)

iX3
la source
1
Ce ne sont pas des pathologies, bien que vous puissiez également utiliser plusieurs bibliothèques de style fonctionnel pour traiter les collections.
Dave Newton
La question de l' Listinterface est-elle spécifique?
Sotirios Delimanolis
@SotiriosDelimanolis, à toutes fins utiles, oui, il est spécifique à la <code> liste </code>, mais s'il existe d'autres façons intéressantes de travailler avec, par exemple, une <code> collection </code>, je serais intéressé à les connaître.
iX3
@DaveNewton, merci pour l'idée. Je n'ai jamais rien utilisé de tel. Veuillez jeter un œil à ma question modifiée et faites-moi savoir si j'ai compris ce que vous vouliez dire.
iX3

Réponses:

265

Les trois formes de bouclage sont presque identiques. La forboucle améliorée :

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

est, selon la spécification du langage Java , identique en effet à l'utilisation explicite d'un itérateur avec une forboucle traditionnelle . Dans le troisième cas, vous ne pouvez modifier le contenu de la liste qu'en supprimant l'élément courant et, ensuite, uniquement si vous le faites via la removeméthode de l'itérateur lui-même. Avec l'itération basée sur un index, vous êtes libre de modifier la liste de n'importe quelle manière. Cependant, l'ajout ou la suppression d'éléments antérieurs à l'index actuel risque de faire sauter vos éléments en boucle ou de traiter le même élément plusieurs fois; vous devez ajuster correctement l'index de boucle lorsque vous effectuez de telles modifications.

Dans tous les cas, elementest une référence à l'élément de liste réel. Aucune des méthodes d'itération ne copie quelque chose de la liste. Les modifications de l'état interne de elementseront toujours visibles dans l'état interne de l'élément correspondant de la liste.

Essentiellement, il n'y a que deux façons d'itérer sur une liste: en utilisant un index ou en utilisant un itérateur. La boucle for améliorée n'est qu'un raccourci syntaxique introduit dans Java 5 pour éviter l'ennui de définir explicitement un itérateur. Pour les deux styles, vous pouvez proposer des variations essentiellement triviales en utilisant for, whileou des do whileblocs, mais elles se résument toutes à la même chose (ou, plutôt, deux choses).

EDIT: Comme @ iX3 le fait remarquer dans un commentaire, vous pouvez utiliser a ListIteratorpour définir l'élément actuel d'une liste pendant que vous itérez. Vous auriez besoin d'utiliser List#listIterator()au lieu de List#iterator()pour initialiser la variable de boucle (qui, évidemment, devrait être déclarée a ListIteratorplutôt que an Iterator).

Ted Hopp
la source
OK, merci, mais si l'itérateur retourne réellement une référence à l'élément réel (pas une copie), comment puis-je l'utiliser pour changer la valeur dans la liste? Je suppose que si j'utilise un e = iterator.next()alors faire e = somethingElsechange simplement l'objet eauquel il se réfère plutôt que de changer le magasin réel à partir duquel iterator.next()la valeur a été récupérée.
iX3
@ iX3 - Cela serait également vrai pour une itération basée sur un index; assigner un nouvel objet à ene changera pas le contenu de la liste; vous devez appeler list.set(index, thing). Vous pouvez changer le contenu de e(par exemple, e.setSomething(newValue)), mais pour changer quel élément est stocké dans la liste pendant que vous l'itérez, vous devez vous en tenir à une itération basée sur un index.
Ted Hopp
Merci pour cette explication; Je pense que je comprends ce que vous dites maintenant et je mettrai à jour ma question / mes commentaires en conséquence. Il n'y a pas de "copie" en soi, mais en raison de la conception du langage, pour apporter des modifications au contenu de, eje dois appeler l'une des eméthodes de, car l'affectation ne fait que modifier le pointeur (pardonnez mon C).
iX3
Ainsi, pour les listes de types immuables comme Integeret Stringil ne serait pas possible de modifier le contenu à l'aide de for-eachou des Iteratorméthodes - il faudrait manipuler l'objet de liste lui-même pour le remplacer par des éléments. Est-ce correct?
iX3
@ iX3 - Correct. Vous pouvez supprimer des éléments avec le troisième formulaire (itérateur explicite), mais vous ne pouvez ajouter ou remplacer des éléments dans la liste que si vous utilisez une itération basée sur un index.
Ted Hopp
46

Exemple de chaque type énuméré dans la question:

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
la source
23

La boucle de base n'est pas recommandée car vous ne connaissez pas l'implémentation de la liste.

S'il s'agissait d'une LinkedList, chaque appel à

list.get(i)

serait itérer sur la liste, entraînant une complexité temporelle de N ^ 2.

amarseillan
la source
1
Correct; c'est un bon point, et je mettrai à jour l'exemple de la question.
iX3
selon cet article, votre affirmation n'est pas correcte: quelle est la plus efficace, une boucle pour chaque, ou un itérateur?
Hibbem
5
Ce que j'ai lu dans ce post est exactement ce que j'ai dit ... Quelle partie lisez-vous exactement?
amarseillan
20

Une itération de style JDK8:

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
la source
Merci, j'ai l'intention de mettre à jour la liste en haut avec les solutions Java 8 à terme.
iX3
1
@ eugene82 cette approche est-elle beaucoup plus efficace?
nazar_art
1
@nazar_art Vous n'allez pas voir beaucoup d'amélioration par rapport à autre chose à moins que vous n'ayez peut-être utilisé parallelStream sur une très grande collection. C'est plus efficace dans le sens de guérir la verbosité seulement, vraiment.
Rogue
7

Dans Java 8, nous avons plusieurs façons d'itérer sur les classes de collection.

Utiliser Iterable forEach

Les collections qui implémentent Iterable(par exemple toutes les listes) ont désormais une forEachméthode. Nous pouvons utiliser la référence de méthode introduite dans Java 8.

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

Utilisation de Streams forEach et forEachOrdered

Nous pouvons également parcourir une liste en utilisant Stream comme:

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

Nous devrions préférer forEachOrderedplutôt forEachque le comportement de forEachest explicitement non déterministe alors queforEachOrdered effectue une action pour chaque élément de ce flux, dans l'ordre de rencontre du flux si le flux a un ordre de rencontre défini. Ainsi, forEach ne garantit pas que la commande sera conservée.

L'avantage des flux est que nous pouvons également utiliser des flux parallèles le cas échéant. Si l'objectif est uniquement d'imprimer les articles quelle que soit la commande, nous pouvons utiliser le flux parallèle comme:

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

Je ne sais pas ce que vous considérez comme pathologique, mais permettez-moi de vous proposer quelques alternatives que vous n'auriez pas pu voir auparavant:

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

Ou sa version récursive:

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

En outre, une version récursive du classique 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);
}

Je les mentionne car vous êtes "un peu nouveau pour Java" et cela pourrait être intéressant.

Mario Rossi
la source
1
Merci de l'avoir mentionné. Je n'avais jamais regardé la méthode subList. Oui, je considérerais cela comme pathologique car je ne connais aucune circonstance où il serait jamais avantageux de l'utiliser en dehors peut-être des concours d'obscurcissement.
iX3
3
D'ACCORD. Je n'aime pas être appelé "pathologique" alors voici une explication: je les ai utilisés tout en suivant ou en suivant des chemins dans les arbres. Un de plus? En traduisant certains programmes Lisp en Java, je ne voulais pas qu'ils perdent leur esprit Lisp, et j'ai fait de même. Votez le commentaire si vous pensez que ces utilisations sont valides et non pathologiques. J'ai besoin d'un câlin de groupe !!! :-)
Mario Rossi
Les chemins dans les arbres ne sont-ils pas différents des listes? BTW, je ne voulais pas vous appeler ou toute personne "pathologique", je veux juste dire que certaines réponses à ma question seront naturellement peu pratiques ou très peu susceptibles d'avoir une valeur dans les bonnes pratiques de génie logiciel.
iX3
@ iX3 Ne vous inquiétez pas; Je plaisantais. Les chemins sont des listes: "commencer à la racine" (évident), "passer au 2ème enfant", "passer au 1er enfant", "passer au 4ème enfant". "Arrêtez". Ou [2,1,4] pour faire court. Ceci est une liste.
Mario Rossi
Je préférerais créer une copie de la liste et l'utiliser while(!copyList.isEmpty()){ E e = copyList.remove(0); ... }. C'est plus efficace que la première version;).
AxelH
2

Vous pouvez utiliser forEach à partir de Java 8:

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

 nameList.forEach((v) -> System.out.println(v));
Sudip Bhandari
la source
0

Pour une recherche en arrière, vous devez utiliser les éléments suivants:

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

Si vous voulez connaître une position, utilisez iterator.previousIndex (). Cela aide également à écrire une boucle interne qui compare deux positions dans la liste (les itérateurs ne sont pas égaux).

CoolMind
la source
0

À droite, de nombreuses alternatives sont répertoriées. Le plus simple et le plus propre serait simplement d'utiliser l' forinstruction améliorée comme ci-dessous. Le Expressionest d'un type qui est itérable.

for ( FormalParameter : Expression ) Statement

Par exemple, pour parcourir les identifiants List <String>, nous pouvons simplement le faire,

for (String str : ids) {
    // Do something
}
Yu Chen
la source
3
Il demande s'il existe d'autres moyens que ceux décrits à la question (dont celui que vous avez mentionné)!
ericbn
0

Dans, java 8vous pouvez utiliser la List.forEach()méthode avec lambda expressionpour parcourir une liste.

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);
                }
        );
    }
}
Résultats de recherche Résultats Web Pi
la source
Cool. Pourriez-vous expliquer en quoi cela diffère de eugene82la réponse et de i_am_zerola réponse ?
iX3
@ iX3 ahh. N'a pas lu toute la liste de réponses. J'essayais d'être utile. Voulez-vous que je supprime la réponse?
Résultats de la recherche Résultats Web Pi
Peu m'importe, mais peut-être pourriez-vous l'améliorer en le comparant et en le contrastant avec d'autres techniques. Ou si vous pensez qu'elle ne démontre aucune nouvelle technique mais qu'elle pourrait tout de même être utile comme référence pour d'autres, vous pourriez peut-être ajouter une note expliquant cela.
iX3
-2

Vous pouvez toujours changer les premier et troisième exemples avec une boucle while et un peu plus de code. Cela vous donne l'avantage de pouvoir utiliser le do-while:

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

Bien sûr, ce genre de chose peut provoquer une NullPointerException si list.size () renvoie 0, car il est toujours exécuté au moins une fois. Cela peut être corrigé en testant si l'élément est nul avant d'utiliser ses attributs / méthodes. Pourtant, il est beaucoup plus simple et plus facile d'utiliser la boucle for

shieldgenerator7
la source
C'est vrai ... Je suppose que c'est techniquement différent, mais le comportement n'est différent que si la liste est vide, non?
iX3
@ ix3 oui, et dans ce cas, le comportement est pire. Je n'appellerais pas cela une bonne alternative.
CPerkins
Bien sûr, mais en toute équité, cette question concerne moins ce qui est «bon» et plus ce qui est «possible», donc j'apprécie toujours cette réponse.
iX3