深度理解Iterator底层源码

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
    //外部操作数：记录添加数据、删除数据的次数（记录元素个数变化的次数）
 	protected transient int modCount = 0;//4
}

这段代码是一个抽象类AbstractList，实现了List接口。下面是对代码的解析：

1. AbstractList类的定义：

• E：泛型参数，表示列表中的元素类型。
• AbstractCollection：继承了AbstractCollection抽象类，实现了Collection接口。
• List：实现了List接口。

2. modCount变量：

• modCount：记录添加数据、删除数据的次数，即记录元素个数变化的次数。
• transient修饰符：表示该变量不会被默认的序列化机制序列化，即不会被保存到文件中。
• 初始值为0。

3. modCount变量的作用：

• 在集合框架中，modCount变量用于实现"快速失败"机制。
• 当对集合进行迭代操作时，如果在迭代过程中集合的结构发生了变化（例如添加或删除了元素），那么就会抛出ConcurrentModificationException异常，以避免出现并发修改的问题。
• modCount变量记录了集合结构发生变化的次数，每次添加或删除元素时，都会增加modCount的值。
• 在迭代操作中，会将modCount的值保存下来，然后在迭代的过程中检查modCount是否发生了变化，如果发生了变化，则抛出异常。
• 这样可以在迭代过程中及时发现并发修改的情况，避免出现不一致的问题。

public class ArrayList<E> extends AbstractList<E> implements List<E>{
    //数据容器
    transient Object[] elementData;//["aaa","bbb","ccc","ddd",null,null,...]
    //元素个数/指针
    private int size;//4
    
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    
    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    
    public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }
    
    private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work
    }
    
    public Iterator<E> iterator() {
        return new Itr();
    }
    
    private class Itr implements Iterator<E> {
        int cursor;       // 游标 - 4
        int lastRet = -1; // 遍历当前元素的下标 - 3
        int expectedModCount = modCount;//内部操作数 - 4

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

        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();//判断内外操作数是否一致，不一致就报错
            //i = 3
            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];
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                //迭代器内部还是使用ArrayList的remove方法去做删除
                ArrayList.this.remove(lastRet);
                //把当前的元素下标赋值给游标
                cursor = lastRet;
                lastRet = -1;
                //重新将外部操作数赋值给内部操作数，保证了内外部操作数是一致的
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        final void checkForComodification() {
            //外部操作数不等于内部操作数就报错
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }
}

这段代码是一个ArrayList类，继承了AbstractList类，实现了List接口。下面是对代码的解析：

1. ArrayList类的定义：

• E：泛型参数，表示列表中的元素类型。
• AbstractList：继承了AbstractList抽象类，实现了List接口。
• List：实现了List接口。

elementData数组：

• elementData：数据容器，用于存储ArrayList中的元素。
• transient修饰符：表示该变量不会被默认的序列化机制序列化，即不会被保存到文件中。
• Object[]：数组类型为Object，可以存储任意类型的对象。
• 初始值为null。

size变量：

• size：元素个数/指针，表示ArrayList中当前存储的元素个数。
• 初始值为0。

1. add方法：用于向ArrayList中添加元素。

1. 参数e：要添加的元素。
2. ensureCapacityInternal方法：确保ArrayList的容量足够存放新的元素。

• size + 1：计算新的元素个数。
• 调用ensureCapacityInternal方法，传入新的元素个数，确保容量足够。

3. elementData[size++] = e：将新的元素添加到elementData数组中，并将size加1。

• elementData：数据容器，存储ArrayList中的元素。
• size++：先将size的值赋给elementData数组的下标，然后将size加1。
• e：要添加的元素。

4. 返回true表示添加成功

2. ensureCapacityInternal方法，用于确保ArrayList的容量足够存放新的元素。

1. 参数minCapacity：最小需要的容量。
2. 判断elementData数组是否为默认空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA。

• DEFAULTCAPACITY_EMPTY_ELEMENTDATA：默认的空数组，用于表示ArrayList初始时没有元素。
• 如果elementData数组是默认空数组，表示ArrayList是刚刚创建的，容量为0。
• 此时，需要根据minCapacity和DEFAULT_CAPACITY的比较结果来确定新的容量。

3. Math.max(DEFAULT_CAPACITY, minCapacity)：取DEFAULT_CAPACITY和minCapacity中的较大值。

• DEFAULT_CAPACITY：默认的初始容量，为10。
• minCapacity：最小需要的容量。
• 如果minCapacity小于DEFAULT_CAPACITY，将新的容量设为DEFAULT_CAPACITY。

4. 调用ensureExplicitCapacity方法，传入新的容量，确保容量足够。

• ensureExplicitCapacity方法会根据新的容量和当前容量的大小关系，决定是否需要扩容。

3. ensureExplicitCapacity方法，用于确保ArrayList的容量足够存放新的元素。

1. 参数minCapacity：最小需要的容量。
2. modCount++：增加modCount的值。

