[TOC]

1.List接口的特性

java.util.List 接口继承于 Collection 接口，与Map最大的不同之处，在于它属于单列集合,相当于一个列表，有以下这些特点：

有顺序，按照添加的顺序存储，是一种线性结构。
可以根据索引查询元素。
元素可以重复。

An ordered collection(also known as a sequence ).The user of this interface has precise control over where in the list each element is inserted.The user can access elements by their integer index(position in the list), and search for elements in the list.

Unlike sets, lists typically allow duplicate elements. More formally,lists typically allow pairs of elements <tt>e1</tt> and <tt>e2</tt> such that <tt>e1.equals(e2)</tt>, and they typically allow multiple null elements if they allow null elements at all. It is not inconceivable that someone might wish to implement a list that prohibits duplicates, by throwing runtime exceptions when the user attempts to insert them, but we expect this usage to be rare.

下面是List接口的继承关系：

2.List接口的源码解析

继承于Collection接口，有顺序，取出的顺序与存入的顺序一致，有索引，可以根据索引获取数据，允许存储重复的元素，可以放入为null的元素。
最常见的三个实现类就是ArrayList，Vector,LinkedList，ArrayList和Vector都是内部封装了对数组的操作，唯一不同的是，Vector是线程安全的，而ArrayList不是，理论上ArrayList操作的效率会比Vector好一些。

里面是接口定义的方法：

int size();  //获取大小

boolean isEmpty();  //判断是否为空

boolean contains(Object o);  //是否包含某个元素

Iterator<E> iterator(); //获取迭代器

Object[] toArray();  // 转化成为数组（对象）

<T> T[] toArray(T[] a);  // 转化为数组（特定位某个类）

boolean add(E e); //添加

boolean remove(Object o);  //移除元素

boolean containsAll(Collection<?> c); // 是否包含所有的元素

boolean addAll(Collection<? extends E> c); //批量添加

boolean addAll(int index, Collection<? extends E> c); //批量添加，指定开始的索引

boolean removeAll(Collection<?> c); //批量移除

boolean retainAll(Collection<?> c); //将c中不包含的元素移除

default void replaceAll(UnaryOperator<E> operator) {}//替换

default void sort(Comparator<? super E> c) {}// 排序

void clear();//清除所有的元素

boolean equals(Object o);//是否相等

int hashCode(); //计算获取hash值

E get(int index); //通过索引获取元素

E set(int index, E element);//修改元素

void add(int index, E element);//在指定位置插入元素

E remove(int index);//根据索引移除某个元素

int indexOf(Object o);  //根据对象获取索引

int lastIndexOf(Object o); //获取对象元素的最后一个元素

ListIterator<E> listIterator(); // 获取List迭代器

ListIterator<E> listIterator(int index); // 根据索引获取当前的位置的迭代器

List<E> subList(int fromIndex, int toIndex); //截取某一段数据

default Spliterator<E> spliterator(){} //获取可切分迭代器

比较常用的几个方法无非增删改查：

E get(int index); //通过索引获取元素

E set(int index, E element);//修改元素

void add(int index, E element);//在指定位置插入元素

E remove(int index);//根据索引移除某个元素

上面的方法都比较简单，值得一提的是里面出现了ListIterator，这是一个功能更加强大的迭代器，继承于Iterator,只能用于List类型的访问，拓展功能例如：通过调用listIterator()方法获得一个指向List开头的ListIterator，也可以调用listIterator(n)获取一个指定索引为n的元素的ListIterator,这是一个可以双向移动的迭代器。
操作数组索引的时候需要注意，由于List的实现类底层很多都是数组，所以索引越界会报错IndexOutOfBoundsException。

3.相关子类介绍

说起List的实现子类，最重要的几个实现类如下：

ArrayList：底层存储结构是数组结构，增加删除比较慢，查找比较快，是最常用的List集合。线程不安全。
LinkedList：底层是链表结构，增加删除比较快，但是查找比较慢。线程不安全。
Vector：和ArrayList差不多，但是是线程安全的，即同步。

3.1 ArrayList

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

ArrayList 继承了AbstractList接口，实现了List，以及随机访问，可克隆，序列化接口。不是线程安全的，如果需要线程安全，则需要选择其他的类或者使用Collections.synchronizedList(arrayList)
允许存储null元素，也允许相同的元素存在。

其底层实际上是数组实现的，那为什么我们使用的时候只管往里面存东西，不用关心其大小呢？因为ArrayList封装了这样的功能，容量可以动态变化，不需要使用者关心。

3.1.1 成员变量

transient表示这个属性不需要自动序列化，因为element存储的不是真的元素的对象，而是指向对象的地址，所以这样的属性序列化是没有太大意义的。对地址序列化之后，反序列化的时候找不到之前的对象，所以需要手动实现对对象的序列化。

    // 真正存取数据的数组
    transient Object[] elementData; 
    // 实际元素个数(不是elementData的大小，是具体存放的元素的数量)
    private int size;

