ArrayList数据结构设计原理的简要深入分析.md

成员变量

空参构造非常简单，它会为我们创建一个空的集合。elementData成员变量是用来存放数据的对象,是一个Object[]，DEFAULTCAPACITY_EMPTY_ELEMENTDATA则是一个空的数组。

/**
　* Constructs an empty list with an initial capacity of ten.
　*/
public ArrayList() {
　　this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

空参构造非常简单，它会为我们创建一个空的集合。elementData成员变量是用来存放数据的对象,是一个Object[]，DEFAULTCAPACITY_EMPTY_ELEMENTDATA则是一个空的数组。注意DEFAULTCAPACITY_EMPTY_ELEMENTDATA类型为static final，表明其在内存中只有一份且禁止修改。

　* Shared empty array instance used for default sized empty instances. We
　* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
　* first element is added.
　*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

注意elementData使用transient修饰。表明在采用Java默认的序列化机制的时候，被该关键字修饰的属性不会被序列化。而ArrayList类实现了java.io.Serializable接口，即采用了Java默认的序列化机制。但是elementData在网络传输的时候不序列化肯定是不行的，翻看源码会发现ArrayList自己实现了序列化和反序列化的方法。

transient Object[] elementData; // non-private to simplify nested class access

构造方法

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) { //如果指定了初始容量，则用该容量去new一个10的null数组
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
  	// 10个容量的空数组,注意this.elementData一定是指向数组本身
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray(); //取出集合的数组元素，放到Object[]数组中
    if ((size = elementData.length) != 0) { 
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
          	// 将c.toArray()拷贝到一个新Object数组上，并用elementData指向它
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA; //DEFAULTCAPACITY_EMPTY_ELEMENTDATA用在空参数的构造方法中，而EMPTY_ELEMENTDATA用在入参为集合的构造方法中。
    }
}

add方法

首次add一个元素时：

public boolean add(E e) {
    //首次添加时，size=0，将size+1看看是否有超过默认容量10，注意minCapacity=size + 1),size+1表示elementData所需要的最小长度。这里的size变量，是用来记录ArrayList包含元素的多少的，初始值为0
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e; //注意这里是指elementData[size] = e 然后再将size自增1
  	//切勿以为index=size+1然后elementData[index]=e，否则就会出现首个元素对应elementData[1]这样的误解
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

calculateCapacity

private static int calculateCapacity(Object[] elementData, int minCapacity) {
  	//首次add一个元素时,elementData就是指向DEFAULTCAPACITY_EMPTY_ELEMENTDATA，而minCapacity=size+1=0+1，因此calculateCapacity返回10给到ensureExplicitCapacity
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
  	// 每次添加一个节点后，minCapacity=size+1
    return minCapacity; 
}

首次add一个元素时：

private void ensureExplicitCapacity(int minCapacity) {
    modCount++; //首次add一个元素，modCount当然为1

    // overflow-conscious code
   	// 首次add一个元素，前面计算出minCapacity=10，而elementData.length=0，因此需要grow增加数组容量（因为空构造方法创建的是空数组，而添加一个元素前，就需要将数组容量扩容到10）
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

grow

private void grow(int minCapacity) {
    // overflow-conscious code
   // 首次add一个元素时，elementData还是空数组
    int oldCapacity = elementData.length;// 0
  	// 扩容值：new=old+0.5old=1.5old
    int newCapacity = oldCapacity + (oldCapacity >> 1); //0
    if (newCapacity - minCapacity < 0) //前面算出minCapacity=10
        newCapacity = minCapacity; // 因此使用10作为elementData首次add的数组容量
    if (newCapacity - MAX_ARRAY_SIZE > 0) // MAX_ARRAY_SIZE=Integer.MAX_VALUE - 8
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
  	// 首先elementData还是空数组，经过以下数组扩容后（本质是利用拷贝到新数组实现），elementData指向了一个容量10的null数组
    elementData = Arrays.copyOf(elementData, newCapacity);
  	//也即以上执行完后，elementData.length=10,但此时size还是=1
}

hugeCapacity

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow 
        throw new OutOfMemoryError();
   	// 看看是否需要取到最大值：2^31-1
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

ensureCapacity

/**
 * Increases the capacity of this <tt>ArrayList</tt> instance, if
 * necessary, to ensure that it can hold at least the number of elements
 * specified by the minimum capacity argument.
 *
 * @param   minCapacity   the desired minimum capacity
 */
public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
        // any size if not default element table
        ? 0
        // larger than default for default empty table. It's already
        // supposed to be at default size.
        : DEFAULT_CAPACITY;
		//上面看的是是否达到10的默认容量，如果计算出的最小需求容量大于最小扩容容量，那么就需要进行扩容了
  	// 例如minCapacity=11，minExpand要么是0，要么就是10，显然是需要扩容的
    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}

trimToSize

例如elementData是一个容量为10的数组，而当前elementData仅拥有一个元素，那么使用trimToSize后，

elementData就是一个容量为1的数组，“感觉像被压实了”。

/**
 * Trims the capacity of this <tt>ArrayList</tt> instance to be the
 * list's current size.  An application can use this operation to minimize
 * the storage of an <tt>ArrayList</tt> instance.
 */
// 官方都说这样裁剪可以使用最小空间来存储一个ArrayList
public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
          ? EMPTY_ELEMENTDATA
          : Arrays.copyOf(elementData, size);
    }
}

