基準測試了 ArrayList 和 LinkedList ，發現我們一直用 ArrayList 也是沒什麼問題的

• 2019 年 10 月 31 日
• 筆記

ArrayList 應該是 Java 中最常用的集合類型了，以至於我們說到集合就會自然而然的想到 ArrayList。很多同學都沒有用過除了 ArrayList 之外的其他集合，甚至於都已經忘了除了 ArrayList 之外的其他集合，例如 LinkedList、Vector 等。

那麼我們平時只用 ArrayList 是不是正確呢，我既然知道了 LinkedList、Vector ，是不是也要用一下它呢，那麼什麼情況下用呢。

Vector 是執行緒安全的集合類型，所以僅在多執行緒編程的時候才考慮是否用它，凡是為了多執行緒設計，必然在性能上有所損失， Vector 只是在每個方法上簡單的加上 synchronized 關鍵字，所以性能損失是肯定的。

那麼現在就來比較一下 ArrayList 和 LinkedList，都說插入、刪除操作多的話用 LinkedList，插入操作多的話用 ArrayList，產生這種說法的大致依據如下。

ArrayList

內部是用 Object 數組作為存儲結構，數組是記憶體中連續的記憶體空間，並且繼承了 RandomAccess介面，所以可以實現元素的快速訪問。但如果不是在末尾插入元素的話，需要拷貝插入位置之後的元素。

LinkedList

內部自己實現的 Node 鏈表，每個節點都指明了上一節點和下一節點， 所以不要求記憶體連續，並且插入數據只需要修改上一節點和下一節點的指針即可。但是訪問元素需要遍歷查找，所以查詢元素較慢。

真的是這樣嗎？下面我做了一系列的測試，來看一下真實的情況。

插入數據

分別從頭部、尾部和隨機位置插入數據，初始的列表長度分別為 10、1w、10w 來測試幾種插入數據的性能，以平均耗時為依據。得到的結果如下：

頭部插入數據，ArrayList 耗時明顯大於 LinkedList ，得出結論頭部插入數據 LinkedList 性能優於 ArrayList，因為在頭部位置插入數據時，ArrayList 要拷貝插入位置之後的數據，往後移動一個位置。

尾部插入數據，ArrayList 耗時小於 LinkedList，得出結論：尾部插入數據，ArrayList 性能優於 LinkedList。

隨機位置是用 Random 產生的，上限是當前列表長度。可見隨機位置插入數據，ArrayList 耗時小於 LinkedList ，得出結論：多次隨機位置插入數據，平均性能 ArrayList 優於 LinkedList，注意，這裡說的是多次隨機插入求的平均值。

插入數據得出以下結論

獲取數據

分別從頭部、尾部和隨機位置獲取數據，初始的列表長度分別為1000、10w、100w、1000w 來測試幾種獲取數據的性能，以吞吐量為判斷依據，吞吐量單位是 每毫秒內操作數。得到的結果如下：

頭部獲取數據，ArrayList 吞吐量大於 LinkedList，得出結論頭部獲取數據，ArrayList 性能優於 LinkedList

尾部獲取數據，ArrayList 吞吐量大於 LinkedList，得出結論尾部獲取數據，ArrayList 性能優於 LinkedList

多次隨機位置獲取數據，ArrayList 吞吐量大於 LinkedList，得出結論多次隨機位置獲取數據，ArrayList 性能優於 LinkedList

綜上，獲取數據操作的結論如下

這是毋庸置疑的，實現了隨機訪問並且內部以數組形式存儲數據的 ArrayList 擁有明顯的優勢。

刪除數據

分別從頭部、尾部和隨機位置獲取數據，初始的列表長度分別為1w、100w、1000w 來測試幾種刪除數據的性能，以吞吐量為判斷依據，吞吐量單位是 每毫秒內操作數。得到的結果如下：

頭部刪除數據，LinkedList 吞吐量大於 ArrayList，得出結論：頭部刪除數據，LinkedList 性能優於 ArrayList

尾部刪除數據，ArrayList 吞吐量大於 LinkedList，得出結論：尾部刪除數據，ArrayList 性能優於 LinkedList

多次隨機位置刪除數據，ArrayList 吞吐量大於 LinkedList，得出結論：尾部刪除數據，ArrayList 性能優於 LinkedList

綜上，刪除數據操作的結論如下

遍曆數據

分別比較了 5 種遍歷方式在1000、100w、1000w 長度的列表下的性能狀況。

遍歷方式一，原始形式的 for 循環

for(int i = 0;i<x;i++){    //do something  }

遍歷方式二，增強形式的 for 循環

for(Integer i : arrayList){    // do something  }

遍歷方式三，迭代器方式

Iterator iterator = arrayList.iterator();  while (iterator.hasNext()){     // do something  }

遍歷方式四，forEach 方式

arrayList.forEach(integer -> {     // do something  });

遍歷方式五，stream 方式

正常來講，stream 後面再接 forEach 是不太正確的測試方式，一般 stream 都會配合 map、filter 等操作來進行篩選、計算等。這裡為了方面測試，姑且先這個寫了。

arrayList.stream().forEach(integer -> {     // do something  });

ArrayList 這 5 種方式遍歷的性能

無論是1w、100w、1000w ，這五種方式的性能排名都是基本穩定的。原始 for 循環最優，forEach 方式最差。

LinkedList 這 5 種方式遍歷的性能

無論是1w、100w、1000w ，這五種方式的性能排名都是基本穩定的。和 ArrayList 相似，都是原始 for 循環最優，forEach 方式最差，其他三種方式相差不大。

比較這五種方式下 ArrayList 和 LinkedList 的性能

觀察發現，迭代器方式、stream 方式、增強 for 循環這三種方式，ArrayList 的性能基本上都要優於 LinkedList，而最原始的 for 循環方式，直到列表長度達到了 1000w，仍然是 LinkedList 優於 ArrayList。

LinkedList 只有在頭部插入和刪除數據頻繁的時候才有優勢，但是能找到這種應用場景似乎也不容易找到。如此看來，我們在程式中用到列表就隨手 new 一個 ArrayList 倒也很有道理。

不要吝惜你的「推薦」呦

本文中的測試使用 JMH 基準測試完成的，圖表是用 Excel 做的，如果需要源碼和 Excel 文件，請在公眾號內回復關鍵詞 「jmh」

歡迎關注，不定期更新本系列和其他文章
古時的風箏 ，進入公眾號可以加入交流群