集合概述

Java集合框架标准化了Java处理对象组的方式。Java集合框架在JDK1.2版本提出，在JDK1.5版本进行了修改(引入了泛型、自动装箱/拆箱以及for-each格式循环)。
集合框架再设计之初有几个目标：

• 框架是高性能的，基本集合(动态数组、链表、树、哈希表等)的实现是高效的。
• 框架必须允许不同类型的集合以类似的方式进行工作，并且有很高的互操作性。
• 扩展或改造集合必须是容易实现的
• 比如添加可以将标准数组集成到集合框架的机制。

Java集合框架由以下几部分组成：

• 接口：表示集合抽象的数据类型。接口允许我们操作集合时不需要关注具体的实现，从而达到多态。
• 实现类：集合接口的具体实现，是重用性很高的数据结构。
• 算法：根据需要对实现类实现的集合进行计算，比如排序、搜索。

Java集合框架除了定义集合相关的数据结构，还定义了映射的数据结构。虽然映射是集合框架的一部分，但是严格意义上映射并不是集合。

image.png

Iterator迭代器

再看集合实现前，我们需要先看下迭代器，因为我们想要遍历集合、获取或者移除元数时，都需要使用迭代器，而实现Iterator接口是使用迭代器的方法之一。
迭代器是一种模式，它可以使得遍历序列方式和被遍历对象分离。即我们无需该序列的底层结构是什么样子，只要拿到迭代器对象就可以遍历该序列。

Enumeration接口

在Iterator接口之前，Java在1.0版本采用的是Enumeration接口作为迭代器接口，但是该接口在当初设计没有考虑全面，比如它只包含了两个方法。

public interface Enumeration<E> {
    /**
     * 是否还有元素
     */
    boolean hasMoreElements();

    /**
     * 返回下一个元素
     */
    E nextElement();
}

我们可以看到在JDK1.0版本提供需要使用迭代器的类都还是继承的Enumeration，比如StringTokenizer类就是实现了Enumeration接口。但是从JDK2.0开始，官方使用Iterator接口代替了Enumeration接口，所以当我们需要实现使用迭代器功能的类时记得要使用Iterator接口。

Iterator

Iterator被定义为集合上的迭代器。Iterator取代了Enumeration，它们二者的主要区别为：

• Iterator允许调用方在遍历过程中，以正确的方式删除元素
• 对方法名称进行了改进，Enumeration中的方法名称太长了。

public interface Iterator<E> {
    /**
     * 迭代中是否还是更多元素
     */
    boolean hasNext();

    /**
     * 返回迭代中的下一个元素.
     * 如果没有下一个元素，应该抛出NoSuchElementException。
     */
    E next();

    /**
     * 从迭代器指向的Collection中移除迭代器返回最后一个元素。Java8将该方法改为默认方法实现，对于没有实现remove方法的集合类，如果使用remove方法会抛出UnsupportedOperationException。
     */
    default void remove() {
        throw new UnsupportedOperationException("remove");
    }

    /**
     * 对集合中没有处理的元素，执行action指定动作。
     * JDK8新增方法，并且提供接口方法默认实现
     */
    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

JDK1.5新增的forEach循环就是使用Iterator实现的。但是使用forEach循环是不能修改集合内容，想要在遍历过程中修改集合内容，还需要使用Iterator迭代器。

Iterable

我们会发现我们无论自己写代码还是集合类型都没有直接实现Iterator接口，而是实现了Iterable接口。我们可以看下面Iterable接口的源码，它最主要的一个方法是返回一个Iterator方法。
之所以不直接实现Iterator接口，而是通过Iterable返回一个迭代器。主要原因就是Iterator接口的核心方法hasNext和next都依赖当前位置迭代位置，如果将集合框架直接实现Iterator接口，那么就需要一个指针来标识这个迭代位置，但是如果这样就会导致再对同一个集合进行遍历时，指针出现混乱。所以我们通过实现Iterable接口为需要遍历集合的方法都提供一个新的迭代器，它们之间互不影响。

public interface Iterable<T> {
    /**
     * 返回该集合的一个迭代器
     */
    Iterator<T> iterator();

    /**
     * 对Iterable所有元素执行特定操作，直到所有元素处理完成或操作元素出现异常。
     * 接口方法默认实现。
     */
    default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }

    /**
     * 返回Spliteratordei迭代器。
     * JDK8提供
     */
    default Spliterator<T> spliterator() {
        return Spliterators.spliteratorUnknownSize(iterator(), 0);
    }
}

如果想要使用for-each循环，就需要实现Iterable接口

Spliterator

我们会看到上面Iterable还返回一个了Spliterator接口，那么这个Spliterator是什么呢？
Spliterator是JDK1.8新增的一种迭代器，它主要是为了并行迭代遍历数据源中元素而设计的(因为现在是多核时代，顺序遍历已经不能满足性能上的需求了)。
Spliterator接口的设计思想就是利用递归将任务分解成小任务，然后并行处理，最终再将结果进行合并。JDK8中函数式编程是Java主要发展的一个方向，所以Spliterator接口方法基本都是使用函数式编程的思想。
Spliterator有几个核心的方法：

方法	用途
boolean tryAdvance(Consumer<? super T> action)	顺序处理每个元素，如果还有元素要处理，则返回true，否则返回false
Spliterator<T> trySplit()	转换为Spliterator设计的方法，它会将一部分元素划分出来生成一个新的Spliterator，然后并行执行。如果元素个数小到无法划分，则返回false
int characteristics()	表示该Spliterator有哪些特征，便于控制和优化Spliterator
long estimateSize()	估计剩余要迭代的元素个数

除了这些方法，Spliterator还有一些关于特征的方法以及特定常量的定义，它们能够帮助创建高效、健壮的代码。

关于Spliterator的具体实现我们可以到ArrayList时候在查看。
下面是一个使用Spliterator的实例：