从上面也可以看出，只要实际元素个数少于数组容量，那么就可以进行“数组裁剪”，如果如果size为0，那么

就让elementData指向EMPTY_ELEMENTDATA这个空数组，（在这里再次可以感受到与DEFAULTCAPACITY_EMPTY_ELEMENTDATA的区别），否则就会使用Arrays.copyOf方法，创建一个只有size容量的数组，然后elementData再指向它。

indexOf

返回给定元素所在的下标，可以看到：如果存在，则返回值就是0到size-1方法

public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

contains复用了indexOf；显然如果检索不到，返回-1，那么下面就会返回false

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

尾部遍历lastIndexOf

显然最后一个元素对应的下标是size-1

public int lastIndexOf(Object o) {
    if (o == null) {
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

注意toArray的官方解释

返回的array是不存在有任何引用指向它，因为它是全新分配的，因此caller可以自由修改toArray() 返回的数组。

/**
 * Returns an array containing all of the elements in this list
 * in proper sequence (from first to last element).
 *
 * <p>The returned array will be "safe" in that no references to it are
 * maintained by this list.  (In other words, this method must allocate
 * a new array).  The caller is thus free to modify the returned array.
 *
 * <p>This method acts as bridge between array-based and collection-based
 * APIs.
 *
 * @return an array containing all of the elements in this list in
 *         proper sequence
 */
public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

Positional Access Operations

// Positional Access Operations

  @SuppressWarnings("unchecked")
  E elementData(int index) {
      return (E) elementData[index];
  
  
	 public E get(int index) {
        rangeCheck(index);
        return elementData(index);
    }
  
    public E set(int index, E element) {
        rangeCheck(index);
		
        E oldValue = elementData(index);	//取出旧值
        elementData[index] = element; // 设置新值
        return oldValue;	//返回旧值
    }

rangeCheck

private void rangeCheck(int index) {
  	//只要给定的下标index大于等于size，即可抛出异常
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

add

Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).

public void add(int index, E element) {
    rangeCheckForAdd(index);
    ensureCapacityInternal(size + 1);  // Increments modCount!!
  	/* 从源数组的index到index+(length-1)个元素要拷贝，因为length=size - index，因此对于src来说，拷贝的元素范围为[index,index+(size - index -1)]，也即src拷贝元素的范围是[index,size-1]
  	放在目标数组：index+1位置到index+1+(length-1)
  	而length=size - index个，这里是size是src的实际元素个数，故index+1+(size - index-1)=size
  	对于dest来说，就是讲src的元素放置在[index+1,size]位置上，由于dest就是源数组，因此需要确保新的源数组容量至少比之前大1个空位。
  	将[index,size-1]的元素整体往右挪动1格，变成[index+1,size]，这就是官方解释的
  	 Shifts the element currently at that position (if any) and any subsequent elements to the right，然后adds one to their indices
   	*/ 
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element; //再将原index位置元素覆盖即可
    size++;
}

检查所插入的位置index是否合法

/**
 * A version of rangeCheck used by add and addAll.
 */
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

size和index的区别

例如：如果一个数组a的元素个数有3个，那么size就等于3，也即size是从1开始计算

那么索引呢？ index最大值为2，因为索引是从0开始计算，因此为了简化思维：

如果要计算元素个数差值：需要将index和size对齐，再来做加减

index+1即可对齐size的元素计数

因此在下面的remove方法即可用到这种计算策略！！

remove

跟add相反：把index+1~size的元素向左边整体挪动一格，挪到index~size-1

    /**
     * Removes the element at the specified position in this list.
     * Shifts any subsequent elements to the left (subtracts one from their
     * indices).
     *
     * @param index the index of the element to be removed
     * @return the element that was removed from the list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
public E remove(int index) {
    rangeCheck(index); // 确保给定下标不越界

    modCount++; 
    E oldValue = elementData(index);  // eturn (E) elementData[index]
		/*(1) 索引index对齐到size
		size元素个数的计算视角是从1开始，index索引计算视角是从0开始，先对齐index+1，那么要迁移的元素个数就是
  	 numMoved=size-(index-1)
  	（2）size转为索引视角
  	size-1就是变成从0开始计数，也即跟索引index对齐
  	因此计算元素个数：索引a-索引b就是元素差的个数，也即numMoved=size-1-index
  	*/
    int numMoved = size - index - 1; ;
    if (numMoved > 0)
      	//从[index+1,size-1]的元素整体向左迁移一格变成[index,size-2]
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work 将elementData数组的第size-1个桶位置空用于GC

    return oldValue;
}

以下案例模拟remove操作

String[] src={"foo","bar","foobar"};
// 将[1,2]的元素迁移到[0,1]中，迁移的元素个数2个 
System.arraycopy(src,1,src,0,2);
System.out.println(Arrays.toString(src));  // [bar, foobar, foobar]
src[2]=null; // elementData[--size] = null
System.out.println(Arrays.toString(src)); // [bar, foobar, null]

删除一个对象

先使用遍历桶位的方式去处理，如果找到，则调用fastRemove删除

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

fastRemove：其实就是remove方法里面跳过index检查以及目标删除值返回

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
}

clear

注意：虽然clear会把所有桶位置null，但是只能算一次结构修改！！

public void clear() {
    modCount++;

    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;
    size = 0; // 这里可以再次看到size是实际元素个数
}

System.arraycopy

src: the source array 源数组

srcPoc: 从该位置开始拷贝拷贝元素

dest: 目标数组

destPos：从该位置开始放置拷贝过来元素

length：要将源数组拷贝多少个元素到目标数组中

 * @param      src      . //
 * @param      srcPos   starting position in the source array.
 * @param      dest     the destination array.
 * @param      destPos  starting position in the destination data.
 * @param      length   the number of array elements to be copied.
 System.arraycopy(elementData, index, elementData, index + 1,
                 size - index);

官方注释：

/**
 * Copies an array from the specified source array, beginning at the
 * specified position, to the specified position of the destination array.
 * A subsequence of array components are copied from the source
 * array referenced by <code>src</code> to the destination array
 * referenced by <code>dest</code>. The number of components copied is
 * equal to the <code>length</code> argument. The components at
 * positions <code>srcPos</code> through
 * <code>srcPos+length-1</code> in the source array are copied into
 * positions <code>destPos</code> through
 * <code>destPos+length-1</code>, respectively, of the destination
 * array.
 * <p>

也即将src中范围为srcPoc~srcPoc+length-1 的节点，拷贝到destPos~destPos+length-1，拷贝的节数数量有length个

实例

String[] src={"foo","bar","foobar"};
String[] dest={"public","private","protected","this"};
System.arraycopy(src,1,dest,1,2);
System.out.println(Arrays.toString(dest)); //输出：[public, bar, foobar, this]

将src数组中的“bar”、“foobar”这两个元素拷贝到dest的index=1中，覆盖两个元素，显然”private”,”protected”会被覆盖

异常情况

• ArrayIndexOutOfBoundsException

那么如果拷贝的元素数量length大于dest数组长度，那么显然会抛出异常

String[] src={"foo","bar","foobar"};
String[] dest={"public","private","protected","this"};
System.arraycopy(src,1,dest,2,3);
System.out.println(Arrays.toString(dest)); //ArrayIndexOutOfBoundsException

因为destPos+length大于dest.length，也即destPos+length=2+3=5，大于dest.length=4

或者srcPos+length大于src.length，表示指定要拷贝的元素数量超过实际拥有的元素

srcPos+length=1+3=4,大于src.length=3

• NullPointerException

System.arraycopy(null,1,dest,1+1,src.length-1);
System.arraycopy(src,1,null,1+1,src.length-1);

源数组为空，没元素可供拷贝，目标数组为空，拷贝的元素没地方放置

• ArrayStoreException

System.arraycopy(src,1,"test",1+1,src.length-1);

有其中一个不是数组类型的

或者src和

addAll

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length; // 这里的length就是c集合实际元素的个数，不是c集合底层数组的容量长度
    ensureCapacityInternal(size + numNew);  // Increments modCount
  	// 将c集合的0~length-1范围内的元素拷贝到，elementData的[size,length-1]位置上
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

removeRange

Removes from this list all of the elements whose index is between fromIndex, inclusive, and toIndex, exclusive。Shifts any succeeding elements to the left (reduces their index). This call shortens the list by (toIndex - fromIndex) elements

例如，[0,3]，size=4，现在要删除fromIndex=1，toIndex=3，其中不包括toIndex=3指向的元素

ArrayList<String> src= new ArrayList<String>(Arrays.asList("foo","bar","foobar","test"));
System.out.println(src.subList(1,3)); // [bar, foobar]

截取子链的数量：toIndex-fromIndex

底层调用：

[0,….fromIndex,….,toIndex,…..size-1]

实际要拿走的元素访问是[formIndex,toIndex-1]

protected void removeRange(int fromIndex, int toIndex) {
    modCount++;  //删除再多也是被计为改动一次
  	/*（1）
  	使用size对齐到索引index,因为removeRange不包括toIndex指向的节点，因此实际只删除到toIndex-1
  	(size-1)-(toIndex-1)=size-toIndex
  	（2）或者说size本身元素个数视角，toIndex相当于元素个数视角，因此要挪动元素个数就是size-toIndex个
  	*/
    int numMoved = size - toIndex; //也可通过索引角度来计算
  	// 将toIndex到toIndex+length-1向左迁移到fromIndex~fromIndex+length-1
    System.arraycopy(elementData, toIndex, elementData, fromIndex,
                     numMoved);

    // clear to let GC do its work
  	// 将size转为索引视角：size-1，将toIndex转为索引视角:toIndex-1，fromIndex本身就是索引视角
  	// 0->fromIndex->toIndex-1->size-1
  	//剩余的元素个数为：(size-1)-(toIndex-1-fromIndex)=size-(toIndex-fromIndex)
    int newSize = size - (toIndex-fromIndex);
    for (int i = newSize; i < size; i++) {
        elementData[i] = null;
    }
    size = newSize;
}

