ArrayList,LinkedList,Vector对比

1. List 的概述

List，顾名思义，是一个有序的元素序列。我们所说的List,与Set对比是个很好的主意，Set是一套唯一的无序的元素。下面是托收的类层次关系图，从层次关系图中可以得到Java集合的基本概念。

2. ArrayList , LinkedList , Vector的区别

从层次图可以看出，它们都是继承List接口，它们用起来很相似，但是它们的主要区别在于它们的实现，这将导致不同操作的不同性能。

ArrayList 实现的是可变的数组，随着更多的元素被添加到ArrayList中，它的大小会被动态地增加。它的元素可以通过使用get和set方法直接访问，因为ArrayList本质上是一个数组。
LinkedList 实现的是双向链表，它在add和remove上的性能优于Arraylist，但在get和set方法上更糟糕。
Vector 类似与ArrayList，但是它是同步的。
ArrayList 是一个线程安全很好的选择。ArrayList和Vector当添加更多元素时，需要更多的空间，ArrayList以50%的长度增长，Vector都是加倍增长。然而LinkedList又实现了Queue增加了更多的方法，比如offer()，peek()，poll()等等。

注：ArrayList的默认初始容量非常小。构建具有较高初始容量的ArrayList是一个好习惯。这可以避免调整成本。

3. ArrayList 的例子

ArrayList<Integer> al = new ArrayList<Integer>();
al.add(3);
al.add(2);      
al.add(1);
al.add(4);
al.add(5);
al.add(6);
al.add(6);

Iterator<Integer> iter1 = al.iterator();
while(iter1.hasNext()){
    System.out.println(iter1.next());
}

4. LinkedList 的例子

LinkedList<Integer> ll = new LinkedList<Integer>();
ll.add(3);
ll.add(2);      
ll.add(1);
ll.add(4);
ll.add(5);
ll.add(6);
ll.add(6);

Iterator<Integer> iter2 = ll.iterator();
while(iter2.hasNext()){
    System.out.println(iter2.next());
}

从上面的例子看来，他们的使用上是很相似的。

5. Vector

Vertor几乎与ArrayList相同，它们的不同就是Vertor是同步的，因此它有更多的开销，一般JAVA程序员会用ArrayList代替Vector因为可以他们自己可以在线程同步中使用。Vector是线程同步的，所以它也是线程安全的，而Arraylist是线程异步的，是不安全的。如果不考虑到线程的安全因素，一般用Arraylist效率比较高。就是说单线程时要用ArrayList，多线程时考虑用Vector。

ArrayList 和 LinkedList 的性能

我用下面的代码来测试它们的性能：

ArrayList<Integer> arrayList = new ArrayList<Integer>();
LinkedList<Integer> linkedList = new LinkedList<Integer>();

// ArrayList add
long startTime = System.nanoTime();

for (int i = 0; i < 100000; i++) {
    arrayList.add(i);
}
long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.println("ArrayList add:  " + duration);

// LinkedList add
startTime = System.nanoTime();

for (int i = 0; i < 100000; i++) {
    linkedList.add(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("LinkedList add: " + duration);

// ArrayList get
startTime = System.nanoTime();

for (int i = 0; i < 10000; i++) {
    arrayList.get(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("ArrayList get:  " + duration);

// LinkedList get
startTime = System.nanoTime();

for (int i = 0; i < 10000; i++) {
    linkedList.get(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("LinkedList get: " + duration);



// ArrayList remove
startTime = System.nanoTime();

for (int i = 9999; i >=0; i--) {
    arrayList.remove(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("ArrayList remove:  " + duration);



// LinkedList remove
startTime = System.nanoTime();

for (int i = 9999; i >=0; i--) {
    linkedList.remove(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("LinkedList remove: " + duration);

结果：

ArrayList add: 13265642
LinkedList add: 9550057
ArrayList get: 1543352
LinkedList get: 85085551
ArrayList remove: 199961301
LinkedList remove: 85768810

上面结果可得出结论，LinkedList添加和删除的速度更快，但是查询慢。我们可以知道什么时候用LinkedList或者ArrayList。简而言之，LinkedList 更适合使用的时候是：

• 没有大量的随机访问元素
• 有大量的添加删除的操作