Java List笔记

List

List是一个接口，继承于Collenction接口，它代表着有序的队列。

ps：java.util.Collection是一个集合接口，它提供了对集合对象进行基本操作的通用接口方法；javautil.Collections是一个包装类，它包含各种有关集合操作的静态多态方法，该类不能实例化，服务于Collection框架。

ArrayList：底层是用数组实现。

LinkedList：底层是通过双向链表实现。

Vector：通过数组实现，线程安全。

ArrayList扩容

默认初始容量为10.

/**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;
    
    transient Object[] elementData; // non-private to simplify nested class access

    private int size;

扩容，默认为1.5倍方式

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

ArrayList和LinkedList

ArrayList是实现了基于动态数组的数据结构，LinkedList是基于链表结构。

对于随机访问的get和set方法，ArrayList要优于LinkedList，因为LinkedList要移动指针。

对于新增和删除操作add和remove，LinkedList比较占优势，因为ArrayList要移动数据。

对ArrayList和LinkedList而言，在列表末尾增加一个元素所花的开销都是固定的。对 ArrayList而言，主要是在内部数组中增加一项，指向所添加的元素，偶尔可能会导致对数组重新进行分配；而对LinkedList而言，这个开销是统一的，分配一个内部Entry对象。

在ArrayList集合中添加或者删除一个元素时，当前的列表所所有的元素都会被移动。而LinkedList集合中添加或者删除一个元素的开销是固定的。

LinkedList集合不支持高效的随机随机访问（RandomAccess），因为可能产生二次项的行为。

ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间。

Arrays.asList()方法

int[] a = {1,2,3,4};
        List a_list = Arrays.asList(a);
        System.out.println(a_list.size());//size=1
        Integer[] b = {1,2,3,4};
        List b_list = Arrays.asList(b);
        System.out.println(b_list.size());//size=4

Arrays.asList方法返回的是List，通过Arrays类的一个内部类实现，内部用的数组就是传入的数组，没有拷贝，也不会动态改变大小，所以对数组的修改也会反应到List中，对List调用add/remove方法会抛出异常。

使用ArrayList方法实现为：

1	List<Integer> list = new ArrayList<Integer>(Arrays.asList(a));

ArrayList线程不安全

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

因为ArrayList本身不是线程安全的，通过Collections.synchronizedList可以将其包装成一个线程安全的List。

Vector和ArrayList

vector是线程（Thread）同步（Synchronized）的，所以它也是线程安全的，而Arraylist是线程异步（ASynchronized）的，是不安全的。如果不考虑到线程的安全因素，一般用Arraylist效率比较高。

如果集合中的元素的数目大于目前集合数组的长度时，vector增长率为目前数组长度的100%,而arraylist增长率为目前数组长度的50%.如过在集合中使用数据量比较大的数据，用vector有一定的优势。