那在哪里去实现对西那个的序列化和反序列化的呢？这个需要我们看源码里面的readOject()和writeOject()两个方法。其实就除了默认的序列化其他字段，这个elementData字段，还需要手动序列化和反序列化。

    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
        // 序列之前需要保存原本的修改的次数，序列化的过程中不允许新修改
        int expectedModCount = modCount;
        // 将当前类的非静态和非transient的字段写到流中，其实就是默认的序列化
        s.defaultWriteObject();

        // 将大小写到输出流中
        s.writeInt(size);

        // 按照顺序序列化里面的每一个元素，注意使用的是`writeOject()`
        for (int i=0; i<size; i++) {
            s.writeObject(elementData[i]);
        }
        // 如果序列化期间有发生修改，就会抛出异常
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }

    // 反序列化
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        elementData = EMPTY_ELEMENTDATA;

        // 读取默认的反序列化数据
        s.defaultReadObject();

        // 读取大小
        s.readInt(); // ignored

        if (size > 0) {
            // 和clone()类似，根据size分配空间，而不是容量
            int capacity = calculateCapacity(elementData, size);
            SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
            ensureCapacityInternal(size);

            Object[] a = elementData;
            // 循环读取每一个元素
            for (int i=0; i<size; i++) {
                a[i] = s.readObject();
            }
        }
    }

很多人可能会有疑问，为什么这个函数没有看到有调用呢？在哪里调用的呢？
其实就是在对象流中，通过反射的方式进行调用的，这里就不展开了，下次一定！！！有兴趣可以看看。

如果我们创建的时候不指定大小，那么就会初始化一个默认大小为10。

private static final int DEFAULT_CAPACITY = 10;

里面定义了两个空数组，EMPTY_ELEMENTDATA名为空数组,DEFAULTCAPACITY_EMPTY_ELEMENTDATA名为默认大小空数组,用来区分是空构造函数还是带参数构造函数构造的arrayList,第一次添加元素的时候使用不同的扩容。之所以是一个空数组，不是null，是因为使用的时候我们需要制定参数的类型。

    private static final Object[] EMPTY_ELEMENTDATA = {};

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

还有一个特殊的成员变量modCount，这是快速失败机制所需要的，也就是记录修改操作的次数，主要是迭代的时候，防止元素被修改。如果操作前后的修改次数对不上，那么有些操作就是非法的。transient表示这个属性不需要自动序列化。

protected transient int modCount = 0;

序列化id如下：为什么需要这个字段呢？这是因为如果没有显示声明这个字段，那么序列化的时候回自动生成一个序列化的id，这样子的话，假设序列化完成之后，往原来的类里面添加了一个字段，那么这个时候反序列化会失败，因为默认的序列化id已经改变了。假设我们给它指定了序列化id的话，就可以避免这种问题，只是增加的字段反序列化的时候是空的。

private static final long serialVersionUID = 8683452581122892189L;

3.1.2 构造方法

构造方法有三个，可以指定容量，指定初始的元素集，可以什么都不指定。

    // 指定初始化的大小
    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() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

   // 传入一个集合，转成数组之后，复制一份作为显得数据集
    public ArrayList(Collection<? extends E> c) {
        Object[] a = c.toArray();
        if ((size = a.length) != 0) {
            if (c.getClass() == ArrayList.class) {
                elementData = a;
            } else {
                elementData = Arrays.copyOf(a, size, Object[].class);
            }
        } else {
            // replace with empty array.
            elementData = EMPTY_ELEMENTDATA;
        }
    }

3.1.3 常用增删改查方法

添加元素

add()方法有两个：

add(E e)：添加一个元素，默认是在末尾添加
add(int index, E element) ：在指定位置index添加(插入)一个元素

    public boolean add(E e) {
        // 确定容量是不是足够，足够就不会增加
        ensureCapacityInternal(size + 1); 
        // size+1的地方，赋值为现在的e
        elementData[size++] = e;
        return true;
    }
    // 在指定的位置插入一个元素
    public void add(int index, E element) {
        // 检查插入的位置，是否合法
        rangeCheckForAdd(index);
        // 检查是不是需要扩容，容量是否足够
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 复制index后面的元素，都往后面移动一位（这是c++实现的底层原生方法）
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        // 在index处插入元素
        elementData[index] = element;
        // 实际的存储元素个数增加
        size++;
    }

查询元素

