ArrayList 和 LinkedList

在 List 集合的实现类中，主要有 3 个实现类：ArrayList、Vector 和 LinkedList。其中 Vector 还有一个 Stack 子类，这个 Stack 子类仅在 Vector 父类的基础上增加了 5 个方法，这 5 个方法就将一个 Vector 扩展成了 Stack。本质上，Stack 依然是一个 Vector，它只是比 Vector 多了 5 个方法。

下面是 Stack 类的源代码

public class Stack<E> extends Vector<E> {
    //无参数的构造器
    public Stack() {
    }
    //实现向栈顶添加元素的方法
    public E push(E item) {
        //调用父类的方法来添加元素
        addElement(item);
        return item;
    }
    //实现出栈的方法（位于栈顶的元素将被弹出栈FILO）
    public synchronized E pop() {
        E       obj;
        int     len = size();
        //取出最后一个元素
        obj = peek();
        //删除最后一个元素
        removeElementAt(len - 1);
        return obj;
    }
    //取出最后一个元素，但并不弹出栈
    public synchronized E peek() {
        int     len = size();
        //如果不包含任何元素，直接抛出异常
        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }
    public boolean empty() {
        //如果不包含任何元素就是空栈
        return size() == 0;
    }
    public synchronized int search(Object o) {
        //获取o在集合中的位置
        int i = lastIndexOf(o);
        if (i >= 0) {
            //用集合长度减去o在集合中的位置，就得到该元素到栈顶的距离
            return size() - i;
        }
        return -1;
    }
    private static final long serialVersionUID = 1224463164541339165L;
}

从上面代码可以看出，Stack 的本质依然上是一个 Vector，只是增加了 5 个方法而已。而 Stack 新增的 5 个方法中有 3 个使用了 synchronized 修饰————那些需要操作集合元素的方法都添加了 synchronized 修饰。也就是说，Stack 是一个线程安全的类，这也是为了让 Stack 和 Vector 保持一致————Vector 也是一个线程安全的类。

实际上即使当程序中需要栈这种数据结构时，Java 也不再推荐使用 Stack 类，而是推荐使用 Deque 实现类。从 JDK1.6 开始，Java 提供了一个 Deque 接口，并为该接口提供一个 ArrayDeque 实现类。在无需保证线程安全的情况下，程序完全可以使用 ArrayDuque 来代替 Stack。

Deque 接口代表双端队列这种数据结构。双端队列已经不再是简单的队列了，它既具有队列的性质先进先出（FIFO），也具有栈的性质（FILO），也就是双端队列既是队列，也是栈。Java 为 Deque 提供了一个常用的实现类 ArrayDeque。

就像 List 集合拥有 ArrayList 实现类一样，Deque 集合则拥有 ArrayDeque实现类。ArrayList 和 ArrayDeque 底层都是基于 Java 数组来实现的，只是它们所提供的方法不同而已。

Vector 和 ArrayList 的区别

Vector 和 ArrayList 这两个集合类的本质并没有太大的不同，它们都实现了List 接口，而且底层都是基于 Java 数组来储存集合元素。

在 ArrayList 集合类的源代码中可以看到如下一行：

//采用elementData数组来保存集合元素
transient Object[] elementData;

在 Vector 集合类的源代码也可以看到类似的一行：

//采用elementData数组来保存集合元素
protected Object[] elementData;

从上面的代码可以看出，ArrayList 使用 transient 修饰了 elementData 数组。这保证了系统序列化 ArrayList 对象时不会直接序列化 elementData 数组，而是通过 ArrayList 提供的 writeObject、readObject 方法来实现定制序列化；但对于 Vector 而言，它没有使用 transient 修饰 elementData 数组，而且 Vector 只提供了一个 writeObject 方法，它并未完全实现定制序列化。

从序列化机制的角度来看，ArrayList 的实现比 Vector 的实现更安全。

除此之外，Vector 其实就是 ArrayList 的线程安全版本，ArrayList 和 Vector 绝大部分方法的实现都是相同的，只是 Vector 的方法增加了 synchronized 修饰。

