老徐和阿珍的故事：ArrayList和LinkedList的效率到底哪個高？

人物背景：老徐，男，本名徐福貴，從事Java相關研發工作多年，職場老油條，摸魚小能手，雖然歲數不大但長的比較著急，人稱老徐。據說之前炒某幣敗光了所有家產，甚至現在還有欠債。阿珍，女，本名陳家珍，剛剛入職不久的實習生，雖然是職場菜鳥但聰明好學。據說是學校的四大校花之一，追求她的人從旺角排到了銅鑼灣 ...

人物背景：

老徐，男，本名徐福貴，從事Java相關研發工作多年，職場老油條，摸魚小能手，雖然歲數不大但長的比較著急，人稱老徐。據說之前炒某幣敗光了所有家產，甚至現在還有欠債。

阿珍，女，本名陳家珍，剛剛入職不久的實習生，雖然是職場菜鳥但聰明好學。據說是學校的四大校花之一，追求她的人從旺角排到了銅鑼灣，不過至今還單身。

老徐問道：“阿珍，你知道ArrayList和LinkedList的區別嗎？”

阿珍微微一笑，說：“這也太小兒科了，ArrayList是基於數組實現，LinkedList是基於鏈表實現。”

老徐豎起了大拇指，說：“不錯，有進步！那你知道ArrayList和LinkedList的效率到底哪個高？”

阿珍回答：“這也難不倒我，這要分不同情況的。在新增、刪除元素時，LinkedList的效率要高於ArrayList，而在遍歷的時候，ArrayList的效率要高於LinkedList。”

老徐反問到：“不一定哦。在新增、刪除元素時，LinkedList的效率有可能低於ArrayList，而在遍歷的時候，ArrayList的效率有可能低於LinkedList。”

阿珍回答：“不可能，絕對不可能，書上都是這麼寫的。”

老徐得意地笑了，說：“實踐是檢驗真理的唯一標準。趁著老闆不在，咱兩寫個程式實踐一下。”

ArrayList和LinkedList的新增元素對比

首先，寫一段計算新增元素耗時的代碼：

/**
 * 從List的頭部新增元素
 * @param list list
 * @param count 新增元素的個數
 * @return 所耗費的時間（單位：ms）
 */
public static long addHeader(List<String> list, int count) {
    long start = System.nanoTime();
    for (int i = 0; i < count; i++) {
        list.add(0, "onemore-" + i);
    }
    long end = System.nanoTime();
    return (end - start) / 1000000;
}

/**
 * 從List的中部新增元素
 * @param list list
 * @param count 新增元素的個數
 * @return 所耗費的時間（單位：ms）
 */
public static long addMiddle(List<String> list, int count) {
    long start = System.nanoTime();
    for (int i = 0; i < count; i++) {
        list.add(list.size() / 2, "onemore-" + i);
    }
    long end = System.nanoTime();
    return (end - start) / 1000000;
}

/**
 * 從List的尾部新增元素
 * @param list list
 * @param count 新增元素的個數
 * @return 所耗費的時間（單位：ms）
 */
public static long addTail(List<String> list, int count) {
    long start = System.nanoTime();
    for (int i = 0; i < count; i++) {
        list.add("onemore-" + i);
    }
    long end = System.nanoTime();
    return (end - start) / 1000000;
}

然後，我們把新增元素的個數設置為50000，對比一下：

public static void main(String[] args) {
    int count = 50000;

    System.out.println("從ArrayList的頭部新增元素：" + addHeader(new ArrayList<>(count), count) + "ms");
    System.out.println("從LinkedList的頭部新增元素：" + addHeader(new LinkedList<>(), count) + "ms");

    System.out.println("從ArrayList的中部新增元素：" + addMiddle(new ArrayList<>(count), count) + "ms");
    System.out.println("從LinkedList的中部新增元素：" + addMiddle(new LinkedList<>(), count) + "ms");

    System.out.println("從ArrayList的尾部新增元素：" + addTail(new ArrayList<>(count), count) + "ms");
    System.out.println("從LinkedList的尾部新增元素：" + addTail(new LinkedList<>(), count) + "ms");
}

運行結果如下：

ArrayList從頭部新增元素：204ms
LinkedList從頭部新增元素：17ms
ArrayList從中部新增元素：71ms
LinkedList從中部新增元素：8227ms
ArrayList從尾部新增元素：13ms
LinkedList從尾部新增元素：21ms

