Remove All Occurrences of a Specific Value from a List – 从列表中删除一个特定值的所有出现次数

1. Introduction

1.绪论

In Java, it’s straightforward to remove a specific value from a List using List.remove(). However, efficiently removing all occurrences of a value is much harder.

在Java中，使用List.remove()从List中删除一个特定的值是很直接的。然而，有效地删除一个值的所有出现要难得多。

In this tutorial, we’ll see multiple solutions to this problem, describing the pros and cons.

在本教程中，我们将看到这个问题的多种解决方案，描述其优点和缺点。

For the sake of readability, we use a custom list(int…) method in the tests, which returns an ArrayList containing the elements we passed.

为了便于阅读，我们在测试中使用了一个自定义的list(int…)方法，它返回一个ArrayList，包含我们传递的元素。

2. Using a while Loop

2.使用while循环

Since we know how to remove a single element, doing it repeatedly in a loop looks simple enough:

既然我们知道如何删除一个元素，那么在一个循环中重复做这个动作看起来很简单。

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

However, it doesn’t work as expected:

然而，它并不像预期的那样工作。

// given
List<Integer> list = list(1, 2, 3);
int valueToRemove = 1;

// when
assertThatThrownBy(() -> removeAll(list, valueToRemove))
  .isInstanceOf(IndexOutOfBoundsException.class);

The problem is in the 3rd line: we call List.remove(int), which treats its argument as the index, not the value we want to remove.

问题出在第三行：我们调用List.remove(int),，它将其参数视为索引，而不是我们想要删除的值。

In the test above we always call list.remove(1), but the element’s index we want to remove is 0. Calling List.remove() shifts all elements after the removed one to smaller indices.

在上面的测试中，我们总是调用list.remove(1)，但是我们想要移除的元素的索引是0.调用List.remove()将移除的元素之后的所有元素转移到更小的索引。

In this scenario, it means that we delete all elements, except the first.

在这种情况下，这意味着我们删除所有的元素，除了第一个。

When only the first remains, the index 1 will be illegal. Hence we get an Exception.

当只剩下第一个时，索引1将是非法的。因此，我们得到一个Exception。

Note, that we face this problem only if we call List.remove() with a primitive byte, short, char or int argument, since the first thing the compiler does when it tries to find the matching overloaded method, is widening.

请注意，只有当我们用原始的byte、short、char或int参数调用List.remove()时，我们才会面临这个问题，因为当编译器试图找到匹配的重载方法时，它首先做的是拓扑。

We can correct it by passing the value as Integer:

我们可以通过将值传递为Integer:来纠正它。

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

Now the code works as expected:

现在，代码按预期工作。

// given
List<Integer> list = list(1, 2, 3);
int valueToRemove = 1;

// when
removeAll(list, valueToRemove);

// then
assertThat(list).isEqualTo(list(2, 3));

Since List.contains() and List.remove() both have to find the first occurrence of the element, this code causes unnecessary element traversal.

因为List.contains()和List.remove()都必须找到该元素的第一次出现，这段代码会导致不必要的元素遍历。

We can do better if we store the index of the first occurrence:

如果我们存储第一次出现的索引，我们可以做得更好。

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

We can verify that it works:

我们可以验证它是否有效。

// given
List<Integer> list = list(1, 2, 3);
int valueToRemove = 1;

// when
removeAll(list, valueToRemove);

// then
assertThat(list).isEqualTo(list(2, 3));

While these solutions produce short and clean code, they still have poor performance: because we don’t keep track of the progress, List.remove() has to find the first occurrence of the provided value to delete it.

虽然这些解决方案产生了简短而干净的代码，它们的性能仍然很差：因为我们没有跟踪进度，List.remove()必须找到所提供值的第一次出现来删除它。

Also, when we use an ArrayList, element shifting can cause many reference copying, even reallocating the backing array several times.

另外，当我们使用ArrayList时，元素移位会导致许多引用的复制，甚至重新分配数组的支持。

3. Removing Until the List Changes

3.删除，直到列表改变为止

List.remove(E element) has a feature we didn’t mention yet: it returns a boolean value, which is true if the List changed because of the operation, therefore it contained the element.

List.remove(E element)有一个我们还没有提到的特性：它返回一个boolean值，如果List因为操作而改变，因此它包含了该元素，这个值就是true。

Note, that List.remove(int index) returns void, because if the provided index is valid, the List always removes it. Otherwise, it throws IndexOutOfBoundsException.

注意，List.remove(int index)返回无效，因为如果提供的索引是有效的，List总是将其删除。否则，它会抛出IndexOutOfBoundsException。

With this, we can perform removals until the List changes:

有了这个，我们就可以进行删除，直到List发生变化。

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

It works as expected:

它像预期的那样工作。

// given
List<Integer> list = list(1, 1, 2, 3);
int valueToRemove = 1;

// when
removeAll(list, valueToRemove);

// then
assertThat(list).isEqualTo(list(2, 3));

Despite being short, this implementation suffers from the same problems we described in the previous section.

尽管很短，但这种实现方式也存在着我们在上一节中描述的问题。

3. Using a for Loop

3.使用for循环