//这里并没有体现Spliterator的强大，在并行处理的地方Spliterator的最大优势才能体现出来。一般Spliterator和流API中使用
List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        Spliterator<Integer> sIterator=  list.spliterator();
        while (sIterator.tryAdvance(n -> System.out.println(n)));

JDK已经所有集合提供了默认的Spliterator实现，但是它并不是根据不同集合特征而实现的，所以效率可能不是非常高。如果想要高效使用，还需要根据自己的集合特征进行实现。

借鉴：
Java8编程官方参考文档
https://segmentfault.com/q/1010000007087438

ListIterator

ListIterator继承自Iterator接口，它相对Iterator来说有以下特点：

• 允许双向遍历列表。
• 允许在遍历过程中修改列表元素。
• 能够获取遍历过程中元素的下标位置。

ListIterator不存在当前元素的概念，因为它使用游标来获取元素，游标总是在要获取下一个元素的前面。这就是为什么它能够双向遍历，并且能够获取元素下标位置的原因。

image.png

可以看到上面除了next、hasNext、remove这些Iterator接口，ListIterator还提供了向前遍历方法hasPrevious、previous，获取位置下标方法nextIndex、修改和增加元素的set、add方法。

游标默认开始是-1，因为游标总是在要访问元素的前面(向后遍历的情况)。

关于ListIterator的使用可以在查看List源码时候来讲解。

Collection集合框架

集合表示一组对象，每个对象在集合中称为元素。集合可以分为有序、无序集合，可重复、不可重复等集合。Collection是集合层级结构的根接口。正因为集合的种类多种多样，所以JDK没有提供Collection接口的直接实现类，而是提供了更具体的接口比如有序可重复的List、有序不可重复的Set等等。Collection接口一般用于传递集合，并在需要最大的通用性时提供操作。

Collection接口

Collection接口是集合类的根接口，它的位置如图所示：

image.png

Collection定义了集合所需要的基本方法，它集成Iterable接口，所以能够使用iterator方法返回迭代器，并且所有集合类都能够使用for-each循环。

public interface Collection<E> extends Iterable<E> {}

下面是Collection提供的方法：

image.png

这些方法主要分为五类：查询操作、修改操作、批处理操作、比较和散列、流处理。

查询操作

• int size()：返回集合元素中的个数，如果超过Integer.MAX_VALUE则直接返回Integer.MAX_VALUE。
• boolean isEmpty()：如果集合元素为空，则返回true。
• boolean contains(Object o)：如果集合包含指定元素则返回true。一般判断方法：o==null ? e==null : o.equals(e)
• Iterator<E> iterator()：返回迭代器
• default Spliterator<E> spliterator()：返回并行迭代器Spliterator(JDK8新增)。
• Object[] toArray()：返回包含所有集合元素的数组，它是数据和集合之间的桥梁。
• <T> T[] toArray(T[] a)：同上，只不过指定了数组具体数据类型。如果返回元素大于数组a，则会重新创建一个新数组存储集合元素返回，如果小于等于则直接返回数组a。

修改操作

• boolean add(E e)：将元素e添加到集合中，如果添加成功则返回true。如果元素已经存在集合中，并且该集合不允许重复，则返回false。
• boolean remove(Object o)：删除集合中指定元素。

批处理操作

批处理操作就是方法用于操作另一个集合。

• boolean containsAll(Collection<?> c)：如果集合包含集合c中的所有元素，则返回true，否则返回false。
• boolean addAll(Collection<? extends E> c)：将集合c中所有元素添加到集合中，如果调用的集合发生的改变，则返回true，否则返回false。
• boolean removeAll(Collection<?> c)：从调用集合中删除c中的所有元素，如果调用集合发生改变，则返回true。
• default boolean removeIf(Predicate<? supper E> filter)：从调用集合中删除满足predicate过滤条件的元素(JDK8新增)。
• boolean retainAll(Collectio<?> c)：移除调用者集合中不包含在集合c中的元素，如果集合有变化，则返回true。
• clean()：移除集合中所有元素

比较和散列

• boolean equals(Object o)：如果调用集合与obj相等，则返回true。
• int hashCode()：返回调用集合散列值。

流处理

• default Stream<E> stream()：返回一个使用调用集合作为源的流，该流是顺序流。
• default Stream<E> parallelStream()：同上，但是该流支持并行操作

默认实现Collection接口的方法并没有使用同步协议，所以当需要方法同步处理时，需要覆盖Collection提供的方法，自己实现同步协议。
JDK8新增的接口默认实现方法语法极大的方便了接口的扩展，这样对向下兼容提供了很好的帮助。所以如果想要对已有接口进行扩展，为了向前兼容，就需要使用这种接口默认实现方法。

List列表

List结合框架实现如下，除了这些还有AttributeList、RoleList、RoleUnresolvedList这些javax.management包下的实现。

image.png

List是一个元素有序、空重复、允许为空的集合序列(列表)。List的数据结构是一个线性表，它里面有顺序表、链表的实现类。
List扩展了Collection<E>接口，我们会发现Collection<E>中的接口方法List又重新定义了一遍。我理解之所以这么做是因为在List中这些方法的定义比Collection<E>中更具体，比如add()方法在List说明了通过add()将元素添加到列表某位，而Collection<E>中add()方法就是说了将元素添加到集合。这样做就是通过注释将含义具体化，在语法上List其实是可以不重写的。

List中定义发生改变的方法

下面我将List中重写Collection<E>方法定义发生改变的梳理了一下：

• boolean add(E e)：将元素添加到列表末尾，具体实现类可以对该方法进行添加限制，比如不允许添加null。
• boolean remove(Object o)：删除列表中第一元素。
• boolean addAll(Collection<? extends E> c)：将集合c中所有元素添加到列表的末尾。
• boolean equals(Object o)：比较两个列表是否相等，两个列表定义相同，列表元素也相同返回true。
• int hashCode()：返回列表哈希值，计算方式：

  int hashCode = 1;
     for (E e : list)
         hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());

List接口新增方法

