一、List常用的实现

List的常见的容器有 ArrayList、LinkedList、Vector、Stack，下面对
每个实现类的特点和实现进行分析。

二、AarrayList

1） 概述

是底层用数组来实现的存储容器，线程是不安全的。

2） 特点

a. 底层实现是通过数组
b. 查询效率高、增删效率低
c. 线程是不安全的
d. 元素是有序的，可以包含重复元素

3） 问答

Q: 大家肯定会有这么一个疑问，既然是数组实现的话，那么数组长度是固定的，Arralist是怎么实现动态扩容的？
A: 通过观察源码分析是其实是通过数组的拷贝来实现的，ArrayList 内部会维护一个 Object[] 对象，并默认初始值为10，当超过这个值的时候，会通过拷贝旧的数组，来实现动态扩容。下面是具体实现的源码。

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // >> 1 右移操作 相当于 n/2 新数组的长度 为 旧数组的长度 + 旧数组长度/2
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 拷贝旧的数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}

三、LinkedList

1） 概述

是底层用双向链表实现的存储容器，线程是不安全的，实现了Deque 和 List接口。

2） 特点

a.底层实现是双向链表，这代表增删效率高。
b.实现了 Deque 接口, 提供了对两端元素操作的方法，意味着可以当做 FIFO (先进先出) 队列 、LIFO（后进先出）栈使用。
c.线程是不安全的。
d.元素是有序的，可以包含重复元素

3）问答

Q: 都说是双向链表结构，那么到底他内部是怎么维护这个结构的呢？
A: Linked内部创建了一个维护 Node 元素，这个元素 记录了当前元素的上一个元素和下一个元素。

private static class Node<E> {
	// 当前元素
    E item;
    // 上一个元素
    Node<E> next;
    // 下一个元素
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E>     next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

LinkedList 在内部维护了 first 首元素 和 last 尾元素，所以可以在内部方法中获得 首元素和尾元素。

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

在 调用add 方法的时候，尾元素添加为当前元素的的上一个元素 ，并设置上一个元素的下一元素为当前元素

void linkLast(E e) {
    final Node<E> l = last;
    // 创建当前元素，设置尾元素 为当前元素的上一元素
    final Node<E> newNode = new Node<>(l, e, null);
    // 将当前元素设置为尾元素
    last = newNode;
    if (l == null)
        first = newNode;
    else 
        l.next = newNode;
    size++;
    modCount++;
}

四、Vector

1）概述

底层是数组结构，但是线程相对安全的容器。

2）特点

a. 底层是通过数组实现
b. 线程是相对安全的
c. 是有有序的,可以重复
d.实现了RandmoAccess接口，即提供了随机访问功能

3）问答

(1) Q：vector是怎么保证线程安全的呢
A：vector 在add 、remove上都加了 synchronzied 关键字来保证线程安全。但是这个安全是相对安全，下面这个例子有会体现vector线程不安全的的情况

public static void main(String[] args) {
    Vector vector = new Vector();
    for (int i = 0; i < 2; i++) {
        new Thread(()->{
            int count=0;
            while(count<10){
                vector.add(count);
                System.out.println("当前线程："+Thread.currentThread().getName()+"，vector大小："+vector.size());
                count++;
            }
        }).start();
    }
}

打印结果，会出现大小的相同的情况，这是为什么呢，因为size和add方法是线程安全的，但是当两者结合会出现线程不安全的情况，比如 A、B线程 同时调用add ,然后size方法，可能出现 A add 完成后，B获得锁 ，执行 add 和size 方法，再 A线程 执行 size 方法 ，这时候就会导致线程不安全。

当前线程：Thread-1，vector大小：2
当前线程：Thread-0，vector大小：2

五、Stack

1） 概述

继承Vector，代表底层是数组的容器，但是他具有先进后出（FILO） 的特性

2）特点

a. 底层是数组
b. 具有先进后出（FILO）的特点，与栈相似。
c. 线程是相对安全的。

3）常用 API

             boolean       empty() // 判断栈是否为空
synchronized E             peek() // 返回栈顶元素，不执行删除操作
synchronized E             pop() //返回栈顶元素，并将其从栈中删除
             E             push(E object) // 将元素存入栈顶
synchronized int           search(Object o) // 查找“元素o”在栈中的位置：由栈底向栈顶方向数

4) 源码分析

（1）push 方法与 ArrayList和 Vector 相似，都是通过grow 实现动态扩容。

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    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);
}

（2）pop 方法，是调用peek方法 返回当前数组下标最后的元素，然后将数组最后一位 置空。

public synchronized void removeElementAt(int index) {
    modCount++;
    if (index >= elementCount) {
        throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                 elementCount);
    }
    else if (index < 0) {
        throw new ArrayIndexOutOfBoundsException(index);
    }
    // elementCount 是当前数组大小
    int j = elementCount - index - 1;
    // 如果当前移除对象索引不是最后一位,则进行数组拷贝,当指定移除元素时会进入判断
    if (j > 0) {
        // 从指定元素位置开始拷贝后面元素 比如 1 2 3 4 5 指定元素为3 则替换成 1 2 4 5 5
        System.arraycopy(elementData, index + 1, elementData, index, j);
    }
    elementCount--;
    // 将数组最后一位 置空
    elementData[elementCount] = null; 
}

六、总结

最后总结下List各个实现类的特点
（1）保证线程相对安全的：Vector、Stack
（2）底层实现是数组的：ArrayList 、Vector、Stack，底层实现是双向链表的：LinkedList
（3）查询速度快：ArrayList、Vector、Stack ，增删速度快 LinkedList
（4）Vector可以当作 队列和栈使用，Stack可以当作栈使用