一行一行读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)