ArrayList

ArrayList是一个数组队列，相当于动态数组，使用连续的内存空间。ArrayList线程不安全。

ArrayList构造方法

默认构造函数，使用此函数构造默认大小是10.

ArrayList()

指定容量的构造函数，capacity是ArrayList的初始容量大小。当由于增加数据导致容量不足时，容量会增加上一次容量大小的一半，也就是扩容至原来大小的1.5倍。

ArrayList(int capacity)

创建一个包含collection的ArrayList。

ArrayList(Collection<? extends E> collection)

ArrayList属性

elementData

elementData是一个Object数组，保存了添加到ArrayList中的元素。实际上，elementData是个动态数组，同上文介绍ArrayList构造函数中对应的，我们通过不含参数的构造函数ArrayList()来创建ArrayList，则elementData的容量默认是10；通过构造函数 ArrayList(int initialCapacity)来构造ArrayList，则此数组的初始容量为initialCapacity。elementData数组的大小会根据ArrayList容量的增长而动态的增长。

size

记录了动态数组的实际大小。

ArrayList序列化方式

ArrayList实现Serializable接口，所以可被序列化。当序列化时，写入到输出流先写入“容量”，再依次写入每一个元素；当反序列化时，读到输入流先读取“容量”，再依次读每一个元素。

ArrayList遍历方式

迭代器遍历

获得ArrayList的迭代器对象遍历数组。

Integer value = null;
Iterator iter = list.iterator();
while (iter.hasNext()) {
    value = (Integer)iter.next();
}

随机访问遍历

通过索引的下标值快速随机访问以遍历ArrayList

Integer value = null;
int size = list.size();
for (int i=0; i<size; i++) {
    value = (Integer)list.get(i);        
}

*什么是随机访问？
随机访问对应于顺序访问：

顺序访问意味着只能从第一个元素开始依次逐个读取下一个元素。如链表只能支持顺序访问：要读取链表的第十个元素，得先读取前九个元素，并沿链接找到第十个元素。
随机访问意味着可直接跳到第十个元素。经常说数组的读取速度更快，这是因为它们支持随机访问。

for循环遍历

Integer value = null;
for (Integer integ:list) {
    value = integ;
}

遍历效率比较

随机访问遍历方法效率最高，迭代器效率最低。

ArrayList插入时间复杂度

插入末尾时间复杂度O(1)，插入第i个位置时间复杂度O(n-i)

Vector

向量队列，也是可动态扩展的数组，使用连续存储空间。线程安全。

Vector构造方法

Vector共有4个构造函数
默认构造函数，使用此方法构造默认初始容量为10.

Vector()

capacity指定初始容量大小。当由于增加数据导致容量增加时，每次容量会增加一倍。

Vector(int capacity)

capacity指定Vector初始容量大小，capacityIncrement指定每次Vector扩容时的增量的容量。

Vector(int capacity, int capacityIncrement)

创建一个包含collection的Vector

Vector(Collection<? extends E> collection)

Vector属性

Vector的属性和ArrayList唯一的不同是Vector多了一项capacityIncrement，即在构造函数中指定的自定义的扩容值。如果不指定此属性，那么默认扩容至原来容量的两倍。

Vector遍历方式

同样可以采用迭代器、随机快速访问、for循环的方式遍历。因为Vector与ArrayList类似，同样支持随机访问，所以采用随机访问遍历方式最高效。

LinkedList

LinkedList是用链表实现的集合类。1.7为双向链表，1.6为双向循环链表，取消循环更能分清头尾。

LinkedList属性

LinkedList是通过双向链表实现的，而双向链表的节点就是通过Node类来体现的，类中通过item变量保存了当前节点的值，通过next变量指向下一个节点，通过prev变量指向上一个节点。

size：集合的长度
first：双向链表头部节点
last：双向链表尾部节点

LinkedList随机访问

链表严格来说是不支持随机访问的。如果要通过索引值来获得元素，无疑要通过顺序访问实现，所以效率很低。下面从LinkedList提供的“随机访问”方法get具体深入一下背后的原因：

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

/**
 * 返回一个指定索引的非空节点.
 */
Node<E> node(int index) {
    // assert isElementIndex(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与集合长度size/2，如果是index小，那么从第一个顺序循环，直到找到为止；如果index大，那么从最后一个倒序循环，直到找到为止。也就是说越靠近中间的元素，调用get(int index方法遍历的次数越多，效率也就越低，而且随着集合的越来越大，get(int index)执行性能也会快速降低。因此在使用LinkedList的时候，通过下标访问的效率很低。但可以使用getFirst()，getLast()方法，可以在O(1)复杂度直接获取到first和last变量。

LinkedList插入效率

由于LinkedList是基于链表实现的，所以插入效率相对较高，因为它省去了ArrayList插入数据可能的数组扩容和数据元素移动时所造成的开销。删除也类似。

LinkedList遍历方式

同上两种集合方式，LinkedList可通过下标、迭代器、for循环迭代遍历。因为它底层为链表的数据结构，所以通过下标方式遍历效率最低（O(n2))，用迭代器和for迭代遍历方式效率类似，复杂度只为（O(n)）。实际上for迭代遍历的方式底层也是用迭代器进行遍历的。

参考

https://www.cnblogs.com/msymm/p/9872818.html
https://blog.csdn.net/h18208975507/article/details/85758100
https://www.cnblogs.com/msymm/p/9873551.html
https://www.cnblogs.com/LiaHon/p/11107245.html

JAVA三种List（ArrayList、Vector、LinkedList）详解与对比