我們可以看出，從頭部新增元素時，ArrayList的效率低於LinkedList；從中部新增元素時，ArrayList的效率高於LinkedList；從尾部新增元素時，ArrayList的效率高於LinkedList。

阿珍驚呆了，說：“怎麼可能？這是為什麼呀？”老徐回答：“我來幫你簡單分析一下。”

ArrayList是基於數組實現的，在添加元素到數組頭部的時候，在添加元素之前需要把頭部以後的元素一個一個地往後挪，所以效率很低；而LinkedList是基於鏈表實現，從頭部添加元素的時候，通過頭部指針就可以直接添加，所以效率很高。

ArrayList在添加元素到數組中間的時候，同樣有部分元素需要一個一個地往後挪，所以效率也不是很高；而LinkedList從中部添加元素的時候，是添加元素最低效率的，因為靠近中間位置，在添加元素之前需要迴圈查找遍歷部分元素，所以效率很低。

ArrayList從尾部添加元素的時候，不需要挪動任何元素，直接把元素放入數組，效率非常高。而LinkedList雖然不需要迴圈查找遍歷元素，但LinkedList中多了實列化節點對象和變換指針指向的過程，所以效率較低一些。

當然，這裡有一個大前提，就是ArrayList初始化容量足夠，不需要動態擴容數組容量。所以，在我們的日常開發中，最好指定ArrayList的初始化容量。

ArrayList和LinkedList的刪除元素對比

首先，寫一段計算刪除元素耗時的代碼：

/**
 * 從List的頭部刪除元素
 * @param list list
 * @param count 刪除元素的個數
 * @return 所耗費的時間（單位：ms）
 */
public static double deleteHeader(List<String> list, int count) {
    for (int i = 0; i < count; i++) {
        list.add("onemore-" + i);
    }
    long start = System.nanoTime();
    for (int i = 0; i < count; i++) {
        list.remove(0);
    }
    long end = System.nanoTime();
    return (end - start) / 1000000.0;
}

/**
 * 從List的中部刪除元素
 * @param list list
 * @param count 刪除元素的個數
 * @return 所耗費的時間（單位：ms）
 */
public static double deleteMiddle(List<String> list, int count) {
    for (int i = 0; i < count; i++) {
        list.add("onemore-" + i);
    }
    long start = System.nanoTime();
    for (int i = 0; i < count; i++) {
        list.remove(list.size() / 2);
    }
    long end = System.nanoTime();
    return (end - start) / 1000000.0;
}

/**
 * 從List的尾部刪除元素
 * @param list list
 * @param count 刪除元素的個數
 * @return 所耗費的時間（單位：ms）
 */
public static double deleteTail(List<String> list, int count) {
    for (int i = 0; i < count; i++) {
        list.add("onemore-" + i);
    }
    long start = System.nanoTime();
    for (int i = 0; i < count; i++) {
        list.remove(list.size() - 1);
    }
    long end = System.nanoTime();
    return (end - start) / 1000000.0;
}

然後，我們把刪除元素的個數設置為50000，對比一下：

public static void main(String[] args) {
    int count = 50000;

    System.out.println("從ArrayList的頭部刪除元素：" + deleteHeader(new ArrayList<>(count), count) + "ms");
    System.out.println("從LinkedList的頭部刪除元素：" + deleteHeader(new LinkedList<>(), count) + "ms");

    System.out.println("從ArrayList的中部刪除元素：" + deleteMiddle(new ArrayList<>(count), count) + "ms");
    System.out.println("從LinkedList的中部刪除元素：" + deleteMiddle(new LinkedList<>(), count) + "ms");

    System.out.println("從ArrayList的尾部刪除元素：" + deleteTail(new ArrayList<>(count), count) + "ms");
    System.out.println("從LinkedList的尾部刪除元素：" + deleteTail(new LinkedList<>(), count) + "ms");

}

運行結果如下：

從ArrayList的頭部刪除元素：260.7014ms
從LinkedList的頭部刪除元素：14.2948ms
從ArrayList的中部刪除元素：95.9073ms
從LinkedList的中部刪除元素：3602.6931ms
從ArrayList的尾部刪除元素：1.6261ms
從LinkedList的尾部刪除元素：3.9645ms