get()方法相对比较简单，获取之前检查参数是否合法，就可以返回元素了。

    public E get(int index) {
        // 检查下标
        rangeCheck(index);

        return elementData(index);
    }
    // 检查下标
    private void rangeCheck(int index) {
        if (index >= size)
            // 数组越界
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

更新元素

set()和之前的get()有点像，但是必须制定修改的元素下标，检查下标之后，修改，然后返回旧的值。

    public E set(int index, E element) {
        // 检查下标
        rangeCheck(index);
        // 获取旧的值
        E oldValue = elementData(index);
        // 修改元素
        elementData[index] = element;
        // 返回旧的值
        return oldValue;
    }

删除元素

按照元素移除，或者按照下标移除元素

    public E remove(int index) {
        // 检查下标
        rangeCheck(index);
        // 修改次数改变
        modCount++;
        // 获取旧的元素
        E oldValue = elementData(index);
        // 计算需要移动的下标（往前面移动一位）
        int numMoved = size - index - 1;
        if (numMoved > 0)
            // 调用native方法将后面的元素复制，移动往前一步
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        // 将之前的元素置为空，让垃圾回收方便进行
        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 {
            // 遍历，如果equals,则调用删除
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }
    // 快速删除方法
    private void fastRemove(int index) {
        // 修改次数增加1
        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
    }

ArrayList是基于数组动态扩容的，那它什么时候扩容的呢？好像上面的源代码中我们没有看到，其实是有的，所谓扩容嘛，就是容量不够了，那么容量不够的时候只会发生在初始化一个集合的时候或者是增加元素的时候，所以是在add()方法里面去调用的。
在最小调用的时候容量不满足的时候，会调用grow()，grow()是真正扩容的函数，这里不展开了。

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

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

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

3.1.4 小结一下

ArrayList是基于动态数组实现的，增加元素的时候，可能会触发扩容操作。扩容之后会触发数组的拷贝复制。remove操作也会触发复制，后面的元素统一往前面挪一位，原先最后面的元素会置空，这样可以方便垃圾回收。
默认的初始化容量是10，容量不够的时候，扩容时候增加为原先容量的一般，也就是原来的1.5倍。
线程不安全，但是元素可以重复，而且可以放null值，这个需要注意一下，每次取出来的时候是需要判断是不是为空。
3.2 LinkedList
LinkedList底层是以双向链表实现的，这是和ArrayList最大的不同，除此之外它还实现了Deque接口,继承AbstractSequentialList,AbstractSequentialList继承了AbstractList。
同时它也是线程不安全的。
```
public class LinkedList<E>
  extends AbstractSequentialList<E>
  implements List<E>, Deque<E>, Cloneable, java.io.Serializable
```

双向链表底层的数据结构如下:

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

3.2.1 成员变量

里面的成员变量主要有三个，之所以记录同时记录头结点和尾节点，主要是为了能够更快的插入以及查找数据。

// 元素个数
transient int size = 0;
// 链表的首节点
transient Node<E> first;
// 俩表的尾节点
transient Node<E> last;

3.2.2 构造函数

构造函数主要有两个，一个是无参数的够着，一个是需要初始化元素集的函数，初始化的时候其实是调用了批量添加元素的函数addAll()。

    public LinkedList() {
    }
    public LinkedList(Collection<? extends E> c) {
        this();
        // 调用了批量添加元素的函数
        addAll(c);
    }

3.2.3 常用函数

添加元素

linkFirst()在队列头部添加元素
linkLast（）在队列尾部添加元素

    // 往头部添加元素
    public void addFirst(E e) {
        linkFirst(e);
    }
    // 往尾部添加元素
    public void addLast(E e) {
        linkLast(e);
    }
    private void linkFirst(E e) {
        // 首节点
        final Node<E> f = first;
        // 创建新节点，新节点的next是之前的首节点
        final Node<E> newNode = new Node<>(null, e, f);
        // 让新节点，作为首节点
        first = newNode;
        /**
        * 判断新加入的节点是不是第一个添加的元素
        */
        if (f == null)
            // 如果这是首次往list里面添加节点，那么last也需要置为新的节点
            last = newNode;
        else
            // 如果这不是第一次往list里面添加节点，那么就把原来的首节点的前面一个元素（指针）指向新的节点
            f.prev = newNode;
        // 元素个数+1
        size++;
        // 修改次数+1
        modCount++;
    }
    void linkLast(E e) {
        // 尾节点
        final Node<E> l = last;
        // 创建新的节点，新节点的前面一个元素是之前的尾节点（新节点的pre指针指向前面一个元素（之前的尾节点））
        final Node<E> newNode = new Node<>(l, e, null);
        // 让现在的新插入节点，成为尾节点
        last = newNode;
        // 判断之前的最后一个节点是不是空的
        if (l == null)
            // 如果是空的，那么说明之前没有插入过节点，现在的节点也是第一个节点。
            first = newNode;
        else
            // 如果不是空的，那么说明之前前面的有节点的，需要把之前的尾节点的下一个元素（指针）指向现在新加的节点。
            l.next = newNode;
        // 个数增加
        size++;
        // 修改次数增加
        modCount++;
    }

调用add()方法，默认是在尾部添加元素。

    public boolean add(E e) {
        linkLast(e);
        return true;
    }

当然，除了可以在收尾添加元素之外，还可以在中间指定位置添加元素，通过下面这个方法实现。

    public void add(int index, E element) {
        // 检查index是否在合法的范围
        checkPositionIndex(index);
        // 如果index等于大小size，那么应该直接在尾部添加元素即可
        if (index == size)
            linkLast(element);
        else
            // 否则需要调用linkBefore在前面插入
            linkBefore(element, node(index));
    }

上面有一个函数是node(index)，这个函数是根据index索引获取节点,比较有意思的一点，是当这个索引在前面一半的时候，从前面开始遍历，当这个索引在后面半部分的时候，从后面往前面遍历。判断在哪一部分，使用的是二进制。

    Node<E> node(int index) {
        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;
        }
    }

在某个下标之前插入元素的函数，首先需要判断索引index的位置是否合法，如果index正好等于大小size的话，那就直接在最后面插入该元素即可，否则，需要调用函数，在某个元素之前插入。

    public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }

