Entfernen Sie alle Vorkommen eines bestimmten Werts aus einer Liste

1. Einleitung

In Java ist es einfach, einen bestimmten Wert mit List.remove () aus einer Liste zu entfernen . Das effiziente Entfernen aller Vorkommen eines Werts ist jedoch viel schwieriger.

In diesem Tutorial sehen wir mehrere Lösungen für dieses Problem, in denen die Vor- und Nachteile beschrieben werden.

Aus Gründen der Lesbarkeit verwenden wir in den Tests eine benutzerdefinierte Listenmethode (int…) , die eine ArrayList zurückgibt, die die übergebenen Elemente enthält.

2. Verwenden einer while- Schleife

Da wir wissen, wie man ein einzelnes Element entfernt, sieht es einfach aus , es wiederholt in einer Schleife auszuführen:

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

Es funktioniert jedoch nicht wie erwartet:

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

Das Problem liegt in der dritten Zeile: Wir rufen List.remove (int) auf, das sein Argument als Index behandelt, nicht als den Wert, den wir entfernen möchten.

Im obigen Test rufen wir immer list.remove (1) auf , aber der Index, den wir entfernen möchten, ist 0. Durch Aufrufen von List.remove () werden alle Elemente nach dem entfernten auf kleinere Indizes verschoben .

In diesem Szenario bedeutet dies, dass wir alle Elemente außer dem ersten löschen.

Wenn nur der erste übrig bleibt, ist der Index 1 unzulässig. Daher bekommen wir eine Ausnahme .

Beachten Sie , dass wir dieses Problem nur stellen , wenn wir nennen List.remove () mit einem primitiven Byte , kurz gesagt, char oder int Argument, da das erste , was der Compiler tut , wenn er versucht , die passende überladene Methode zu finden, wird immer größer.

Wir können es korrigieren, indem wir den Wert als Integer übergeben:

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

Jetzt funktioniert der Code wie erwartet:

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

Da List.contains () und List.remove () beide das erste Vorkommen des Elements finden müssen, verursacht dieser Code unnötigen Elementdurchlauf.

Wir können es besser machen, wenn wir den Index des ersten Auftretens speichern:

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

Wir können überprüfen, ob es funktioniert:

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

Diese Lösungen erzeugen zwar kurzen und sauberen Code, weisen jedoch eine schlechte Leistung auf : Da wir den Fortschritt nicht verfolgen, muss List.remove () das erste Vorkommen des angegebenen Werts finden, um ihn zu löschen.

Wenn wir eine ArrayList verwenden , kann das Verschieben von Elementen viele Referenzkopien verursachen und sogar das Backing-Array mehrmals neu zuweisen.

3. Entfernen, bis sich die Liste ändert

List.remove (E-Element) hat eine Funktion, die wir noch nicht erwähnt haben: Es gibt einen booleschen Wert zurück. Dies ist der Fall, wenn sich die Liste aufgrund der Operation geändert hat und daher das Element enthält .

Beachten Sie, dass List.remove (int index) void zurückgibt. Wenn der angegebene Index gültig ist, wird er von der Liste immer entfernt. Andernfalls wird eine IndexOutOfBoundsException ausgelöst .

Damit können wir Entfernungen durchführen, bis sich die Liste ändert:

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

Es funktioniert wie erwartet:

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

Obwohl diese Implementierung kurz ist, weist sie dieselben Probleme auf, die wir im vorherigen Abschnitt beschrieben haben.

3. Verwenden einer for- Schleife

Wir können unseren Fortschritt verfolgen, indem wir die Elemente mit einer for- Schleife durchlaufen und die aktuelle entfernen, wenn sie übereinstimmt:

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

Es funktioniert wie erwartet:

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

Wenn wir es jedoch mit einer anderen Eingabe versuchen, liefert es eine falsche Ausgabe:

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

Lassen Sie uns Schritt für Schritt analysieren, wie der Code funktioniert:

  • i = 0
    • element und list.get (i) sind in Zeile 3 beide gleich 1 , sodass Java in den Hauptteil der if- Anweisung eingibt.
    • wir entfernen das Element am Index 0 ,
    • Die Liste enthält jetzt 1 , 2 und 3
  • i = 1
    • list.get (i) gibt 2 zurück, da beim Entfernen eines Elements aus einer Liste alle fortlaufenden Elemente auf kleinere Indizes verschoben werden

Wir stehen also vor diesem Problem, wenn wir zwei benachbarte Werte haben, die wir entfernen möchten . Um dies zu lösen, sollten wir die Schleifenvariable beibehalten.

Verringern Sie es, wenn wir das Element entfernen:

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

Erhöhen Sie es nur, wenn wir das Element nicht entfernen:

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

Aufgrund der Tatsache, dass die Liste selbst diese Methode implementiert, können wir davon ausgehen, dass sie die beste verfügbare Leistung aufweist. Darüber hinaus bietet diese Lösung den saubersten Code von allen.

9. Fazit

In diesem Artikel haben wir viele Möglichkeiten gesehen, ein einfaches Problem zu lösen, einschließlich falscher. Wir haben sie analysiert, um für jedes Szenario die beste Lösung zu finden.

Wie üblich sind die Beispiele auf GitHub verfügbar.