[[410551]]

前言

在面試的時候，經常會被問到幾個問題：

ArrayList和LinkedList的區別，相信大部分朋友都能回答上：

• ArrayList是基于數組實現，LinkedList是基于鏈表實現
• 當隨機訪問List時，ArrayList比LinkedList的效率更高，等等

當被問到ArrayList和LinkedList的使用場景是什么時，大部分朋友的答案可能是：

• ArrayList和LinkedList在新增、刪除元素時，LinkedList的效率要高于 ArrayList，而在遍歷的時候，ArrayList的效率要高于LinkedList

那這個回答是否準確呢?今天我們就來研究研究!

我們先來簡單介紹下ArrayList和LinkedList的原理實現!

源碼分析

ArrayList

實現類

public class ArrayList<E> extends AbstractList<E> 
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable 

ArrayList實現了List接口，繼承了AbstractList抽象類，底層是數組實現的，并且實現了自增擴容數組大小。

ArrayList還實現了Cloneable接口和Serializable接口，所以他可以實現克隆和序列化。

ArrayList還實現了RandomAccess接口，這個接口是一個標志接口，他標志著“只要實現該接口的List類，都能實現快速隨機訪問”。

基本屬性

ArrayList屬性主要由數組長度size、對象數組elementData、初始化容量default_capacity等組成， 其中初始化容量默認大小為10。

//默認初始化容量 
private static final int DEFAULT_CAPACITY = 10; 
//對象數組 
transient Object[] elementData;  
//數組長度 
private int size; 

從ArrayList屬性來看，elementData被關鍵字transient修飾了，transient關鍵字修飾該字段則表示該屬性不會被序列化。

• 但ArrayList其實是實現了序列化接口，這是為什么呢?

由于ArrayList的數組是基于動態擴增的，所以并不是所有被分配的內存空間都存儲了數據。

如果采用外部序列化法實現數組的序列化，會序列化整個數組，ArrayList為了避免這些沒有存儲數據的內存空間被序列化，內部提供了兩個私有方法writeObject以及readObject來自我完成序列化與反序列化，從而在序列化與反序列化數組時節省了空間和時間。

因此使用transient修飾數組，是防止對象數組被其他外部方法序列化。

ArrayList自定義序列化方法如下：

初始化

有三種初始化辦法：無參數直接初始化、指定大小初始化、指定初始數據初始化，源碼如下：

 

當ArrayList新增元素時，如果所存儲的元素已經超過其已有大小，它會計算元素大小后再進行動態擴容，數組的擴容會導致整個數組進行一次內存復制。

因此，我們在初始化ArrayList時，可以通過第一個構造函數合理指定數組初始大小，這樣有助于減少數組的擴容次數，從而提高系統性能。

注意點：

ArrayList 無參構造器初始化時，默認大小是空數組，并不是大家常說的 10，10 是在第一次 add 的時候擴容的數組值。

新增元素

ArrayList新增元素的方法有兩種，一種是直接將元素加到數組的末尾，另外一種是添加元素到任意位置。

public boolean add(E e) { 
       ensureCapacityInternal(size + 1);  // Increments modCount!! 
       elementData[size++] = e; 
       return true; 
   } 
 
   public void add(int index, E element) { 
       rangeCheckForAdd(index); 
 
       ensureCapacityInternal(size + 1);  // Increments modCount!! 
       System.arraycopy(elementData, index, elementData, index + 1, 
                        size - index); 
       elementData[index] = element; 
       size++; 
   } 

兩個方法的相同之處是在添加元素之前，都會先確認容量大小，如果容量夠大，就不用進行擴容;如果容量不夠大，就會按照原來數組的1.5倍大小進行擴容，在擴容之后需要將數組復制到新分配的內存地址。

下面是具體的源碼：

這兩個方法也有不同之處，添加元素到任意位置，會導致在該位置后的所有元素都需要重新排列，而將元素添加到數組的末尾，在沒有發生擴容的前提下，是不會有元素復制排序過程的。