在尾部插入节点linkLast():

    void linkLast(E e) {
        // 保存最后一个元素
        final Node<E> l = last;
        // 新建一个节点，上一个元素是之前的最后一个元素
        final Node<E> newNode = new Node<>(l, e, null);
        // 将新节点作为最后一个节点
        last = newNode;
        // 如果最后一个节点为空
        if (l == null)
            // 说明原来的list是空的，那么第一个元素也就是现在插入的元素
            first = newNode;
        else
            // 否则原来的元素的下一个元素指定为新的元素
            l.next = newNode;
        // 大小改变
        size++;
        // 修改次数改变
        modCount++;
    }

在某个节点的前面插入，调用linkBefore

    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        // 获取当前节点的前面一个节点
        final Node<E> pred = succ.prev;
        // 创建一个新节点，e它的前面一个节点指针指向前面一个节点pred，后面一个节点指向succ
        final Node<E> newNode = new Node<>(pred, e, succ);
        // succ的前面一个节点指针指向newnode
        succ.prev = newNode;
        如果pred为空
        if (pred == null)
            // 说明之前的链表就是空的，刚刚插入的节点就是第一个节点
            first = newNode;
        else
            // 否则需要将前面节点的下一个节点指针指向新节点
            pred.next = newNode;
        // 大小增加1
        size++;
        // 修改次数增加
        modCount++;
    }

查询元素

主要是get(int index)这个函数：

    public E get(int index) {
        // 检查下标是否合法
        checkElementIndex(index);
        // 直接调用上面说过的node(index)方法，获取到节点之后，再返回其item
        return node(index).item;
    }

修改元素

修改元素，主要调用的是set(index,element)方法,主要是先查找到该节点，然后将其item属性修改。

    public E set(int index, E element) {
        // 校验index的合法性
        checkElementIndex(index);
        // 查找节点
        Node<E> x = node(index);
        // 保存原来的节点
        E oldVal = x.item;
        // 修改item为新的元素
        x.item = element;
        // 返回旧的元素
        return oldVal;
    }

删除元素

removeFirst()：移除第一个元素
removeLast()：移除最后一个元素
remove(Object object):移除object
pop():移除首个元素
remove()：移除首个元素
remove(int index):移除索引为index的元素
clear()：移除所有的元素

删除第一个元素

    public E removeFirst() {
        // 取出第一个元素
        final Node<E> f = first;
        // 如果为空，则不合法
        if (f == null)
            throw new NoSuchElementException();
        // 真正的从链表中剔除第一个元素
        return unlinkFirst(f);
    }

    private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        // 保存当前元素的item
        final E element = f.item;
        // 取出下一个节点next
        final Node<E> next = f.next;
        将第一个元素的item置为null，方便垃圾回收
        f.item = null;
        // next指针也置为null
        f.next = null; // help GC
        // 将first置为下一个元素
        first = next;
        // 如果下一个节点是null，那么说明删掉第一个元素之后，链表是空的
        if (next == null)
            last = null;
        else
            // 否则next的前节点需要只为空
            next.prev = null;
        // 大小减小
        size--;
        // 修改次数增加
        modCount++;
        return element;
    }

移除最后一个元素：

    public E removeLast() {
        // 取出最后一个节点
        final Node<E> l = last;
        // 如果最后一个节点是null，则不合法
        if (l == null)
            throw new NoSuchElementException();
        // 真正从链表中移除最后一个元素
        return unlinkLast(l);
    }

    private E unlinkLast(Node<E> l) {
        // assert l == last && l != null;
        // 保存item
        final E element = l.item;
        // 取出前面一个节点
        final Node<E> prev = l.prev;
        // 将当前节点的item置空
        l.item = null;
        // 前置节点置空
        l.prev = null; // help GC
        // 将最后一个节点置为刚刚保存的前置节点
        last = prev;
        // 如果前面一个节点是空的，那么证明之前的链表只有一个元素，删掉之后，链表已经是空的了。
        if (prev == null)
            first = null;
        else
            // 否则需要将next只为null
            prev.next = null;
        // 大小减小
        size--;
        // 修改次数增多
        modCount++;
        return element;
    }

