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

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

情景复现

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

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

源码分析

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

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

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

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

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异常

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异常

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 异常。现来通过复现场景结合相关源码分析解释其中缘由。测试代码及测试结果如下所示

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方法
            }
        }
  }

源码分析

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

    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() 进行判断

现结合下图来对迭代器的 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方法

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

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() 方法

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

xyZGHio

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

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

情景复现

源码分析

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

情景复现

源码分析