一行一行读Java源码——迭代器

迭代器

我们都知道，当我们需要删除List中元素时，必须使用迭代器来操作，为什么需要使用迭代器来进行remove操作，而不能在for循环中删除？那么迭代器又是什么呢？

迭代器接口

以下代码是一个基本的迭代器接口，声明了迭代器的基本方法，而我们常用的就是hasNext、next、remove。

package java.util;

import java.util.function.Consumer;

public interface Iterator<E> {
    
    boolean hasNext();

    E next();

    default void remove() {
        throw new UnsupportedOperationException("remove");
    }

    // Java 1.8加入，用于支持lambda表达式
    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

每一种数据结构，其迭代器的实现必然存在差异，此处我以List为例。
List统称为线性表，而线性表又分为顺序表和链表。接下来，我们来看看AbstractList中是如何实现这两种类型迭代器的。（顺序表也就是常见的数组）

顺序表的迭代器实现——Itr

private class Itr implements Iterator<E> {
        // 游标，指示将要访问的元素的位置
        int cursor = 0;

        // 指示最后一次访问位置，如果是最后一次是删除操作，该值为-1
        int lastRet = -1;

        // 同步校验位，主要用于remove时校验是否有多线程并行删除元素，此机制类似乐观锁
        int expectedModCount = modCount;

        // 是否还有可访问元素
        public boolean hasNext() {
            return cursor != size();
        }
        
        // 校验顺序表是否被其它线程修改过，未修改才可访问，否则抛ConcurrentModificationException异常
        // 返回游标指示元素
        // 标记最近一次访问位置为游标位置
        // 游标向前推进一位
        public E next() {
            checkForComodification();
            try {
                int i = cursor;
                E next = get(i);
                lastRet = i;
                cursor = i + 1;
                return next;
            } catch (IndexOutOfBoundsException e) {
                checkForComodification();
                throw new NoSuchElementException();
            }
        }

        // 判断该位置元素是否已经删除过
        // 并发访问校验
        // 调用List的当前实例删除当前(最近访问)元素
        // 游标回退一位
        // 最近访问的元素被删除后，那最近访问的元素下标标记为-1
        // 因为AbstractList.this.remove(lastRet)中的remove方法会修改modCount的值，所有expectedModCount也需要被重新赋值
        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                AbstractList.this.remove(lastRet);
                if (lastRet < cursor)
                    cursor--;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException e) {
                throw new ConcurrentModificationException();
            }
        }

        // 校验当前List的修改数modCount是否和迭代器中存储的一致，防止多线程并发访问
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

链表的迭代器实现——ListItr

// 链表的迭代器实现继承了顺序表迭代器，所以它拥有顺序表迭代器的所有功能
private class ListItr extends Itr implements ListIterator<E> {
        // 增加了指定位置的迭代器
        ListItr(int index) {
            cursor = index;
        }

        // 是否有前向节点（元素）
        public boolean hasPrevious() {
            return cursor != 0;
        }

        // 访问前向节点
        // 因为链表不支持随机访问，所以访问前向节点也是从首节点开始遍历到游标位置的前一个节点，时间复杂度为O(n)，迭代器虽然提供了这样的操作，但是我们平时使用时需要注意，尽量减少对链表的这种操作
        public E previous() {
            checkForComodification();
            try {
                int i = cursor - 1;
                E previous = get(i);
                lastRet = cursor = i;
                return previous;
            } catch (IndexOutOfBoundsException e) {
                checkForComodification();
                throw new NoSuchElementException();
            }
        }

        public int nextIndex() {
            return cursor;
        }

        public int previousIndex() {
            return cursor-1;
        }
        
        // 修改游标指示元素值
        public void set(E e) {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                AbstractList.this.set(lastRet, e);
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        // 此处体现了链表的优势
        // 在游标位置插入一个元素，时间复杂度为O(1)，如果是顺序表，插入一个元素的时间复杂度为O(n)
        public void add(E e) {
            checkForComodification();

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

结论

1、迭代器封装了对List的操作，使得访问更安全、准确，增删元素不是简单地通过List实例remove或者add，还包含了并发校验等；
2、两种for循环都不能准确删除元素，如下方例子所示。

public static void main(String[] args) {
    List<Integer> digits = new ArrayList<>();
    digits.add(0);
    digits.add(1);
    digits.add(2);
        
    for (int i = 0; i < digits.size(); i++) {
        System.out.println("Size of list : " + digits.size());
        digits.remove(i);
    }
        
    for (Integer integer : digits) {
        digits.remove(integer);
    }
}

输出

Size of list : 3
Size of list : 2
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)
    at collection.ListRemove.main(ListRemove.java:19)