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

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

請注意,僅當我們使用原始byteshort, charint參數調用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
    • elementlist.get(i)在第3行都等於1 ,因此Java輸入if語句的主體,
    • 我們刪除索引為0的元素,
    • 所以list現在包含123
  • 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遍曆元素。但是,當我們修改ListIterator進入不一致狀態。因此,它拋出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上找到

0 條評論,你可以發表評論,我們會進行改進
Comment author placeholder