We can keep track of our progress by traversing through the elements with a for loop and remove the current one if it matches:

我们可以通过用for循环遍历元素来跟踪我们的进展，如果当前的元素匹配，就删除它。

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

It works as expected:

它像预期的那样工作。

// given
List<Integer> list = list(1, 2, 3);
int valueToRemove = 1;

// when
removeAll(list, valueToRemove);

// then
assertThat(list).isEqualTo(list(2, 3));

However, if we try it with a different input, it provides an incorrect output:

然而，如果我们用不同的输入试试，它就会提供一个不正确的输出。

// given
List<Integer> list = list(1, 1, 2, 3);
int valueToRemove = 1;

// when
removeAll(list, valueToRemove);

// then
assertThat(list).isEqualTo(list(1, 2, 3));

Let’s analyze how the code works, step-by-step:

让我们一步一步地分析一下代码是如何工作的。

• 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<Integer> 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<Integer> 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.

注意，在后者中，我们删除了第2行的语句i++。

Both solutions work as expected:

这两种解决方案都如预期的那样工作。

// given
List<Integer> 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

4.使用for-each循环

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

从Java 5开始，我们可以使用for-each循环来迭代一个List。让我们用它来删除元素。

void removeAll(List<Integer> 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.

注意，我们使用Integer作为循环变量的类型。因此，我们不会得到一个NullPointerException。

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

另外，这种方式我们调用List.remove(E element)，它期望我们要删除的值，而不是索引。

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

虽然看起来很干净，但不幸的是，它并不工作。

// given
List<Integer> 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.

for-each循环使用Iterator来遍历这些元素。然而，当我们修改List时，Iterator会进入一个不一致的状态。因此它抛出了ConcurrentModificationException。

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

教训是：当我们在for-each循环中访问一个List的元素时，我们不应该修改它。

5. Using an Iterator

5.使用一个迭代器

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

我们可以直接使用Iterator，用它来遍历和修改List。

void removeAll(List<Integer> list, int element) {
    for (Iterator<Integer> 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:

这样，Iterator可以跟踪List的状态（因为它进行了修改）。结果是，上面的代码如期工作。

// given
List<Integer> 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.

由于每个List类都可以提供自己的Iterator实现，我们可以安全地假设，它以最有效的方式实现元素的遍历和移除。

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.

然而，使用ArrayList仍然意味着大量的元素移位（也许还有数组的重新分配）。另外，上面的代码稍微有点难读，因为它与大多数开发者熟悉的标准for循环不同。

6. Collecting

6.采集

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对象。相反，我们可以创建一个新的List并收集我们想保留的项目。

List<Integer> removeAll(List<Integer> list, int element) {
    List<Integer> 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:

由于我们在一个新的List对象中提供了结果，我们必须从该方法中返回它。因此，我们需要以另一种方式使用该方法。

// given
List<Integer> list = list(1, 1, 2, 3);
int valueToRemove = 1;

// when
List<Integer> 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.

注意，现在我们可以使用for-each循环，因为我们不会修改我们目前正在迭代的List。

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

因为没有任何移除，所以不需要对元素进行转移。因此，当我们使用一个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:

另外，我们可以修改我们的实现，以获得旧的行为；我们清除原来的List，并将收集的元素添加到其中。

void removeAll(List<Integer> list, int element) {
    List<Integer> 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<Integer> 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().

由于我们没有持续地修改List，所以我们不必通过位置来访问元素或移动它们。另外，只有两种可能的数组重新分配：当我们调用List.clear()和List.addAll()时。

7. Using the Stream API

7.使用流API

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

Java 8引入了lambda表达式和流API。有了这些强大的功能，我们可以用非常简洁的代码来解决我们的问题。

List<Integer> removeAll(List<Integer> 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<Integer> list = list(1, 1, 2, 3);
int valueToRemove = 1;

// when
List<Integer> 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

8.使用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.

通过lambdas和功能接口，Java 8也引入了一些API扩展。例如，List.removeIf()方法，它实现了我们在上一节看到的内容。

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:

它期待一个Predicate，当我们想移除元素时，它应该返回true，与之前的例子相反，当我们想保留该元素时，我们必须返回true。

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

It works like the other solutions above:

它的作用与上述其他解决方案一样。

// given
List<Integer> list = list(1, 1, 2, 3);
int valueToRemove = 1;

// when
removeAll(list, valueToRemove);

// then
assertThat(list).isEqualTo(list(2, 3));

Due to the fact, that the List itself implements this method, we can safely assume, that it has the best performance available. On top of that, this solution provides the cleanest code of all.

由于List本身实现了这个方法，我们可以有把握地认为，它具有最佳的性能。最重要的是，这个解决方案提供了最简洁的代码。

9. Conclusion

9.结语

In this article, we saw many ways to solve a simple problem, including incorrect ones. We analyzed them to find the best solution for every scenario.

在这篇文章中，我们看到了许多解决一个简单问题的方法，包括不正确的方法。我们对它们进行了分析，以便为每种情况找到最佳解决方案。

As usual, the examples are available over on GitHub.

像往常一样，这些例子可以在GitHub上找到over。