下面先来看 ArrayList 中 add(int index, E element) 方法的源代码：

    public void add(int index, E element) {
        rangeCheckForAdd(index);
        //保证ArrayList底层的数组可以保存所有集合元素
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //将elementData数组中index位置之后的所有元素向后移动一位
        //也就是将elementData数组的index位置的元素空出来
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        //将新元素放入elementData数组的index位置
        elementData[index] = element;
        size++;
    }
    private void rangeCheckForAdd(int index) {
        //如果添加位置大于集合长度或者小于0，抛出异常
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

再来看 Vector 中 add(int index, E element) 方法的源代码：

    public void add(int index, E element) {
        insertElementAt(element, index);
    }
    public synchronized void insertElementAt(E obj, int index) {
        //增加集合的修改次数
        modCount++;
        //如果添加位置大于集合长度，抛出异常
        if (index > elementCount) {
            throw new ArrayIndexOutOfBoundsException(index
                                                     + " > " + elementCount);
        }
        //保证ArrayList底层的数组可以保存所有集合元素
        ensureCapacityHelper(elementCount + 1);
        //将elementData数组中index位置之后的所有元素向后移动一位
        //也就是将elementData数组的index位置的元素空出来
        System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
        //将锌元素放入elementData数组的index位置
        elementData[index] = obj;
        elementCount++;
    }

将 ArrayList 中的 add(int index, E element) 方法和 Vector 的 insertElementAt(E obj, int index) 方法进行比对，可以发现 Vector 的 insertElementAt(E obj, int index) 方法只是多了 synchronized 修饰，而且多了一行增加集合修改次数的代码。这并不代表 ArrayList 的 add(int index, E element) 方法就没有这行代码，ArrayList 只是将这行代码放在 ensureCapacityInternal(size + 1) 中完成。

ArrayList 中使用 size 实例变量来保存集合中的元素的个数，而 Vector 中使用 elementCount 实例变量来保存集合元素的个数。两个变量的作用没有任何区别，只是 size 变量名更简洁。

下面是 ArrayList 的 ensureCapacityInternal(int minCapacity) 方法的源代码：

    private void ensureCapacityInternal(int minCapacity) {
        //如果elementData数组是默认的空数组
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            //就选择默认的容量10和传入的参数中较大的数值
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }
    private void ensureExplicitCapacity(int minCapacity) {
        //增加
        modCount++;
        //如果minCapacity大于原来数组的长度
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    private void grow(int minCapacity) {
        //保存ArrayList底层数组的长度
        int oldCapacity = elementData.length;
        //将新容量扩充为原来的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果newCapacity依然小于minCapacity，直接将minCapacity赋给newCapacity
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //如果newCapacity大于最大的数组长度，默认的最大数组长度为Integer.MAX_VALUE-8
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        //通过Arrays的copyOf复制一个新数组，新数组长度为newCapacity
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    private static int hugeCapacity(int minCapacity) {
        //如果minCapacity小于0，抛出内存溢出的错误
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        //如果minCapacity大于最大数组长度，就让minCapacity等于Integer.MAX_VALUE，否则等于最大数组数组长度Integer.MAX_VALUE-8
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

类似地，Vector 提供了 ensureCapacityHelper(int minCapacity) 方法来完成类似的功能，如下所示：

    private void ensureCapacityHelper(int minCapacity) {
        //如果minCapacity大于原来数组的长度
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    private void grow(int minCapacity) {
        //保存Vector底层数组的长度
        int oldCapacity = elementData.length;
        //capacityIncrement是Vector底层数组增加的增量
        //如果capacityIncrement大于0，就让原来的容量增加capacityIncrement，否则将新容量扩充为原来的2倍
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
        //如果newCapacity依然小于minCapacity，直接将minCapacity赋给newCapacity
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //如果newCapacity大于最大的数组长度，默认的最大数组长度为Integer.MAX_VALUE-8
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        //通过Arrays的copyOf复制一个新数组，新数组长度为newCapacity
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    private static int hugeCapacity(int minCapacity) {
        //如果minCapacity小于0，抛出内存溢出的错误
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        //如果minCapacity大于最大数组长度，就让minCapacity等于Integer.MAX_VALUE，否则等于最大数组数组长度Integer.MAX_VALUE-8
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

将 ArrayList 中的 ensureCapacityInternal(int minCapacity) 和 Vector 的 ensureCapacityHelper(int minCapacity) 方法进行比较，可以发现这两个方法几乎完全相同，只是在扩充底层数组的容量时略有区别而已。ArrayList 总是将底层数组容量扩充为原来的 1.5 倍，但 Vectore 有两种选择：当 capacityIncrement 实例变量大于 0 时，扩充后的容量等于原来的容量加上 capacityIncrement 的值；当 capacityIncrement 实例变量等于 0 时，扩充后的容量等于原来容量的2倍。

Vector 的 ensureCapacityHelper(int minCapacity) 方法在扩充底层数组容量时多一个选择是因为，创建 Vector 可以传入一个 capacityIncrement 参数，如下构造器所示：

• Vector(int initialCapacity, int capacityIncrement)：以 initialCapacity 作为底层数组的初始长度，以 capacityIncrement 作为数组长度扩充时的增大步长来创建 Vector 对象。

但对于 ArrayList 而言，它的构造器最多只能指定一个 initialCapacity 参数。

除此之外，Vector 是一个非常古老的集合，它从 JDK1.0 开始就存在了，那时候它已经包含了大量集合操作元素的方法，例如刚刚介绍的 insertElementAt(int index, E element) 方法等，这些方法都具有方法名冗长、难于记忆的特征。随着 JDK1.2 增加了 List 接口之后，Vector 改为了实现 List 接口，因此 Vector 将原有的方法（如 insertElementAt）进行了包装，包装成满足 List 接口的新方法（如 addElement）。

由于 Vector 包含的方法比 ArrayList 更多，因此 Vector 类的源代码比 ArrayList 的源代码要多，而且 ArrayList 的序列化比 Vector 的序列化实现更安全，因此 Vector 基本上已经被 ArrayList 替所替代了。Vector 唯一的好处是它是线程安全的。

即使需要在多线程环境下使用 List 集合，而且需要保证 List 集合的线程安全，依然可以避免使用 Vector，而是考虑将 ArrayList 包装成线程安全的集合类。Java 提供了一个 Collections 工具类，通过该工具类 synchronizedList 方法即可将一个普通 ArrayList 包装成线程安全的 ArrayList。

ArrayList 和 LindedList 的实现差异

List 代表一种线性表的数据结构，ArrayList 则是一种顺序储存的线性表。ArrayList 底层采用数组来保存每个集合元素，LinkedList 则是一种链式储存的线性表。其本质上就是一个双向链表，但它不仅实现了 List 接口，还实现了 Deque 接口。也就是说 LinkedList 既可以当成双向链表使用，也可以当成队列使用，还可以当成栈来使用（Deque 代表双端队列，既具有队列的特征，也具有栈的特征）。

前面已经看到：ArrayList 底层采用一个 elementData 数组来保存所有的集合元素，因此 ArrayList 在插入元素时需要完成下面的两件事情：

• 保证 ArrayList 底层封装的数组长度大于集合元素的个数；
• 将插入位置之后的所有数组元素“整体搬家”，向后移动一“格”。

反过来，当删除 ArrayList 集合中指定位置的元素时，程序也要进行“整体搬家”，而且还需将被删索引处的数组赋为 null。下面是 ArrayList 集合的 remove(int index) 方法的源代码。

    public E remove(int index) {
        //如果index是大于或等于size，抛出异常
        rangeCheck(index);
        modCount++;
        //保证index索引处的元素
        E oldValue = elementData(index);
        //计算需要“整体搬家”的元素个数
        int numMoved = size - index - 1;
        //当numVoved大于0时，开始搬家
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        //释放被删除的元素，以免GC回收该元素
        elementData[--size] = null; // clear to let GC do its work
        return oldValue;
    }

对于 ArrayList 集合而言，当程序向 ArrayList 中添加、删除集合元素时，ArrayList 底层都需要对数组进行“整体搬家”，因此性能非常差。

但如果程序调用 get(int index) 方法来取出 ArrayList 集合中的元素时，性能和数组几乎相同————非常快。下面是 ArrayList 集合 get(int index) 方法的源代码：

    public E get(int index) {
        //如果index超过了集合的长度，抛出异常
        rangeCheck(index);
        //取出index索引处的元素
        return elementData(index);
    }

LinkedList 本质上就是一个双向链表，因此它使用如下内部类来保存每个集合元素。

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

从上面的程序中可以看出，一个Node（JDK1.8 之前版本，该类名称为 Entry，但除此之外，Node 和 Entry 没有区别）对象代表双向链表的一个节点，该对象中 next 变量指向下一个节点，prev（JDK1.8 之前的版本该变量的名称为 previous）则指向上一个节点。

由于 LinkedList 采用双向链表来保存集合元素，因此它在添加集合元素的时候，只需要将插入位置节点的上一个节点的 next 引用到需要添加的元素节点；将插入位置的下一个节点的 prev 引用到需要添加的元素节点即可。

下面是 LinkedList 添加节点的源代码：

    public void add(int index, E element) {
        //如果index超过链表长度，则抛出异常
        checkPositionIndex(index);
        //如果index=size，直接在末尾插入新节点
        if (index == size)
            linkLast(element);
        //否则，在index索引处的节点之前插入新节点
        else
            linkBefore(element, node(index));
    }

从上面的代码可以看出，由于 LinkedList 本质上就是一个双向链表，因此它可以非常方便地在指定节点之前插入新节点，Linked 在指定位置添加新节点也是通过这种方式来实现的。

上面 add(int index, E element) 方法实现中用到了以下两个方法：

• node(int index)：搜索指定索引处的元素；
• linkBefore(E element, Node<E> succ) 在 succ 节点之前插入 element 新节点。

node(int index) 实际上就是 get(int index) 方法的底层实现。对于 ArrayList 而言，由于它底层采用数组来保存集合元素，因此可以直接根据数组索引取出 index 位置的元素；但对于 LinkedList 就比较麻烦了，LinkedList 必须一个元素一个元素的搜索，直到找到第 index 个元素为止。

下面是 node(int index) 方法的源代码：

    Node<E> node(int index) {
        //如果index小于size/2
        if (index < (size >> 1)) {
            //从链接头部开始搜索
            Node<E> x = first;
            //从链接头部开始搜索
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            //否则，从链接尾部开始搜索
            Node<E> x = last;
            //从链接尾部开始搜索
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

上面 node(int index) 方法就是一个元素一个元素地找到 index 索引处的元素，只是由于 LinkedList 是一个双向链表，因此程序先根据 index 的值判断它到底离链表头端近（当 index < size / 2时），还是离链表尾端近。如果离头端近则从头端开始搜索，如果离尾端近则从头端开始搜索，如果离尾端近则从尾端搜索。

LinkedList 的 get(int index) 方法只是对上面 node(int index) 方法的简答包装。get(int index) 方法的源代码如下：

    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

无论如何，LinkedList 为了获取指定索引处的元素都是比较麻烦的，系统开销也会比较大。但单纯的插入操作就比较简单了，只要修改几个节点里的 prev、next 引用的值。下面是 linkBefore(E element, Node<E> succ) 方法的源代码：

    //在指定节点succ之前添加一个新节点
    void linkBefore(E e, Node<E> succ) {
        //取出指定节点succ的上一个节点
        final Node<E> pred = succ.prev;
        //创建新节点，新节点的下一个节点指向succ，上一个节点指向succ的上一个节点
        final Node<E> newNode = new Node<>(pred, e, succ);
        //让succ的上一个节点向后指向新节点
        succ.prev = newNode;
        //如果succ的上一个节点等于null，就让头端节点指向新节点
        if (pred == null)
            first = newNode;
        //否则，让pred的向后节点指向新节点
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

如果只是单纯地添加某个节点，LinkedList 的性能会非常好，可以如果需要向指定索引处添加节点，LinkedList 必须先赵丹指定索引处的节点————这个搜索过程的系统开销并不小，因此 LinkedList 的 add(int index, E element) 方法的性能并不是特别好。

当单纯地把 LinkedList 当成双向链表使用，通过 addFirst(E e)、addList(E e)、offerFirst(E e)、offerLast(E e)、pollLast() 等方法来操作 LinkedList 集合元素时，LinkedList 的性能非常好————因为可以避免搜索过程。

如果希望从 LinkedList 中删除一个节点，需要将要删除的节点的上一个节点的 next 引用指向被删除节点的下一个节点，再将被删除节点的下一个节点的 prev 引用指向被删除节点的上一个节点。

类似地，LinkedList 为了实现 remove(int index) 方法————删除指定索引处的节点，也必须先通过 node(int index) 方法站到 index 索引处的节点，然后修改它前一个节点的 next 引用以及后一个节点的 prev 引用。下面是 LinkedList 的 remove(int index) 方法的源代码：

    public E remove(int index) {
        //如果index超过链表大小，则抛出异常
        checkElementIndex(index);
        //搜索到index索引处的节点，然后删除该节点
        return unlink(node(index));
    }

从上面的代码可以看出，程序先调用 node(int index) 搜索到 index 索引处的节点，然后调用 unlink(Node x) 方法删除指定节点。删除 x 节点时，只需要修改 x 前一个节点的 next 引用，修改 x 后一个节点的 prev 引用。下面是该方法的源代码：

    E unlink(Node<E> x) {
        //先保存e节点的元素
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;
        //如果x节点的上一个节点等于null，则将表头first指向x的下一个节点
        if (prev == null) {
            first = next;
        //否则，x节点的上一个节点的next指向x的下一个节点，并将x的上一个节点指向null，方便垃圾回收
        } else {
            prev.next = next;
            x.prev = null;
        }
        //如果x节点的下一个节点等于null，则将表尾last指向x的上一个节点
        if (next == null) {
            last = prev;
        //否则，x节点的下一个节点的prev指向x的上一个节点，并将x的下一个节点指向null，方便垃圾回收
        } else {
            next.prev = prev;
            x.next = null;
        }
        //将x节点保存的元素指向null，方便垃圾回收
        x.item = null;
        size--;
        modCount++;
        return element;
    }

ArrayList 和 LinkedList 的性能分析和适用场景

经过上面对 ArrayList 和 LinkedList 底层实现的详细介绍，读者应该对 ArrayList 和 LinkedList 质检的优劣有了一个大致的印象。就笔者的经验来说，ArrayList 性能总体上优于 LinkedList。

当程序需要以 get(int index) 方法获取 List 集合指定索引处的元素时，ArrayList 的性能大大地优于 LinkedList。因为 ArrayList 底层以数组来保存集合元素，所示调用 get(int index) 方法获取指定索引处的元素时，底层实际上调用 elementData[index] 来返回该元素，因此性能非常好。而 LinkedList 则必须一个一个地搜索过去。

当程序调用 add(int index, Object obj) 向 List 集合中添加元素时，ArrayList 必须对底层数组元素进行“整体搬家”。如果添加元素导致集合长度将要超过底层数组长度，ArrayList 必须创建一个长度为原来 1.5 倍的数组，再由垃圾回收机制回收原有数组，因此系统开销比较大。对于 LinkedList 而言，它主要的开销集中在 node(int index) 方法上，该方法必须一个一个地搜索过去，直到找到 index 处的元素，然后再在该元素之前插入新元素。即使如此，执行该方法的时候 LinkedList 方法的性能依然高于 ArrayList。

当程序调用 remove(int index) 方法删除 index 索引处的元素时，ArrayList 同样也需要对底层数组元素进行“整体搬家”。但调用 remove(int index) 方法删除集合元素时，ArrayList 无需考虑创建新数组，因此执行 ArrayList 的 remove(int index) 方法比执行 add(int index, Object obj) 方法略快一点。当 LinkedList 调用 remove(int index) 方法删除集合元素时，与调用 add(int index, Object obj) 方法添加元素的系统开销几乎完全相同。

当程序调用 add(Object obj) 方法向 List 集合尾端添加一个元素时，大部分时候 ArrayList 无需对底层数组元素进行“整体搬家”，因此也可以获得很好的性能（甚至比 LinkedList 的 add(Object obj) 方法的性能更好）；但如果添加这个元素导致集合长度将要超过底层数组长度，那么 ArrayList 必须创建一个长度为原来 1.5 倍的数组，再由垃圾回收机制回收原有数组————这样系统开销就比较大了。但 LinkedList 调用 add(Object obj) 方法添加元素时总可以获得较好的性能。

当程序把 LinkedList 当成双端队列、栈使用，调用 addFirst(E e)、addList(E e)、getFirst(E e)、getLast(E e)、offerFirst(E e)、offerLast(E e) 等方法来操作集合元素时，LinkedList 可以快速定位需要操作的元素，因此 LinkedList 总是具有较好的性能表现。

上面分析了 Array、LinkedList 各自适用场景。大部分情况下，ArrayList 的性能总是优于 LinkedList，因此绝大部分都应该考虑使用 ArrayList 集合。但如果程序经常需要添加、删除元素，尤其是经常需要调用 add(E e) 方法向集合中添加元素时，则应该考虑使用 LinkedList 集合。

Iterator 迭代器

Iterator 是一个迭代器接口，它专门用于迭代各种 Collection 集合，包括 Set 集合 和 List 集合。如果查询 JDK 的 API 文档将发现，Iterator 迭代器接口实现子类中并没有 List 和 Set 相关的集合类。，那迭代 List、Set 集合的 Iterator 迭代器实现类在那里？

下面一个程序用来测试 Iterator 迭代器各种集合所返回的 Iterator 对象。

enum Gender {
    MALE, FEMALE;
}
public class Iterator {
    public static void main(String[] args) {
        //创建一个HashSet集合
        HashSet<String> hashSet = new HashSet<>();
        //获取HashSet集合的Iterator
        System.out.println("HashSet 的 Iterator:" + hashSet.iterator());
        //创建一个LinkedHashSet集合
        LinkedHashSet<String> linkedHashSet = new LinkedHashSet<>();
        //获取LinkedHashSet集合的Iterator
        System.out.println("LinkedHashSet 的 Iterator:" + linkedHashSet.iterator());
        //创建一个TreeSet集合
        TreeSet<String> treeSet = new TreeSet<>();
        //获取TreeSet集合的Iterator
        System.out.println("TreeSet 的 Iterator:" + treeSet.iterator());
        //创建一个EnumSet集合
        EnumSet<Gender> enumSet = EnumSet.allOf(Gender.class);
        //获取EnumSet集合的Iterator
        System.out.println("EnumSet 的 Iterator:" + enumSet.iterator());
        //创建一个ArrayList集合
        ArrayList<String> arrayList = new ArrayList<>();
        //获取ArrayList集合的Iterator
        System.out.println("ArrayList 的 Iterator:" + arrayList.iterator());
        //创建一个Vector集合
        Vector<String> vector = new Vector<>();
        //获取Vector集合的Iterator
        System.out.println("Vector 的 Iterator:" + vector.iterator());
        //创建一个LinkedList集合
        LinkedList<String> linkedList = new LinkedList<>();
        //获取LinkedList集合的Iterator
        System.out.println("LinkedList 的 Iterator:" + linkedList.iterator());
        //创建一个ArrayDeque集合
        ArrayDeque<String> arrayDeque = new ArrayDeque<>();
        //获取ArrayDeque集合的Iterator
        System.out.println("ArrayDeque 的 Iterator:" + arrayDeque.iterator());
    }
}

上面程序创建了 Java 的各种集合，然后调用这些集合的 iterator() 方法来获取各种集合对应的 Iterator 对象。运行上面的程序，结果如下：

HashSet 的 Iterator:java.util.HashMap$KeyIterator@15db9742
LinkedHashSet 的 Iterator:java.util.LinkedHashMap$LinkedKeyIterator@6d06d69c
TreeSet 的 Iterator:java.util.TreeMap$KeyIterator@7852e922
EnumSet 的 Iterator:java.util.RegularEnumSet$EnumSetIterator@70dea4e
ArrayList 的 Iterator:java.util.ArrayList$Itr@5c647e05
Vector 的 Iterator:java.util.Vector$Itr@33909752
LinkedList 的 Iterator:java.util.LinkedList$ListItr@55f96302
ArrayDeque 的 Iterator:java.util.ArrayDeque$DeqIterator@3d4eac69

从上面运行的结果来看，除了 EnumSet 集合的 Iterator 就是 RegularEnumSet 的一个内部类和 LinkedHahshSet 集合的 Iterator 是调用 LinkedHashMap 的内部类 LinkedKeyIterator 之外，其余所有 Set 集合对应的 Iterator 都是它对应的 Map 类的内部类 KeyIterator。这是因为，Set 集合底层是通过 Map 来实现的。

ArrayList 和 Vector 的实现基本相同，除了 ArrayList 是线程不安全的，而 Vector 是线程安全的。因此，它们两个对应的 Iterator 都是相同的，即 AbstractList 的内部类 Itr。LinkedList 集合对应的 Iterator 是其内部类 ListItr。ArrayDeque 集合对应的 Iterator 是 ArrayDeque$DeqIterator。

通过上面介绍不难发现，对于 Iterator 迭代器而言，它只是一个接口。Java 要求各种集合都提供一个 iterator() 方法，该方法可以返回一个 Iterator 用于遍历该集合中元素，至于返回的 Iterator 到底是哪种实现类，程序并不关心，这就是典型的“迭代器模式”。

Java 的 Iterator 和 Enumeration 两个接口都是迭代器模式的代表之作，它们就是迭代器模式里的“迭代器接口”。所谓迭代器模式指的是，系统为遍历多种数据列表、集合、容器提供一个标准的“迭代器接口”，这些数据列表、集合、容器就可以面向相同的“迭代器接口”编程，通过相同的迭代器接口访问不同数据列表、集合、容器里的数据。不同的数据列表、集合、容器如何实现这个“迭代器接口”，则交给各数据列表、集合、容器自己完成。

迭代时删除指定元素

由于 Iterator 迭代器只负责对各种集合所包含的元素进行迭代，它自己并没有保留集合元素，因此使用 Iterator 进行迭代时，通过不应该删除集合元素，否则将引发 ConcurrentModificationException 异常。当然，Java 允许通过 Iterator 提供的 remove() 方法删除刚刚迭代的集合。

但实际上在某些特殊情况下，可以在使用 Iterator 迭代集合时直接删除集合中某个元素。示例如下：

public class ArrayListRemove {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("111");
        list.add("222");
        list.add("333");
        for (Iterator<String> it = list.iterator();it.hasNext();) {
            String ele = it.next();
            //当迭代倒数第2个元素时
            if (ele.equals("222")) {
                //直接删除集合中倒数第2个元素
                list.remove(ele);
            }
        }
    }
}

上面程序中就尝试了使用 Iterator 遍历 ArrayList 集合时，直接调用 List 的 remove() 方法删除指定集合元素。运行上面程序，发现该程序完全可以正常结束，并未引发任何异常。

实际上，对于 ArrayList、Vector、LinkedList 等 List 集合而言，当使用 Iterator 遍历它们时，如果正在遍历倒数第 2 个集合元素，使用 List 集合的 remove() 方法删除集合的任何一个元素并不会引发 ConcurrentModificationException 异常，当正在遍历其它元素时删除其它元素就会引发该异常。也就是说，如果将程序中 if (ele.equals("222")) 修改为其它元素，就会引发 ConcurrentModificationException 异常。

对于 Set 集合，同样有类似的现象。示例如下：

public class TreeSetRemove {
    public static void main(String[] args) {
        TreeSet<String> set = new TreeSet<>();
        set.add("111");
        set.add("222");
        set.add("333");
        System.out.println(set);
        for (Iterator<String> it = set.iterator(); it.hasNext();) {
            String ele = it.next();
             if (ele.equals("333")) {
                 set.remove(ele);
             }
        }
    }
}

上面程序中就尝试了使用了 Iterator 遍历 TreeSet 集合时，直接调用 Set 的 remove() 方法删除指定集合元素。运行上面程序，发现该程序完全可以正常结束，并未引发任何异常。

对于 TreeSet、HashSet 等 Set 集合而言，当使用 Iterator 遍历它们时，如果正在遍历最后一个集合元素，使用 Set 集合的 remove() 方法删除集合的任意元素并不会引发 ConcurrentModificationException 异常，当正在遍历其它元素时删除任意元素都将引发该异常。也就是说，如果将程序中 if (ele.equals("3333")) 修改成其它元素，就会引发 ConcurrentModificationException 异常。

为何使用 Iterator 遍历 List 集合的倒数第 2 个元素时，直接使用 List 集合的 remove() 方法删除 List 集合的倒数第 2 个元素没有引发 ConcurrentModificationException 异常呢？关键在于 List 集合对应的 Iterator 实现类（Itr）的 hasNext() 方法。下面是该方法的实现：

        public boolean hasNext() {
            //如果下一步即将访问的集合元素的索引不等于集合的大小，就返回true
            return cursor != size;
        }

对于 Itr 遍历器而言，它判断是否还有下一个元素的标准很简单：如果下一步即将访问的元素的索引不等于集合的大小，就会返回 true，否则就会返回 false。当程序中使用 Iterator 遍历 List 集合的倒数第 2 个元素时，下一步即将访问的元素的索引为 size() - 1。如果此时通过 List 删除集合的任意一个元素，将导致集合 size() 变为 size(0 - 1，这将导致 hasNext() 方法返回 false。也就是说，遍历将提前结束，Iterator 不会访问 List 集合的最后一个元素。

可以在 ArrayListRemove.java 的程序中添加如下代码来输出每个被遍历到的集合元素：

System.out.println(ele);

添加上面的代码之后，可以看到 ArrayListRemove.java 永远不会访问到 ArrayList 的最后一个集合元素————这就是 Itr 类的 hasNext() 方法导致的。

也就是说，如果使用 Itr 正在遍历 List 集合的倒数第 2 个元素，程序直接调用 List 集合的 remove() 方法删除任意元素后，程序不会调用 Itr 的 next() 方法访问集合的下一个元素。否则，Itr 总是引发 ConcurrentModificationException 异常。Itr 的 next() 方法中调用 checkForComodification() 方法来检查集合是否被修改，该方法代码如下：

        final void checkForComodification() {
            //如果集合的修改次数和遍历之前的修改次数不相等
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }

Itr 的 checkForComodification() 实现非常简单：遍历之前使用 expectedModCount 保留该集合被修改的次数，每次获取集合的下一个元素之前检查集合的当前修改次数（modCount）与遍历之前的修改次数（expectedModCount）是否相等，如果不相等就直接抛出 ConcurrentModificationException 异常。

类似地，对于 Set 集合而言，如果当前正在遍历集合的最后一个元素，也就是集合遍历操作已经完成，此时删除 Set 集合的任意元素都不会引发异常————实际上该删除动作已经是在遍历操作的范围之外了。

本文转账自：《疯狂Java 突破程序员基本功的16课》第三章 常见的 Java 集合的实现细节