[数据结构与算法]ArrayList、Vector、LinkedList源码学习（部分）

一、ArrayList

1、ArrayList使用的数据结构

ArrayList底层使用数组，数组是一块内存中连续的空间，数组，用于顺序存储数据，每一个数据都有一个对应的下标，可以通过下标唯一地获取数组中的数据。

在ArrayList实现中，查询效率比较高；添加和删除效率较低。

2、属性

// 该集合的序列化版本号，允许集合序列化
private static final long serialVersionUID = 8683452581122892189L;

// 集合如果没有指定长度，存入第一个元素时，初始化的elementData底层数组的默初始长度
private static final int DEFAULT_CAPACITY = 10;

// 当有参构造传入容量为0时，集合底层数组使用的空数组(之所以用这个是方便后序空集合==判断)
private static final Object[] EMPTY_ELEMENTDATA = {};

// 使用无参构造创建时，底层数组使用的值(之所以用这个是方便后序，对空集合直接用==判断地址即可)
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 当前集合底层使用来存储元素的真实数组，可以在有参构造器指定数组长度。transient修饰，说明这个集合是不会被序列化的
transient Object[] elementData;

// 保存当前底层数组的元素个数
private int size;

// 用于进行扩容时判断是否快要达到Integer的最大值，使用Integer.MAX_VALUE - 8是有些JVM支持的数组最大长度
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

3、构造器

• 如果使用无参构造器，默认这个集合底层为一个空数组；
• 如果传入的是一个数字，那么会根据这个数字创建一个指定长度的数组；
• 如果传入的是一个集合，那就把集合转为数组，然后拷贝出一份赋值给elementData，如果集合是ArrayList的话，那么直接把引用给elementData。

// 创建空集合
public ArrayList() {
    
    // 无参构造底层的数组将被赋值一个空数组{}
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

// 指定长度创建集合
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
      	// 创建指定长度的底层数组
        this.elementData = new Object[initialCapacity];
    }
    
    else if (initialCapacity == 0) {
        // 创建一个空集合，底层数组使用{}
        this.elementData = EMPTY_ELEMENTDATA;
    } 
    
    else {
        throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
    }
}

// 使用指定的集合去初始化一个数组
public ArrayList(Collection<? extends E> c) {
    // 把传入的集合转成数组
    Object[] a = c.toArray();
    
    if ((size = a.length) != 0) {
        
        // 如果传入集合是ArrayList，就直接将数组赋值给elementData
        if (c.getClass() == ArrayList.class) {
            elementData = a;
        } 
        
        else {
            // 如果传入集合不是ArrayList，就进行数组拷贝到elementData
            elementData = Arrays.copyOf(a, size, Object[].class);
        }
    } 
    
    // 如果是空集合
    else {
        // 赋值elementData为{}
        elementData = EMPTY_ELEMENTDATA;
    }
}

4、add方法

add一个元素，先检查容量是否足够，不够就会去获取最小容量，如果是然后根据最小容量扩容，默认扩容是1.5倍。

并且，当集合的最小容量已经达到了Integer.MAX_VALUE - 8时，扩容将会是扩容至Integer.MAX_VALUE，这是集合最大容量。

// 给集合放入指定的一个元素
public boolean add(E e) {
    
    // 判断是否需要扩容，如果需要会进行扩容
    ensureCapacityInternal(size + 1);
    
    // size下标对应位置用来存新元素，并且size自增
    elementData[size++] = e;
    return true;
}

// 判断是否需要扩容
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

// 计算新增元素后的容量和当前的elementData大小，返回较大值，作为最小容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

// minCapacity，表示当前集合内的数组至少要容得下minCapacity个元素
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    
    // 新增元素后的容量比elementData的长度大的话，需要扩容
    if (minCapacity - elementData.length > 0)
        // 扩容的方法
        grow(minCapacity);
}

// 扩容操作，1.5倍
private void grow(int minCapacity) {
    
    // 获取旧elementData的长度
    int oldCapacity = elementData.length;
    // 根据原本的长度扩容1.5倍
    // oldCapacity >> 1,如果oldCapacity为1010(10),那么oldCapacity >> 1为0101(5)
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    
    // 如果扩容后的长度比新增元素后的长度还小的话，新容量就要新增元素后的长度，主要是防止第一次扩容时newCapacity为0而使数组长度为0的情况
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    
    // 如果新容量已经超过ArrayList允许的最大容量，那么获取新容量为Integer.MAX_VALUE或者Integer.MAX_VALUE - 8
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    
    // 进行数组扩容
    elementData = Arrays.copyOf(elementData, newCapacity);
}