下面是List接口根据列表的特性，新增的一些接口方法定义。

• boolean addAll(int index,Collection<? extends E> c)：将集合c中所有元素插入到列表的index索引位置，列表中index后面的元素全部向后移动。如果调用列表发生了改变，则返回true。
• default void replaceAll(UnaryOperator<E> operator)：将列表中所有元素通过operator函数处理，来更新列表中所有元素。
• default void sort(Comparator<? supper E> c)：使用c比较器，将列表元素进行排序。
• E get(int index)：返回列表指定索引位置元素
• E set(int index,E element)：替换指定索引位置元素，返回旧元素。
• void add(int index,E element)：在列表指定索引位置添加元素。
• E remove(int index)：删除指定索引位置元素。
• int indexOf(Object o)：返回指定元素在列表中第一次出现的位置。如果列表不包含该元素，则返回-1。
• int lastIndexOf(Object o)：同上，不过返回最后一次出现的维值。
• ListIterator<E> listiterator()：返回编列列表的listiterator。
• ListIterator<E> listiterator(int index)：返回指定起始索引位置的Listiterator。
• List<E> subList(int fromIndex,int toIndex)：返回该列表从索引位置fromIndex到toIndex元素的视图。注意，这里并不是创建了一个新列表，二者是同一引用。一个很好的使用方式，比如删除列表指定范围元素：list.subList(from, to).clear();。

ArrayList

ArrayList接口继承抽象类AbstractList<E>，并且实现了List<E>、RandomAccess、Cloneable和Java.io.Serializable接口。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

再说ArrayList之前我们先看下AbstractList抽象类把。

AbstractList

AbstractList抽象抽类继承AbstractCollection<E>抽象类和List<E>接口。
它在集合框架中的位置如下图：

image.png

AbstractCollection<E>抽象类是Cllection<E>接口骨架实现，除了将iterator()和size()方法定义为抽象方法，其它方法基本都进行了默认实现。
AbstractCollection<E>实现分为两种类型，一种是真正的通用，所有下面的集合类基本都会以相同的方式实现该方法。比如isEmpty()、contains()、remove()、toArray()等这些方法，

public abstract class AbstractCollection<E> implement Collection<E>{
    public boolean isEmpty() {
        //通过子类实现的size方法比较
        return size() == 0;
    }
    public boolean contains(Object o) {
        //调用子类实现的迭代器，通过迭代器遍历集合
        Iterator<E> it = iterator();
        //通过null值的判断就知道，Collection底层本身是支持存储null的
        if (o==null) {
            while (it.hasNext())
                if (it.next()==null)
                    return true;
        } else {
            while (it.hasNext())
                if (o.equals(it.next()))
                    return true;
        }
        return false;
    }
    public boolean remove(Object o) {
        Iterator<E> it = iterator();
        if (o==null) {
            while (it.hasNext()) {
                if (it.next()==null) {
                    it.remove();
                    return true;
                }
            }
        } else {
            while (it.hasNext()) {
                //子类需要自己实现equal方法
                if (o.equals(it.next())) {
                    it.remove();
                    return true;
                }
            }
        }
        return false;
    }
    ....
}

我们可以看到AbstractCollection<E>所有遍历操作都是用子类需要实现的迭代器iterator()来完成的，对于比较操作都是使用equals()方法，所以子类都需要实现和重写这两个方法。接下来我们再来看看AbstractList<E>抽象类。

AbstractList<E>是List<E>接口的骨干实现抽象类，它最大限度的为Java能够“随机访问”数据存储(比如数组)提供了实现。

对于顺序访问的数据存储，需要使用AbstractList的子类AbstractSequentialList抽象类。

首先AbstractList实现了AbstractCollection中的iterator()方法，但是没有实现size()方法，并且又增加了一个get()方法。所以AbstractList的子类必须实现size()和get()方法。

abstract public E get(int index);

下面看看AbstractList具体实现的方法。

默认AbstractList是不支持修改操作的，所以如果想要支持修改，子类需要重新实现set、add、remove方法，否则抛出UnsupportedOperationException异常。

    public E set(int index, E element) {
        throw new UnsupportedOperationException();
    }
    public void add(int index, E element) {
        throw new UnsupportedOperationException();
    }
    public E remove(int index) {
        throw new UnsupportedOperationException();
    }

通过ListIterator来实现正反向索引数据方法。ListIterator通过游标的方式记录遍历位置，所以当调用next()方法时游标其实已经移到元素后面了，所以当我们找到元素后要返回游标的前一个位置。

public int indexOf(Object o) {
        ListIterator<E> it = listIterator();
        if (o==null) {
            while (it.hasNext())
                //当next()方法已经找到匹配元素后，返回游标的前一个位置
                if (it.next()==null)
                    return it.previousIndex();
        } else {
            while (it.hasNext())
                if (o.equals(it.next()))
                    return it.previousIndex();
        }
        return -1;
    }

    public int lastIndexOf(Object o) {
        ListIterator<E> it = listIterator(size());
        if (o==null) {
            while (it.hasPrevious())
                //同理通过previous()方法匹配到指定元素后，返回游标的后一个位置
                if (it.previous()==null)
                    return it.nextIndex();
        } else {
            while (it.hasPrevious())
                if (o.equals(it.previous()))
                    return it.nextIndex();
        }
        return -1;
    }

清除列表全部元素，AbstractList抽象出一个removeRange方法，能够删除列表中任意连续元素。

    public void clear() {
        removeRange(0, size());
    }
    protected void removeRange(int fromIndex, int toIndex) {
        //从删除起始位置获取ListIterator迭代器
        ListIterator<E> it = listIterator(fromIndex);
       //很细节n的使用
        for (int i=0, n=toIndex-fromIndex; i<n; i++) {
            it.next();
            it.remove();
        }
    }

将集合元素添加到当前列表，使用子类实现的add方法。

