ArrayList, LinkedList, Vector, Stack是List的4个实现类。
ArrayList 是一个数组队列，相当于动态数组。它由数组实现，随机访问效率高，随机插入、随机删除效率低。
LinkedList 是一个双向链表。它也可以被当作堆栈、队列或双端队列进行操作。LinkedList随机访问效率低，但随机插入、随机删除效率低。
Vector 是矢量队列，和ArrayList一样，它也是一个动态数组，由数组实现。但是ArrayList是非线程安全的，而Vector是线程安全的。
Stack 是栈，它继承于Vector。它的特性是：先进后出(FILO, First In Last Out)。
(1) 对于需要快速插入，删除元素，应该使用LinkedList。
(2) 对于需要快速随机访问元素，应该使用ArrayList。
(3) 对于“单线程环境” 或者 “多线程环境，但List仅仅只会被单个线程操作”，此时应该使用非同步的类(如ArrayList)。
对于“多线程环境，且List可能同时被多个线程操作”，此时，应该使用同步的类(如Vector)。
LinkedList和ArrayList性能差异分析（基于jdk1.8）
1.随机插入
LinkedList在指定位置插入元素：
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
//查找指定的node
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;
}
}
从上面可以看出，通过add(int,E)向LinkedList中插入元素时，先是在双向链表中找到要插入节点的位置index；找到之后，再插入一个新节点。双向链表查找index位置的节点时，有一个加速动作：若index < 双向链表长度的1/2，则从前向后查找; 否则，从后向前查。
ArrayList向指定位置插入元素：
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
可以看到有个操作
System.arraycopy(elementData, index, elementData, index + 1,
size - index)
这意味着，每插入一个元素，这个元素之后的所有元素index都会改变。之所以插入元素慢，原因就在这里
2.随机访问
LinkedList访问指定位置元素
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
//查找指定的node
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;
}
}
可以看出，在LinkedList中获取指定元素时，需要先在双向链表中找到index位置的元素，然后才能访问
而ArrayList访问指定元素：
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
可以看出，在ArrayList中获取指定元素时，直接返回数组中index位置的元素，而不需要像LinkedList一样进行查找，因此速度更快
3.性能测试对比
在头部插入节点，元素数量分别为10000,10 * 10000,100 * 10000, 1000 * 10000, 10000 * 10000，测试代码如下：
public static void main(String[] args) {
int[] nums = {10000,10 * 10000,100 * 10000, 1000 * 10000, 10000 * 10000};
for(int i=0; i<nums.length; i++){
testList(nums[i]);
}
}
public static void testList(int num){
List<String> aList = new ArrayList<String>();
List<String> lList = new LinkedList<String>();
long starttime, endtime;
starttime= System.currentTimeMillis();
for(int i=0; i<num; i++){
aList.add(0, "1");
}
endtime = System.currentTimeMillis();
System.out.println("num : " + num + "ArrayList cost : " + (endtime - starttime) + "ms");
starttime= System.currentTimeMillis();
for(int i=0; i<num; i++){
lList.add(0,"1");
}
endtime = System.currentTimeMillis();
System.out.println("num : " + num + "LinkedList cost : " + (endtime - starttime) + "ms");
}
}
结果：
num : 100ArrayList cost : 2ms
num : 100LinkedList cost : 0ms
num : 1000ArrayList cost : 2ms
num : 1000LinkedList cost : 4ms
num : 5000ArrayList cost : 5ms
num : 5000LinkedList cost : 24ms
num : 10000ArrayList cost : 6ms
num : 10000LinkedList cost : 76ms
num : 100000ArrayList cost : 535ms
num : 100000LinkedList cost : 33265ms
num : 1000000ArrayList cost : 84961ms
由于机子性能一般，卡到100W还在一直跑...
分析：即使在头部插入节点，LinkedList效率也不如ArrayList，而且性能差很多，和网上资料并不相符。希望有大神可以解释一下
随机插入：
public static void main(String[] args) {
int[] nums = {10000,10 * 10000,100 * 10000, 1000 * 10000, 10000 * 10000};
for(int i=0; i<nums.length; i++){
testList(nums[i]);
}
}
public static void testList(int num){
List<String> aList = new ArrayList<String>();
List<String> lList = new LinkedList<String>();
long starttime, endtime;
starttime= System.currentTimeMillis();
for(int i=0; i<num; i++){
aList.add((int)(Math.random()*i), "1");
}
endtime = System.currentTimeMillis();
System.out.println("num : " + num + "ArrayList cost : " + (endtime - starttime) + "ms");
starttime= System.currentTimeMillis();
for(int i=0; i<num; i++){
lList.add((int)(Math.random()*i),"1");
}
endtime = System.currentTimeMillis();
System.out.println("num : " + num + "LinkedList cost : " + (endtime - starttime) + "ms");
}
结果：
num : 10000ArrayList cost : 12ms
num : 10000LinkedList cost : 87ms
num : 100000ArrayList cost : 477ms
num : 100000LinkedList cost : 37157ms
由于机子性能一般，卡到100W还在一直跑...
分析：从上面看出，LinkedList随机插入效果还不如ArrayList，感觉不太对啊，是数据量太大了吗？那换小一点试试
num : 100ArrayList cost : 2ms
num : 100LinkedList cost : 0ms
num : 1000ArrayList cost : 2ms
num : 1000LinkedList cost : 4ms
num : 5000ArrayList cost : 5ms
num : 5000LinkedList cost : 24ms
效率依然不怎么样啊，想不明白。。
在尾部插入：
public static void main(String[] args) {
int[] nums = {10000,10 * 10000,100 * 10000, 1000 * 10000, 10000 * 10000};
for(int i=0; i<nums.length; i++){
testList(nums[i]);
}
}
public static void testList(int num){
List<String> aList = new ArrayList<String>();
List<String> lList = new LinkedList<String>();
long starttime, endtime;
starttime= System.currentTimeMillis();
for(int i=0; i<num; i++){
aList.add("1");
}
endtime = System.currentTimeMillis();
System.out.println("num : " + num + "ArrayList cost : " + (endtime - starttime) + "ms");
starttime= System.currentTimeMillis();
for(int i=0; i<num; i++){
lList.add("1");
}
endtime = System.currentTimeMillis();
System.out.println("num : " + num + "LinkedList cost : " + (endtime - starttime) + "ms");
}
结果：
num : 10000ArrayList cost : 2ms
num : 10000LinkedList cost : 2ms
num : 100000ArrayList cost : 7ms
num : 100000LinkedList cost : 5ms
num : 1000000ArrayList cost : 29ms
num : 1000000LinkedList cost : 22ms
num : 10000000ArrayList cost : 150ms
num : 10000000LinkedList cost : 4874ms
num : 100000000ArrayList cost : 1800ms
num : 100000000LinkedList cost : 66919ms
分析：在数据量较小（小于100W）时，两种list插入效率差不多，原因是只在尾部插入，ArrayList并不需要移动元素，而在数据量较大时，LinkedList效率急速下降，这里我认为是LinkedList在插入节点时，需要向jvm申请空间而导致效率降低，在网上也没有查到相关资料
感觉出现了许多和预期不一样的结果，有没有大佬可以解释一下的~
