List概括

先回顧一下List的框架圖

Paste_Image.png

• List 是一個接口，它繼承于Collection的接口。它代表著有序的隊列。
• AbstractList 是一個抽象類，它繼承于AbstractCollection。AbstractList實現(xiàn)List接口中除size()、get(int location)之外的函數(shù)。
• AbstractSequentialList 是一個抽象類，它繼承于AbstractList。AbstractSequentialList 實現(xiàn)了“鏈表中，根據(jù)index索引值操作鏈表的全部函數(shù)”。
• ArrayList, LinkedList, Vector, Stack是List的4個實現(xiàn)類。
• ArrayList 是一個數(shù)組隊列，相當于動態(tài)數(shù)組。它由數(shù)組實現(xiàn)，隨機訪問效率高，隨機插入、隨機刪除效率低。
• LinkedList 是一個雙向鏈表。它也可以被當作堆棧、隊列或雙端隊列進行操作。LinkedList隨機訪問效率低，但隨機插入、隨機刪除效率低。
• Vector 是矢量隊列，和ArrayList一樣，它也是一個動態(tài)數(shù)組，由數(shù)組實現(xiàn)。但是ArrayList是非線程安全的，而Vector是線程安全的。
• Stack 是棧，它繼承于Vector。它的特性是：先進后出(FILO, First In Last Out)。

第2部分 List使用場景

學東西的最終目的是為了能夠理解、使用它。下面先概括的說明一下各個List的使用場景，后面再分析原因。

如果涉及到“?！?、“隊列”、“鏈表”等操作，應該考慮用List，具體的選擇哪個List，根據(jù)下面的標準來取舍。

• 對于需要快速插入，刪除元素，應該使用LinkedList。
• 對于需要快速隨機訪問元素，應該使用ArrayList。
• 對于“單線程環(huán)境” 或者 “多線程環(huán)境，但List僅僅只會被單個線程操作”，此時應該使用非同步的類(如ArrayList)。
• 對于“多線程環(huán)境，且List可能同時被多個線程操作”，此時，應該使用同步的類(如Vector)。

通過下面的測試程序，我們來驗證上面的(01)和(02)結(jié)論。參考代碼如下：

import java.util.*;
import java.lang.Class;

/*
 * @desc 對比ArrayList和LinkedList的插入、隨機讀取效率、刪除的效率
 *
 * @author skywang
 */
public class ListCompareTest {

    private static final int COUNT = 100000;

    private static LinkedList linkedList = new LinkedList();
    private static ArrayList arrayList = new ArrayList();
    private static Vector vector = new Vector();
    private static Stack stack = new Stack();

    public static void main(String[] args) {
        // 換行符
        System.out.println();
        // 插入
        insertByPosition(stack) ;
        insertByPosition(vector) ;
        insertByPosition(linkedList) ;
        insertByPosition(arrayList) ;

        // 換行符
        System.out.println();
        // 隨機讀取
        readByPosition(stack);
        readByPosition(vector);
        readByPosition(linkedList);
        readByPosition(arrayList);

        // 換行符
        System.out.println();
        // 刪除 
        deleteByPosition(stack);
        deleteByPosition(vector);
        deleteByPosition(linkedList);
        deleteByPosition(arrayList);
    }

    // 獲取list的名稱
    private static String getListName(List list) {
        if (list instanceof LinkedList) {
            return "LinkedList";
        } else if (list instanceof ArrayList) {
            return "ArrayList";
        } else if (list instanceof Stack) {
            return "Stack";
        } else if (list instanceof Vector) {
            return "Vector";
        } else {
            return "List";
        }
    }

    // 向list的指定位置插入COUNT個元素，并統(tǒng)計時間
    private static void insertByPosition(List list) {
        long startTime = System.currentTimeMillis();

        // 向list的位置0插入COUNT個數(shù)
        for (int i=0; i<COUNT; i++)
            list.add(0, i);

        long endTime = System.currentTimeMillis();
        long interval = endTime - startTime;
        System.out.println(getListName(list) + " : insert "+COUNT+" elements into the 1st position use time：" + interval+" ms");
    }

    // 從list的指定位置刪除COUNT個元素，并統(tǒng)計時間
    private static void deleteByPosition(List list) {
        long startTime = System.currentTimeMillis();

        // 刪除list第一個位置元素
        for (int i=0; i<COUNT; i++)
            list.remove(0);

        long endTime = System.currentTimeMillis();
        long interval = endTime - startTime;
        System.out.println(getListName(list) + " : delete "+COUNT+" elements from the 1st position use time：" + interval+" ms");
    }

    // 根據(jù)position，不斷從list中讀取元素，并統(tǒng)計時間
    private static void readByPosition(List list) {
        long startTime = System.currentTimeMillis();

        // 讀取list元素
        for (int i=0; i<COUNT; i++)
            list.get(i);

        long endTime = System.currentTimeMillis();
        long interval = endTime - startTime;
        System.out.println(getListName(list) + " : read "+COUNT+" elements by position use time：" + interval+" ms");
    }
}

從中，我們可以發(fā)現(xiàn)：

• 插入10萬個元素，LinkedList所花時間最短：29ms。
• 刪除10萬個元素，LinkedList所花時間最短：15ms。
• 遍歷10萬個元素，LinkedList所花時間最長：10809 ms；而ArrayList、Stack和Vector則相差不多，都只用了幾秒。

考慮到Vector是支持同步的，而Stack又是繼承于Vector的；因此，得出結(jié)論：

• 對于需要快速插入，刪除元素，應該使用LinkedList。
• 對于需要快速隨機訪問元素，應該使用ArrayList。
• 對于“單線程環(huán)境” 或者 “多線程環(huán)境，但List僅僅只會被單個線程操作”，此時應該使用非同步的類。Vector
• ArrayList支持序列化，而Vector不支持；即ArrayList有實現(xiàn)java.io.Serializable接口，而Vector沒有實現(xiàn)該接口。
• Vector支持通過Enumeration去遍歷，而對于需要快速插入，刪除元素，應該使用LinkedList，ArrayList不支持

本文來自： http://www.cnblogs.com/skywang12345/p/3308900.html