從列表中刪除所有出現的特定值

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:來更正它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由於操作而更改，則返回boolean值，則為true ，因此其中包含element** 。

請注意， 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的元素，
  • 所以list現在包含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刪除一個元素，將所有元素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

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

 }

 }

 }

這樣， 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));

由於每個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.時，此實現效果很好ArrayList.

此實現在某些方面的行為與早期的有所不同：

• 它不會修改原始List但會返回一個新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.使用Stream 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

借助lambda和功能接口，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上找到。