移除指定的对象，这里指的是节点里面的item，从源码中可以看出，只会移除第一个满足条件的元素，成功移除则返回true，否则将返回false。

    public boolean remove(Object o) {
        // 如果是o为null
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                // 判断item是不是null
                if (x.item == null) {
                    // 满足条件则移除x节点
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                // 这里使用equal方法判断是否相等
                if (o.equals(x.item)) {
                    // 满足条件则移除x
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

默认移除第一个元素，由于LinkedList是双向链表，所以，pop()和reomve()都是默认删除第一个元素。

    public E pop() {
        return removeFirst();
    }
    public E remove() {
        return removeFirst();
    }

移除索引下标为index的元素，思路是先查找到该节点，然后调用unlink(node)移除节点即可。

    public E remove(int index) {
        // 检查合法性
        checkElementIndex(index);
        return unlink(node(index));
    }

移除所有的节点：

    public void clear() {
        // 循环将元素置空
        for (Node<E> x = first; x != null; ) {
            Node<E> next = x.next;
            x.item = null;
            x.next = null;
            x.prev = null;
            x = next;
        }
        // 第一个元素和最后一个元素置空
        first = last = null;
        // 大小置0
        size = 0;
        // 修改次数增加
        modCount++;
    }

3.2.4 小结一下

LinkedList底层就是双向链表，实现了List和Queue接口，允许包含所有的元素，元素可以为null。LinkedList里面的节点为null怎么保存数据？节点为null确实不能保存数据，但是数据是保存在节点下面的item里面的，所以，item可以为null。

每一个节点都保存了前一个节点的引用和下一个节点的引用，以及当前节点的数据。

由于底层是双向链表以及实现了Queue接口，所以它也可以当成双向队列来使用。

线程不安全，多线程环境下操作很容易出现底层链表错误操作。

3.3 Vector

Vector和ArrayList差不多，区别就是Vector是线程安全的。继承于AbstractList，实现了List, RandomAccess, Cloneable这些接口，可以随机访问，也可以克隆。

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

3.3.1 成员变量

底层是数组，增加元素，数组空间不够的时候，需要扩容。

elementData：真正保存数据的数组
elementCount：实际元素个数
capacityIncrement：容量增加系数

serialVersionUID：序列化id

  // 真正保存数据的数组
  protected Object[] elementData;

  // 元素个数
  protected int elementCount;

  //容量增加系数
  protected int capacityIncrement;
  // 序列化id
  private static final long serialVersionUID = -2767605614048989439L;

3.3.2 构造函数

指定容量和增长系数构造函数

    public Vector(int initialCapacity, int capacityIncrement) {
        super();
        // 非法判断
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        // 初始化数组
        this.elementData = new Object[initialCapacity];
        // 指定增长系数
        this.capacityIncrement = capacityIncrement;
    }

指定初始化容量，增长系数默认为0

    public Vector(int initialCapacity) {
        this(initialCapacity, 0);
    }

什么都不指定，默认给的容量是10：

    public Vector() {
        this(10);
    }

指定集合初始化：

    public Vector(Collection<? extends E> c) {
        // 转换成为数组
        Object[] a = c.toArray();
        // 大小为数组的大小
        elementCount = a.length;
        // 如果是ArrayList，则直接复制
        if (c.getClass() == ArrayList.class) {
            elementData = a;
        } else {
            // 否则需要进行拷贝
            elementData = Arrays.copyOf(a, elementCount, Object[].class);
        }
    }

3.3.3 常用方法

增加

增加元素，默认是在最后添加

    public synchronized void addElement(E obj) {
        // 修改次数增加
        modCount++;
        // 确保容量足够（如果需要，里面会有扩容，复制操作）
        ensureCapacityHelper(elementCount + 1);
        // 将新元素放在最后一个元素，个数增加
        elementData[elementCount++] = obj;
    }

那么它是如何确保容量的呢？
可以看到ensureCapacityHelper()里面判断增加后的元素个数是否大于现在数组的长度，如果不满足，就需要扩容。调用grow()函数扩容。

    private void ensureCapacityHelper(int minCapacity) {
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    // 扩容，传入的是需要最小的容量
    private void grow(int minCapacity) {
        // overflow-conscious code
        // 以前的容量
        int oldCapacity = elementData.length;
        // 现在的容量，是以前的容量加上扩展系数，如果扩展系数小于等于0，那么，就是以前的容量的两倍
        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);
    }

在指定的索引index，插入数据，实际上调用的是insertElementAt(element, index).

    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);
        }
        // 确保容量足够
        ensureCapacityHelper(elementCount + 1);
        // 拷贝数据，将后面的元素，往后移动一位
        System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
        // 将实际的数据插入
        elementData[index] = obj;
        // 个数增加
        elementCount++;
    }

将一个集合所有元素添加进去：

    public synchronized boolean addAll(Collection<? extends E> c) {
        // 修改次数增加
        modCount++;
        // 转成数组
        Object[] a = c.toArray();
        // 数组的长度
        int numNew = a.length;
        // 确保容量足够
        ensureCapacityHelper(elementCount + numNew);
        // 拷贝
        System.arraycopy(a, 0, elementData, elementCount, numNew);
        // 更新个数
        elementCount += numNew;
        // 返回添加的数组是不是有数据
        return numNew != 0;
    }

指定index，插入一个集合，和前面不一样的地方在于复制之前，需要计算往后面移动多少位，不是用for循环去插入，而是一次性移动和写入。

    public synchronized boolean addAll(int index, Collection<? extends E> c) {
        // 修改次数增加
        modCount++;
        // 合法判断
        if (index < 0 || index > elementCount)
            throw new ArrayIndexOutOfBoundsException(index);
        // 转换数组
        Object[] a = c.toArray();
        // 插入数组长度
        int numNew = a.length;
        // 确保数组的长度是否合法
        ensureCapacityHelper(elementCount + numNew);
        // 移动的步长计算
        int numMoved = elementCount - index;
        if (numMoved > 0)
            // 移动后面的元素，腾出位置给插入的元素
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);
        // 插入元素
        System.arraycopy(a, 0, elementData, index, numNew);
        // 更新个数
        elementCount += numNew;
        // 插入元素个数是否为0
        return numNew != 0;
    }

