ArrayList删除元素的细则

101 阅读 0 评论 67 点赞

我是靠谱客的博主英俊发夹，这篇文章主要介绍ArrayList删除元素的细则，现在分享给大家，希望可以做个参考。

删除ArrayList数组中某个元素，通常会使用for循环匹配目标元素完成删除操作。

复制代码

1
2
3
4
5
6
7
8
9
public void remove(List<String> list, String str){
Iterator<String> it = list.iterator();
while(it.hasNext()){
if(str.equals(it.next())){
it.remove();
}
}
}

复制代码

1
2
3
4
5
6
7
8
public void remove(List<String> list, String str){
for(String s: list){
if(str.equals(it.next())){
list.remove(s);
}
}
}

以上两种写法，第一种使用了显示声明迭代器Iterator的方式来遍历数组，匹配成功后删除；第二种使用JDK语法糖foreach的方式来遍历数组，匹配成功后删除。但是第二种写法会发生ConcurrentModificationException异常，简单来讲foreach是一个语法糖，其在进行遍历的时候还是使用的是ArrayList内部自己实现的迭代器Iterator，foreach的每次遍历都相当于调用Iterator的next()方法获取下一个元素，且方法内部会校验Iterator维护的expectedModCount是否等于ArrayList类维护的modCount，如不等就会抛出ConcurrentModificationException异常，又因为直接通过ArrayList的remove()方法来删除元素只会维护modCount，所以最终导致expectedModCount和modCount不相等。

ArrayList#remove

抛开remove()方法中越界校验、移除后数组拷贝等逻辑，发现ArrayList在进行删除元素前会先将modCount属性自增加一来记录当前数组的修改次数。这就导致一边使用foreach语法糖遍历数组，一边使用ArrayList类remove()方法删除元素会发生ConcurrentModificationException异常。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}

Iterator

ArrayList内部通过实现Iterator接口实现了一个迭代器，如下代码所示（省略部分代码）：

每次调用迭代器的next()方法时，都会执行checkForComodification()方法的校验逻辑；
checkForComodification()方法主要职责就是校验迭代器内属性expectedModCount和ArrayList类中属性modCount是否相等，不相等就抛出ConcurrentModificationException异常。

迭代器中的remove()方法，首先会调用checkForComodification()方法来校验当前数组的修改次数是否相等；然后会调用ArrayList类中的remove()方法完成删除；最后再将执行删除操作后ArrayList类中modCount属性的最新值赋给expectedModCount以保持两值相等。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
private class Itr implements Iterator<E> {
int cursor;
// index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}

ArrayList#removeIf

想要删除数组中一个元素还可以使用ArrayList类的removeIf()方法，源代码逻辑可以参考下面六个步骤：

将modCount赋值给removeIf()方法局部变量expectedModCount；
使用for i 循环遍历数组每一个元素与目标删除元素比对，如果相等就将当前下标放入BitSet中标记为true（待删除元素）；
校验局部变量expectedModCount与modCount是否相等，防止其它线程操作数组，如果两值不相等同样抛出ConcurrentModificationException异常；
再次for i循环遍历数组，利用BitSet完成删除目标元素、原地移动元素；
再校验一次局部变量expectedModCount与modCount是否相等，同样防止同时有其它线程在操作数组；
将modCount自增加一；