public boolean addAll(int index, Collection<? extends E> c) {
        //检测下标是否越界
        rangeCheckForAdd(index);
        //只要有元素添加进去就返回true
        boolean modified = false;
        for (E e : c) {
            add(index++, e);
            modified = true;
        }
        return modified;
    }
    private void rangeCheckForAdd(int index) {
        if (index < 0 || index > size())
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

AbstractList不但实现了iterator()方法，还提供了listIterator()方法。

    public Iterator<E> iterator() {
        return new AbstractList.Itr();
    }
    public ListIterator<E> listIterator() {
        return listIterator(0);
    }
    public ListIterator<E> listIterator(final int index) {
        rangeCheckForAdd(index);
        return new AbstractList.ListItr(index);
    }

并且以内部类实现了Iterator的Itr和ListIterator的ListItr。这两个内部类代码太长了，就不贴了说下他们思想。
Itr通过游标cursor来表示下一个元素的位置，同时它利用一个lastRet表示本次迭代的位置，lastRet的作用就是为remove方法提供删除最后一次迭代的元素。lastRet只要在remove用完一次都会将它置为-1。Itr在next()和remove()方法中都会调用下面这个方法，判断操作数(modCount)是否在遍历期间发生改变，如果有就直接抛出ConcurrentModificationException，目的就是为了防止并发修改。

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

ListItr继承了Itr类，同样使用游标cursor来索引数据。只不过提供了previous()和hasPrevious()和获取索引位置的接口。

AbstractList针对截取还提供了内个实现类：SubList和RandomAccessSubList。SubList虽然是个独立类，但实际操作的就是AbstractList。而RandomAccessSubList就是提供了标识能够支持随机随机访问的SubList。

      public List<E> subList(int fromIndex, int toIndex) {
        return (this instanceof RandomAccess ?
                new RandomAccessSubList<>(this, fromIndex, toIndex) :
                new SubList<>(this, fromIndex, toIndex));
    }

RandomAccess

ArrayList还实现了RandomAccess接口，RandomAccess是一个空接口，用于标识子类支持快速随机访问。
比如对于支持随机访问的集合，使用随机访问的速度是快于使用迭代器的。

//速度更快，所以List应该实现它
for (int i=0, n=list.size(); i < n; i++)
         list.get(i);

for (Iterator i=list.iterator(); i.hasNext(); )
         i.next();     

Clonable

Clonable接口也是一个标识接口，表示实现类可以使用clone方法(clone()是java.lang.Object中定义的方法，所以所有类实际都可以重写该方法)。如果没有使用Clonable接口标记类，直接调用clone()方法将会抛出CloneNotSupportedException异常。
需要注意的两点是：

1. 拷贝对象返回的是一个新对象，而不是之前的引用(从堆中重新创建一个对象)。
2. 使用clone()方法和new操作符返回的对象相比，clone()返回的对象已经包含原对象的操作信息，而不是对象的初始信息。

Object中的clone()方法已经有默认实现了，但是这个实现的是一种浅拷贝，也就是并不会把对象所有属性全部拷贝一份，而是有选择的拷贝。比如对于引用类型，实际拷贝过去的是引用地址，这样就会导致两个对象操作同一个引用。
所以如果想要使用深拷贝，需要重新实现clone方法，不仅利用浅拷贝将基础类型进行拷贝，而且还还需将引用类型进行深拷贝。
还有一种实现深拷贝的方法就是利用序列化与反序列化，将对象序列化成字节，然后反序列化成对象返回。

Serializable

Serializable也是一个标记接口，用于表示实现类可以被序列化。序列化与反序列化其实就是将Java中对象转换成字节，或从字节反序列化成对象。之所以需要转换成字节，是因为我们无论是将对象持久化还是将对象进行网络传输，操作的只能是字节。
Java提供了对象的序列化与反序列化方法，就是使用ObjectInputStream和ObjectOutputStream。

序列化一般常用于：

1. 将内存中的对象持久化到磁盘上。
2. 使用套接字将对象在网络上传输。
3. 想通过RMI在网络中传输对象。

使用序列化需要有以下注意点：

• 当一个父类实现序列化，子类自动实现序列化，无需重新实现Serializable接口。
• 序列化时只保存对象的状态，不保存对象的方法。
• 序列化对象会将引用类型变量也进行序列化，并且这个过程是递归的。

实际中我们可能不需要序列化对象中所有的数据(比如一些敏感数据，或一些不重要数据)，这时候就可以使用transient关键字。使用transient关键字修饰的变量，不会被序列化。

除了使用Serializable接口进行序列化，还可以使用Externalizable接口进行序列化。使用Externalizable接口进行序列化就需要自己实现writeExternal和readExternal方法。

    private void writeObject(ObjectOutputStream out) throws IOException {
        out.defaultWriteObject();
        out.writeInt(age);
    }
    private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
        in.defaultReadObject();
        age = in.readInt();
    }

使用Externalizable接口还需要提供一个无参构造方法，因为在读取该对象时，会调用无参改造方法创建对象。
对于单例对象，为了保证单例对象的特性，我们可以提供一个readResolve()方法，该方法直接返回单例对象。

private Object readResolve() throws ObjectStreamException{
    return getInstance();
} 

ArrayList实现

说完了上面这些，我们来看看ArrayList具体是怎么实现的。
ArrayList有以下特点：

• 容量不固定，可以动态扩容。
• 元素可重复并且有序。
• 允许存储null值。
• 对于随机访问效率非常高，时间复杂度为O(1)。
• 对于添加和删除元素，需要移动数据，平均时间复杂度为O(n)。
• 相较LinkedList占用空间更小，不需要存储额外数据。

ArrayList在集合框架的位置：

image.png

ArrayList使用Object数组作为底层存储。

    //列表默认大小
    private static final int DEFAULT_CAPACITY = 10;
    //ArrayList为空时存储数组对应的数组，不知道用途
    private static final Object[] EMPTY_ELEMENTDATA = {};
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    //ArrayList存储数据的数组
    transient Object[] elementData; 
    //ArrayList的长度
    private int size;
    //数组最大长度，因为有些JVM会在数组前添加一个标签，所以减去8。最大值为2^31-1，大概有2147483647
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