删除

删除指定元素

    public boolean remove(Object o) {
        return removeElement(o);
    }

    // 实际调用的是removeElement()
    public synchronized boolean removeElement(Object obj) {
        // 修改次数增加
        modCount++;
        // 获取第一个满足条件的元素缩影
        int i = indexOf(obj);
        // 索引如果满足条件
        if (i >= 0) {
            // 将索引为i的元素从数组中移除
            removeElementAt(i);
            return true;
        }
        return false;
    }
    // 操作数组删除元素
    public synchronized void removeElementAt(int index) {
        // 修改次数增加
        modCount++;
        // 是否合法
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                     elementCount);
        }
        else if (index < 0) {
            throw new ArrayIndexOutOfBoundsException(index);
        }
        // index后面的元素个数
        int j = elementCount - index - 1;
        if (j > 0) {
            // 往前面移动一位（复制，覆盖）
            System.arraycopy(elementData, index + 1, elementData, index, j);
        }
        // 更新个数
        elementCount--;
        // 原来最后一个元素的位置置空
        elementData[elementCount] = null; /* to let gc do its work */
    }

按照索引删除元素：

    public synchronized E remove(int index) {
        // 修改次数增加
        modCount++;
        // 合法性判断
        if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(index);
        // 保存原来的数据
        E oldValue = elementData(index);
        // 移动的个数
        int numMoved = elementCount - index - 1;
        // 如果移动个数大于0
        if (numMoved > 0)
            // 后面的元素往前面移动一位，赋值，覆盖
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        // 最后一个元素置空
        elementData[--elementCount] = null; // Let gc do its work
        // 返回旧的元素
        return oldValue;
    }

修改

下面两个set函数都是，修改索引为index的元素，区别就是一个会返回旧的元素，一个不会返回旧的元素。

    public synchronized E set(int index, E element) {
        // 合法性判断
        if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(index);
        // 取出旧的元素
        E oldValue = elementData(index);
        // 更新
        elementData[index] = element;
        // 返回旧的元素
        return oldValue;
    }
    public synchronized void setElementAt(E obj, int index) {
        // 合法哦性判断
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                     elementCount);
        }
        // 直接更新
        elementData[index] = obj;
    }

查询

    public synchronized E get(int index) {
        // 合法判断
        if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(index);
        // 返回数组的元素
        return elementData(index);
    }

3.3.4 小结一下

Vector的思路和ArrayList基本是相同的，底层是数组保存元素，Vector 默认的容量是10，有一个增量系数，如果指定，那么每次都会增加一个系数的大小，否则就扩大一倍。

扩容的时候，其实就是数组的复制，其实还是比较耗时间的，所以，我们使用的时候应该尽量避免比较消耗时间的扩容操作。

和ArrayList最大的不同，是它是线程安全的，几乎每一个方法都加上了Synchronize关键字，所以它的效率相对也比较低一点。

3.4 顺便说说AbstractList

AbstractList是一个抽象类，实现了List接口，继承了AbstractCollection类。其内部实现了一些增删改查的操作，

我在想为什么需要AbstractList实现List，再让ArrayList去继承AbstractList。为啥要这样子干，直接继承List不行么？

这里主要是因为要遵循一个原则，接口中只能有抽象的方法，但是抽象类除了抽象方法之外，还可以有具体的实现方法。而List的实现类比较多，比如ArrayList,LinkedList,Vector等等，肯定有共同之处，有通用的方法。
要是它们都直接实现List接口，那么就会产生一些冗余重复的代码。而要是这些共同之处，通用的方法，被抽象出来实现放在AbstractList里面，多简洁，香不香？香！！！

这样一来，就相当于加了一层中间层，计算机设计的原理也是动不动就加一个缓冲层。（手动狗头）

下面我们来大概介绍一下AbstractList:

3.4.1 定义以及成员变量

实现了List接口，继承了AbstractCollection类,AbstractList无参数构造protected修饰。

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
    protected AbstractList() {
    }
}

成员变量:修改次数

    protected transient int modCount = 0;

里面只有一个抽象方法get()

    abstract public E get(int index);

3.4.2 常用方法

增加

定义了一套add方法实现的标准，一个默认在最后添加，一个是在指定索引位置的，但是考虑到不同的子类实现不一样，这个方法必须实现，要不就会抛出异常。

    public boolean add(E e) {
        add(size(), e);
        return true;
    }
    public void add(int index, E element) {
        throw new UnsupportedOperationException();
    }

指定索引的位置，添加集合里面所有的元素

    public boolean addAll(int index, Collection<? extends E> c) {
        // 检查index是否合法
        rangeCheckForAdd(index);
        boolean modified = false;
        // 循环添加
        for (E e : c) {
            add(index++, e);
            modified = true;
        }
        return modified;
    }

