关于LinkedList、ArrayList以及Vector的理解_arraylist,linklist和vector

java中的List接口中有三个实现类：ArrayList、Vector和LinkedList。前两个是使用数组实现，用索引来取数据是它的优势。后者是用双向链表实现，在插入和删除操作上占优势。

底层实现

LinkedList 底层实现是双向链表，无大小限制。 链表支持顺序访问， 查询速度慢， 增删元素快
ArrayList 底层实现就是数组，默认大小10，容量不足时需动态扩容为原来的1.5倍。 数组支持随机访问， 查询速度快， 增删元素慢；
Vector的底层实现也是采用一个动态对象数组，只不过它的默认构造方法创建一个大小为10的对象数组

线程安全

ArrayList：线程不安全的，它的方法之间是线程不同步的，因为它不考虑线程安全，效率会高些
LinkedList：不是线程安全的，LinkedList提供了一些方法，使得LinkedList可以被当作堆栈和队列来使用
Vector则是线程安全的（它的方法之间是线程同步的synchronized）。

为何说ArrayList和LinkedList不是线程安全的？
比如一个 ArrayList 类，假设在添加一个元素的时候，它可能会有两步来完成：
1、在 Items[Size] 的位置存放此元素；
2、增大 Size 的值。
单线程情况下，向一个空的 ArrayList添加一个元素后，元素被放在了0的位置，然后执行第二部将size的值由0变为1。
多线程情况下，假如有两个线程，线程 A 先将元素存放在位置 0，还没有完成第二步将size变为1。结果此时 CPU 调度线程A暂停，线程 B 得到运行的机会。线程B也向此 ArrayList 添加元素，因为此时 Size 仍然等于 0， 所以线程B也将元素放到了位置0。之后线程A和线程B继续运行，都增加了size的值。此时ArrayList实际上只有一个元素，但size却为2，所以是线程不安全的。

至于Vector线程安全则是因为Vector的很多方法都有同步关键字synchronized,从而保证所有的对外接口都会以 Vector对象为锁，即，在Vector内部，所有的方法都不会被多线程访问。
注意：单个方法的原子性（程序的原子性即不会被线程调度机制打断），并不能保证复合操作也具有原子性。说其线程安全只是单个方法线程安全。但是对于复合操作而言，只是同步方法并没有解决线程安全的问题。还需要以vector对象为锁，来达到绝对线程安全。

实现的主要接口

java.util.List接口：支持泛型，ArrayList和LinkList都能够用来存放各种数据类型的对象
Cloneable接口：能够支持克隆
java.io.Serializable接口：能够支持序列化

RandomAccess接口:ArrayList,Vector实现了，表示它们能快速随机访问存储的元素，通过下标 index 访问，只是我们需要用 get() 方法的形式。LinkedList则没有实现

扩容机制

LinkedList
由于LinkedList 是一个双向链表，没有初始化大小，所以没有扩容的机制，就是一直在头或者尾新增就好。

ArrayList
有两个属性，存储数据的数组ElementData，和存储记录数目的size。
ArrayList的默认容量为10，扩容的规则是新增的时候发现容量不够用了，就去扩容，
扩容后的大小= 原始大小*1.5。以下是ArrayList的底层源码。

/**
*Default initial capacity.	默认初始容量
*/
private static final int DEFAULT_CAPACITY = 10;

/**
* Shared empty array instance used for empty instances.	用于空实例的共享空数组实例。
*/
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

判断当前数组是否是默认构造方法生成的空数组，是的话minCapacity为10，不是的话minCapacity的值传入下一个方法判断是否需要扩容，

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) {//此时的minCapacity是修改后的值
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
 }

//判断当前ArrayList是否需要进行扩容
private void ensureExplicitCapacity(int minCapacity) {
        modCount++;	//快速报错机制
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
}            
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

ArrayList扩容的核心方法grow()

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
}
1
2
3
4
5
6
7
8
9
10

Vector
Vector有三个属性，存储数据的数组ElementData，存储记录数目的elementCount，还有扩展数组大小的扩展因子capacityIncrement。以下是Vector扩容的底层源码

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);
}
1
2
3
4
5
6
7
8
9
10

LinkedList

双向链表
构造方法

ArrayList

构造方法

Vector

构造方法