ArrayList vs LinkedList vs Vector

List概覽

List，正如它的名字，表明其是有順序的。當討論List的時候，最好拿它跟Set作比較，Set中的元素是無序且唯一；下面是一張類層次結構圖，從這張圖中，我們可以大致了解java集合類的整體架構；

ArrayList vs LinkedList vs Vector

從上面的類層次結構圖中，我們可以發現他們都實現了List接口，它們使用起來非常相似。區別主要在於它們各自的實現，不同的實現導致了不同的性能和不同的操作。

ArrayList是為可變數組實現的，當更多的元素添加到ArrayList的時候，它的大小會動態增大。它的元素可以通過get/set方法直接訪問，因為ArrayList本質上是一個數組。

LinkedList是為雙向鏈表實現的，添加、刪除元素的性能比ArrayList好，但是get/set元素的性能較差。

Vector與ArrayList相似，但是它是同步的。

如果你的程序是線程安全的，ArrayList是一個比較好的選擇。當更多的元素被添加的時候，Vector和ArrayList需要更多的空間。Vector每次擴容會增加一倍的空間，而ArrayList增加50%。

注意：ArrayList默認的初始空間大小相當的小，通過構造函數去初始化一個更大的空間是一個好習慣，可以避免擴容開銷。

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

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

從以上代碼，我們可以發現它們的使用非常相似，真正地區別在於它們的底層實現和操作復雜度。

Vector

Vector和ArrayList幾乎是一樣的，區別在於Vector是線程安全的，因為這個原因，它的性能較ArrayList差。通常情況下，大部分程序員都使用ArrayList，而不是Vector，因為他們可以自己做出明確的同步操作。

ArrayList和LinkedList性能對比

表中的add()方法指add(E e)， remove()方法指remove(int index)

• ArrayList對任意的add，remove操作，時間復雜度為O(n)，但是在列表末尾的操作，其時間復雜度為O(1)。
• LinkedList對任意的add，remove操作，時間復雜度為O(n)，但是在列表末尾的操作，其時間復雜度為O(1)。

我使用如下代碼測試它們的性能：

package simplejava;

import java.util.ArrayList;
import java.util.LinkedList;

public class Q24 {

    public static void main(String[] args) {
        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

它們性能的區別很明顯。對於Add和remove操作，LinkedList性能較好，但是get操作性能較差。基於上面的時間復雜度表和測試結果，我們可以得出什麼時候使用ArrayList還是LinkedList。簡單的說，LinkedList適用於如下情況：

• 沒有大量的隨機訪問操作
• 有大量的add/remove操作

譯文鏈接：http://www.programcreek.com/2013/03/arraylist-vs-linkedlist-vs-vector/