Iterator在ArrayList中的源码实现

获取迭代器

List<LinkedHashMap> list = new ArrayList<>();
        Iterator iterator = list.iterator();

iterator()方法实现

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

Itr 源码

/**
 * An optimized version of AbstractList.Itr
 */
private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

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

    @SuppressWarnings("unchecked")
    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];
    }

    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();
        }
    }

    @Override
    @SuppressWarnings("unchecked")
    public void forEachRemaining(Consumer<? super E> consumer) {
        Objects.requireNonNull(consumer);
        final int size = ArrayList.this.size;
        int i = cursor;
        if (i >= size) {
            return;
        }
        final Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length) {
            throw new ConcurrentModificationException();
        }
        while (i != size && modCount == expectedModCount) {
            consumer.accept((E) elementData[i++]);
        }
        // update once at end of iteration to reduce heap write traffic
        cursor = i;
        lastRet = i - 1;
        checkForComodification();
    }

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

Itr 为ArrayList的一个内部类,结构:

首先看变量

int cursor;       // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;

**cursor 返回下个元素的下标索引,初始化为0

lastRet 上一个元素的下标索引,初始化为-1,因为当前元素下标为0时没有上一个元素

modCount 声明的变量如下,用于记录数组集合是否被修改过**

protected transient int modCount = 0;

使用到的方法如下:

trimToSize()
ensureExplicitCapacity()
add()
remove()
fastRemove()
clear()
addAll()
removeRange()
batchRemove()
sort()

再看一下, expectedModCount 除了初始化的时候被赋值了意外,只有在迭代过程中将modCount重新赋值给它, 其它任何时候它都不会变化。 因此,当我们用迭代器进行迭代的时候,单线程条件下,理论上expectedModCount = modCount 是恒成立的。 但在多线程环境下,就会出现二者不像等的情况。

hasNext()

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

**意思就是数组下表索引没有越界之前都是有元素的 **

next()

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

**获取当前索引下标元素,指针(cursor)后移,不多说。 **

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();
            }
        }


### 校验数组是否修改过(在迭代遍历过程中经常会抛出的异常)

这里输入代码

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

校验数组是否越界

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

数组复制:

public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);

arraycopy 的源码在这

System.arraycopy 源码

我翻看了下注释说明: 敲重点:

  • If the <code>src</code> and <code>dest</code> arguments refer to the
  • same array object, then the copying is performed as if the
  • components at positions <code>srcPos</code> through
  • <code>srcPos+length-1</code> were first copied to a temporary
  • array with <code>length</code> components and then the contents of
  • the temporary array were copied into positions
  • <code>destPos</code> through <code>destPos+length-1</code> of the
  • destination array.

就是说,原数组与将要复制的数组为同一个的时候,就是元素之间的移动。其它的实现暂时不解释。 于是,我们可以理解为:删除指定数组下标index位置的元素,然后从数组下表index+1的位置开始向前移动size-index-1 个元素,学过数据结构的童鞋 这里就很好理解啦,不多做解释。 这里的size 指的是数组的容量(如果元素不为空觉得能得到元素的个数效率更高一点)

_总结

** 1.迭代器在ArrayList中的实现,起始是对对象数组的一系列操作。**

** 2.在List集合中可以使用迭代器的原因是ArrayList 中的内部类 Itr 实现了 Iterator接口 ** ** 3. 在对数组元素进行删除或者更新添加元素等操作时,单线程下最好用迭代器, 用传统的for循环或者foreach循环都将导致异常。 解决遍历过程中对集合进行修改的问题请参考 CopyOnWriteArrayList_**

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏用户画像

6.3.2 B+树基本概念

2)非叶根(不是叶子的根结点)结点至少有两棵子树,其他每个分支结点至少有【m/2】(向下取整)棵子树。(B树是要求至少2棵子树)

992
来自专栏java技术学习之道

Java进阶--深入理解ArrayList实现原理

1293
来自专栏数据结构笔记

数据结构(六):树

ADT Tree{ ​ 数据对象: ​ D={1=<i<=n, n>=0, a(i)属于 ElemType类型} ​ 数据关系: ​...

972
来自专栏微信公众号:Java团长

Java集合源码剖析——ArrayList源码剖析

ArrayList是基于数组实现的,是一个动态数组,其容量能自动增长,类似于C语言中的动态申请内存,动态增长内存。

1122
来自专栏Java 源码分析

ArrayList 源码分析

ArrayList 源码分析 1. 在阅读源码时做了大量的注释,并且做了一些测试分析源码内的执行流程,由于博客篇幅有限,并且代码阅读起来没有 IDE 方便,所...

3494
来自专栏Bingo的深度学习杂货店

Q108 Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a hei...

3253
来自专栏wannshan(javaer,RPC)

关于 java.util.ConcurrentModificationException jdk源码分析

先看怎么发生 List<Integer> list=new ArrayList<>(); for(int i=0;i<10;i++){ list.add...

2993
来自专栏闻道于事

Java常用工具类之时间转换(注释乱码,全)

package com.wazn.learn.util; import java.text.ParseException; import java.text....

3847
来自专栏机器学习和数学

[算法与数据结构] 《算法导论》堆排序笔记

堆排序的实现是靠叫做“堆”的数据结构来实现的。所以学习堆排序,首先要了解什么是堆 堆 堆是一个数组,每个结点表示数组中的一个元素,堆可以看做是一个近似的完全二叉...

3139
来自专栏IT可乐

JDK1.8源码(五)——java.util.ArrayList 类

  关于 JDK 的集合类的整体介绍可以看这张图,本篇博客我们不系统的介绍整个集合的构造,重点是介绍 ArrayList 类是如何实现的。 1、ArrayLis...

41611

扫码关注云+社区

领取腾讯云代金券