前言

之前聽到的說法是 ArrayList 優勢在於查詢資料

而 LinkedList 優勢在於插入資料

那麼今天來針對插入資料的部分驗證一下是否如此

驗證

一開始先向兩種 List 塞入 50 萬筆資料

然後以 1000 為間隔從索引值 0 開始插入 10000 筆資料

紀錄兩者所花費的時間

public static void main(String[] args) throws Exception {
    int initSize = 500000;
    
    for (int j = 0; j <= initSize; j += 1000){    
        ArrayList<Integer> array = new ArrayList<Integer>();
        LinkedList<Integer> linked = new LinkedList<Integer>();

        for (int i = 0; i < initSize; i++) {
            Integer integer = new Integer(1);
            array.add(integer);
            linked.add(integer);
        }
        
        System.out.printf("index: %6d result: ", j);
        start(array, j);
        start(linked, j);
        System.out.println("");
    }
}

public static void start(List<Integer> list, int index) {
    long time1 = System.currentTimeMillis();
    
    for (int i = 0; i < 10000; i++) {
        list.add(index, new Integer(1));
    }
    
    System.out.printf("%4d ", System.currentTimeMillis() - time1);
}

結果轉換成圖表呈現

結論

LinkedList 在插入資料的部分的確是快，這句話對一半

這個快的前提是插入資料的索引值必須要在前面或後面

以這個例子來說在索引值 60000 多的時候 ArrayList 的速度已經壓死 LinkedList

並且 ArrayList 是線性遞減的，而 LinkedList 則是越靠近資料中心的部分速度越慢

更別提隨機取資料的時候

所以在實務上除非真的有必要，否則就使用 ArrayList 吧

補充

因為有網友對於一回合插入 10000 筆資料是一次次add

覺得這樣有點不太好

所以更改了一下測試程式，這次只插入一筆

但無法轉換成圖表，因為時間太接近了

這次就換成計算時間大於 0 的次數

public static void main(String[] args) throws Exception {
    int initSize = 500000;
    int arraySum = 0;
    int linkedSum = 0;
    
    for (int j = 0; j <= initSize; j += 1000){
        ArrayList<Integer> array = new ArrayList<Integer>();
        LinkedList<Integer> linked = new LinkedList<Integer>();

        for (int i = 0; i < initSize; i++) {
            Integer integer = new Integer(1);
            array.add(integer);
            linked.add(integer);
        }

        if (start(array, j) > 0){
            ++arraySum;
        }

        if (start(linked, j) > 0){
            ++linkedSum;
        }
    }

    System.out.println("ArrayList：" + arraySum + " LinkedList：" + linkedSum);
}

public static long start(List<Integer> list, int index) {
    long time1 = System.currentTimeMillis();
    
    for (int i = 0; i < 1; i++) {
        list.add(index, new Integer(1));
    }
    
    return System.currentTimeMillis() - time1;
}

結果

ArrayList:67 LinkedList:260
ArrayList:72 LinkedList:260
ArrayList:56 LinkedList:274

二次結論

我想了想，為什麼會有 LinkedList 會比較快的說法

我認為是解釋不同

若單就“插入”這個動作來說，LinkedList 一定是快的，很多篇文章也是這樣子解釋

但是實際運作的時候，在插入前還有一個步驟叫做“找到插入點”，跑完後才算是完成動作

那麼算上這一步得出上方的結果好像也就沒什麼好奇怪的了