// 用于获取ArrayList在不造成堆溢出的情况下，最大扩容Integer.MAX_VALUE或者Integer.MAX_VALUE - 8
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) 
        throw new OutOfMemoryError();
    // 最大扩容Integer.MAX_VALUE或者Integer.MAX_VALUE - 8
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
    	MAX_ARRAY_SIZE;
}

在指定的index下去add元素，那会先判断index是否越界，然后判断是否需要扩容（1.5倍，最大为Integer.MAX_VALUE）；

最后再指定index坐标以及其后的元素统一使用System.arrayCopy向后移动一位。

// 在当前已经有的某个下标存入元素数据，不会覆盖原数据，index以及其后的元素都会后移
public void add(int index, E element) {
    // 判断下标是否越界
    rangeCheckForAdd(index);
    
    // 查看是否需要扩容
    ensureCapacityInternal(size + 1);
    
    // 将下表为index及其后面的全部元素，往后移动一位
    System.arraycopy(elementData, index, elementData, index + 1,size - index);
    
    // 把下表为index的位置赋值为element
    elementData[index] = element;
    
    // size自增
    size++;
}

// 查看下标是否越界，允许访问的区间为[0,size-1]
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

5、remove方法

// 根据下标删除元素
public E remove(int index) {
    // 查看下标是否越界
    rangeCheck(index);
    modCount++;
    // 获取要被删除的元素
    E oldValue = elementData(index);
    
    // 获取在index后的元素需要向前移动的位数
    int numMoved = size - index - 1;
    // 如果向前移动的位数是大于0的
    if (numMoved > 0)
        // 通过数组拷贝进行迁移
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    // 把原最后一个元素的位置置为null
    elementData[--size] = null; 
    return oldValue;
}

// 获取指定下标元素
E elementData(int index) {
    // 根据下标在数组中获取元素
    return (E) elementData[index];
}

// 删除指定的元素
public boolean remove(Object o) {
    // 如果是null
    if (o == null) {
        // 遍历删除所有为null的值
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } 
    // 如果不是null
    else {
        // 遍历删除所有equals的值
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

/*
 * Private remove method that skips bounds checking and does not
 * return the value removed.
 */
private void fastRemove(int index) {
    modCount++;
    // 获取index后的元素需要向前移动的位数
    int numMoved = size - index - 1;
    
    // 如果需要移动的话
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    
    // 把最后一位给置为null
    elementData[--size] = null; // clear to let GC do its work
}

6、为何迭代器迭代时，使用集合对象删除元素后会报错

/*
	由于在创建迭代器时，会把对ArrayList对象的修改modCount，赋值给迭代器对象的expectedModCount，如果遍历的时候，会判断modCount是否和expectedModCount相等
*/
static final class ArrayListSpliterator<E> implements Spliterator<E> {
    // 被绑定的ArrayList
	private final ArrayList<E> list;
    // 当前迭代器所在的下标
    private int index;
    // 初始值为-1，在遍历之后会保存着list的最后一个下标的下一位
    private int fence;
    // 初始化的时候，把ArrayList集合对象的modCount赋值给它
    private int expectedModCount; 
}

二、Vector

1、基本介绍和底层数据结构

和ArrayList的API基本一致，底层的实现原理也是使用数组，只不过Vector是线程安全的，几乎所有的操作方法都有加synchronized关键字。

2、属性

// 真正存储放入集合元素
protected Object[] elementData;

// 保存当前存入集合的元素的个数
protected int elementCount;

// 表示扩容时要扩容多少，如果是0，则为扩容2倍
protected int capacityIncrement;

// 序列化版本号
private static final long serialVersionUID = -2767605614048989439L;

// 限定默认是最大的容量，由于有些JVM不支持更高容量的Vector
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

3、构造器

// 传入初始化容量和每次扩容时，扩容多少
public Vector(int initialCapacity, int capacityIncrement) {
    super();
    // 如果初始化容量小于0，则不合法
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
    
    // 创建底层存储数据的指定长度的数组
    this.elementData = new Object[initialCapacity];
    // 初始化扩容因子
    this.capacityIncrement = capacityIncrement;
}


// 指定容器的初始化容量，以后的扩容，都是扩容到它的两倍
public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}

// 默认构造器，初始化容量为10，扩容为2倍
public Vector() {
    this(10);
}

// 用一个集合来初始化Vector
public Vector(Collection<? extends E> c) {
    // 获取集合的数组
    Object[] a = c.toArray();
    // 获得需要添加的元素个数
    elementCount = a.length;
    // 如果是ArrayList，那么可以直接把引用赋给Vector底层的elementData
    if (c.getClass() == ArrayList.class) {
        elementData = a;
    } else {
        // 否则，根据这个数组复制一个数组赋值给elementData
        elementData = Arrays.copyOf(a, elementCount, Object[].class);
    }
}

4、add方法

// 添加一个元素
public synchronized boolean add(E e) {
    // 标志当前集合已经修改
    modCount++;
    // 判断是否需要扩容并扩容
    ensureCapacityHelper(elementCount + 1);
    // 把元素放到下标为容器长度的位置
    elementData[elementCount++] = e;
    return true;
}

// 判断是否需要扩容，并调用方法扩容
private void ensureCapacityHelper(int minCapacity) {
    // 判断是否需要扩容
    if (minCapacity - elementData.length > 0)
        // 扩容
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // 获取旧容量
    int oldCapacity = elementData.length;
    // 获取扩容后的新容量，如果capacityIncrement是0，那么扩容为2倍
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
    // 判断size+1后跟新容量那个比较大，使用较大者进行扩容
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 判断新容量是否大于指定的最大值
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

// 获取最大的容量，只有当capacity大于Integer.MAX_VALUE - 8才会执行
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0)
        throw new OutOfMemoryError();
    // 如果长度大于Integer.MAX_VALUE - 8，那么扩容至Integer.MAX_VALUE
    return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
}