removeAll

 ArrayList<String> src= new ArrayList<String>(Arrays.asList("foo","bar","foobar","test"));
 ArrayList<String> dest= new ArrayList<String>(Arrays.asList("foo","bar","foobar"));
	System.out.println(src.removeAll(dest)); //true
System.out.println(src); // [test]

public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}

batchRemove

private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData; // 原列表
    int r = 0, w = 0; 
    boolean modified = false;
  	// r是读索引指针，w是写索引指针
    try {
        for (; r < size; r++) //size是原列表元素个数
          	// 首先原列表要删除c这个子集，那么就说要保留只在list且不在c中元素即可
          // c.contains(elementData[r])==fasle,说明不在c里面，就将写入到elementData的w位置
          // 因此最终就是0到w个保留了，而w+1到size-1被删除
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
      /*
      比如写到第r个元素发生了异常，那么由于elementData保留到[0,w]个元素，那么直接再把r+1到size-1这一段节点迁移到从w开始处
        */
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r; // w是个数，加上拷贝过来的(length= size - r)个就是
        }
        if (w != size) {
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

retainAll是removeAll的相反版本：

将list保留和c一样的元素，也即只保留c和list的交集

public boolean retainAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, true);
}

  ArrayList<String> src= new ArrayList<String>(Arrays.asList("foo","bar","foobar","test"));
  ArrayList<String> dest= new ArrayList<String>(Arrays.asList("foo","bar","foobar"));