ArrayList提供了三个构造方法。

//指定列表容量大小
    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);
        }
    }
    //没有指定容量大小，测试用默认大小(默认大小为10)
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    //构造包含指定集合的列表
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray有可能返回不是Object[]数组
            if (elementData.getClass() != Object[].class)
            //Arrays.copyOf可以用来创建一个新数组。
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

下面是一些查询相关的实现：

 //返回指定长度
    public int size() {
        return size;
    }
    //通过长度来判断列表是否为空
    public boolean isEmpty() {
        return size == 0;
    }
    //判断是否包含指定元素，通过indexOf正向搜索判断。如果不存在则-1 < 0
    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }
    //正向索引只要包括指定元素就返回其索引位置，否则返回-1
    public int indexOf(Object o) {
        if (o == null) {
            //通过随机访问来遍历，效率要比iterator高
            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;
    }
    //同上，只不过从后向前搜索
    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;
    }

将ArrayList转换成数组。

    public Object[] toArray() {
        //使用Arrays.copyOf创建一个包含指定数组元素的新数组，之所以不直接返回，是因为有可能数组还有空余空间
        return Arrays.copyOf(elementData, size);
    }
    public <T> T[] toArray(T[] a) {
        //如果给定数组小于列表长度，则返回一个新数组
        if (a.length < size)
            // Make a new array of a's runtime type, but my contents:
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
        //使用System.arraycopy将一个数组元素copy到另一个数组中
        System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }

下面是一些获取、修改、增加的常规操作。需要注意在调用ensureCapacityInternal()扩容方法时，modCount进行了自加1操作。modCount的作用就是fail-fast，防止迭代过程中其它线程修改列表。

//通过elementData方法强制数据类型转换，只需要添加一个unchecked注解
    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }
    public E get(int index) {
        //检测给定的下标是否越界
        rangeCheck(index);
        return elementData(index);
    }
    //修改元素没有增加modCount。。。
    public E set(int index, E element) {
        rangeCheck(index);
        //修改完元素后，返回修改前的值
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }
    public boolean add(E e) {
        //添加元素前判断是否需要扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        //添加元素判断是否需要动态扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                size - index);
        elementData[index] = element;
        size++;
    }
    public E remove(int index) {
        rangeCheck(index);
        //增加操作记录数，用于fail-fast判断，防止迭代过程中并发修改
        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            //通过System.arrayCopy将要删除元素位置后面的所有元素向前移动一位
            System.arraycopy(elementData, index+1, elementData, index,
                    numMoved);
        //将最后一位置为null
        elementData[--size] = null; // clear to let GC do its work
        return oldValue;
    }
    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;
    }
    //用于删除指定位置元素
    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
    }
    public void clear() {
        modCount++;

        //并没有直接将数组置为null，而是逐个元素置为null。方便之后使用
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }

下面看一下ArrayList如何实现的动态扩容。

1. 每当添加新元素时，首先判断剩余容量是否满足新添加的元素。如果不足，则进行扩容。
2. 首先尝试分配原容量1.5倍，判断是否满足需求。如果不满足需求，则扩容至所需的最少容量。这个最小容量就是原大小加上所要添加的元素个数。
3. 如果扩容后的大小超过了Integer.MAX_VALUE则直接OOM。
4. 最大能够分配的容量大小为Integer.MAX_VALUE个元素。

