ArrayList 可以完全替代陣列嗎？

本文已收錄到  GitHub · AndroidFamily，有 Android 進階知識體系，歡迎 Star。技術和職場問題，請關注公眾號 [彭旭銳] 加入 Android 交流群。

前言

大家好，我是小彭。

在前面的文章裡，我們學習了很多資料結構與演演算法思想。在實際的業務開發中，往往不需要我們手寫資料結構，而是直接使用標準庫的資料結構 / 容器類。

在後續的文章裡，我們將以 Java 語言為例，分析從 ArrayList 到 LinkedHashMap 等一系列標準庫容器類，最後再有一篇總結回顧，請關注。

學習路線圖：

1. 說一下 ArrayList 和 LinkedList 的區別？

• 1、資料結構： 在資料結構上，ArrayList 和 LinkedList 都是 「線性表」，都繼承於 Java 的 List 介面。另外 LinkedList 還實現了 Java 的 Deque 介面，是基於連結串列的棧或佇列，與之對應的是 ArrayDeque 基於陣列的棧或佇列；

• 2、執行緒安全： ArrayList 和 LinkedList 都不考慮執行緒同步，不保證執行緒安全；

• 3、底層實現： 在底層實現上，ArrayList 是基於動態陣列的，而 LinkedList 是基於雙向連結串列的。事實上，它們很多特性的區別都是因為底層實現不同引起的。比如說：

  • 在遍歷速度上： 陣列是一塊連續記憶體空間，基於區域性性原理能夠更好地命中 CPU 快取行，而連結串列是離散的記憶體空間對快取行不友好；

  • 在存取速度上： 陣列是一塊連續記憶體空間，支援 O(1) 時間複雜度隨機存取，而連結串列需要 O(n) 時間複雜度查詢元素；

  • 在新增和刪除操作上： 如果是在陣列的末尾操作只需要 O(1) 時間複雜度，但在陣列中間操作需要搬運元素，所以需要 O(n)時間複雜度，而連結串列的刪除操作本身只是修改參照指向，只需要 O(1) 時間複雜度（如果考慮查詢被刪除節點的時間，複雜度分析上依然是 O(n)，在工程分析上還是比陣列快）；

  • 額外記憶體消耗上： ArrayList 在陣列的尾部增加了閒置位置，而 LinkedList 在節點上增加了前驅和後繼指標。

2. ArrayList 原始碼分析

這一節，我們來分析 ArrayList 中主要流程的原始碼。

2.1 ArrayList 的屬性

ArrayList 的屬性很好理解，底層是一個 Object 陣列，我要舉手提問：