ArrayList algorithms: filter and the remove bug · ⁨Algorithmes ArrayList : filtrage et le bug remove⁩

English

Doing work on a whole list

Now you can store data in an ArrayList. Next we process it.
Common jobs: count items that match a rule, filter them into a new list, and remove some of them.
All of these use a loop over the list.

Français

Travailler sur toute une liste

Maintenant, vous pouvez stocker des données dans un ArrayList. La prochaine étape consiste à les traiter.
Tâches courantes : compter les éléments qui correspondent à une règle, les filtrer dans une nouvelle liste, et supprimer certains d'entre eux.
Toutes ces tâches utilisent une boucle sur la liste.

English

Counting with a rule

Walk the list, test each item, and add 1 to a counter when the test is true.
n % 2 == 0 is true when n is even. n % 2 != 0 is true when n is odd.
This only reads the list, so an enhanced for-loop is fine.

Français

Compter selon une règle

Parcourir la liste, tester chaque élément, et ajouter 1 à un compteur lorsque le test est vrai.
n % 2 == 0 est vrai si n est pair. n % 2 != 0 est vrai si n est impair.
Cela ne fait que lire la liste, donc une boucle for améliorée suffit.

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> nums = new ArrayList<Integer>();
        nums.add(4);
        nums.add(7);
        nums.add(10);
        nums.add(3);

        int evens = 0;
        for (int x : nums) {
            if (x % 2 == 0) {
                evens = evens + 1;
            }
        }
        System.out.println(evens);   // 2
    }
}

English

Filtering into a new list

Filtering keeps only the items that pass a test.
A safe pattern: make an empty new list, then add each item that passes.
The old list is not changed. This avoids the bug we see next.

Français

Filtrer dans une nouvelle liste

Le filtrage conserve uniquement les éléments qui passent le test.
Pattern sûr : créer une nouvelle liste vide, puis add chaque élément qui passe.
L'ancienne liste n'est pas modifiée. Cela évite le bug que nous verrons ci-dessous.

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> nums = new ArrayList<Integer>();
        nums.add(4);
        nums.add(7);
        nums.add(10);
        nums.add(3);

        ArrayList<Integer> bigOnes = new ArrayList<Integer>();
        for (int x : nums) {
            if (x >= 5) {
                bigOnes.add(x);
            }
        }
        System.out.println(bigOnes);   // [7, 10]
    }
}

English

The remove-while-iterating bug

It looks easy: loop forward and remove(i) the items you do not want.
But remove(i) shifts every later item one place left. The loop then adds 1 to i and skips the item that moved into the old spot.
The example below tries to remove all evens but misses one.

Français

Le bug de suppression lors de l'itération

Cela semble facile : boucler vers l'avant et remove(i) les éléments que vous ne voulez pas.
Mais remove(i) décale tous les éléments suivants d'une place vers la gauche. La boucle incrémente ensuite 1 vers i et saute l'élément qui s'est déplacé dans l'ancien emplacement.
L'exemple ci-dessous tente de supprimer tous les pairs mais en manque un.

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> nums = new ArrayList<Integer>();
        nums.add(2);
        nums.add(4);   // this one gets skipped!
        nums.add(5);

        // BUGGY: forward loop while removing
        for (int i = 0; i < nums.size(); i++) {
            if (nums.get(i) % 2 == 0) {
                nums.remove(i);
            }
        }
        System.out.println(nums);   // [4, 5]  -- wrong, 4 was missed
    }
}

English

Why it skips

Start: [2, 4, 5], i = 0. 2 is even, remove it. List becomes [4, 5].
The 4 slid down into index 0. But the loop now sets i = 1.
At i = 1 we look at 5, not 4. The 4 was never checked. It stays in.

Français

Pourquoi cela saute-t-il ?

Départ : [2, 4, 5], i = 0. 2 est pair, on le supprime. La liste devient [4, 5].
Le 4 a glissé dans l'index 0. Mais la boucle définit maintenant i = 1.
À i = 1, on regarde 5, pas 4. Le 4 n'a jamais été vérifié. Il reste dans la liste.

English

The fix: loop backwards

Walk from the last index down to 0.
When you remove index i, only items after i shift — and you have already passed those.
The indexes you still need to visit are smaller than i, so nothing moves out from under you.

Français

La solution : boucler vers l'arrière

Parcourir depuis l'index le plus grand jusqu'à 0.
Lorsque vous supprimez l'index i, seuls les éléments situés après i se déplacent — et vous avez déjà traité ceux-là.
Les indices que vous devez encore visiter sont plus petits que i, donc rien ne se décale sous vous.

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> nums = new ArrayList<Integer>();
        nums.add(2);
        nums.add(4);
        nums.add(5);

        // SAFE: backward loop while removing
        for (int i = nums.size() - 1; i >= 0; i--) {
            if (nums.get(i) % 2 == 0) {
                nums.remove(i);
            }
        }
        System.out.println(nums);   // [5]  -- correct
    }
}