//传入最小需要的容量大小，如果add()调用则minCapacity为size+1，如果addAll()则minCapacity为需要添加的集合大小加上原始长度
    //注意minCapacity为原始长度加上要扩容的大小
    private void ensureCapacityInternal(int minCapacity) {
        //如果当前数组为空，则最小扩容至minCapacity的最大值。也就是说数组最小长度一定大于默认容量10
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        //每次调用该方法，说明肯定修改了列表，将修改记录器自加1
        modCount++;

        // 判断剩余容量不够，需要进行扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //扩容到原来容量的1.5，增加当前数组长度一半
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果1.5倍容量不足，则使用传递过来的最小所需容量
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //如果新容量超过了最大值，则尽量分配所能分配的大小，最大值也就是Integer.MAX_VALUE
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 创建一个更大的数组
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    private static int hugeCapacity(int minCapacity) {
        //如果所需容量都超过了MAX_INTEGER(超过MAX_INTEGER后，为负数了)直接抛出OOM
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
    }

我们再来看下ArrayList的clone方法，它实际是一个浅拷贝，列表元素如果为引用类型，则只是将引用拷贝过去。

    public Object clone() {
        try {
            ArrayList<?> v = (ArrayList<?>) super.clone();
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
    }

实现forEach方法，将每个元素作用action，遍历过程中如果其它线程修改了列表，则直接fail-fast。

    public void forEach(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        final int expectedModCount = modCount;
        @SuppressWarnings("unchecked")
        final E[] elementData = (E[]) this.elementData;
        final int size = this.size;
        for (int i=0; modCount == expectedModCount && i < size; i++) {
            action.accept(elementData[i]);
        }
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }

最后我们再来看下ArrayList如何完成的排序。传入c为比较器，如果为null，则默认采用自然排序比较器。

    @Override
    @SuppressWarnings("unchecked")
    public void sort(Comparator<? super E> c) {
        final int expectedModCount = modCount;
        Arrays.sort((E[]) elementData, 0, size, c);
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }

ArrayList还重新实现了ListItr和Itr，实现原理和AbstractList差不多，只是添加了一个forEachRemaining方法。
Arraylist还实现了SplIterator，并行迭代器。

LinkedList

LinkedList是列表的双向链表实现，LinkedList是双向队列Deque的一种实现，但是它是为一个允许存储null元素的队列。LinkedList不是线程安全的，如果我们向操作线程安全的LinkedList可以在创建LinkedList时添加同步处理：

List list = Collections.synchronizedList(new LinkedList(...));

LinkedList是顺序访问的列表，它不是继承AbstractList抽象类，而是继承AbstractSequenceList。AbstractSequenceList是List的简化版本，它只支持按顺序访问。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

AbstractSequenceList抽象类定义，

image.png

它对外提供了随机获取的接口，但是内部还是通过迭代器顺序访问所需元素。

    public E get(int index) {
        try {
            //利用子类实现的listIterator迭代器访问指定位置元素
            return listIterator(index).next();
        } catch (NoSuchElementException exc) {
            throw new IndexOutOfBoundsException("Index: "+index);
        }
    }
    public E set(int index, E element) {
        try {
            //利用子类实现的listIterator迭代器访问指定位置元素
            ListIterator<E> e = listIterator(index);
            E oldVal = e.next();
            e.set(element);
            return oldVal;
        } catch (NoSuchElementException exc) {
            throw new IndexOutOfBoundsException("Index: "+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;
        }
    }

因为它是双向队列Deque的实现类，所以LinkedList也支持双向操作。LinkedList通过指向头尾节点的指针来完成相应操作。

transient Node<E> first;
transient Node<E> last;

下面是链表的核心实现，列表其它方法都是调用的这些方法操作链表。

//在链表头部插入元素
    private void linkFirst(E e) {
        final LinkedList.Node<E> f = first;
        //创建新节点，将原头节点作为新节点的next
        final LinkedList.Node<E> newNode = new LinkedList.Node<>(null, e, f);
        //插入节点作为first节点
        first = newNode;
        //最后要修改原头节点的prev
        //如果fist节点之前为空，说明之前是一个空链表，要将last节点指向新节点
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }
    //在链表尾部添加元素
    void linkLast(E e) {
        final LinkedList.Node<E> l = last;
        //将原尾节点作为新节点的prev节点
        final LinkedList.Node<E> newNode = new LinkedList.Node<>(l, e, null);
        //下面是修改原尾节点的next
        last = newNode;
        //如果原尾节点为null，说明之前是一个空列表，需要将头部元素也指向当前节点。
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }
    //在指定节点前添加元素
    void linkBefore(E e, LinkedList.Node<E> succ) {
        //指定节点作为新节点的前节点，指定节点的后节点最为新节点的后节点
        final LinkedList.Node<E> pred = succ.prev;
        final LinkedList.Node<E> newNode = new LinkedList.Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }
    //删除头节点
    private E unlinkFirst(LinkedList.Node<E> f) {
        // 取出头节点元素，作为返回值
        final E element = f.item;
        final LinkedList.Node<E> next = f.next;
        //释放头结点空间
        f.item = null;
        f.next = null; // help GC
        //将头节点指向下一个节点
        first = next;
        //如果下一个节点为空，说明删除节点后就是空链表了，需要将尾节点置为null
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }
    //删除尾节点
    private E unlinkLast(LinkedList.Node<E> l) {
        //取出尾节点值，作为返回值
        final E element = l.item;
        final LinkedList.Node<E> prev = l.prev;
        //释放尾节点空间
        l.item = null;
        l.prev = null; // help GC
        //将尾节点指向前一个节点
        last = prev;
        //如果前一个节点为null，说明此列表当前为空列表
        if (prev == null)
            first = null;
        else
            prev.next = null;
        size--;
        modCount++;
        return element;
    }
    //删除指定节点
    E unlink(LinkedList.Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final LinkedList.Node<E> next = x.next;
        final LinkedList.Node<E> prev = x.prev;
        //如果删除节点的前节点为null，则说明删除的是头节点，需要将fist指向删除节点的后节点
        if (prev == null) {
            first = next;
        } else {
            //否则将删除节点的前节点的尾指针，指向删除节点的后节点
            prev.next = next;
            x.prev = null;
        }
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }
        x.item = null;
        size--;
        modCount++;
        return element;
    }

CopyOnWriteArrayList

线程安全的ArrayList，它的所有操作都是通过创建底层数组的新副本来实现的。
CopyOnWriteArrayList是直接实现List接口来实现的：

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {

CopyOnWriteArrayList对于修改和新增元素通过ReentrantLock锁来防止多线程并发操作，并且所有操作都是通过创建一个新数组来完成的。

    public boolean add(E e) {
        //同步锁
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            //使用新数组添加元素
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            newElements[len] = e;
            //将新数组赋值为CopyOnWriteArrayList的数组
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }

Vector

Vector和ArrayList一样实现了可动态扩容的动态数组，Vector相比ArrayList的区别就是它是线程安全的。如果不需要线程安全特性，可以使用ArrayList来代替。
Vector定义和ArrayList完全一样：

 public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable

Vector与ArrayList不同的是提供了一种构造方法能够制定每次动态扩容的增长容量。

public Vector(int initialCapacity, int capacityIncrement) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
        //制定每次增长的容量
        this.capacityIncrement = capacityIncrement;
    }

方法实现方式和ArrayList基本相同，只不过每个方法都添加了synchronize标识。

    public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }

下面是Vector的动态扩容机制，实现原理和ArrayList一样，区别就是每次扩容的大小。

   private void ensureCapacityHelper(int minCapacity) {
        //判断是否需要动态扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //如果没有指定每次扩容大小，则默认为之前的2倍
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                capacityIncrement : oldCapacity);
        //如果扩容之后的大小还是不满足需求，则使用最少需要的容量作为扩容后大小
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //超过容量最大值
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        //最多分配Integer.MAX_VALUE
        return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
    }

Vector中的许多方法定义感觉名称和淘汰Enumeratio如果没有同步需求最好使用ArrayList，否则效率太低。

Stack

Stack是数据结构的堆栈实现，它扩展了Vector类，提供了栈的入栈、出栈、查看元素、是否为空和搜索元素这几个方法。

image.png

由于它基于Vector实现，所以Stack也是线程安全的。

