列表和队列之ArrayList（二）迭代器实现原理

程序员文章站 2022-03-15 19:44:39

...

1.我们先看下ArrayList中iterator方法的实现

public Iterator<E> iterator() {
  return new Itr();
}

新建一个Iterator对象，Iterator是一个成员内部类，实现了Iterator接口，声明为：

private class Itr implements Iterator<E>

它有三个实例成员变量：

int cursor; //下一个要返回的元素位置
int lastRet = -1; //最后一个返回的索引位置，如果没有则为-1
int expectedModCount = modCount;

cursor表示下一个要返回的元素位置，lasRet表示最后一个返回的索引位置，expectedModCount 表示期望的修改次数，初始化为外部类当前的修改次数modCount，回顾一下，成员内部类可以直接访问外部类的实例变量。每次发生结构性变化的时候modCount都会增加，而每次迭代器操作的时候都会检查expectedModCount是否与modCount相同，这样就能检测出结构性变化。

我们先从hasNext(),代码如下：

public boolean hasNext() {
   return cursor != size;
}

cursor与size比较，nex方法如下：

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

首先调用了checkForComodification方法，代码如下：

final void checkForComodification() {
  if(modCount != expectedModCount)
  throw new ConcurrentModificationException();
}

所以，next前面部分主要就是在检查是否发生结构性变化，如果没有发生变化，就更新cursor和lasRet的值，来保持语义，然后返回对应的元素。remove代码如下：

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的remove方法，但同时更新了cursor、lastRet和expectedModCount的值，所以它可以正确删除。需要注意的是，调用remove方法前必须先调用next，比如，通过迭代器删除所有元素，直觉上，可以写成下面这种形式：

public static void removeAll(ArrayList<Integer> list){
  Iterator<Integer> it = list.iterator();
  while(it.hasNext()){
    it.remove();
  }
}

实际运行，会抛出异常java.lang.IllegalStateException，正确的写法如下：

public static void removeAll(ArrayList<Integer> list){
    Iterator<Integer> it = list.iterator();
    while(it.hasNext()){
      it.next();
      it.remove();
    }
}

当然，如果只要删除所有元素，ArrayList有现成的方法clear()。

listIterator()的实现使用了另一个内容部类ListIterator，它继承自Iterator，原理基本和上述一致。

2.迭代器的好处

为什么要通过迭代器这种方式访问元素呢？直接使用size()和get(index)语法不也可以吗？在一些场景下两种方式都可以。但是foreach语法根伟简洁，迭代器语法更为通用，适用于各种容器类。

更重要的是，迭代器表示的是一种关注点分离的思想，将数据的实际组织方式与数据的迭代便利相分离，是一种常见的设计模式。需要访问容器元素的代码只需要一个Iterator接口的引用，不需要关注数据的世界级组织方式，可以使用一致和统一方式进行访问。

从封装的思路来说，迭代器封装了各种数据组织方式的迭代操作，提供了简单和一致的接口。