修改

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

删除

删除指定索引的元素，不做实现，要求子类自实现

    public E remove(int index) {
        throw new UnsupportedOperationException();
    }

// 删除所有的元素

    public void clear() {
        removeRange(0, size());
    }

删除指定范围的元素

    protected void removeRange(int fromIndex, int toIndex) {
        // 获取迭代器到开始删除的位置
        ListIterator<E> it = listIterator(fromIndex);
        // 循环删除
        for (int i=0, n=toIndex-fromIndex; i<n; i++) {
            it.next();
            it.remove();
        }
    }

查询

抽象方法，不做实现。

    abstract public E get(int index);

查询索引位置

    // 查询object的索引的位置
    public int indexOf(Object o) {
        // 获取迭代器
        ListIterator<E> it = listIterator();
        if (o==null) {
            // 如果对象为空
            while (it.hasNext())
                // 不能使用null，这里由于cursor+1，需要取前面一个索引值
                if (it.next()==null)
                    return it.previousIndex();
        } else {
            while (it.hasNext())
                // 使用equal判断
                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())
                if (it.previous()==null)
                    return it.nextIndex();
        } else {
            while (it.hasPrevious())
                if (o.equals(it.previous()))
                    return it.nextIndex();
        }
        return -1;
    }

截取list

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

3.4.3 迭代器

我们其实可以看到AbstractList里面定义了两个迭代器，分别是Itr和ListItr,Itr实现了Iterator接口，ListItr实现了ListIterator，继承了Itr.

细心点我们就会发现，这里面有几个方法都是操作Iterator相关的。

    public Iterator<E> iterator() {
        return new Itr();
    }
    public ListIterator<E> listIterator() {
        return listIterator(0);
    }
    // 返回指定索引处的迭代器
    public ListIterator<E> listIterator(final int index) {
        rangeCheckForAdd(index);

        return new ListItr(index);
    }