public E push(E item) {
        //入栈，并返回元素
        addElement(item);
        return item;
    }
    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) {
        //从后向前搜索
        int i = lastIndexOf(o);
        if (i >= 0) {
            return size() - i;
        }
        return -1;
    }

由于Deque双边队列的特性，其实我们可以使用它作为栈使用，这也是官方推荐的。比如使用LinkedList作为栈使用，是非常方便的。

Queue/Deque

Java提供的队列：

image.png

Queue

队列是一种非常重要的数据结构，它具有先进先出的特点。元素从尾部添加，从头部移出。
队列有两种：单队列和循环队列。单队里就是最普通的队列，单队列对于空间利用率非常低，因为队头移出元素后就不能使用了，而循环队列是对他的一种改进。
队列一般用于缓存、并发访问等场景。

Java集合的Queue接口继承自Collection接口，Deque、LinkedList、PriorityQueue、BlockQueue等都实现了Queue接口。
Queue除了提供Collection里面的方法，它又根据队列的特性提供了一些方法。

image.png

Queue对于添加、删除、获取都分别提供了两个方法，其中一种操作失败后直接抛出异常，另一种是返回特殊值。

image.png

Queue建议不要添加null元素，如果添加null元素，则抛出NullPointException。这样做的目的就是为了防止获取的元素为null时不知道是对还是错。Queue下面的实现类基本都复合了该要求，但是LinkedList没有对这一要求实现。
Insert操作，

Deque

Deque是Double ended queue的缩写，即双端队列。Dequeu支持从两端添加和删除元素。Deque继承了Queue接口，并且提供的添加、删除、访问也都是两套方法，一种操作失败直接抛出异常，一种是返回指定值。

image.png

Deque除了提供Queue中的指定方法外，还分别提供了操作队前元素和队尾操作的方法。

image.png

比如void addFirst(E e)在队前添加元素如果失败则直接抛出异常，boolean offerFirst(E e)队前添加元素，如果失败则返回false。同理E removeFirst()和E pollFirst()是一样的道理。

Deque还提供了堆栈方法，堆栈方法如果操作失败，直接抛出异常。

//返回队头元素，并且删除它。如果队列为空，则直接抛出NoSuchElementException异常
E poll();
//在队头添加指定元素，如果队列已满，则直接抛出IllegalStateException异常
void push(E e);

堆栈方法和poll和removeFirst的作用是一样的，push和addFirst的作用是一样的。

Deque还提供了两个删除元素的方法，一个是从队头开始查找指定元素，找到后将其删除。另一个则是相反，从队尾开始查找。

boolean removeFirstOccurrence(Object o);
boolean removeLastOccurrence(Object o);

Deque在最后还定义了一些集合方法：

//删除双端队列第一个出现o的元素
boolean remove(Object o)
//判断队列是否存在指定元素
boolean contains(Object o)
//返回队列长度
int size()
//返回队列的迭代器
Iterator<E> iterator()
//相反方向的迭代器
Iterator<E> descendingIterator()

Deque很有趣的提供了一个从队尾向前遍历的迭代器方法。

Dequeu的一般实现：

• LinkedDeque：大小可变的链表双端队列，允许存储null。
• ArrayDeque：大小可变的数组双端队列，不允许存储null
• LinkedBlockingDeque：并发场景，如果队列为空，获取操作将被阻塞，知道有元素。

ArrayBlockingQueue/

ArrayBlockingQueue是一个有界的阻塞队列，

AbstractQueue

AbstractQueue是Queue接口的骨干实现，它实现了AbstractCollection抽象类，实现了Queue接口。它定义了添加、删除、获取抛出异常的实现。

    public boolean add(E e) {
        //如果添加失败，直接抛出异常
        if (offer(e))
            return true;
        else
            throw new IllegalStateException("Queue full");
    }
    public E remove() {
        E x = poll();
        //如果删除失败，直接抛出异常
        if (x != null)
            return x;
        else
            throw new NoSuchElementException();
    }
    public E element() {
        E x = peek();
        //获取元素为空，直接抛出异常
        if (x != null)
            return x;
        else
            throw new NoSuchElementException();
    }
    public void clear() {
        while (poll() != null)
            ;
    }

可以看到它们还是依赖子类去实现不抛出异常的方法。

ArrayBlockingQueue/LinkedBlockingQueue

对于Query因为ArrayBlockingQueue和LinkedBlockingQueue也可以作为非阻塞是先用(比如offer和poll)方法，所以就没有单独针对非阻塞Queue进行实现。ArrayBlockingQueue和LinkedBlockingQueue本身也是线程安全的。

ArrayBlockingQueue

ArrayBlockQueue是一个阻塞有限队列，每次使用时，需要指定容量大小，也可以指定操作线程顺序是否按照FIFO形式。它使用Object[]数组存储队列元素，ArrayBlockQueue在使用每个方法时使用ReentrantLock锁来保证访问。
ArrayBlockQueue添加元素时，如果队列满了则会阻塞线程等待。提供了三种添加操作add、offer、put，add添加失败直接抛出异常，它底层依赖的是offer。如果队列满了，offer可以直接返回false，也可以设置一个阻塞等待时间。而put方法会一直阻塞等待。

    public boolean offer(E e) {
        checkNotNull(e);
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            //队列满了直接返回失败
            if (count == items.length)
                return false;
            else {
                enqueue(e);
                return true;
            }
        } finally {
            lock.unlock();
        }
    }
    
    public boolean offer(E e, long timeout, TimeUnit unit)
        throws InterruptedException {
        checkNotNull(e);
        long nanos = unit.toNanos(timeout);
        final ReentrantLock lock = this.lock;
        lock.lockInterruptibly();
        try {
            //等待指定的超时时间
            while (count == items.length) {
                if (nanos <= 0)
                    return false;
                nanos = notFull.awaitNanos(nanos);
            }
            enqueue(e);
            return true;
        } finally {
            lock.unlock();
        }
    }
    public void put(E e) throws InterruptedException {
        checkNotNull(e);
        final ReentrantLock lock = this.lock;
        lock.lockInterruptibly();
        try {
            //无限阻塞等待
            while (count == items.length)
                notFull.await();
            enqueue(e);
        } finally {
            lock.unlock();
        }
    }

