Eliminar todas las apariciones de un valor específico de una lista

1. Introducción

En Java, es sencillo eliminar un valor específico de una Lista usando List.remove () . Sin embargo, eliminar de manera eficiente todas las apariciones de un valor es mucho más difícil.

En este tutorial, veremos múltiples soluciones a este problema, describiendo los pros y los contras.

En aras de la legibilidad, usamos un método de lista personalizada (int…) en las pruebas, que devuelve una ArrayList que contiene los elementos que pasamos.

2. Usar un bucle while

Como sabemos cómo eliminar un solo elemento, hacerlo repetidamente en un bucle parece bastante simple:

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

Sin embargo, no funciona como se esperaba:

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

El problema está en la tercera línea: llamamos List.remove (int), que trata su argumento como el índice, no como el valor que queremos eliminar.

En la prueba anterior siempre llamamos a list.remove (1) , pero el índice del elemento que queremos eliminar es 0. Llamar a List.remove () desplaza todos los elementos después del eliminado a índices más pequeños.

En este escenario, significa que eliminamos todos los elementos, excepto el primero.

Cuando solo quede el primero, el índice 1 será ilegal. Por lo tanto, obtenemos una excepción .

Tenga en cuenta que nos enfrentamos a este problema solo si llamamos a List.remove () con un argumento de byte primitivo , short, char o int , ya que lo primero que hace el compilador cuando intenta encontrar el método sobrecargado coincidente es ampliar.

Podemos corregirlo pasando el valor como Integer:

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

Ahora el código funciona como se esperaba:

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

Dado que List.contains () y List.remove () tienen que encontrar la primera aparición del elemento, este código provoca un cruce innecesario del elemento.

Podemos hacerlo mejor si almacenamos el índice de la primera aparición:

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

Podemos verificar que funciona:

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

Si bien estas soluciones producen código corto y limpio, aún tienen un rendimiento deficiente : debido a que no hacemos un seguimiento del progreso, List.remove () tiene que encontrar la primera aparición del valor proporcionado para eliminarlo.

Además, cuando usamos una ArrayList , el cambio de elementos puede causar muchas copias de referencia, incluso reasignar la matriz de respaldo varias veces.

3. Extracción Hasta la Lista de Cambios

List.remove (elemento E) tiene una característica que no mencionamos todavía: devuelve un valor booleano , que es verdadero si la lista cambió debido a la operación, por lo tanto, contenía el elemento .

Tenga en cuenta que List.remove (int index) devuelve void, porque si el índice proporcionado es válido, List siempre lo elimina. De lo contrario, arroja IndexOutOfBoundsException .

Con esto, podemos realizar eliminaciones hasta que cambie la Lista :

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

Funciona como se esperaba:

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

A pesar de ser breve, esta implementación adolece de los mismos problemas que describimos en el apartado anterior.

3. Uso de un bucle for

Podemos realizar un seguimiento de nuestro progreso atravesando los elementos con un bucle for y eliminar el actual si coincide:

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

Funciona como se esperaba:

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

Sin embargo, si lo probamos con una entrada diferente, proporciona una salida incorrecta:

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

Analicemos cómo funciona el código, paso a paso:

  • i = 0
    • element y list.get (i) son ambos iguales a 1 en la línea 3, por lo que Java ingresa al cuerpo de la declaración if ,
    • eliminamos el elemento en el índice 0 ,
    • entonces la lista ahora contiene 1 , 2 y 3
  • i = 1
    • list.get (i) devuelve 2 porque cuando eliminamos un elemento de una lista , cambia todos los elementos anteriores a índices más pequeños

Entonces nos enfrentamos a este problema cuando tenemos dos valores adyacentes, que queremos eliminar . Para resolver esto, debemos mantener la variable de ciclo.

Disminuirlo cuando eliminamos el elemento:

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--; } } }

Aumentándolo solo cuando no eliminamos el elemento:

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

Debido al hecho de que la propia Lista implementa este método, podemos asumir con seguridad que tiene el mejor rendimiento disponible. Además de eso, esta solución proporciona el código más limpio de todos.

9. Conclusión

En este artículo, vimos muchas formas de resolver un problema simple, incluidos los incorrectos. Los analizamos para encontrar la mejor solución para cada escenario.

Como de costumbre, los ejemplos están disponibles en GitHub.