5、copyInto方法

// 把Vector内部的数组复制一份到传入的数组中
public synchronized void copyInto(Object[] anArray) {
    System.arraycopy(elementData, 0, anArray, 0, elementCount);
}

三、LinkedList

1、基本介绍和底层数据结构

• LinkedList底层实现了双向链表和双端队列特点，是非顺序的存储结构，数据元素的逻辑顺序通过链表节点的指针连接实现；
• 链表是由一系列节点（链表中的元素称为节点）组成，节点可以在运行时动态生成，每个节点包括两个部分：存储数据的数据域，存储下一个节点指针的指针域；
• 双链表是链表的一种，由节点组成，每个节点有两个指针，分别指向直接前驱和直接后继节点；
• 可以添加任意元素元素还可以重复，可以为null；线程不安全，没有实现同步。

2、属性

// 存入链表中的元素个数
transient int size = 0;

// 头节点
transient Node<E> first;

// 尾结点
transient Node<E> last;

3、构造器

public LinkedList() {
    
}
// 使用别的集合来初始化LinkedList
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

4、私有静态内部Node类

节点，是链表的组成，LinkedList每一个数据都是存在Node中。

private static class Node<E> {
    // 节点存储的数据
    E item;
    // 节点的直接前驱节点
    Node<E> next;
    // 节点的直接后继节点
    Node<E> prev;
    
    Node(Node<E> prev, E element, Node<E> next) {
		this.item = element;
        this.next = next;
       	this.prev = prev;
	}
}

5、add方法

获取头节点，如果头节点本为null，那么就设置新节点为头节点；如果不是null，那就设置头节点为新节点，然后原头节点的前驱节点为新节点；

// 加入一个元素到链表的第一位
public void addFirst(E e) {
    // 添加在链表的末尾
    linkFirst(e);
}

// 添加在链表的第一位
private void linkFirst(E e) {
    // 获得头节点
    final Node<E> f = this.first;
    // 创建新节点
    final Node<E> newNode = new Node<>(null, e, f);
    // 把链表的this.first指针指向新节点
    this.first = newNode;
    // 判断原头指针是不是null，就是判断原本链表中有没有元素
    if (f == null)
        // 如果没有，那么尾结点也是新节点
        last = newNode;
    // 如果不是null
    else
        // 那头节点就是新节点
        f.prev = newNode;
    // 节点数++
    size++;
    // 记录链表被修改
    modCount++;    
}

直接add一个元素，本质就是添加节点到链表末尾；

// 添加元素到链表中
public boolean add(E e) {
    // 添加元素到链表结尾
    linkLast(e);
    return true;
}

