List刪除所有指定元素
環(huán)境:jdk8
1.概要
java中List使用List.remove()直接刪除指定元素,然而高效刪除元素是很難, 在本文章中介紹多種
方法,討論其中優(yōu)點(diǎn)和缺點(diǎn),為了可讀性,我創(chuàng)建list(int…) 方法在測(cè)試類中,返回ArrayList
2.使用while循環(huán)
知道如何刪除一個(gè)元素，然后循環(huán)刪除肌蜻，看下簡(jiǎn)單例子
void removeAll(List<Integer> list, int element) {
while (list.contains(element)) {
list.remove(element);
}
}
然而執(zhí)行下面會(huì)報(bào)錯(cuò)
// given
List<Integer> list = list(1, 2, 3);
int valueToRemove = 1;
// when
assertThatThrownBy(() -> removeAll(list, valueToRemove))
.isInstanceOf(IndexOutOfBoundsException.class);
造成這個(gè)原因在第一個(gè)代碼塊3行互墓，調(diào)用List.remove(int),該參數(shù)被當(dāng)成list索引index,不是刪除元素
這個(gè)測(cè)試用例調(diào)用list.remove(1) ,但是刪除元素索引是0,調(diào)用List.remove() 改變所有元素在刪除元素之后
在這個(gè)場(chǎng)景我們刪除所有元素,除了第一條記錄,為什么僅僅只有第一條剩下呢,1代表索引是非法,因此最后會(huì)報(bào)錯(cuò)
注意,這個(gè)問題原因是調(diào)用List.remove() 參數(shù)是基本類型 short, char 或者int,因此編譯器第一次認(rèn)為調(diào)用匹配重載方法
可以用傳入Integer類型正確執(zhí)行
void removeAll(List<Integer> list, Integer element) {
while (list.contains(element)) {
list.remove(element);
}
}
現(xiàn)在下面可以正確執(zhí)行難
// 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() 都必須找到第一個(gè)出現(xiàn)元素,這個(gè)代碼引起沒必要遍歷
我們可以做到更好如果我們保存元素第一次出現(xiàn)索引
void removeAll(List<Integer> list, Integer element) {
int index;
while ((index = list.indexOf(element)) >= 0) {
list.remove(index);
}
}
以下代碼可以通過
List<Integer> list = list(1,2,3);
int valueToRemove = 1;
// when
removeAll(list, valueToRemove);
assertThat(list).isEqualTo(list(2, 3));
上面情況代碼非常整潔和簡(jiǎn)潔，但是仍然性能很差,因?yàn)槲覀儾荒芨欉@個(gè)循環(huán)過程,List.remove()* 必須找到第一個(gè)list中元素然后刪除,當(dāng)使用ArrayList 蒋搜，元素改變引起許多引用拷貝篡撵，甚至重新分配內(nèi)存幾次
3.刪除元素直到改變?cè)瓉?em>list
List.remove(E element) 有一個(gè)特色我們還沒提及到,方法返回布爾值true，List 改變由于包含該元素并刪除 操作
注意點(diǎn)豆挽，List.remove(int index) 返回void育谬，因?yàn)楦鶕?jù)索引刪除是有效，List 總會(huì)刪除元素帮哈，否則會(huì)拋出異
常IndexOutOfBoundsException
執(zhí)行刪除直到List 改變
void removeAll(List<Integer> list, int element) {
while (list.remove(element));
}
結(jié)果如下
// 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循環(huán)
我們可以管理遍歷過程通過for循環(huán)并且如果匹配元素直接刪除
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);
}
}
}
結(jié)果如下:
// given
List<Integer> list = list(1, 2, 3);
int valueToRemove = 1;
// when
removeAll(list, valueToRemove);
// then
assertThat(list).isEqualTo(list(2, 3));
然而膛檀，如果不同輸入，得到錯(cuò)誤結(jié)果輸出:
// 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
- 元素和list.get(i)都是等于1在第3行代碼，因此java進(jìn)入if語句
- 刪除元素索引0
- list包含1宿刮，2和3
- i = 1
- list.get(i) 返回2因?yàn)閘ist刪除一個(gè)元素互站，因此改變所有元素位置
現(xiàn)在面臨問題當(dāng)有兩個(gè)相鄰值，我們都想刪除僵缺，解決這個(gè)問題胡桃，我們?cè)黾友h(huán)變量
當(dāng)刪除元素變量要減一
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--;
}
}
}
當(dāng)我們不刪除變量增加1
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++;
}
}
}
注意，在這之后磕潮，移除i++語句第2行
結(jié)果如下：
// given
List<Integer> list = list(1, 1, 2, 3);
int valueToRemove = 1;
// when
removeAll(list, valueToRemove);
// then
assertThat(list).isEqualTo(list(2, 3));
這個(gè)實(shí)現(xiàn)好像是對(duì)第一眼看上去翠胰，這個(gè)方法仍然有很嚴(yán)重性能問題：
- 刪除元素改變之后所有元素
- 索引訪問元素LinkedList 意味遍歷通過元素一個(gè)接一個(gè)知道找到該元素
4.使用for-each循環(huán)
從java5之后可以用for-each循環(huán)迭代通過list，下面使用迭代刪除元素:
void removeAll(List<Integer> list, int element) {
for (Integer number : list) {
if (Objects.equals(number, element)) {
list.remove(number);
}
}
}
注意：使用Integer作為循環(huán)類型自脯，因此不會(huì)得到NullPointerException ,同時(shí)這個(gè)方法調(diào)用 List.remove(E element) 是我們期望調(diào)用方法之景，不是索引，
代碼很簡(jiǎn)潔膏潮，不幸是代碼報(bào)錯(cuò)：
// given
List<Integer> list = list(1, 1, 2, 3);
int valueToRemove = 1;
// when
assertThatThrownBy(() -> removeWithForEachLoop(list, valueToRemove))
.isInstanceOf(ConcurrentModificationException.class);
for-each循環(huán)使用迭代器遍歷元素锻狗，當(dāng)修改List 迭代器得到不一致狀態(tài)，因此拋出常ConcurrentModificationException 焕参，從上面代碼得出結(jié)論：我們不能修改List轻纪，當(dāng)for-each訪問元素時(shí)候。
5.使用迭代器
使用迭代器遍歷和修改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狀態(tài)（因?yàn)檫@個(gè)可以修改List）,下面結(jié)果可以正常通過：
// given
List<Integer> list = list(1, 1, 2, 3);
int valueToRemove = 1;
// when
removeAll(list, valueToRemove);
// then
assertThat(list).isEqualTo(list(2, 3));
因?yàn)槊總€(gè)List類提供自己迭代器實(shí)現(xiàn)刻帚，我們可以安全假定，迭代器實(shí)現(xiàn)元素迭代和刪除最高效涩嚣。然而使用Arraylist 仍然要移動(dòng)很多元素（可以數(shù)組重新分配內(nèi)存）崇众，同時(shí)上面代碼有點(diǎn)難度這個(gè)不是標(biāo)準(zhǔn)for循環(huán)對(duì)于大多數(shù)開發(fā)來說不熟悉。
6.搜集
到目前為止航厚，刪除元素都會(huì)修改原List 顷歌，我們不必要這樣，可以創(chuàng)建新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;
}
方法結(jié)果返回新的List 幔睬，方法必須返回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));
注意，現(xiàn)在使用for-each循環(huán)不能修改List 溪窒，我們現(xiàn)在通過它迭代元素，因?yàn)闆]用任何刪除,這里沒有必要移動(dòng)元素冯勉，因此這個(gè)實(shí)現(xiàn)性能也很好當(dāng)我們使用ArrayList
這實(shí)現(xiàn)比之前一些方式有些不同：
- 它不會(huì)修改原List 但是返回新List
- 這個(gè)方法決定返回List的實(shí)現(xiàn)澈蚌，它可以是不同于原List
同時(shí)我們修改我們實(shí)現(xiàn)得到以前方法獲得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灼狰，不必要按照位置訪問或者改變宛瞄，同時(shí)，這里有兩個(gè)Array分配，當(dāng)調(diào)用List.clear() and List.addAll().
7.使用stream api
java 8 介紹lambda表達(dá)式和stream api份汗，有這寫強(qiáng)大特色盈电，我們可以解決我們問題并且用很簡(jiǎn)潔代碼
List<Integer> removeAll(List<Integer> list, int element) {
return list.stream()
.filter(e -> !Objects.equals(e, element))
.collect(Collectors.toList());
}
這個(gè)方法作用和上一部分一樣，當(dāng)我們收集保存元素杯活，然后把這些結(jié)果增加原List 匆帚，有相同特征，
我們應(yīng)該返回結(jié)果：
// 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
有l(wèi)ambdas和函數(shù)接口java8中旁钧，java8還有一些擴(kuò)展api吸重，例如，List.removeIf() 方法歪今，最后一個(gè)部分看見用這個(gè)實(shí)現(xiàn) 嚎幸，參數(shù)需要一個(gè)條件，如果條件返回true就直接刪除元素寄猩，對(duì)比之前示例嫉晶，我們必須返回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));
實(shí)際上，List 本身實(shí)現(xiàn)該方法田篇，我們可以放心假定替废，這種方式性能最好，在以上方法中這個(gè)方案是最簡(jiǎn)潔代碼
9.總結(jié)
本文介紹許多方式解決簡(jiǎn)單問題斯辰，包括錯(cuò)誤示例舶担，分析他們找出最好解決方案
參考地址
github地址