• 所以ArrayList在大量新增元素的場景下效率不一定就很慢的

如果我們在初始化時就比較清楚存儲數據的大小，就可以在ArrayList初始化時指定數組容量大小，并且在添加元素時，只在數組末尾添加元素，那么ArrayList在大量新增元素的場景下，性能并不會變差，反而比其他List集合的性能要好。

刪除元素

ArrayList 刪除元素有很多種方式，比如根據數組索引刪除、根據值刪除或批量刪除等等，原理和思路都差不多。

ArrayList在每一次有效的刪除元素操作之后，都要進行數組的重組，并且刪除的元素位置越靠前，數組重組的開銷就越大。

我們選取根據值刪除方式來進行源碼說明：

遍歷元素

由于ArrayList是基于數組實現的，所以在獲取元素的時候是非常快捷的。

public E get(int index) { 
        rangeCheck(index); 
 
        return elementData(index); 
    } 
 
    E elementData(int index) { 
        return (E) elementData[index]; 
    } 

LinkedList

LinkedList是基于雙向鏈表數據結構實現的。

這個雙向鏈表結構，鏈表中的每個節點都可以向前或者向后追溯，有幾個概念如下：

• 鏈表每個節點我們叫做 Node，Node 有 prev 屬性，代表前一個節點的位置，next 屬性，代表后一個節點的位置;
• first 是雙向鏈表的頭節點，它的前一個節點是 null。
• last 是雙向鏈表的尾節點，它的后一個節點是 null;
• 當鏈表中沒有數據時，first 和 last 是同一個節點，前后指向都是 null;
• 因為是個雙向鏈表，只要機器內存足夠強大，是沒有大小限制的。

Node結構中包含了3個部分：元素內容item、前指針prev以及后指針next，代碼如下。

private static class Node<E> { 
    E item;// 節點值 
    Node<E> next; // 指向的下一個節點 
    Node<E> prev; // 指向的前一個節點 
 
    // 初始化參數順序分別是：前一個節點、本身節點值、后一個節點 
    Node(Node<E> prev, E element, Node<E> next) { 
        this.item = element; 
        this.next = next; 
        this.prev = prev; 
    } 
} 

LinkedList就是由Node結構對象連接而成的一個雙向鏈表。

實現類

LinkedList類實現了List接口、Deque接口，同時繼承了AbstractSequentialList抽象類，LinkedList既實現了List類型又有Queue類型的特點;LinkedList也實現了Cloneable和Serializable接口，同ArrayList一樣，可以實現克隆和序列化。

由于LinkedList存儲數據的內存地址是不連續的，而是通過指針來定位不連續地址，因此，LinkedList不支持隨機快速訪問，LinkedList也就不能實現RandomAccess接口。

public class LinkedList 
    extends AbstractSequentialList 
    implements List, Deque, Cloneable, java.io.Serializable 

基本屬性

transient int size = 0; 
transient Node first; 
transient Node last; 

我們可以看到這三個屬性都被transient修飾了，原因很簡單，我們在序列化的時候不會只對頭尾進行序列化，所以LinkedList也是自行實現readObject和writeObject進行序列化與反序列化。

下面是LinkedList自定義序列化的方法。

節點查詢

鏈表查詢某一個節點是比較慢的，需要挨個循環查找才行，我們看看 LinkedList 的源碼是如何尋找節點的：

LinkedList 并沒有采用從頭循環到尾的做法，而是采取了簡單二分法，首先看看 index 是在鏈表的前半部分，還是后半部分。

如果是前半部分，就從頭開始尋找，反之亦然。通過這種方式，使循環的次數至少降低了一半，提高了查找的性能。

新增元素

LinkedList添加元素的實現很簡潔，但添加的方式卻有很多種。

默認的add (Ee)方法是將添加的元素加到隊尾，首先是將last元素置換到臨時變量中，生成一個新的Node節點對象，然后將last引用指向新節點對象，之前的last對象的前指針指向新節點對象。