System.out.println(src.retainAll(dest));
System.out.println(src); //[foo, bar, foobar]

transient 在ArrayList的作用！

然后我们看一下ArrayList的源码中是实现了java.io.Serializable序列化了的，也就是transient Object[] elementData; 这行代码的意思是不希望elementData被序列化，那这时候我们就有一个疑问了，为什么elementData不进行序列化？这时候我去网上找了一下答案，觉得这个解释是最合理且易懂的“

在ArrayList中的elementData这个数组的长度是变长的,java在扩容的时候,有一个扩容因子,也就是说这个数组的长度是大于等于ArrayList的长度的,我们不希望在序列化的时候将其中的空元素也序列化到磁盘中去，只需要那些桶位不为空的节点，所以需要手动的序列化数组对象,所以使用了transient来禁止自动序列化这个数组

 // Write out all elements in the proper order.
//从遍历的细节可以看出：size是实际的元素个数，因此以下是把实际元素写入流中，所以这里不是用 elementData.length作为遍历极值，因为elementData.length是数组长度容量
 for (int i=0; i<size; i++) {
     s.writeObject(elementData[i]);
 }

以上需要改为下面的逻辑吗：

注意：不能这么写，因为ArrayList的元素可以为null，如果按下面这么写，就把需要序列化的元素给排除了。

