关于面试题“ArrayList循环remove()要用Iterator”的研究-白红宇

两个月前我在参加一场面试的时候，被问到了ArrayList如何循环删除元素，当时我回答用Iterator,当面试官问为什么要用Iterator而不用foreach时，我没有答出来，如今又回想到了这个问题，我觉得应该把它搞一搞，所以我就写了一个小的demo并结合阅读源代码来验证了一下。

下面是我验证的ArrayList循环remove()的4种情况,以及其结果(基于oracle jdk1.8)：

//List
    
      list = new ArrayList<>();//list.add(1);//list.add(2);//list.add(3);//list.add(4);//循环remove()的4种情况的代码片段：//#1for (Integer integer : list) {    list.remove(integer);}结果：Exception in thread "main" java.util.ConcurrentModificationException    at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)    at java.util.ArrayList$Itr.next(ArrayList.java:851)-----------------------------------------------------------------------------------//#2Iterator
     
       iterator = list.iterator();while(iterator.hasNext()) {    Integer integer = iterator.next();    list.remove(integer);}结果：Exception in thread "main" java.util.ConcurrentModificationException    at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)    at java.util.ArrayList$Itr.next(ArrayList.java:851)-----------------------------------------------------------------------------------//#3for (int i = 0; i < list.size(); i++) {    list.remove(i);}System.out.println(list);结果：[2, 4]-----------------------------------------------------------------------------------//#4Iterator
      
        iterator = list.iterator();while (iterator.hasNext()){    iterator.next();    iterator.remove();}System.out.println(list.size());结果：(唯一一个得到期望值的)0复制代码

可以看出来这几种情况只有最后一种是得到预期结果的，其他的要么异常要么得不到预期结果，下面咱们一个一个进行分析。

#1

//#1for (Integer integer : list) {    list.remove(integer);}结果：Exception in thread "main" java.util.ConcurrentModificationException    at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)    at java.util.ArrayList$Itr.next(ArrayList.java:851)复制代码

通过异常栈，我们可以定位是在ArrayList的内部类Itr的checkForComodification方法中爆出了ConcurrentModificationException异常(关于这个异常是怎么回事咱们暂且不提)我们打开ArrayList的源码，定位到901行处：

final void checkForComodification() {    if (modCount != expectedModCount)        throw new ConcurrentModificationException();}复制代码

这个爆出异常的方法实际上就做了一件事，检查modCount != expectedModCount因为满足了这个条件，所以抛出了异常，继续查看modCount和expectedModCount这两个变量，发现modCount是继承自AbstractList的一个属性，这个属性有一大段注释

/** * The number of times this list has been structurally modified. * Structural modifications are those that change the size of the * list, or otherwise perturb it in such a fashion that iterations in * progress may yield incorrect results. * * This field is used by the iterator and list iterator implementation * returned by the {@code iterator} and {@code listIterator} methods. * If the value of this field changes unexpectedly, the iterator (or list * iterator) will throw a {@code ConcurrentModificationException} in * response to the {@code next}, {@code remove}, {@code previous}, * {@code set} or {@code add} operations.  This provides * fail-fast behavior, rather than non-deterministic behavior in * the face of concurrent modification during iteration. * * 
Use of this field by subclasses is optional. If a subclass * wishes to provide fail-fast iterators (and list iterators), then it * merely has to increment this field in its {@code add(int, E)} and * {@code remove(int)} methods (and any other methods that it overrides * that result in structural modifications to the list).  A single call to * {@code add(int, E)} or {@code remove(int)} must add no more than * one to this field, or the iterators (and list iterators) will throw * bogus {@code ConcurrentModificationExceptions}.  If an implementation * does not wish to provide fail-fast iterators, this field may be * ignored. */protected transient int modCount = 0;复制代码

大致的意思是这个字段用于有fail-fast行为的子集合类的，用来记录集合被修改过的次数，我们回到ArrayList可以找到在add(E e)的调用链中的一个方法ensureExplicitCapacity(int minCapacity) 中会对modCount自增：