// 添加元素到链表结尾
void linkLast(E e) {
    // 获取尾节点
    final Node<E> l = this.last;
    // 创建新节点
    final Node<E> newNode = new Node<>(l, e, null);
    // 设置新节点为链表的末节点
    this.last = newNode;
    // 如果this.last是null，即原链表为空
    if (l == null)
        // 把新节点也设置为头节点
        first = newNode;
    // 如果不是空，说明原链表内有数据
    else
        // 设置原末接点的下一个节点为新节点
        l.next = newNode;
    size++;        
    modCount++;
}

指定一个下标增加元素，本质上是让指定的下标的节点的pre指针指向含有数据element的新节点，让指定的下标的节点的原直接前驱节点的next指针指向含有数据element的新节点。

public void add(int index, E element) {
    // 判断index是否越界，即不超过容器中的元素个数
    checkPositionIndex(index);
    // 如果index恰好是容器的元素个数，说明加在链表末尾
    if (index == size)
        // 把数据节点加到链表末尾
        linkLast(element);
    else
        // 否则就是加到index下标的节点的前面
        linkBefore(element, node(index));
}

// 判断是否越界
private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

// 判断越界的具体实现
private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}

// 在指定节点succ的前面添加一个含有数据e的新节点
void linkBefore(E e, Node<E> succ) {
    // 获取succ节点的前一个节点，方便后续设置它的next指向新节点
    final Node<E> pred = succ.prev;
    // 把数据e封装成一个节点，并且直接前驱节点为指定节点succ的前驱节点，直接后继节点为succ
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 将新节点设置为指定节点succ的直接前驱节点
    succ.prev = newNode;
    // 如果指定节点succ的原直接前驱节点如果是null，说明succ原是头节点
    if (pred == null)
        // 就把新节点设置为头节点
        this.first = newNode;
    // 如果指定节点的直接前驱节点不是null
    else
        // 就把succ的原直接前驱节点的next指向新节点
        pred.next = newNode;
    size++;
    modCount++;
}

// 获取指定下标的节点
Node<E> node(int index) {
    // 如果index小于节点总数的一半，从头节点向末节点找
    if (index < (size >> 1)) {
        // 获取头节点
        Node<E> x = first;
        // 依次遍历，获取index下标的节点
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } 
    // 如果index大于节点总数的一半，从尾节点向前开始找
    else {
        // 获取尾节点
        Node<E> x = last;
        // 依次遍历，获取index下标的节点
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

添加一个元素到链表头。

// 把数据e包装成节点，连接到末尾
public void addFirst(E e) {
    linkFirst(e);
}

// 把数据e包装成节点，连接到末尾具体实现
private void linkFirst(E e) {
    // 获取头节点
    final Node<E> f = this.first;
    // 把数据e包装成节点，节点前驱为null，后继为原头节点
    final Node<E> newNode = new Node<>(null, e, f);
    
    // 让头指针指向新节点
    this.first = newNode;
    // 如果如果first指针指向是null，说明原链表为空
    if (f == null)
        // 把last指针指向新节点
        this.last = newNode;
    
    // 如果原本不是空链表
    else
        // 把原头节点的prev指针指向新节点
        f.prev = newNode;
    size++;
    modCount++;
}

把指定集合内的元素全部添加进链表；

// 把指定集合所以元素加入到链表
public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}

// 把指定集合所以元素加入到链表具体实现，返回true和false取决于是否添加元素进去
public boolean addAll(int index, Collection<? extends E> c) {
    // 查看index是否越界
    checkPositionIndex(index);

    // 把集合转成数组
    Object[] a = c.toArray();
    
    // 获取数组长度，即要添加的元素个数
    int numNew = a.length;
    // 如果是0，那么直接返回false
    if (numNew == 0)
        return false;

    // 定义pred指针指向待加入的新节点的前一个节点，succ指向待加入的新节点的后一个节点
    Node<E> pred, succ;
    // 判断index是不是等于当前集合的元素个数
    if (index == size) {
        // 是的话，就将前一个pred指向原末节点succ为null
        succ = null;
        pred = last;
    }
	// 如果index不是最后
    else {
        succ = node(index);
        pred = succ.prev;
    }
    
    // 遍历所有的元素，分别封装加到pred后串起来
    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);
        // 判断是否在链表的起始位置加
        if (pred == null)
            // 是的话，将first指针指向刚增加的节点
            this.first = newNode;
        else
            // 不是的话，让新节点连接到链表上
            pred.next = newNode;
        // 让pred每次都指向待新增节点的前一个节点
        pred = newNode;
    }
    
    // 判断是否在链表末尾加节点
    if (succ == null) {
        // 让last指针指向新增节点
        this.last = pred;
    } 
    // 如果不是在链表末尾加
    else {
        // 让新增节点的next指向succ
        pred.next = succ;
        // 让succ的前驱节点的next指向新增节点
        succ.prev = pred;
    }

    size += numNew;
    modCount++;
    return true;
}