for (int i=0; i<size; i++) {
  	if(elementData[i] != null)
    		s.writeObject(elementData[i]);
}

Iterator

Returns an iterator over the elements in this list in proper sequence.

该迭代器是从列表的左到右方向迭代的

public Iterator<E> iterator() {
    return new 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;

    Itr() {}

    public boolean hasNext() {
        return cursor != size; // cursor有效指向范围跟索引一样：o到size-1
    }

    @SuppressWarnings("unchecked")
  
  	/*
  	观测cursor指向
        Iterator<String> iterator= src.iterator();
        iterator.next(); //cursor=1 ,返回是的lastRet=cursor-1值，cursor指向的值
        iterator.next();//cursor=2
        while (iterator.next()!=null){
            iterator.remove();
        }
      */
    public E next() {
      	// 每次执行next()过程都会检查fail-fast
        checkForComodification();
        int i = cursor; 
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
      	//首次调用next()方法时：放置值是lastRet = i指向的元素，也即0指向的元素，此时cursor指针会指向下一个元素
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }
  
  

    public void remove() {
      /*
      	每次remove方法前必须调用next()方法，以下是错误示范
      	（1）
        while (iterator.hasNext()){
            iterator.remove();
        }
        （2）仅有一次next()调用，但在第一次remove()执行完后，lastRet、cursor都会置为初始值，因此第二次remove()必然IllegalStateException
        iterator.next();
        while (iterator.hasNext()){
            iterator.remove();
        }
       
       */
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.remove(lastRet);
/*
        ArrayList<String> src= new ArrayList<String>(Arrays.asList("foo","bar","foobar"));
        Iterator<String> iterator= src.iterator();
        while (iterator.next()!=null){  
            iterator.remove();
        }
        可以看到，如果是上面这样的while循环，那么lastRet和cursor就会在-1,0到0，1来回变化
  */          
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;  //这就是为何在迭代器中使用remove方法不会造成fail-fast原因
        } 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; //如果当前游标指针指向size，说明无元素处理了
        if (i >= size) {
            return;
        }
        final Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length) {
            throw new ConcurrentModificationException();
        }
      	// 只要i未越界且迭代过程没有其他结构性修改，
        while (i != size && modCount == expectedModCount) {
          	//也即consumer.accept((E) elementData[i])，然后在i++
            consumer.accept((E) elementData[i++]);
        }
        // update once at end of iteration to reduce heap write traffic
        cursor = i; //循环内部已经更新i指针了，其实此时i=size,cursor=size，lastRet=cursor-1
        lastRet = i - 1;
        checkForComodification();
    }

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

forEachRemaining

System.out.println("first:"+iterator.next());
System.out.println("remain:");
iterator.forEachRemaining(p->System.out.println(p)); //最终cursor会指向size，lastRet指向size-1

输出：

first:foo
remain:
bar
foobar

ListIterator具有增强功能

对比iterator：可以反向迭代、可以指定任意索引位置开始迭代

/**
 * An optimized version of AbstractList.ListItr
 */
private class ListItr extends Itr implements ListIterator<E> {
    ListItr(int index) {
        super();
        cursor = index; // 可以指定从哪个索引位置开始启用迭代器
    }

    public boolean hasPrevious() {
        return cursor != 0; // 当cursor指向0时，显然迭代器当然没有previous节点了，再比如cursor=1时，迭代器还有一个previous节点即elementData[0]
    }

    public int nextIndex() {
        return cursor; //因为cursor本身就是指向下一个索引位置,当index=0，那么cursor=0，nextIndex()也是指向0
    }

    public int previousIndex() {
        return cursor - 1;  // 因为cursor本身就是指向下一个索引位置,那么 cursor - 1就是前一个索引位置
    }

  
    @SuppressWarnings("unchecked")
    public E previous() {
        checkForComodification();
        int i = cursor - 1;  // 例如cursor=size，由于previous是不断向左边迭代，第一次遍历时，尾部节点显然是size-1也即cursor-1指向的节点
        if (i < 0) //i的有效取值范围0到cursor-1
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i; // 更新游标，将cursor指向当前处理的节点索引i
        return (E) elementData[lastRet = i];//
    }

    public void set(E e) {
      	// 要启动next()方法才能调用set
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.set(lastRet, e); // 注意this.set方法里面有rangeCheck(index)，其中index>=size就会抛出异常
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    public void add(E e) {
      
        checkForComodification();

        try {
            int i = cursor; 
            ArrayList.this.add(i, e);
            cursor = i + 1; // 增加1个元素后，cursor也要指向下一个位置
            lastRet = -1; // 因为add无需返回值，因此可需要设为初始值-1
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
}