LinkedList也有添加元素到任意位置的方法，如果我們是將元素添加到任意兩個元素的中間位置，添加元素操作只會改變前后元素的前后指針，指針將會指向添加的新元素，所以相比ArrayList的添加操作來說，LinkedList的性能優勢明顯。

刪除元素

在LinkedList刪除元素的操作中，我們首先要通過循環找到要刪除的元素，如果要刪除的位置處于List的前半段，就從前往后找;若其位置處于后半段，就從后往前找。

這樣做的話，無論要刪除較為靠前或較為靠后的元素都是非常高效的，但如果List擁有大量元素，移除的元素又在List的中間段，那效率相對來說會很低。

遍歷元素

LinkedList的獲取元素操作實現跟LinkedList的刪除元素操作基本類似，通過分前后半段來循環查找到對應的元素，但是通過這種方式來查詢元素是非常低效的，特別是在for循環遍歷的情況下，每一次循環都會去遍歷半個List。

所以在LinkedList循環遍歷時，我們可以使用iterator方式迭代循環，直接拿到我們的元素，而不需要通過循環查找List。

分析測試

新增元素操作性能測試

測試用例源代碼：

• ArrayList：https://paste.ubuntu.com/p/gktBvjgMGk/
• LinkedList：https://paste.ubuntu.com/p/3jQrY2XMPr/

測試結果：

 

通過這組測試，我們可以知道LinkedList添加元素的效率未必要高于ArrayList。

• 從集合頭部位置添加元素

由于ArrayList是數組實現的，在添加元素到數組頭部的時候，需要對頭部以后的數據進行復制重排，所以效率很低;

LinkedList是基于鏈表實現，在添加元素的時候，首先會通過循環查找到添加元素的位置，如果要添加的位置處于List的前半段，就從前往后找;若其位置處于后半段，就從后往前找，因此LinkedList添加元素到頭部是非常高效的。

• 從集合中間位置位置添加元素

ArrayList在添加元素到數組中間時，同樣有部分數據需要復制重排，效率也不是很高;

LinkedList將元素添加到中間位置，是添加元素最低效率的，因為靠近中間位置，在添加元素之前的循環查找是遍歷元素最多的操作。

• 從集合尾部位置添加元素

而在添加元素到尾部的操作中，在沒有擴容的情況下，ArrayList的效率要高于LinkedList。

這是因為ArrayList在添加元素到尾部的時候，不需要復制重排數據，效率非常高。

LinkedList雖然也不用循環查找元素，但LinkedList中多了new對象以及變換指針指向對象的過程，所以效率要低于ArrayList。

• 注意：這是排除動態擴容數組容量的情況下進行的測試，如果有動態擴容的情況，ArrayList的效率也會降低。

刪除元素操作性能測試

ArrayList和LinkedList刪除元素操作測試的結果和添加元素操作測試的結果很接近!

結論：如果需要在List的頭部進行大量的插入、刪除操作，那么直接選擇LinkedList。否則，ArrayList即可。

遍歷元素操作性能測試

測試用例源代碼：

• ArrayList：https://paste.ubuntu.com/p/ZNWc9H2pYm/
• LinkedList：https://paste.ubuntu.com/p/xSk4nHDHvN/

測試結果：

我們可以看到，LinkedList的for循環性能是最差的，而ArrayList的for循環性能是最好的。

這是因為LinkedList基于鏈表實現的，在使用for循環的時候，每一次for循環都會去遍歷半個List，所以嚴重影響了遍歷的效率;ArrayList則是基于數組實現的，并且實現了RandomAccess接口標志，意味著ArrayList可以實現快速隨機訪問，所以for循環效率非常高。

LinkedList的迭代循環遍歷和ArrayList的迭代循環遍歷性能相當，也不會太差，所以在遍歷LinkedList時，我們要切忌使用for循環遍歷。