书签

从列表中删除所有出现的特定值

评论 0 浏览 0 2018-08-07

1.绪论

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

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

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

2.使用while循环

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

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

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

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

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

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

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

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

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

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

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

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

现在，代码按预期工作了。

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

// when
removeAll(list, valueToRemove);

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

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

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

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

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

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

// when
removeAll(list, valueToRemove);

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

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

另外，当我们使用ArrayList时，元素移动会导致多次引用复制，甚至多次重新分配后备数组。

3.删除，直到List改变为止

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

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

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

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

它的工作原理和预期的一样。

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

// when
removeAll(list, valueToRemove);

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

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

3.使用for循环

我们可以通过用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);
        }
    }
}

它的工作原理和预期的一样。

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

// when
removeAll(list, valueToRemove);

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

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

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

// when
removeAll(list, valueToRemove);

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

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

  • i = 0
    • element 和 list.get(i) 在第 3 行都等于 1，所以 Java 进入了 if声明，
    • 我们删除索引0处的元素。
    • 所以列表中现在包含了1、2和3
  • i = 1
    • list.get(i)返回2，因为当我们从List中移除一个元素时，它会将所有继续进行的元素转移到更小的索引上。

因此，当我们有两个相邻的值，而我们想移除这些值时，我们会面临这个问题。为了解决这个问题，我们应该维护循环变量。

当我们删除该元素时，会减少它。

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

只有当我们不删除元素时才会增加它。

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

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

这两种解决方案都能如愿以偿地工作。

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

// when
removeAll(list, valueToRemove);

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

这种实现方式乍看之下是正确的。然而，它仍然有严重的性能问题。

  • 从ArrayList中删除一个元素，将其后面的所有项目都移开。
  • 在LinkedList中按索引访问元素，意味着逐一遍历元素，直到找到索引为止

4.使用for-each循环

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

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

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

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

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

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

// when
assertThatThrownBy(() -> removeWithForEachLoop(list, valueToRemove))
  .isInstanceOf(ConcurrentModificationException.class);

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

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

5.使用一个迭代器

我们可以直接使用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();
        }
    }
}

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

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

// when
removeAll(list, valueToRemove);

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

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

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

6.采集

在这之前，我们通过删除我们不需要的项目来修改原来的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;
}

由于我们在一个新的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));

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

因为没有任何移除，所以不需要对元素进行转移。因此，当我们使用一个ArrayList.时，这个实现表现得很好。

这个实现在某些方面的表现与之前的不同。

  • 它并不修改原始的List，而是返回一个新的的。
  • 该方法决定返回的List的实现是什么，它可能与原来的不同

另外，我们可以修改我们的实现，以获得旧的行为；我们清除原来的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);
}

它的工作方式与之前的那些相同。

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

// when
removeAll(list, valueToRemove);

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

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

7.使用流API

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

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

这个解决方案以同样的方式运作，就像我们在收集剩余的元素时一样。

作为一个结果，它具有相同的特征，我们应该用它来返回结果。

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

请注意，我们可以通过与最初的‘收集'实现相同的方法，将其转换为与其他解决方案一样的工作。

8.使用removeIf

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

它需要一个 Predicate，当我们想要删除元素时它应该返回 true，这与前面的例子相反，在我们想要保留元素时我们必须返回 true：

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

它的工作原理与上面的其他解决方案一样。

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

// when
removeAll(list, valueToRemove);

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

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

9.结语

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

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

最后更新2022-12-22
0 个评论
标签
Java List