xyZGHio

本是青灯不归客,却因浊酒恋风尘

0%

Java List 迭代器删除元素细节的源码分析

Java List 迭代器用于遍历、删除等相关操作——Iterator、ListIterator,前者只能向后遍历,而后者则通过继承前者以提供了向前遍历的方法。本文将结合JDK源码解释迭代器遍历过程中删除元素的相关细节,具体以ArrayList为例进行分析,LinkedList迭代器与其虽在实现上略有差别,但是设计思想大同小异

abstract.png

迭代器遍历不能使用List.remove()删除元素

情景复现

众所周知,在迭代器遍历List过程中,如果需要删除元素,正确的姿势是通过迭代器Iterator的remove方法,而不能使用List的remove方法,否则将会引发 ConcurrentModificationException 异常。现来通过复现场景结合相关源码分析解释其中缘由。测试代码及测试结果如下所示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void removeList1() {
List<String> strList = new ArrayList<>();
strList.add("Aaron");
strList.add("Bob");
strList.add("Cain");
strList.add("Dad");
strList.add("Eee"); // 此时modCount值为5

String node1 = "Cain"; // 欲删除元素

Iterator<String> iterator = strList.iterator(); // 此时expectedModCount即被初始化为5
while (iterator.hasNext()) {
String node = iterator.next();
if(node1.equals(node)) {
strList.remove(node);
}
}
}

figure 1.jpeg

源码分析

ArrayList类从AbstractList类中继承了一个受保护的成员变量modCount

1
2
3
4
5
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
...
protected transient int modCount = 0;
...
}

[Note]: 在Java Serializable序列化中, transient 关键字用于指示该成员变量在序列化时将会被自动忽略

变量modCount用于记录列表中元素被修改(添加、删除元素)的次数,如ArrayList中的add、remove方法

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
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
...
// 向列表中添加元素
public boolean add(E e) {
modCount++; // 被修改次数自增一次
add(e, elementData, size);
return true;
}
// 从列表中删除元素
public boolean remove(Object o) {
final Object[] es = elementData;
final int size = this.size;
int i = 0;
found: {
if (o == null) {
for (; i < size; i++)
if (es[i] == null)
break found;
} else {
for (; i < size; i++)
if (o.equals(es[i]))
break found;
}
return false;
}
fastRemove(es, i); // 被修改次数自增一次
return true;
}
private void fastRemove(Object[] es, int i) {
modCount++; // 被修改次数自增一次
final int newSize;
if ((newSize = size - 1) > i)
System.arraycopy(es, i + 1, es, i, newSize - i);
es[size = newSize] = null;
}
}

ArrayList内部类——迭代器Itr类,实现了Iterator接口。其有一个成员变量expectedModCount,在构造该内部类对象时,即使用当前的modCount值进行初始化。迭代器的 next() 方法中会先调用checkForComodification方法(),如果expectedModCount、 modCount 值不一致,即会抛出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
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
...
public Iterator<E> iterator() {
return new Itr();
}
...
private class Itr implements Iterator<E> {
int expectedModCount = modCount;
...
public E next() {
// 检查 expectedModCount、 modCount 是否一致
checkForComodification();
try {
int i = cursor;
E next = get(i);
lastRet = i;
cursor = i + 1;
return next;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}
// 检查 expectedModCount、 modCount 是否一致
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
}

以上文的测试代码removeList1()方法为例,List的add()方法(strList.add(…))被调用了5次,此时modCount值已为5。 strList.iterator() 获取新构造的迭代器对象时,expectedModCount被初始化为5。利用List的remove方法(strList.remove(node))删除元素后,modCount则又被自增一次,此刻值即为6;而expectedModCount依然值为5,并未发生更新。 在while的下一次循环中,通过迭代器的next() 方法(iterator.next())获取元素时,由于 modCount、expectedModCount 值不等,即会抛出ConcurrentModificationException异常

类似地,对于ListIterator迭代器而言,其 previous() 方法内部同样会首先调用checkForComodification() 方法,以检查 expectedModCount、 modCount 是否一致,如若不一致,即会抛出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
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
...
public ListIterator<E> listIterator() {   
return new ListItr(0);
}
...
private class ListItr extends Itr implements ListIterator<E> {
...
ListItr(int index) {   
super();   
cursor = index;
}

public E previous() {
checkForComodification(); // 检查 expectedModCount、 modCount 是否一致
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[lastRet = i];
}
}
}

迭代器的remove()方法不可多次连续调用

情景复现

如上文所述,在迭代器遍历List过程中,如果需要删除元素,正确的姿势是通过迭代器Iterator的remove方法,但是不可连续两次及其以上调用来删除,否则将会引发 IllegalStateException 异常。现来通过复现场景结合相关源码分析解释其中缘由。测试代码及测试结果如下所示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void removeList2() {
List<String> strList = new ArrayList<>();
strList.add("Aaron");
strList.add("Bob");
strList.add("Cain");
strList.add("Dad");
strList.add("Eee");

// 欲删除元素
String node1 = "Cain";

Iterator<String> iterator = list.iterator();
for(; iterator.hasNext(); ) {
String node = iterator.next();
if( node1.equals(node) ) {
iterator.remove();
iterator.remove(); // 再一次调用迭代器的remove方法
}
}
}

