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 条评论
登录 后参与评论

相关文章

来自专栏Java开发者杂谈

最大公约数的算法

算法的原理:   对于辗转相除法:i和j的最大公约数,也就是i和j都能够除断它。换句话讲,就是i比j的n倍多的那个数k(i = j*n + k,即i % j =...

2908
来自专栏james大数据架构

原生JS编写的照片墙效果实例演示特效

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.or...

18010
来自专栏Java后端技术

一道面试题引发的思考

为什么呢?那么我们怎么来发现它背后的秘密呢?答案只有一个:那就是通过源码来解惑(ArrayList部分源码)。

500
来自专栏猿人谷

求大于整数m且紧靠m的k个素数 及 判断一个数是否为素数的方法

题目:   请编写一个函数void fun(int m,int k ,int xx[]),该函数的功能是:将大于整数m且紧靠m的k个素数存入xx所指的数组中。 ...

1679
来自专栏Android知识点总结

Java容器源码攻坚战--第二战:ArrayList

942
来自专栏ml

斗地主算法

       不得不承认,算法搁置了一些时间,代码的风格下降了好多!  贴上一个曹点多多且丑的代码!  Orz...  题目要求:      编码:3表示3点 ...

6508
来自专栏Hongten

素数_面试中常考

(如:由2÷1=2,2÷2=1,可知2的因数只有1和它本身2这两个约数,所以2就是质数。

742
来自专栏10km的专栏

javabean:boolean和Boolean类型的getter方法名是有区别的

javaBean中,要设置或获取某个property的值,就需要相应的get和set方法,对于primitive和自定义类类型的属性(如:property),g...

1719
来自专栏拭心的安卓进阶之路

Java 集合源码解析(2):ListIterator

今天心情和股票一样红,还是学学 ListIterator 吧! ListIterator ? 根据官方文档介绍, ListIterator 有以下功能: 允许...

1969
来自专栏于晓飞的专栏

读 Java TimSort算法 源码 笔记

本来准备看Java容器源码的。但是看到一开始发现Arrays这个类我不是很熟,就顺便把Arrays这个类给看了。Arrays类没有什么架构与难点,但Arrays...

742

扫码关注云+社区