Java 集合框架的迭代器

Java的容器ArrayList、LinkedList、HashSet等可遍历容器，因为不想暴露底层结构，都会实现一个迭代器用于遍历容器。

Iterator接口

Iterator接口是迭代器的顶层接口，接口方法很简单，就是单向遍历和删除元素：

Iterator {
    boolean hasNext();
    E next();
    void remove();
    forEachRemaining(action);
}

ListIterator接口是Iterator的子接口，增加了双向遍历和修改，添加元素功能：

ListIterator {
    boolean hasNext();
    E next();
    boolean hasPrevious();
    E previous();
    int nextIndex();
    int previousIndex();
    void remove();
    void set(E);
    void add(E);
    ......
}

迭代器实现

以ArrayList内部实现的迭代器举例子：
ArrayList有两个实现了迭代器到的内部类Itr, ListItr。
其中 Itr implements Iterator<E>, ListItr extends Itr implements ListIterator<E>。

Itr的实现比较简单，主要有两个变量， cursor是游标，指向下一个未遍历的元素。lastRet默认值为-1，它的值在next()返回的元素下标和-1两者之间。功能是防止连续两次的执行remove操作，执行过一次remove操作之后lastRet会置为-1，next又会置为返回元素下标。lastRet为-1时remove会抛出异常。

// 主要代码
 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;
        }

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

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

ArrayList.this的用法：因为Itr是内部类，所以ArrayList.this指代外部类对象。

ListItr多出了previous，add，set等操作。
previous()返回的是cursor - 1下标的元素。
add(E)会修正cursor游标值。

        // ListItr部分代码
        public int previousIndex() {
            return cursor - 1;
        }

        @SuppressWarnings("unchecked")
        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];
        }

        public void set(E e) {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.set(lastRet, e);
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        public void add(E e) {
            checkForComodification();

            try {
                int i = cursor;
                ArrayList.this.add(i, e);
                cursor = i + 1;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

为什么不能在for循环中删除元素

for循环遍历删除

而迭代器会remove操作之后会及时修正游标值，不会造成这样的问题。