private void ensureExplicitCapacity(int minCapacity) {    modCount++;    // overflow-conscious code    if (minCapacity - elementData.length > 0)        grow(minCapacity);}复制代码

我们在初始化list时调用了4次add(E e)所以现在modCount的值为4

再来找

expectedModCount：这个变量是定义在

ArrayList的

Iterator的实现类

Itr中的，它默认被赋值为

modCount

知道了这两个变量是什么了以后，我们开始走查吧，在

Itr的相关方法中加好断点(编译器会将

foreach编译为使用

Iterator的方式，所以我们看

Itr就可以了)，开始调试：

循环：

在迭代的每次

next()时都会调用

checkForComodification()

list.remove()：

在

ArrayList的

remove(Object o)中又调用了

fastRemove(index)：

fastRemove(index)中对

modCount进行了自增,刚才说过

modCount经过4次

add(E e)初始化后是

4所以

++后现在是

5：

继续往下走，进入下次迭代：

又一次执行

next()，

next()调用

checkForComodification()，这时在上边的过程中

modCount由于

fastRemove(index)的操作已经变成了

5而

expectedModCount则没有人动，所以很快就满足了抛出异常的条件

modCount != expectedModCount(也就是前面提到的

fail-fast)，程序退出。

#2

//#2Iterator
    
      iterator = list.iterator();while(iterator.hasNext()) {    Integer integer = iterator.next();    list.remove(integer);}结果：Exception in thread "main" java.util.ConcurrentModificationException    at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)    at java.util.ArrayList$Itr.next(ArrayList.java:851)复制代码

其实这个#2和#1是一样的，foreach会在编译期被优化为Iterator调用，所以看#1就好啦。

#3

//#3for (int i = 0; i < list.size(); i++) {    list.remove(i);}System.out.println(list);结果：[2, 4]复制代码

这种一本正经的胡说八道的情况也许在写代码犯困的情况下会出现... 不做文字解释了，用println()来说明吧：

第0次循环开始remove(0)前的list: [1, 2, 3, 4]remove(0)前的list.size()=4执行了remove(0)remove(0)后的list.size()=3remove(0)后的list: [2, 3, 4]下一次循环的i=1下一次循环的list.size()=3第0次循环结束是否还有条件进入下次循环?: true第1次循环开始remove(1)前的list: [2, 3, 4]remove(1)前的list.size()=3执行了remove(1)remove(1)后的list.size()=2remove(1)后的list: [2, 4]下一次循环的i=2下一次循环的list.size()=2第1次循环结束是否还有条件进入下次循环?: falseProcess finished with exit code 0复制代码

实际上ArrayList中Itr用游标和最后一次返回值索引来解决了这种size越删越小，但是要删除元素的index越来越大的尴尬局面，这个将在#4里说明。

#4

这个才是正儿八经能够正确执行的方式，用了ArrayList中迭代器Itr的remove()而不是用ArrayList本身的remove()，我们调试一下吧看看到底经历了什么：

迭代：

Itr初始化：游标 cursor = 0; 最后一次返回值索引 lastRet = -1; 期望修改次数 expectedModCount = modCount = 4;

迭代的

hasNext()：检查游标是否已经到达当前list的

size，如果没有则说明可以继续迭代：

迭代的

next()：

checkForComodification() 此时

expectedModCount和

modCount是相等的，不会抛出

ConcurrentModificationException，然后取到游标(第一次迭代游标是

0)对应的list的元素，再将游标+1，也就是游标后移指向下一个元素，然后将游标原值

0赋给最后一次返回值索引，也就是最后一次返回的是索引

0对应的元素

iterator.remove()：同样checkForComodification()然后调用ArrayList的remove(lastRet)删除最后返回的元素,删除后modCount会自增

删除完成后，将游标赋值成最后一次返回值索引，其实也就是将游标回退了一格回到了上一次的位置，然后将最后一次返回值索引重新设置为了初始值-1,最后expectedModCount又重新赋值为了上一步过程完成后新的modCount

由上两个步骤可以看出来，虽然list的

size每次

remove()都会

-1，但是由于每次

remove()都会将游标回退，然后将最后一次返回值索引重置，所以实际上没回

remove()的都是当前集合的第

0个元素，就不会出现#3中

size越删越小，而要删除元素的索引越来越大的情况了，同时由于在

remove()过程中

expectedModCount和

modCount始终通过赋值保持相等，所以也不会出现

fail-fast抛出异常的情况了。

以上是我通过走查源码的方式对面试题“ArrayList循环remove()要用Iterator”做的一点研究，没考虑并发场景，这篇文章写了大概3个多小时，写完这篇文章办公室就剩我一个人了，我也该回去了，今天1024程序员节，大家节日快乐！

2017.10.25更新#1

感谢@llearn的提醒，#3也可以用用巧妙的方式来得到正确的结果的(再面试的时候，我觉得可以和面试官说不一定要用Iterator了，感谢@llearn：

//#3 我觉得可以这样
for (int i = 0; i < list.size(); ) {

list.remove(0);
}
System.out.println(list);

2017.10.25更新#2

感谢@ChinLong的提醒，提供了另一种不用Iterator的方法，也就是倒着循环(这种方案我写完文章时也想到了，但没有自己印证到demo上)，感谢@ChinLong：

然道就没有人和我一下喜欢倒着删的.
听别人说倒着迭代速度稍微快一点???
for (int i = list.size() -1; i >= 0; i-- ) {

list.remove(i);
}
System.out.println(list);