Supprimer toutes les occurrences d'une valeur spécifique d'une liste

1. Introduction

En Java, il est simple de supprimer une valeur spécifique d'une liste à l' aide de List.remove () . Cependant, supprimer efficacement toutes les occurrences d'une valeur est beaucoup plus difficile.

Dans ce didacticiel, nous verrons plusieurs solutions à ce problème, décrivant les avantages et les inconvénients.

Pour des raisons de lisibilité, nous utilisons une méthode de liste personnalisée (int…) dans les tests, qui renvoie une ArrayList contenant les éléments que nous avons passés.

2. Utilisation d'une boucle while

Puisque nous savons comment supprimer un seul élément, le faire à plusieurs reprises dans une boucle semble assez simple:

void removeAll(List list, int element) { while (list.contains(element)) { list.remove(element); } }

Cependant, cela ne fonctionne pas comme prévu:

// given List list = list(1, 2, 3); int valueToRemove = 1; // when assertThatThrownBy(() -> removeAll(list, valueToRemove)) .isInstanceOf(IndexOutOfBoundsException.class);

Le problème est dans la 3ème ligne: nous appelons List.remove (int), qui traite son argument comme l'index, pas la valeur que nous voulons supprimer.

Dans le test ci-dessus, nous appelons toujours list.remove (1) , mais l'index de l'élément que nous voulons supprimer est 0. L' appel de List.remove () déplace tous les éléments après celui qui a été supprimé vers des index plus petits.

Dans ce scénario, cela signifie que nous supprimons tous les éléments, sauf le premier.

Lorsqu'il ne reste que le premier, l'indice 1 sera illégal. Par conséquent, nous obtenons une exception .

Notez que nous ne sommes confrontés à ce problème que si nous appelons List.remove () avec un argument primitif byte , short, char ou int , puisque la première chose que fait le compilateur lorsqu'il tente de trouver la méthode surchargée correspondante, est de s'élargir.

Nous pouvons le corriger en passant la valeur comme Integer:

void removeAll(List list, Integer element) { while (list.contains(element)) { list.remove(element); } }

Maintenant, le code fonctionne comme prévu:

// given List list = list(1, 2, 3); int valueToRemove = 1; // when removeAll(list, valueToRemove); // then assertThat(list).isEqualTo(list(2, 3));

Puisque List.contains () et List.remove () doivent tous deux trouver la première occurrence de l'élément, ce code provoque une traversée inutile des éléments.

Nous pouvons faire mieux si nous stockons l'index de la première occurrence:

void removeAll(List list, Integer element) { int index; while ((index = list.indexOf(element)) >= 0) { list.remove(index); } }

Nous pouvons vérifier que cela fonctionne:

// given List list = list(1, 2, 3); int valueToRemove = 1; // when removeAll(list, valueToRemove); // then assertThat(list).isEqualTo(list(2, 3));

Bien que ces solutions produisent du code court et propre, elles ont toujours des performances médiocres : parce que nous ne suivons pas la progression, List.remove () doit trouver la première occurrence de la valeur fournie pour la supprimer.

De plus, lorsque nous utilisons une ArrayList , le déplacement des éléments peut entraîner de nombreuses copies de références, voire réallouer plusieurs fois le tableau de sauvegarde.

3. Suppression jusqu'à ce que la liste change

List.remove (élément E) a une fonctionnalité que nous n'avons pas encore mentionnée: il renvoie une valeur booléenne , qui est vraie si la liste a changé à cause de l'opération, donc elle contenait l'élément .

Notez que List.remove (int index) renvoie void, car si l'index fourni est valide, List le supprime toujours. Sinon, il lève IndexOutOfBoundsException .

Avec cela, nous pouvons effectuer des suppressions jusqu'à ce que la liste change:

void removeAll(List list, int element) { while (list.remove(element)); }

Cela fonctionne comme prévu:

// given List list = list(1, 1, 2, 3); int valueToRemove = 1; // when removeAll(list, valueToRemove); // then assertThat(list).isEqualTo(list(2, 3));

Bien qu'elle soit courte, cette implémentation souffre des mêmes problèmes que ceux décrits dans la section précédente.

3. Utilisation d'une boucle for

Nous pouvons suivre notre progression en parcourant les éléments avec une boucle for et en supprimant l'actuelle si elle correspond:

void removeAll(List list, int element) { for (int i = 0; i < list.size(); i++) { if (Objects.equals(element, list.get(i))) { list.remove(i); } } }

Cela fonctionne comme prévu:

// given List list = list(1, 2, 3); int valueToRemove = 1; // when removeAll(list, valueToRemove); // then assertThat(list).isEqualTo(list(2, 3));

Cependant, si nous l'essayons avec une entrée différente, cela fournit une sortie incorrecte:

// given List list = list(1, 1, 2, 3); int valueToRemove = 1; // when removeAll(list, valueToRemove); // then assertThat(list).isEqualTo(list(1, 2, 3));

Analysons le fonctionnement du code, étape par étape:

  • i = 0
    • element and list.get(i) are both equal to 1 at line 3, so Java enters the body of the if statement,
    • we remove the element at index 0,
    • so list now contains 1, 2 and 3
  • i = 1
    • list.get(i) returns 2 because when we remove an element from a List, it shifts all proceeding elements to smaller indices

So we face this problem when we have two adjacent values, which we want to remove. To solve this, we should maintain the loop variable.

Decreasing it when we remove the element:

void removeAll(List list, int element) { for (int i = 0; i < list.size(); i++) { if (Objects.equals(element, list.get(i))) { list.remove(i); i--; } } }

Increasing it only when we don't remove the element:

void removeAll(List list, int element) { for (int i = 0; i < list.size();) { if (Objects.equals(element, list.get(i))) { list.remove(i); } else { i++; } } }

Note, that in the latter, we removed the statement i++ at line 2.

Both solutions work as expected:

// given List list = list(1, 1, 2, 3); int valueToRemove = 1; // when removeAll(list, valueToRemove); // then assertThat(list).isEqualTo(list(2, 3));

This implementation seems right for the first sight. However, it still has serious performance problems:

  • removing an element from an ArrayList, shifts all items after it
  • accessing elements by index in a LinkedList means traversing through the elements one-by-one until we find the index

4. Using a for-each Loop

Since Java 5 we can use the for-each loop to iterate through a List. Let's use it to remove elements:

void removeAll(List list, int element) { for (Integer number : list) { if (Objects.equals(number, element)) { list.remove(number); } } }

Note, that we use Integer as the loop variable's type. Therefore we won't get a NullPointerException.

Also, this way we invoke List.remove(E element), which expects the value we want to remove, not the index.

As clean as it looks, unfortunately, it doesn't work:

// given List list = list(1, 1, 2, 3); int valueToRemove = 1; // when assertThatThrownBy(() -> removeWithForEachLoop(list, valueToRemove)) .isInstanceOf(ConcurrentModificationException.class);

The for-each loop uses Iterator to traverse through the elements. However, when we modify the List, the Iterator gets into an inconsistent state. Hence it throws ConcurrentModificationException.

The lesson is: we shouldn't modify a List, while we're accessing its elements in a for-each loop.

5. Using an Iterator

We can use the Iterator directly to traverse and modify the List with it:

void removeAll(List list, int element) { for (Iterator i = list.iterator(); i.hasNext();) { Integer number = i.next(); if (Objects.equals(number, element)) { i.remove(); } } }

This way, the Iterator can track the state of the List (because it makes the modification). As a result, the code above works as expected:

// given List list = list(1, 1, 2, 3); int valueToRemove = 1; // when removeAll(list, valueToRemove); // then assertThat(list).isEqualTo(list(2, 3));

Since every List class can provide their own Iterator implementation, we can safely assume, that it implements element traversing and removal the most efficient way possible.

However, using ArrayList still means lots of element shifting (and maybe array reallocating). Also, the code above is slightly harder to read, because it differs from the standard for loop, that most developers are familiar with.

6. Collecting

Until this, we modified the original List object by removing the items we didn't need. Rather, we can create a new List and collect the items we want to keep:

List removeAll(List list, int element) { List remainingElements = new ArrayList(); for (Integer number : list) { if (!Objects.equals(number, element)) { remainingElements.add(number); } } return remainingElements; }

Since we provide the result in a new List object, we have to return it from the method. Therefore we need to use the method in another way:

// given List list = list(1, 1, 2, 3); int valueToRemove = 1; // when List result = removeAll(list, valueToRemove); // then assertThat(result).isEqualTo(list(2, 3));

Note, that now we can use the for-each loop since we don't modify the List we're currently iterating through.

Because there aren't any removals, there's no need to shift the elements. Therefore this implementation performs well when we use an ArrayList.

This implementation behaves differently in some ways than the earlier ones:

  • it doesn't modify the original List but returns a new one
  • the method decides what the returned List‘s implementation is, it may be different than the original

Also, we can modify our implementation to get the old behavior; we clear the original List and add the collected elements to it:

void removeAll(List list, int element) { List remainingElements = new ArrayList(); for (Integer number : list) { if (!Objects.equals(number, element)) { remainingElements.add(number); } } list.clear(); list.addAll(remainingElements); }

It works the same way the ones before:

// given List list = list(1, 1, 2, 3); int valueToRemove = 1; // when removeAll(list, valueToRemove); // then assertThat(list).isEqualTo(list(2, 3));

Since we don't modify the List continually, we don't have to access elements by position or shift them. Also, there're only two possible array reallocations: when we call List.clear() and List.addAll().

7. Using the Stream API

Java 8 introduced lambda expressions and stream API. With these powerful features, we can solve our problem with a very clean code:

List removeAll(List list, int element) { return list.stream() .filter(e -> !Objects.equals(e, element)) .collect(Collectors.toList()); }

This solution works the same way, like when we were collecting the remaining elements.

As a result, it has the same characteristics, and we should use it to return the result:

// given List list = list(1, 1, 2, 3); int valueToRemove = 1; // when List result = removeAll(list, valueToRemove); // then assertThat(result).isEqualTo(list(2, 3));

Note, that we can convert it to work like the other solutions with the same approach we did with the original ‘collecting' implementation.

8. Using removeIf

With lambdas and functional interfaces, Java 8 introduced some API extensions, too. For example, the List.removeIf() method, which implements what we saw in the last section.

It expects a Predicate, which should return true when we want to remove the element, in contrast to the previous example, where we had to return true when we wanted to keep the element:

void removeAll(List list, int element) { list.removeIf(n -> Objects.equals(n, element)); }

It works like the other solutions above:

// given List list = list(1, 1, 2, 3); int valueToRemove = 1; // when removeAll(list, valueToRemove); // then assertThat(list).isEqualTo(list(2, 3));

Du fait que la liste elle-même implémente cette méthode, nous pouvons supposer en toute sécurité qu'elle a les meilleures performances disponibles. En plus de cela, cette solution fournit le code le plus propre de tous.

9. Conclusion

Dans cet article, nous avons vu de nombreuses façons de résoudre un problème simple, y compris des problèmes incorrects. Nous les avons analysés pour trouver la meilleure solution pour chaque scénario.

Comme d'habitude, les exemples sont disponibles à l'adresse over sur GitHub.