我們可以看出，從頭部刪除元素時，ArrayList的效率低於LinkedList；從中部刪除元素時，ArrayList的效率高於LinkedList；從尾部刪除元素時，ArrayList的效率高於LinkedList。

阿珍搶著說：“刪除元素這個我知道，和新增元素的原理差不多。”老徐回答：“既然你知道了，我就不啰嗦了，我們繼續看遍歷元素。”

ArrayList和LinkedList的遍歷元素對比

遍歷元素一般有兩種方式：for迴圈和foreach，寫一段計算這兩種遍歷方式耗時的代碼：

/**
 * 通過for迴圈遍歷List
 *
 * @param list  list
 * @param count 遍歷元素的個數
 * @return 所耗費的時間（單位：ms）
 */
public static double getByFor(List<String> list, int count) {
    for (int i = 0; i < count; i++) {
        list.add("onemore-" + i);
    }
    String name = "萬貓學社";
    long start = System.nanoTime();
    for (int i = 0; i < count; i++) {
        if (name.equals(list.get(i))) {
            System.out.println(name);
        }
    }
    long end = System.nanoTime();
    return (end - start) / 1000000.0;
}

/**
 * 通過foreach遍歷List
 *
 * @param list  list
 * @param count 遍歷元素的個數
 * @return 所耗費的時間（單位：ms）
 */
public static double getByForeach(List<String> list, int count) {
    for (int i = 0; i < count; i++) {
        list.add("onemore-" + i);
    }
    String name = "萬貓學社";
    long start = System.nanoTime();
    for (String str : list) {
        if (name.equals(str)) {
            System.out.println(name);
        }
    }
    long end = System.nanoTime();
    return (end - start) / 1000000.0;
}

然後，我們把遍歷元素的個數設置為50000，對比一下：

public static void main(String[] args) {
    int count = 50000;

    System.out.println("通過for迴圈遍歷ArrayList：" + getByFor(new ArrayList<>(count), count) + "ms");
    System.out.println("通過for迴圈遍歷LinkedList：" + getByFor(new LinkedList<>(), count) + "ms");

    System.out.println("通過foreach遍歷ArrayList：" + getByForeach(new ArrayList<>(count), count) + "ms");
    System.out.println("通過foreach遍歷LinkedList：" + getByForeach(new LinkedList<>(), count) + "ms");
}

運行結果如下：

通過for迴圈遍歷ArrayList：3.4403ms
通過for迴圈遍歷LinkedList：3563.1219ms
通過foreach遍歷ArrayList：3.7388ms
通過foreach遍歷LinkedList：3.7953ms

我們可以看到，通過for迴圈遍歷時，ArrayList的效率高於LinkedList，而且LinkedList的效率極低；通過foreach遍歷時，ArrayList的效率和LinkedList相差不大。

老徐：“阿珍，你知道為什麼for迴圈遍歷LinkedList的效率那麼低嗎？”

阿珍：“因為LinkedList基於鏈表實現的，每一次for迴圈都要遍歷找到對應的節點，所以嚴重影響了遍歷的效率；而ArrayList直接可以通過數組下標直接找到對應的元素，所以for迴圈效率非常高。對不對？”

老徐：“是的，所以我們不要使用for迴圈遍歷LinkedList。”

總結

ArrayList是基於數組實現，LinkedList是基於鏈表實現。

在ArrayList初始化容量足夠的情況下，從頭部新增元素時，ArrayList的效率低於LinkedList；從中部新增元素時，ArrayList的效率高於LinkedList；從尾部新增元素時，ArrayList的效率高於LinkedList。

從頭部刪除元素時，ArrayList的效率低於LinkedList；從中部刪除元素時，ArrayList的效率高於LinkedList；從尾部刪除元素時，ArrayList的效率高於LinkedList。

通過for迴圈遍歷時，ArrayList的效率高於LinkedList，而且LinkedList的效率極低；通過foreach遍歷時，ArrayList的效率和LinkedList相差不大。

微信掃描二維碼關註後回覆「電子書」，獲取12本Java必讀技術書籍。

最後，謝謝你這麼帥，還給我點贊和關註。

作者：萬貓學社
出處：http://www.cnblogs.com/heihaozi/
版權聲明：本文遵循 CC 4.0 BY-NC-SA 版權協議，轉載請附上原文出處鏈接和本聲明。
微信掃描二維碼，關註萬貓學社，回覆「電子書」，免費獲取12本Java必讀技術書籍。