对应的poll也可以直接返回或设置阻塞等待时间，take方法则会无限等待。

添加元素：

• add(E e)=offer(E e)：直接返回
• offer(E e,long timeout, TimeUnit unit)：指定超时时间
• put(E e)：无限阻塞
  删除元素：
• remove() = poll()：直接返回
• poll(long timeout, TimeUnit unit)：指定超时时间
• take()：无限阻塞
  访问元素：
• element()=peek()：直接返回

LinkedBlockingQueue

LinkedBlockingQueue实现原理和ArrayBlockQueue原理是一样的，只不过通过单链表进行实现的。通过一个队头指针删除元素，通过对尾指针添加元素。

    static class Node<E> {
        E item;
        Node<E> next;
        Node(E x) { item = x; }
    }
    //队头指针
    transient Node<E> head;
    //队尾指针
    private transient Node<E> last;
   
   private void enqueue(Node<E> node) {
        //队尾添加元素
        last = last.next = node;
    }
    private E dequeue() {
        //队头指针删除元素
        //此时head为空节点(看下面构造方法)
        Node<E> h = head;
        Node<E> first = h.next;
        
        h.next = h; // help GC
        head = first;
        //取出元素返回
        E x = first.item;
        //将队头元素置为null
        first.item = null;
        return x;
    }

注意它是通过一个空节点开始，队头指针和队尾指针都开始都指向这个空节点。

    public LinkedBlockingQueue(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException();
        this.capacity = capacity;
        //空节点一直表示队头指针
        last = head = new Node<E>(null);
    }

ArrayBlockingQueue和LinkedBlockingQueue

1. ArrayBlockingQueue采用数组实现队列，创建ArrayBlockingQueue必须要指定队列大小。
2. LinkeBlockingQueue可以指定大小也可以不指定，如果不指定默认大小时Integer.MAX_VALUE。
3. 对于队列初始大小不确定的阻塞队列可以使用LinkedBlockingQueue，这样能够节省空间。

ArrayDeque/LinkedBlockingDeque

对于双端队列，没有阻塞实现的Deque实现，

ArrayDeque

ArrayDeque是一个容量没有限制的双端数组队列，但是ArrayDeque不是线程安全的，所以不支持多线程并发访问。ArrayDeque大部分操作都是常量时间，
ArrayDeque提供了三个构造方法：

    //如果不指定大小，则默认分配16个元素大小
    public ArrayDeque() {
        elements = new Object[16];
    }
    //指定元素个数
    public ArrayDeque(int numElements) {
        allocateElements(numElements);
    }
    //创建包含指定集合的双端队列
    public ArrayDeque(Collection<? extends E> c) {
        allocateElements(c.size());
        addAll(c);
    }

双端队列的优势在于能够操作队列两端，也就是队列两端都能够增加元素、删除元素。ArrayDeque通过两个游标head和tail来实现这种功能。

LinkedBlockingDeque

链表阻塞双端队列，采用双链表进行实现，即节点即包含指向前节点的指针，也包含指向后节点的指针。
LinkedBlockingDeque是线程安全的，同样使用ReentrantLock锁来保证每个方法的访问。

LinkedBlockingDeque核心方法：

    public boolean offerFirst(E e) {
        if (e == null) throw new NullPointerException();
        //将要添加的元素封装为链表节点
        LinkedBlockingDeque.Node<E> node = new LinkedBlockingDeque.Node<E>(e);
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            return linkFirst(node);
        } finally {
            lock.unlock();
        }
    }
    private boolean linkFirst(LinkedBlockingDeque.Node<E> node) {
        //如果队列长度超过指定容量，则直接返回失败
        if (count >= capacity)
            return false;
        //在链表头部添加一个节点
        LinkedBlockingDeque.Node<E> f = first;
        node.next = f;
        first = node;
        if (last == null)
            last = node;
        else
            f.prev = node;
        ++count;
        notEmpty.signal();
        return true;
    }
    public boolean offerLast(E e) {
        if (e == null) throw new NullPointerException();
        LinkedBlockingDeque.Node<E> node = new LinkedBlockingDeque.Node<E>(e);
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            return linkLast(node);
        } finally {
            lock.unlock();
        }
    }
    private boolean linkLast(LinkedBlockingDeque.Node<E> node) {
        
        if (count >= capacity)
            return false;
        //在链表尾部添加一个元素
        LinkedBlockingDeque.Node<E> l = last;
        node.prev = l;
        last = node;
        if (first == null)
            first = node;
        else
            l.next = node;
        ++count;
        notEmpty.signal();
        return true;
    }

真个LinkedBlockingDeque就是外层通过锁保证并发访问，内层就是操作链表的常规操作。

其它Queue

除了上面说的，针对并发场景Java操作还提供了ConcurrentLinkedQueue和ConcurrentLinkedDeque，对于并发场景我们可以使用上面这两个无界链表队列(虽然阻塞链表队列也能够允许多线程访问，但是效率很低，因为它是通过锁来保证访问单一访问的)。
Java还提供了延迟阻塞队列DelayQueue，队头代表过期元素，越靠近队头过期时间越远。如果没有过期元素，则poll和remove直接返回为空。
下面试DelayQueue类定义，可以看到它里面的所有元素必须是Delayed的子类。

public class DelayQueue<E extends Delayed> extends AbstractQueue<E>
    implements BlockingQueue<E> {

判断元素是否过期的条件是，获取该元素的getDelay(NANOSECONDS)如果小于等于0则说明过期了。

同步队列SynchronousQueue，这个队列是想要添加元素需要等待另一个线程执行删除操作才可以添加，同理相反。这个队列没有容量概念，貌似就一个元素？也不能查看元素。目前不知道这个队列的用途。