figure 2.jpeg

源码分析

ArrayList 中 Iterator 迭代器源码如下,成员变量 expectedModCount 的作用目的在上文已经详细解释过了,此处不再赘述;这里我们重点关注其成员变量 cursor、lastRet,前者是记录当前迭代器所在位置,初值为0;后者则用于记录上次迭代器的位置(下文将具体解释其确切作用,首先是被删除元素的位置,其次是在删除元素后,用lastRet值重新确定迭代器的位置cursor值),初值为-1,意为无效值

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
    public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
...
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;

public boolean hasNext() {
return cursor != size;
}

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];
}

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();
}
}
}
}

现结合下图来对迭代器的 hasNext()、next() 方法中的源码进行分析。我们知道迭代器的位置是位于元素之间,而非正好指向元素,如下图的黄色圆圈所示。当调用一次 next() 方法时,其先会将当前迭代器的位置 cursor 值赋给 lastRet,然后将 cursor 值加1以指向下一个位置,同时将迭代器刚刚越过元素返回;当迭代器到达列表最后一个位置,无元素可以越过时,其 cursor 正好等于 列表长度size,即 hasNext() 返回false。所以每次调用 next() 方法遍历之前应该先调用 hasNext() 进行判断

figure 3.jpeg

现结合下图来对迭代器的 remove() 方法中的源码进行分析。当迭代器位于①处时,根据上文分析,我们可知 cursor 和 lastRet 值分别为2、1,②处调用迭代器的next()方法后,此时cursor 和 lastRet 值即会被更新为3、2,现在我们调用迭代器的remove()方法,从源码中我们可以看出其内部依然是调用ArrayList的remove方法来删除元素,该方法会导致modCount发生更新——自增一次,所以其随后更新了expectedModCount值, 以避免迭代器下次遍历时 next( )方法中的 checkForComodification() 会因 modCount、expectedModCount 值不一致而引发 ConcurrentModificationException 异常。删除了迭代器所在位置之前的元素,所以删除后迭代器的位置也即发生改变,由于 lastRet 存储的是迭代器上一次的位置值,所以将该值重新赋值给 cursor ,即可保证删除元素后,迭代器的位置依然是正确的,即此时 cursor 为2,然后将 lastRet 置为无效值 -1。当再一次调用 remove() 方法时,由于 lastRet=-1<0 ,即引发 IllegalStateException 异常。所以,迭代器的remove()方法不可连续调用多次,因为首先无有效的被删除元素位置,其次无有效的lastRet值可用于更新删除元素后迭代器的新的位置。故对于Iterator迭代器而言,每次调用迭代器的remove方法前,都必须先调用迭代器的next方法

figure 4.png

类似地,对于ListIterator迭代器而言,其 hasPrevious()、previous() 方法逻辑同理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
...
private class ListItr extends Itr implements ListIterator<E> {
public boolean hasPrevious() {
return cursor != 0;
}

public E previous() {
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[lastRet = i];
}
}
}

hasPrevious() 判断迭代器是否已经位于列表首端(位置为0),如果是,则返回false。迭代器在③处时,其cursor、lastRet分别为3、2,当调用迭代器的 previous() 方法时,其会将 cursor值减1以指向前一个位置。如果此时新的迭代器位置小于0,即会引发 NoSuchElementException 异常,故每次调用 previous() 方法前应先调用 hasPrevious() 方法做边界检查。再将减1后的cursor赋值再次给lastRet。此时cursor、lastRet均为2,该方法同时将迭代器刚刚越过元素返回;⑤处调用一次迭代器的remove()方法,根据lastRet的值(值为2),我们可知其删除的正好是迭代器位置之后的元素(即,迭代器在④中越过的元素),所以删除元素后,迭代器的位置实际上并没有发生变化,即,依然是2。 故remove()方法中虽然将 lastRet 再重新赋给 cursor 一次,其实际上并无改变 cursor 的值(亦为2),随后再将 lastRet 置为 -1 并更新 expectedModCount。故如果此时再一次调用 remove() 方法时,由于 lastRet=-1<0 ,同样会引发 IllegalStateException 异常。故对于ListIterator迭代器而言,每次调用迭代器的 remove() 方法前,都必须先调用迭代器的 next()或previous() 方法

figure 5.jpeg

至此,我们通过分析 next()、previous() 方法知道,它们对 lastRet 更新赋值策略是不同的,由于该值是指示所欲删除元素的位置信息,所以迭代器的remove方法所删除的元素和迭代器的状态有关,即,迭代器的 remove() 方法总是删除迭代器 next()、previous() 方法刚刚越过的元素

请我喝杯咖啡捏~

欢迎关注我的微信公众号:青灯抽丝