迭代器

在访问集合类的时候，经常会用到迭代器。

迭代器是一种设计模式：用于访问集合类中的数据。将遍历行为与被遍历的对象分离，无需关心集合类的内部结构和顺序。

优点：当内部结构发生变化，外部不需要修改遍历逻辑。（例如数组存储改为链表存储）

类图：TODO

Java中集合类遍历的几种方式

List<String> list = new ArrayList<>();
//fori：下标访问
for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}
//forr：下标倒序访问
for (int i = list.size() - 1; i >= 0; i--) {
    System.out.println(list.get(i));
}
//foreach：会被编译成迭代器遍历
for (String s : list) {
    System.out.println(s);
}
//forEach：JDK1.8以上支持函数式接口，内部使用foreach遍历
list.forEach(s -> System.out.println(s));

foreach最终会被编译成迭代器，如下：

//泛型被擦除
ArrayList var1 = new ArrayList();
Iterator var2 = var1.iterator();
while(var2.hasNext()) {
    String var3 = (String)var2.next();
    System.out.println(var3);
}

迭代器和for循环

1. for循环适合随机访问（例如ArrayList），可以根据下标获取指定元素，而Iterator适合顺序访问（例如LinkedList）。
2. 迭代器不用考虑集合类内部实现，方便替换数据结构，如List换位Set。

Java中的迭代器

Java中提供了Iterator迭代器接口，结合泛型：避免显式地类型转换

public interface Iterator<E> {
  boolean hasNext();
  E next();
  void remove();
}

迭代器通常由集合类内部提供，通过实现Iterable接口返回迭代器，使用面向接口的方式，当集合从List换成Set时，不需要修改遍历逻辑。

public  interface Iterable<T> { 
  Iterator<T> iterator(); 
}

迭代过程中修改集合

迭代过程中不能通过列表的add、remove方法修改列表，应该使用迭代器提供的add、remove方法，会更新expectedModCount的值

1. 每次添加或删除会记录修改次数：modCount++，
2. 创建迭代器时保存expectedModCount
3. 在迭代过程中判断modCount和expectedModCount是否相等，如果不相等，则表示列表被修改过

以LinkedList为例

private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned;
    private Node<E> next;
    private int nextIndex;
    //创建迭代器时保存列表中的modCount
    private int expectedModCount = modCount;
    ...
    public E next() {
        //每次遍历检查列表是否被修改过
        checkForComodification();
        if (!hasNext()) throw new NoSuchElementException();
        lastReturned = next;
        next = next.next;
        nextIndex++;
        return lastReturned.item;
    }
    //迭代器中的add方法会修改expectedModCount
    public void add(E e) {
        checkForComodification();
        lastReturned = null;
        if (next == null)
            linkLast(e);
        else
            linkBefore(e, next);
        nextIndex++;
        expectedModCount++;
    }
    //通过比较当前modCount和创建迭代器时的expectedModCount，检查列表是否被修改过
    final void checkForComodification() {
        if (modCount != expectedModCount) throw new ConcurrentModificationException();
    }
}

注：

1. 每次调用iterator()方法都会生成一个新的迭代器，并保存当前的modCount
2. 创建两个迭代器同时遍历，即使通过迭代器的方法修改集合，也会出错：expectedModCount只属于各自的迭代器，两个线程对列表的修改都会改变modCount，导致比较出错。

迭代器模式和访问者模式

访问者和迭代器都用于对象内部元素的访问，但二者关注的重点不相同：迭代器模式关心如何访问对象中元素，而访问者模式关心如何对对象中的元素进行操作。

访问者模式可以和迭代器模式一起使用：当对象结构是一个包含多个元素的容器，通过迭代器遍历元素，再通过参数传给访问者进行操作。