English

A note on the enhanced for-loop

You may be tempted to remove inside for (int x : nums).
Do not. Changing the list size during an enhanced for-loop throws a ConcurrentModificationException and stops the program.
For removing, always use the backward index loop above.

Français

Remarque sur la boucle for améliorée

Vous serez tenté de supprimer à l'intérieur de for (int x : nums).
Ne le faites pas. La modification de la taille de la liste pendant une boucle for améliorée lève une ConcurrentModificationException et arrête le programme.
Pour supprimer, utilisez toujours la boucle à index inverse ci-dessus.

English

Common mistakes

Removing while looping forward by index skips the next item (the remove bug).
Loop backwards, or use an iterator, when removing.

Français

Erreurs courantes

Supprimer tout en bouclant vers l'avant par index saute l'élément suivant (le bug de suppression).
Boucler vers l'arrière, ou utiliser un itérateur, pour supprimer.

English

Now you try

Each task pre-fills the class skeleton — write your code inside main, or complete the method shown.
Press Run to compile and run, then Check answer.
Your code compiles and runs on the server, so even the first run is fast.

Français

À vous maintenant

Chaque tâche préremplit le squelette de classe — écrivez votre code dans main, ou complétez la méthode montrée.
Appuyez sur Exécuter pour compiler et exécuter, puis sur Vérifier la réponse.
Votre code compile et s'exécute sur le serveur, donc même la première exécution est rapide.

Explore · ⁨Explorer⁩

Filtering a list · ⁨Filtrage d'une liste⁩

Removing while looping shifts indices — step through to see why. · ⁨Supprimer pendant la boucle décale les indices — faites-le étape par étape pour voir pourquoi.⁩

Complete countOdds(ArrayList<Integer> a) so it returns how many numbers in the list are odd. A number is odd when x % 2 != 0. · ⁨Complétez countOdds(ArrayList<Integer> a) pour qu'elle retourne combien de nombres de la liste sont impairs. Un nombre est impair quand x % 2 != 0.⁩

import java.util.ArrayList;

public class ListUtil {
    // Return how many numbers in a are odd.
    public static int countOdds(ArrayList<Integer> a) {
        return 0;   // change this
    }
}

Click Run to see the output here. · ⁨Cliquez sur Exécuter pour voir le résultat ici.⁩

Complete keepPositives(ArrayList<Integer> a). Build and return a new ArrayList<Integer> that holds only the numbers greater than 0, in their original order. Do not · ⁨non⁩ change · ⁨ changement ⁩a. · ⁨Complétez keepPositives(ArrayList<Integer> a). Construisez et retournez un nouveau ArrayList<Integer> qui contient uniquement les nombres supérieurs à 0, dans leur ordre d'origine. Ne modifiez pas a.⁩

import java.util.ArrayList;

public class ListUtil {
    // Return a new list with only the numbers > 0.
    public static ArrayList<Integer> keepPositives(ArrayList<Integer> a) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        // add the positives here
        return result;
    }
}

Click Run to see the output here. · ⁨Cliquez sur Exécuter pour voir le résultat ici.⁩

Complete removeEvens(ArrayList<Integer> a) so it removes every even number from a itself. Loop backwards by index so you do not skip items. Return nothing (void). · ⁨Complétez removeEvens(ArrayList<Integer> a) pour qu'elle supprime tous les nombres pairs de a lui-même. Bouclez vers l'arrière par indice pour ne pas sauter d'éléments. Ne retournez rien (void).⁩

import java.util.ArrayList;

public class ListUtil {
    // Remove every even number from a. Loop backwards!
    public static void removeEvens(ArrayList<Integer> a) {
        // your code here
    }
}

Click Run to see the output here. · ⁨Cliquez sur Exécuter pour voir le résultat ici.⁩

ArrayList algorithms: filter and the remove bug · ⁨Algorithmes ArrayList : filtrage et le bug remove⁩

Doing work on a whole list

Travailler sur toute une liste

Counting with a rule

Compter selon une règle

Filtering into a new list

Filtrer dans une nouvelle liste

The remove-while-iterating bug

Le bug de suppression lors de l'itération

Why it skips

Pourquoi cela saute-t-il ?

The fix: loop backwards

La solution : boucler vers l'arrière

A note on the enhanced for-loop

Remarque sur la boucle for améliorée

Common mistakes

Erreurs courantes

Now you try

À vous maintenant

Filtering a list · ⁨Filtrage d'une liste⁩

Handout · ⁨Fiche de cours⁩

Log in or create account · ⁨Se connecter ou créer un compte⁩

Your subject · ⁨Votre matière⁩

All sections · ⁨Toutes les sections⁩

Feedback & help · ⁨Retours & aide⁩