6、remove方法

删除链表中指定的元素。

// 指定元素删除
public boolean remove(Object o) {
    // 如果是null
    if (o == null) {
        // 遍历判断null删除所有的null
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } 
    // 如果不是null
    else {
        // 遍历删除与指定元素equals的元素
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    // 找不到元素就返回false
    return false;
}

// 删除节点具体逻辑
E unlink(Node<E> x) {
    // 传进来的被删除的节点不应该为null
    // 获取指定节点的内容
    final E element = x.item;
    // 获取指定节点的直接后继节点
    final Node<E> next = x.next;
    // 获取当前节点的直接前驱节点
    final Node<E> prev = x.prev;
    
    // 如果前驱节点是null，说明是头节点
    if (prev == null) {
        // 那么把头节点设置为指定节点的next
        this.first = next;
    } 
    // 如果不是头节点,孤立指定节点
    else {
        // 设置指定节点的后继节点为其前驱节点的next
        prev.next = next;
        // 指定节点的前驱节点设为null
        x.prev = null;
    }
    
    // 如果指定节点的后继节点是null，说明指定节点是末节点
    if (next == null) {
        // 直接去掉即可
        this.last = prev;
    } 
    // 如果不是末节点
    else {
        //指定节点的前驱节点设为指定节点的后继节点的pre
        next.prev = prev;
        x.next = null;
    }
	// 把原存储的数据设为null，帮助GC回收
    x.item = null;
    size--;
    modCount++;
    // 返回这个节点存储的内容
    return element;
}

根据指定的index删除这个index下的节点。

// 指定下标删除
public E remove(int index) {
    // 查看是否越界
    checkElementIndex(index);
    // 获取对应下标的node，然后删除
    return unlink(node(index));
}

3、get方法

指定下标获取数据。

// 根据指定下标获取数据
public E get(int index) {
    // 查看是否越界
    checkElementIndex(index);
    // 获取这个下标的节点，然后获取item
    return node(index).item;
}

4、iterator方法

返回一个ListItr类对象，List迭代器；

/* 
	通过AbstractList这个方法获取迭代器
*/

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

// 返回一个第一次使用next方法返回下标为0的元素的迭代器
public ListIterator<E> listIterator() {
    return listIterator(0);
}

// 根据下标指定返回一个指针指向
public ListIterator<E> listIterator(final int index) {
    // 查看下标是否越界，要求不超过size
    rangeCheckForAdd(index);
    // 返回一个首次使用next方法返回下标为index的元素迭代器
    return new ListItr(index);
}

关于iterator方法返回的迭代器，是LinkedList下的一个私有内部类ListItr；

属性

// 保存最后一次next()返回的节点
private Node<E> lastReturned;
// 保存着下一次next()返回的节点
private Node<E> next;
// 保存着下一次next()返回
private int nextIndex;
// 保存本次返回的迭代器对应的LinkedList的修改版本号
private int expectedModCount = modCount;

构造器

// 只有一个构造器，传入指定的index，这个index将会是第一次使用next()返回的元素所对应的下标
ListItr(int index) {
    // 如果集合是空的，那么设置this.next指针为null
    this.next = (index == size) ? null : node(index);
    // 设置第一次使用next()访问的元素下标为index
    this.nextIndex = index;
}

next方法

// 指针后移，并返回后移后所指的元素
public E next() {
    // 查看是否在遍历期间被修改过
    checkForComodification();
    
    // 查看是否有下一个元素
    if (!hasNext())
        throw new NoSuchElementException();
    
    // 让lastReturned指向当前返回的元素所在节点
    this.lastReturned = next;
    
    // 让next指向下一次调用next()返回的元素节点
    this.next = next.next;
    // 下一次调用next()返回额元素的下标自增
    this.nextIndex++;
    return lastReturned.item;
}

// 查看集合的是否被修改过
final void checkForComodification() {
    // this.expectedModCount是在初始化迭代器时this.modCount的值，当集合发生修改时，this.modCount会变大
    if (this.modCount != this.expectedModCount)
        throw new ConcurrentModificationException();
}

hasNext方法

// 判断是否还有下个元素可以获取，nextIndex最大值为this.size - 1
public boolean hasNext() {
    return this.nextIndex < this.size;
}