Algorithmes ArrayList : filtrage et le bug remove
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.
Compter selon une règle
- Parcourir la liste, tester chaque élément, et ajouter
1à un compteur lorsque le test est vrai. n % 2 == 0est vrai sinest pair.n % 2 != 0est vrai sinest 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
}
}
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
addchaque é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]
}
}
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 ensuite1versiet 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
}
}
Pourquoi cela saute-t-il ?
- Départ :
[2, 4, 5],i = 0.2est pair, on le supprime. La liste devient[4, 5]. - Le
4a glissé dans l'index0. Mais la boucle définit maintenanti = 1. - À
i = 1, on regarde5, pas4. Le4n'a jamais été vérifié. Il reste dans la liste.
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èsise 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
}
}
Remarque sur la boucle for améliorée
- Vous serez tenté de supprimer à l'intérieur de
for (int x : nums). - Ne pas le faire. Modifier la taille d'une liste pendant une boucle for-améliorée provoque généralement une exception
ConcurrentModificationException, et lorsque cela ne se produit pas, des éléments sont silencieusement ignorés. Utilisez plutôt une boucle par indice. - Pour supprimer, utilisez toujours la boucle à index inverse ci-dessus.
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.
À vous maintenant
- Chaque tâche préremplit le squelette de classe — écrivez votre code dans main, ou complétez la méthode montrée.
- Utilisez Vérifier la réponse pour compiler votre code avec les tests fournis et voir les résultats. Conservez les interfaces de classe et de méthode montrées dans l'en-tête.
- Votre code compile et s'exécute sur le serveur, donc même la première exécution est rapide.
Filtrage d'une liste
Supprimer pendant la boucle décale les indices — faites-le étape par étape pour voir pourquoi.
Difficulté 3/5 · 200 pièces + un petit bonus lors de la première réussite aujourd'hui
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.
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 3/5 · 200 pièces + un petit bonus lors de la première réussite aujourd'hui
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.
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 3/5 · 200 pièces + un petit bonus lors de la première réussite aujourd'hui
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).
Cliquez sur Exécuter pour voir le résultat ici.