ArrayList使用迭代器遍历删除元素（迭代器的具体实现）

222 阅读 0 评论 147 点赞

我是靠谱客的博主激昂凉面，这篇文章主要介绍ArrayList使用迭代器遍历删除元素（迭代器的具体实现），现在分享给大家，希望可以做个参考。

问题简述

为什么使用for循环遍历删除ArrayList中的元素会出错，而使用迭代器方法就不会出错（此处不考虑fast-fail机制问题）。

查阅各种博客，只知道遍历删除元素时的正确方法，但是不知道为什么该方法正确，因此写这篇博客记录一下。

问题描述

ArrayList的底层数据结构是数组，在数组中删除元素，我们可以直接用待删除元素的下一位元素覆盖待删除元素，然后将后面的元素依次往前挪动即可。实际上，ArrayList中也是使用该方法来删除元素的。

复制代码

1
2
3
4
5
6
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

由于使用删除元以上素，因此如果我们直接使用for循环遍历删除数组中某些元素时，可能会存在问题，举例如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//删除列表中所有值为4的元素，这是错误示范！
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>();
list.add(2);
list.add(3);
list.add(4);
list.add(4);
list.add(1);
list.add(3);
list.add(6);
list.add(4);
for(int i=0;i<list.size();i++){
if(list.get(i)==4){
list.remove(i);
}
}
System.out.println(list);
}

输出结果为

复制代码

1
2
[2, 3, 4, 1, 3, 6]

可以看出，值为4的元素并没有被完全删除，这就是因为在删除过程中，由于元素的移动，导致列表中第二个值为4的元素没有被访问到。因此这种方法不正确，我们可以使用迭代器来正确删除容器中的元素。
正确方法如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>();
list.add(2);
list.add(3);
list.add(4);
list.add(4);
list.add(1);
list.add(3);
list.add(6);
list.add(4);
Iterator<Integer> iterator = list.iterator();
while(iterator.hasNext()){
Integer value = iterator.next();
if(value==4){
iterator.remove();
}
}
System.out.println(list);
}

输出结果

复制代码

1
2
[2, 3, 1, 3, 6]

为什么使用迭代器就能正确的删除列表中的元素呢？直接去查看ArrayList的源码！

原因

ArrayList类有一个Itr内部类，该类实现了迭代器接口。正是由于这个类，我们可以使用迭代器来遍历ArrayList。其部分代码如下所示，我们只看和元素删除有关的代码，已在代码的关键位置进行了注释。

复制代码

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;
Itr() {}
public boolean hasNext() {
return cursor != size;
//当前游标不等于数组大小，表示还有后续元素
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
//游标指向下一位
return (E) elementData[lastRet = i];
//记录当前元素的下标位置，在删除时需要用到lastRet
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
//调用ArrayList中的remove方法
cursor = lastRet;
//这是关键的一步，将当前下标的值赋给游标，正是因为这一语句，才能正确删除元素
lastRet = -1;
expectedModCount = modCount;
//修改expectedModCount的值，避免触发fast-fail机制
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}

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
29
30
31
32
33
34
35
36
37
38
39
40
41
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;
Itr() {}
public boolean hasNext() {
return cursor != size;
//当前游标不等于数组大小，表示还有后续元素
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
//游标指向下一位
return (E) elementData[lastRet = i];
//记录当前元素的下标位置，在删除时需要用到lastRet
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
//调用ArrayList中的remove方法
cursor = lastRet;
//这是关键的一步，将当前下标的值赋给游标，正是因为这一语句，才能正确删除元素
lastRet = -1;
expectedModCount = modCount;
//修改expectedModCount的值，避免触发fast-fail机制
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}

上述代码并不复杂，我们可以看到iterator.remove()方法也是调用了ArrayList中的remove()方法实现元素的删除，不同点是在调用了ArrayList的remove()方法后，执行了cursor=lastRet语句，等再执行iterator.next()方法时，还是访问当前位置的元素，这样就避免了在遍历时会遗漏某些元素的情况。
知道了为什么使用迭代器能正确删除列表中的元素，我们也可以使用for循环来正确删除元素，正确方法如下所示

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>();
list.add(2);
list.add(3);
list.add(4);
list.add(4);
list.add(1);
list.add(3);
list.add(6);
list.add(4);
for(int i=0;i<list.size();i++){
if(list.get(i)==4){
list.remove(i);
i = i - 1;//只需要多添加这一行代码，待删除此位置的元素后，再访问此位置一次，就不会造成遗漏了
}
}
System.out.println(list);
}