ArrayList和LinkedList

ArrayList && LinkedList#

ArrayList#

一、概述：#

繼承了 AbstractList，實現了 List 接口，它是一個數組隊列，提供了相關的添加、刪除、修改、遍歷等功能
除了列表接口外，該類提供了一種方法來操作該數組的大小來存儲該列表中的數組的大小
實現Serializable接口，這意味著 ArrayList 支持序列化，能通過序列化去傳輸

1. 時間複雜度：#

ArrayList 實現了RandomAccess接口，即提供了隨機訪問功能
方法size、isEmpty、get、set、iterator和listIterator的調用是常數時間的。
添加刪除的時間複雜度為 O (N)。其他所有操作也都是線性時間複雜度。

2. 容量：#

每個 ArrayList 都有容量，容量大小至少為 List 元素的長度，默認初始化為 10，容量可以自動增長。
如果提前知道數組元素較多，可以在添加元素前通過調用ensureCapacity()方法提前增加容量以減小後期容量自動增長的開銷。
也可以通過帶初始容量的構造器初始化這個容量。

3. 线程不安全：#

ArrayList 不是線程安全的，在多線程中可以選擇Vector或者CopyOnWriteArrayList，用Collections.synchronizedList把一個普通 ArrayList 包裝成一個線程安全版本的數組容器也可以

二、LinkedList#

底層使用雙向鏈表實現、保留了頭尾兩個指針、LinkedList 的其他操作

ArrayList 和 LinkedList 的區別#

LinkedList 實現了 List 和 Deque 接口，一般稱為雙向鏈表；ArrayList 實現了 List 接口，動態數組；
LinkedList 在插入和刪除數據時效率更高，ArrayList 在查找某個 index 的數據時效率更高；
LinkedList 比 ArrayList 需要更多的內存，因為需要維護前後兩個指針

三、思考#

1. ArrayList 插入刪除一定慢麼？#

不一定，取決於插入刪除的位置離數組末端有多遠，比如剛好插入到尾部，那時間複雜度就是 O (1)

2. ArrayList 的遍歷和 LinkedList 遍歷性能比較如何？#

論遍歷的話ArrayList要比LinkedList快得多，ArrayList遍歷最大的優勢在於內存的連續性，CPU 的內部緩存結構會緩存連續的內存片段，可以大幅降低讀取內存的性能開銷

3. ArrayList 是如何擴容的？#

拿添加元素來說，首先calculateCapacity()方法計算所需容量，ensureExplicitCapacity方法內部調用grow方法進行擴容，grow 方法具體實現:

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 擴容到原來容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 判斷擴容後是否足夠，不夠的話就直接使用minCapacity作為容量大小
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 若預設值大於默認最大值檢查是否溢出
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 將數組指向newCapacity新的連續內存空間並拷貝數據
    elementData = Arrays.copyOf(elementData, newCapacity);
}

4. ArrayList 的默認最大數組大小為什麼是`Integer.MAX_VALUE - 8`?#

數組對象有一個額外的元數據，用於表示數組的大小，需要額外的 8 bytes 存儲這部分元數據

5. ArrayList 是線程安全的麼？#

ArrayList 不是線程安全的，在多線程中可以選擇Vector或者用Collections.synchronizedList把一個普通 ArrayList 包裝成一個線程安全版本的數組容器，原理類似，都是直接用synchronized加鎖。CopyOnWriteArrayList是線程安全的，是一種讀寫分離的機制實現，適用於讀多寫少的場景，原理參考: CopyOnWriteArrayList 實現原理及源碼分析

6. 數組用來做隊列合適麼？#

隊列一般是 FIFO 的，如果用 ArrayList 做隊列，就需要在數組尾部追加數據，數組頭部刪除數組，反過來也可以。但是無論如何總會有一個操作會涉及到數組的數據搬遷，這個是比較耗費性能的。
但是定長數組卻是很合適的，比如ArrayBlockingQueue內部實現就是一個環形隊列，它是一個定長隊列，內部是用一個定長數組來實現的。另外著名的 Disruptor 開源 Library 也是用環形數組來實現的超高性能隊列

7. Array 和 ArrayList 有什麼區別？什麼時候該用 Array 而不是 ArrayList 呢？#

Array 可以包含基本類型和對象類型，ArrayList 只能包含對象類型。
Array 大小是固定的，ArrayList 的大小是動態變化的。
ArrayList 提供了更多的方法和特性，比如：addAll ()，removeAll ()，iterator () 等等

四、參考鏈接#

坑人無數的 Java 面試題之 ArrayList