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

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

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

//List<Integer> list = new ArrayList<>();
//list.add(1);
//list.add(2);
//list.add(3);
//list.add(4);
//循环remove()的4种情况的代码片段：

//#1
for (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)
-----------------------------------------------------------------------------------

//#2
Iterator<Integer> 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)
-----------------------------------------------------------------------------------


//#3
for (int i = 0; i < list.size(); i++) {
    list.remove(i);
}
System.out.println(list);

结果：
[2, 4]
-----------------------------------------------------------------------------------

//#4
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()){
    iterator.next();
    iterator.remove();
}
System.out.println(list.size());

结果：(唯一一个得到期望值的)
0复制代码

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

#1

//#1
for (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 <i>structurally modified</i>.
 * 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.
 *
 * <p>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
 * <i>fail-fast</i> behavior, rather than non-deterministic behavior in
 * the face of concurrent modification during iteration.
 *
 * <p><b>Use of this field by subclasses is optional.</b> 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

//#2
Iterator<Integer> 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

//#3
for (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()=3
remove(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()=2
remove(1)后的list: [2, 4]
下一次循环的i=2
下一次循环的list.size()=2
第1次循环结束
是否还有条件进入下次循环?: false


Process 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);