• modCount：用于记录ArrayList结构发生变化的次数，用于迭代器的快速失败机制。

3. 判断minCapacity与elementData数组的长度的差值是否大于0。

• 如果minCapacity大于elementData数组的长度，表示当前容量不足以容纳新的元素。
• 需要调用grow方法进行扩容。

4. 调用grow方法，传入minCapacity，进行扩容操作。

• grow方法会根据新的容量需求，进行扩容操作。

4. remove方法，用于从ArrayList中移除指定的元素。

1. 参数o：要移除的元素。
2. 判断参数o是否为null。

• 如果o为null，表示要移除的元素为null。
• 遍历elementData数组，查找第一个为null的元素。
• 调用fastRemove方法，传入找到的元素的索引，进行快速移除。
• 返回true表示成功移除了元素。

3. 如果o不为null，表示要移除的元素不为null。

• 遍历elementData数组，查找第一个与o相等的元素。
• 调用fastRemove方法，传入找到的元素的索引，进行快速移除。
• 返回true表示成功移除了元素。

4. 如果遍历完整个elementData数组都没有找到要移除的元素，则返回false表示没有移除任何元素。

5. fastRemove方法，用于快速移除指定索引位置的元素。

1. 参数index：要移除的元素的索引。
2. modCount++：增加modCount的值。
3. 计算需要移动的元素个数。

• numMoved = size - index - 1：计算需要移动的元素个数，即从index位置开始，到最后一个元素之间的元素个数。

4. 如果需要移动的元素个数大于0，表示需要进行元素的移动操作。

• 使用System.arraycopy方法，将从index+1开始的元素复制到index位置，覆盖掉要移除的元素。
• 这样就实现了快速移除。

5. 将最后一个元素置为null。

• elementData[--size] = null：将最后一个元素置为null，以便垃圾回收机制回收。
• 这样就完成了元素的快速移除操作。

6. iterator方法，用于返回一个迭代器对象。

1. 返回类型：Iterator，表示返回的是一个实现了Iterator接口的对象，可以用于遍历ArrayList中的元素。
2. 创建一个新的Itr对象并返回。

• Itr是ArrayList的内部类，实现了Iterator接口。
• 通过返回Itr对象，可以使用该对象的方法来遍历ArrayList中的元素。

7. ArrayList类中的Itr内部类，实现了Iterator接口，用于遍历ArrayList中的元素。

1. 属性：

• cursor：游标，表示当前遍历的元素的索引。
• lastRet：上一个遍历的元素的索引。
• expectedModCount：内部操作数，用于判断内外部操作数是否一致。

2. hasNext方法：

• 判断游标是否等于size，如果等于size，表示已经遍历到了最后一个元素，返回false；否则返回true。

3. next方法：

• 调用checkForComodification方法，判断内外部操作数是否一致，如果不一致，抛出ConcurrentModificationException异常。
• 将游标的值赋给局部变量i。
• 如果i大于等于size，表示已经遍历到了最后一个元素，抛出NoSuchElementException异常。
• 获取外部ArrayList对象的elementData数组。
• 如果i大于等于elementData数组的长度，表示在遍历过程中，ArrayList的结构发生了改变，抛出ConcurrentModificationException异常。
• 将游标的值加1，表示遍历到下一个元素。
• 返回elementData数组中lastRet索引位置的元素，并将i赋给lastRet。

4. remove方法：

• 如果lastRet小于0，表示没有执行过next方法或者已经执行过remove方法，抛出IllegalStateException异常。
• 调用checkForComodification方法，判断内外部操作数是否一致，如果不一致，抛出ConcurrentModificationException异常。
• 使用ArrayList的remove方法，根据lastRet的值删除元素。
• 将游标的值赋给lastRet。
• 将lastRet的值置为-1，表示已经执行过remove方法。
• 将外部操作数的值赋给内部操作数，保证内外部操作数一致。
• 如果捕获到IndexOutOfBoundsException异常，表示在遍历过程中，ArrayList的结构发生了改变，抛出ConcurrentModificationException异常。

5. checkForComodification方法：

• 判断内外部操作数是否一致，如果不一致，抛出ConcurrentModificationException异常。

场景：
    ArrayList<String> list = new ArrayList<>();
    list.add("aaa");
    list.add("bbb");
    list.add("ccc");
    list.add("ddd");

    Iterator<String> it = list.iterator();
    while(it.hasNext()){
        String element = it.next();
        System.out.println(element);
    }

使用了ArrayList的iterator方法返回一个迭代器对象，然后通过迭代器遍历ArrayList中的元素，并打印出来。

1. 创建一个ArrayList对象，并添加了四个元素。
2. 调用ArrayList的iterator方法返回一个迭代器对象，赋值给it。
3. 使用while循环，判断迭代器是否还有下一个元素，如果有，则执行循环体内的代码。
4. 调用迭代器的next方法获取下一个元素，并将其赋值给element。
5. 打印element。
6. 循环结束后，所有元素都被遍历完毕，程序结束。