迭代器

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

迭代器接口

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

package java.util;import java.util.function.Consumer;public interface Iterator
    
      {        boolean hasNext();    E next();    default void remove() {        throw new UnsupportedOperationException("remove");    }    // Java 1.8加入，用于支持lambda表达式    default void forEachRemaining(Consumer
      action) {        Objects.requireNonNull(action);        while (hasNext())            action.accept(next());    }}
    

每一种数据结构，其迭代器的实现必然存在差异，此处我以List为例。

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

private class Itr implements Iterator
    
      {        // 游标，指示将要访问的元素的位置        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
    
      {        // 增加了指定位置的迭代器        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，还包含了并发校验等；

public static void main(String[] args) {    List
    
      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 : 3Size of list : 2Exception 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)