为什么需要两个迭代器呢？这个问题一直在我的脑海里，挥之不去...
暂且来看看源码：

    private class Itr implements Iterator<E> {
        // 下一次调用next将返回的索引
        int cursor = 0;
        // 上一次调用next或者previous返回的索引
        int lastRet = -1;
        // 期待被修改的次数
        int expectedModCount = modCount;

        // 只要curse（游标）不等于size大小，就表示还有元素
        public boolean hasNext() {
            return cursor != size();
        }

        // 获取下一个元素
        public E next() {
            // 检查是否被修改
            checkForComodification();
            try {
                // 保存游标
                int i = cursor;
                // 获取元素
                E next = get(i);
                // 将最后一次返回的索引修改成最新的i
                lastRet = i;
                // 将下次即将返回的游标索引更新
                cursor = i + 1;
                // 返回元素
                return next;
            } catch (IndexOutOfBoundsException e) {
                checkForComodification();
                throw new NoSuchElementException();
            }
        }

        // 删除操作
        public void remove() {
            // 上一次返回的
            if (lastRet < 0)
                throw new IllegalStateException();
            // 检查修改次数
            checkForComodification();

            try {
                // 调用外部的方法remove
                AbstractList.this.remove(lastRet);
                // 元素被删除了，游标需要倒走一步
                if (lastRet < cursor)
                    cursor--;
                //删除后，lastRet上一次访问的元素不存在了，需要只为-1
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException e) {
                throw new ConcurrentModificationException();
            }
        }
        // 判断操作后的修改次数，是否等于期待修改次数
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

下面这段代码让我好疑惑，为什么需要判断上一次访问的index是不是小于下一次执行next返回的index才执行-1的操作

if (lastRet < cursor)
    cursor--;

后来我在ListItr的代码中找到了答案，因为ListItr有一个方法是previous()，会倒回迭代器的上一个元素，如果执行了previous()，那么上一次返回的元素，和下一次执行next返回的元素就是同一个，所以这个时候是可能出现lastRet= cursor的。

看看ListItr源码：

    private class ListItr extends Itr implements ListIterator<E> {
        ListItr(int index) {
            cursor = index;
        }
        // 是否前面有元素
        public boolean hasPrevious() {
            return cursor != 0;
        }

        public E previous() {
            // 检查修改次数
            checkForComodification();
            try {
                // 获取前面的元素index
                int i = cursor - 1;
                // 获取前面的元素
                E previous = get(i);
                // 上一次访问的元素index和下一次调用next的index，都需要赋值为i（相当于cursor-1）
                lastRet = cursor = i;
                // 返回前面一个元素
                return previous;
            } catch (IndexOutOfBoundsException e) {
                checkForComodification();
                throw new NoSuchElementException();
            }
        }
        // 下一个索引
        public int nextIndex() {
            return cursor;
        }
        //上一个索引
        public int previousIndex() {
            return cursor-1;
        }
        // 修改上一次访问的元素
        public void set(E e) {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                // 调用外部方法
                AbstractList.this.set(lastRet, e);
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        // 新增元素
        public void add(E e) {
            checkForComodification();

            try {
                int i = cursor;
                // 在迭代器的当前位置添加元素
                AbstractList.this.add(i, e);
                // 不关心lastRet
                lastRet = -1;
                // 下一个元素的索引需要+1
                cursor = i + 1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
    }

为什么需要两个迭代器呢？
我们发现Itr其实只有next()和remove()两个方法，这是适用于普通的大部分的子类的，而ListItr则多了一个回溯上一个元素的hasPrevious以及set()和add()方法，属于升级版本。
Itr属于公共的迭代器，继承它的有ListIterator和PrimitiveIterator。
两个迭代器之间的区别：

使用iterator只能向前移动，但是使用ListIterator可以在读取元素时也移动后退字词。
使用ListIterator，您可以在遍历时随时获取索引，而迭代器则无法实现。
使用iterator，您只能检查下一个元素是否可用，但是在listiterator中，您可以检查上一个和下一个元素。
使用listiterator，您可以在遍历的任何时间添加新元素。使用迭代器是不可能的。
使用listiterator，您可以在遍历时修改元素，而迭代器则不能。

查了一下Stack Overflow，答案链接：https://stackoverflow.com/questions/19799047/what-is-the-need-to-have-listiterator-and-iterator-in-the-list-interface-in

这个有可能是答案：

Since Java 5 it is simply possible to override a method with a more specific return type (called covariant return type). But ListIterator has been introduced with Java 1.2. To avoid casts on usage of iterator() there has to be a new method.

The API could not have been changed from Java 5 on because that would have broken all implementations of List which do not declare iterator() returning ListIterator also if most implementations return a ListIterator instance in real.

A similar dilemma is Enumeration and Iterator. Nowadays Iterator would extend Enumeration and simply add the remove() method. Or better Iterator would have replaced Enumeration and a ModifiableIterator with an additional remove() would have been added.

中文就是：
因为Java 5可以用更特定的返回类型(称为协变返回类型)重写方法。但是ListIterator是在Java 1.2中引入的。为了避免对iterator()的使用进行强制类型转换，必须有一个新方法。

API不可能从Java 5开始改变，因为这将破坏所有没有声明iterator()返回ListIterator的List实现，如果大多数实现在实际中返回ListIterator实例。

类似的困境是枚举和迭代器。现在迭代器将扩展枚举并简单地添加remove()方法。或者更好的迭代器会替换枚举，并且会添加一个额外的remove()来添加一个ModifiableIterator。

个人观点：这是迭代版本的过程中，基于兼容性和可拓展性来做的。也有人说是基于单向链表和双向链表来考虑的，貌似也有一点道理。

3.4.4 小结一下

AbstractList是实现List接口的抽象类，AbstractList抽象类与List接口的关系有点像AbstractCollection抽象类与Collection接口的关系。
拥有一部分抽象方法和一部分实现的方法，属于List和具体容器实现类比如ArrayList中间的一层。

4.总结

List接口,主要是实现了列表的接口标准，常用的三个子类是：

ArrayList
- 底层是数组，扩容就是申请新的数组空间，复制
- 线程不安全
- 默认初始化容量是10，扩容是变成之前的1.5倍
- 查询比较快
LinkedList
- 底层是双向链表，可以往前或者往后遍历
- 没有扩容的说法，可以当成双向队列使用
- 增删比较快
- 查找做了优化，index如果在前面一半，从前面开始遍历，index在后面一半，从后往前遍历。
Vector
- 底层是数组，几乎所有方法都加了Synchronize
- 线程安全
- 有个扩容增长系数，如果不设置，默认是增加原来长度的一倍，设置则增长的大小为增长系数的大小。

AbstractList，是List拓展出来的抽象类，定义了一部分通用的方法，弥补了List是接口，不能对方法有所实现的不足，相当于加了一个中间层。里面定义了两个迭代器Iterator类，也提供了获取它们的方法，可以供不同的子类使用。

此文章仅代表自己（本菜鸟）学习积累记录，或者学习笔记，如有侵权，请联系作者删除。人无完人，文章也一样，文笔稚嫩，在下不才，勿喷，如果有错误之处，还望指出，感激不尽~

技术之路不在一时，山高水长，纵使缓慢，驰而不息。

公众号：秦怀杂货店

Java集合【7】-- List接口源码超详细分析

1.List接口的特性

2.List接口的源码解析

3.相关子类介绍

3.1 ArrayList

3.1.1 成员变量

3.1.2 构造方法

3.1.3 常用增删改查方法

添加元素

查询元素

更新元素

删除元素

3.1.4 小结一下

3.2 LinkedList

3.2.1 成员变量

3.2.2 构造函数

3.2.3 常用函数

添加元素

查询元素

修改元素

删除元素

3.2.4 小结一下

3.3 Vector

3.3.1 成员变量

3.3.2 构造函数

3.3.3 常用方法

增加

删除

修改

查询

3.3.4 小结一下

3.4 顺便说说AbstractList

3.4.1 定义以及成员变量

3.4.2 常用方法

增加

修改

删除

查询

查询索引位置

截取list

3.4.3 迭代器

3.4.4 小结一下

4.总结