面試官:兄弟,說說 ArrayList 和 LinkedList 有什麼區別

ArrayList 和 LinkedList 有什麼區別，是面試官非常喜歡問的一個問題。可能大部分小夥伴和我一樣，能回答出「ArrayList 是基於數組實現的，LinkedList 是基於雙向鍊表實現的。」

關於這一點，我之前的文章裡也提到過了。但說實話，這樣蒼白的回答並不能令面試官感到滿意，他還想知道的更多。

那假如小夥伴們繼續做出下面這樣的回答：

「ArrayList 在新增和刪除元素時，因為涉及到數組複製，所以效率比 LinkedList 低，而在遍歷的時候，ArrayList 的效率要高於 LinkedList。」

面試官會感到滿意嗎？我只能說，如果面試官比較仁慈的話，他可能會讓我們回答下一個問題；否則的話，他會讓我們回家等通知，這一等，可能意味著杳無音訊了。

為什麼會這樣呢？為什麼為什麼？回答的不對嗎？

暴躁的小夥伴請喝口奶茶冷靜一下。冷靜下來後，請隨我來，讓我們一起肩並肩、手拉手地深入地研究一下 ArrayList 和 LinkedList 的數據結構、實現原理以及源碼，可能神秘的面紗就揭開了。

ArrayList 是如何實現的？

ArrayList 實現了 List 接口，繼承了 AbstractList 抽象類，底層是基於數組實現的，並且實現了動態擴容。

public class ArrayList<E> extends AbstractList<E>        implements List<E>, RandomAccess, Cloneable, java.io.Serializable{    private static final int DEFAULT_CAPACITY = 10;    transient Object[] elementData;    private int size;}
ArrayList 還實現了 RandomAccess 接口，這是一個標記接口：
public interface RandomAccess {}
內部是空的，標記「實現了這個接口的類支持快速（通常是固定時間）隨機訪問」。快速隨機訪問是什麼意思呢？就是說不需要遍歷，就可以通過下標（索引）直接訪問到內存地址。
public E get(int index) {    Objects.checkIndex(index, size);    return elementData(index);}E elementData(int index) {    return (E) elementData[index];}
ArrayList 還實現了 Cloneable 接口，這表明 ArrayList 是支持拷貝的。ArrayList 內部的確也重寫了 Object 類的 clone() 方法。
public Object clone() {    try {        ArrayList<?> v = (ArrayList<?>) super.clone();        v.elementData = Arrays.copyOf(elementData, size);        v.modCount = 0;        return v;    } catch (CloneNotSupportedException e) {        // this shouldn't happen, since we are Cloneable        throw new InternalError(e);    }}
ArrayList 還實現了 Serializable 接口，同樣是一個標記接口：
public interface Serializable {}
內部也是空的，標記「實現了這個接口的類支持序列化」。序列化是什麼意思呢？Java 的序列化是指，將對象轉換成以字節序列的形式來表示，這些字節序中包含了對象的欄位和方法。序列化後的對象可以被寫到資料庫、寫到文件，也可用於網絡傳輸。
眼睛雪亮的小夥伴可能會注意到，ArrayList 中的關鍵欄位 elementData 使用了 transient 關鍵字修飾，這個關鍵字的作用是，讓它修飾的欄位不被序列化。
這不前後矛盾嗎？一個類既然實現了 Serilizable 接口，肯定是想要被序列化的，對吧？那為什麼保存關鍵數據的 elementData 又不想被序列化呢?
這還得從 「ArrayList 是基於數組實現的」開始說起。大家都知道，數組是定長的，就是說，數組一旦聲明了，長度（容量）就是固定的，不能像某些東西一樣伸縮自如。這就很麻煩，數組一旦裝滿了，就不能添加新的元素進來了。
ArrayList 不想像數組這樣活著，它想能屈能伸，所以它實現了動態擴容。一旦在添加元素的時候，發現容量用滿了 s == elementData.length，就按照原來數組的 1.5 倍（oldCapacity >> 1）進行擴容。擴容之後，再將原有的數組複製到新分配的內存地址上 Arrays.copyOf(elementData, newCapacity)。
private void add(E e, Object[] elementData, int s) {    if (s == elementData.length)        elementData = grow();    elementData[s] = e;    size = s + 1;}
private Object[] grow() {    return grow(size + 1);}
private Object[] grow(int minCapacity) {    int oldCapacity = elementData.length;    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {        int newCapacity = ArraysSupport.newLength(oldCapacity,                minCapacity - oldCapacity, /* minimum growth */                oldCapacity >> 1           /* preferred growth */);        return elementData = Arrays.copyOf(elementData, newCapacity);    } else {        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];    }}
動態擴容意味著什麼？大傢伙想一下。嗯，還是我來告訴大家答案吧，有點迫不及待。
意味著數組的實際大小可能永遠無法被填滿的，總有多餘出來空置的內存空間。
比如說，默認的數組大小是 10，當添加第 11 個元素的時候，數組的長度擴容了 1.5 倍，也就是 15，意味著還有 4 個內存空間是閒置的，對吧？
序列化的時候，如果把整個數組都序列化的話，是不是就多序列化了 4 個內存空間。當存儲的元素數量非常非常多的時候，閒置的空間就非常非常大，序列化耗費的時間就會非常非常多。
於是，ArrayList 做了一個愉快而又聰明的決定，內部提供了兩個私有方法 writeObject 和 readObject 來完成序列化和反序列化。
private void writeObject(java.io.ObjectOutputStream s)        throws java.io.IOException {    // Write out element count, and any hidden stuff    int expectedModCount = modCount;    s.defaultWriteObject();
    // Write out size as capacity for behavioral compatibility with clone()    s.writeInt(size);
    // Write out all elements in the proper order.    for (int i=0; i<size; i++) {        s.writeObject(elementData[i]);    }
    if (modCount != expectedModCount) {        throw new ConcurrentModificationException();    }}
從 writeObject 方法的源碼中可以看得出，它使用了 ArrayList 的實際大小 size 而不是數組的長度（elementData.length）來作為元素的上限進行序列化。
此處應該有掌聲啊！不是為我，為 Java 源碼的作者們，他們真的是太厲害了，可以用兩個詞來形容他們——殫精竭慮、精益求精。

LinkedList 是如何實現的？
LinkedList 是一個繼承自 AbstractSequentialList 的雙向鍊表，因此它也可以被當作堆棧、隊列或雙端隊列進行操作。
public class LinkedList<E>    extends AbstractSequentialList<E>    implements List<E>, Deque<E>, Cloneable, java.io.Serializable{    transient int size = 0;    transient Node<E> first;    transient Node<E> last;}
LinkedList 內部定義了一個 Node 節點，它包含 3 個部分：元素內容 item，前引用 prev 和後引用 next。代碼如下所示：
private static class Node<E> {    E item;    LinkedList.Node<E> next;    LinkedList.Node<E> prev;
    Node(LinkedList.Node<E> prev, E element, LinkedList.Node<E> next) {        this.item = element;        this.next = next;        this.prev = prev;    }}
LinkedList 還實現了 Cloneable 接口，這表明 LinkedList 是支持拷貝的。
LinkedList 還實現了 Serializable 接口，這表明 LinkedList 是支持序列化的。眼睛雪亮的小夥伴可能又注意到了，LinkedList 中的關鍵欄位 size、first、last 都使用了 transient 關鍵字修飾，這不又矛盾了嗎？到底是想序列化還是不想序列化？
答案是 LinkedList 想按照自己的方式序列化，來看它自己實現的 writeObject() 方法：
private void writeObject(java.io.ObjectOutputStream s)        throws java.io.IOException {    // Write out any hidden serialization magic    s.defaultWriteObject();
    // Write out size    s.writeInt(size);
    // Write out all elements in the proper order.    for (LinkedList.Node<E> x = first; x != null; x = x.next)        s.writeObject(x.item);}
發現沒？LinkedList 在序列化的時候只保留了元素的內容 item，並沒有保留元素的前後引用。這樣就節省了不少內存空間，對吧？
那有些小夥伴可能就疑惑了，只保留元素內容，不保留前後引用，那反序列化的時候怎麼辦？
private void readObject(java.io.ObjectInputStream s)        throws java.io.IOException, ClassNotFoundException {    // Read in any hidden serialization magic    s.defaultReadObject();
    // Read in size    int size = s.readInt();
    // Read in all elements in the proper order.    for (int i = 0; i < size; i++)        linkLast((E)s.readObject());}
void linkLast(E e) {    final LinkedList.Node<E> l = last;    final LinkedList.Node<E> newNode = new LinkedList.Node<>(l, e, null);    last = newNode;    if (l == null)        first = newNode;    else        l.next = newNode;    size++;    modCount++;}
注意 for 循環中的 linkLast() 方法，它可以把鍊表重新連結起來，這樣就恢復了鍊表序列化之前的順序。很妙，對吧？
和 ArrayList 相比，LinkedList 沒有實現 RandomAccess 接口，這是因為 LinkedList 存儲數據的內存地址是不連續的，所以不支持隨機訪問。

ArrayList 和 LinkedList 新增元素時究竟誰快？
前面我們已經從多個維度了解了 ArrayList 和 LinkedList 的實現原理和各自的特點。那接下來，我們就來聊聊 ArrayList 和 LinkedList 在新增元素時究竟誰快？
1）ArrayList
ArrayList 新增元素有兩種情況，一種是直接將元素添加到數組末尾，一種是將元素插入到指定位置。
添加到數組末尾的源碼：
public boolean add(E e) {    modCount++;    add(e, elementData, size);    return true;}
private void add(E e, Object[] elementData, int s) {    if (s == elementData.length)        elementData = grow();    elementData[s] = e;    size = s + 1;}
很簡單，先判斷是否需要擴容，然後直接通過索引將元素添加到末尾。
插入到指定位置的源碼：
public void add(int index, E element) {    rangeCheckForAdd(index);    modCount++;    final int s;    Object[] elementData;    if ((s = size) == (elementData = this.elementData).length)        elementData = grow();    System.arraycopy(elementData, index,            elementData, index + 1,            s - index);    elementData[index] = element;    size = s + 1;}
先檢查插入的位置是否在合理的範圍之內，然後判斷是否需要擴容，再把該位置以後的元素複製到新添加元素的位置之後，最後通過索引將元素添加到指定的位置。這種情況是非常傷的，性能會比較差。
2）LinkedList
LinkedList 新增元素也有兩種情況，一種是直接將元素添加到隊尾，一種是將元素插入到指定位置。
添加到隊尾的源碼：
public boolean add(E e) {    linkLast(e);    return true;}void linkLast(E e) {    final LinkedList.Node<E> l = last;    final LinkedList.Node<E> newNode = new LinkedList.Node<>(l, e, null);    last = newNode;    if (l == null)        first = newNode;    else        l.next = newNode;    size++;    modCount++;}
先將隊尾的節點 last 存放到臨時變量 l 中（不是說不建議使用 I 作為變量名嗎？Java 的作者們明知故犯啊），然後生成新的 Node 節點，並賦給 last，如果 l  為 null，說明是第一次添加，所以 first 為新的節點；否則將新的節點賦給之前 last 的 next。
插入到指定位置的源碼：
public void add(int index, E element) {    checkPositionIndex(index);
    if (index == size)        linkLast(element);    else        linkBefore(element, node(index));}LinkedList.Node<E> node(int index) {    // assert isElementIndex(index);
    if (index < (size >> 1)) {        LinkedList.Node<E> x = first;        for (int i = 0; i < index; i++)            x = x.next;        return x;    } else {        LinkedList.Node<E> x = last;        for (int i = size - 1; i > index; i--)            x = x.prev;        return x;    }}void linkBefore(E e, LinkedList.Node<E> succ) {    // assert succ != null;    final LinkedList.Node<E> pred = succ.prev;    final LinkedList.Node<E> newNode = new LinkedList.Node<>(pred, e, succ);    succ.prev = newNode;    if (pred == null)        first = newNode;    else        pred.next = newNode;    size++;    modCount++;}
先檢查插入的位置是否在合理的範圍之內，然後判斷插入的位置是否是隊尾，如果是，添加到隊尾；否則執行 linkBefore() 方法。
在執行 linkBefore() 方法之前，會調用 node() 方法查找指定位置上的元素，這一步是需要遍歷 LinkedList 的。如果插入的位置靠前前半段，就從隊頭開始往後找；否則從隊尾往前找。也就是說，如果插入的位置越靠近 LinkedList 的中間位置，遍歷所花費的時間就越多。
找到指定位置上的元素（succ）之後，就開始執行 linkBefore() 方法了，先將 succ 的前一個節點（prev）存放到臨時變量 pred 中，然後生成新的 Node 節點（newNode），並將 succ 的前一個節點變更為 newNode，如果 pred 為 null，說明插入的是隊頭，所以 first 為新節點；否則將 pred 的後一個節點變更為 newNode。
經過源碼分析以後，小夥伴們是不是在想：「好像 ArrayList 在新增元素的時候效率並不一定比 LinkedList 低啊！」
當兩者的起始長度是一樣的情況下：
public class ArrayListTest {    public static void addFromHeaderTest(int num) {        ArrayList<String> list = new ArrayList<String>(num);        int i = 0;
        long timeStart = System.currentTimeMillis();
        while (i < num) {            list.add(0, i + "沉默王二");            i++;        }        long timeEnd = System.currentTimeMillis();
        System.out.println("ArrayList從集合頭部位置新增元素花費的時間" + (timeEnd - timeStart));    }}
/** * @author 微信搜「沉默王二」，回復關鍵字 PDF */public class LinkedListTest {    public static void addFromHeaderTest(int num) {        LinkedList<String> list = new LinkedList<String>();        int i = 0;        long timeStart = System.currentTimeMillis();        while (i < num) {            list.addFirst(i + "沉默王二");            i++;        }        long timeEnd = System.currentTimeMillis();
        System.out.println("LinkedList從集合頭部位置新增元素花費的時間" + (timeEnd - timeStart));    }}
num 為 10000，代碼實測後的時間如下所示：
ArrayList從集合頭部位置新增元素花費的時間595LinkedList從集合頭部位置新增元素花費的時間15
ArrayList 花費的時間比 LinkedList 要多很多。
public class ArrayListTest {    public static void addFromMidTest(int num) {        ArrayList<String> list = new ArrayList<String>(num);        int i = 0;
        long timeStart = System.currentTimeMillis();        while (i < num) {            int temp = list.size();            list.add(temp / 2 + "沉默王二");            i++;        }        long timeEnd = System.currentTimeMillis();
        System.out.println("ArrayList從集合中間位置新增元素花費的時間" + (timeEnd - timeStart));    }}
public class LinkedListTest {    public static void addFromMidTest(int num) {        LinkedList<String> list = new LinkedList<String>();        int i = 0;        long timeStart = System.currentTimeMillis();        while (i < num) {            int temp = list.size();            list.add(temp / 2, i + "沉默王二");            i++;        }        long timeEnd = System.currentTimeMillis();
        System.out.println("LinkedList從集合中間位置新增元素花費的時間" + (timeEnd - timeStart));    }}
num 為 10000，代碼實測後的時間如下所示：
ArrayList從集合中間位置新增元素花費的時間1LinkedList從集合中間位置新增元素花費的時間101
ArrayList 花費的時間比 LinkedList 要少很多很多。
public class ArrayListTest {    public static void addFromTailTest(int num) {        ArrayList<String> list = new ArrayList<String>(num);        int i = 0;
        long timeStart = System.currentTimeMillis();
        while (i < num) {            list.add(i + "沉默王二");            i++;        }
        long timeEnd = System.currentTimeMillis();
        System.out.println("ArrayList從集合尾部位置新增元素花費的時間" + (timeEnd - timeStart));    }}
public class LinkedListTest {    public static void addFromTailTest(int num) {        LinkedList<String> list = new LinkedList<String>();        int i = 0;        long timeStart = System.currentTimeMillis();        while (i < num) {            list.add(i + "沉默王二");            i++;        }        long timeEnd = System.currentTimeMillis();
        System.out.println("LinkedList從集合尾部位置新增元素花費的時間" + (timeEnd - timeStart));    }}
num 為 10000，代碼實測後的時間如下所示：
ArrayList從集合尾部位置新增元素花費的時間69LinkedList從集合尾部位置新增元素花費的時間193
ArrayList 花費的時間比 LinkedList 要少一些。
這樣的結論和預期的是不是不太相符？ArrayList 在添加元素的時候如果不涉及到擴容，性能在兩種情況下（中間位置新增元素、尾部新增元素）比 LinkedList 好很多，只有頭部新增元素的時候比 LinkedList 差，因為數組複製的原因。
當然了，如果涉及到數組擴容的話，ArrayList 的性能就沒那麼可觀了，因為擴容的時候也要複製數組。

ArrayList 和 LinkedList 刪除元素時究竟誰快？
1）ArrayList
ArrayList 刪除元素的時候，有兩種方式，一種是直接刪除元素（remove(Object)），需要直先遍歷數組，找到元素對應的索引；一種是按照索引刪除元素（remove(int)）。
public boolean remove(Object o) {    final Object[] es = elementData;    final int size = this.size;    int i = 0;    found: {        if (o == null) {            for (; i < size; i++)                if (es[i] == null)                    break found;        } else {            for (; i < size; i++)                if (o.equals(es[i]))                    break found;        }        return false;    }    fastRemove(es, i);    return true;}public E remove(int index) {    Objects.checkIndex(index, size);    final Object[] es = elementData;
    @SuppressWarnings("unchecked") E oldValue = (E) es[index];    fastRemove(es, index);
    return oldValue;}
但從本質上講，都是一樣的，因為它們最後調用的都是 fastRemove(Object, int) 方法。
private void fastRemove(Object[] es, int i) {    modCount++;    final int newSize;    if ((newSize = size - 1) > i)        System.arraycopy(es, i + 1, es, i, newSize - i);    es[size = newSize] = null;}
從源碼可以看得出，只要刪除的不是最後一個元素，都需要數組重組。刪除的元素位置越靠前，代價就越大。
2）LinkedList
LinkedList 刪除元素的時候，有四種常用的方式：
public E remove(int index) {    checkElementIndex(index);    return unlink(node(index));}
先檢查索引，再調用 node(int) 方法（ 前後半段遍歷，和新增元素操作一樣）找到節點 Node，然後調用 unlink(Node) 解除節點的前後引用，同時更新前節點的後引用和後節點的前引用：
   E unlink(Node<E> x) {        // assert x != null;        final E element = x.item;        final Node<E> next = x.next;        final Node<E> prev = x.prev;
        if (prev == null) {            first = next;        } else {            prev.next = next;            x.prev = null;        }
        if (next == null) {            last = prev;        } else {            next.prev = prev;            x.next = null;        }
        x.item = null;        size--;        modCount++;        return element;    }
public boolean remove(Object o) {    if (o == null) {        for (LinkedList.Node<E> x = first; x != null; x = x.next) {            if (x.item == null) {                unlink(x);                return true;            }        }    } else {        for (LinkedList.Node<E> x = first; x != null; x = x.next) {            if (o.equals(x.item)) {                unlink(x);                return true;            }        }    }    return false;}
也是先前後半段遍歷，找到要刪除的元素後調用 unlink(Node)。
public E removeFirst() {    final LinkedList.Node<E> f = first;    if (f == null)        throw new NoSuchElementException();    return unlinkFirst(f);}private E unlinkFirst(LinkedList.Node<E> f) {    // assert f == first && f != null;    final E element = f.item;    final LinkedList.Node<E> next = f.next;    f.item = null;    f.next = null; // help GC    first = next;    if (next == null)        last = null;    else        next.prev = null;    size--;    modCount++;    return element;}
刪除第一個節點就不需要遍歷了，只需要把第二個節點更新為第一個節點即可。
刪除最後一個節點和刪除第一個節點類似，只需要把倒數第二個節點更新為最後一個節點即可。
可以看得出，LinkedList 在刪除比較靠前和比較靠後的元素時，非常高效，但如果刪除的是中間位置的元素，效率就比較低了。
這裡就不再做代碼測試了，感興趣的小夥伴可以自己試試，結果和新增元素保持一致：
從集合頭部刪除元素時，ArrayList 花費的時間比 LinkedList 多很多；
從集合中間位置刪除元素時，ArrayList 花費的時間比 LinkedList 少很多；
從集合尾部刪除元素時，ArrayList 花費的時間比 LinkedList 少一點。
我本地的統計結果如下所示，小夥伴們可以作為參考：
ArrayList從集合頭部位置刪除元素花費的時間380LinkedList從集合頭部位置刪除元素花費的時間4ArrayList從集合中間位置刪除元素花費的時間381LinkedList從集合中間位置刪除元素花費的時間5922ArrayList從集合尾部位置刪除元素花費的時間8LinkedList從集合尾部位置刪除元素花費的時間12

ArrayList 和 LinkedList 遍曆元素時究竟誰快？
1）ArrayList
遍歷 ArrayList 找到某個元素的話，通常有兩種形式：
public E get(int index) {    Objects.checkIndex(index, size);    return elementData(index);}
由於 ArrayList 是由數組實現的，所以根據索引找元素非常的快，一步到位。
public int indexOf(Object o) {    return indexOfRange(o, 0, size);}
int indexOfRange(Object o, int start, int end) {    Object[] es = elementData;    if (o == null) {        for (int i = start; i < end; i++) {            if (es[i] == null) {                return i;            }        }    } else {        for (int i = start; i < end; i++) {            if (o.equals(es[i])) {                return i;            }        }    }    return -1;}
根據元素找索引的話，就需要遍歷整個數組了，從頭到尾依次找。
2）LinkedList
遍歷 LinkedList 找到某個元素的話，通常也有兩種形式：
public E get(int index) {    checkElementIndex(index);    return node(index).item;}
既然需要調用 node(int) 方法，就意味著需要前後半段遍歷了。
public int indexOf(Object o) {    int index = 0;    if (o == null) {        for (LinkedList.Node<E> x = first; x != null; x = x.next) {            if (x.item == null)                return index;            index++;        }    } else {        for (LinkedList.Node<E> x = first; x != null; x = x.next) {            if (o.equals(x.item))                return index;            index++;        }    }    return -1;}
需要遍歷整個鍊表，和 ArrayList 的 indexOf() 類似。
那在我們對集合遍歷的時候，通常有兩種做法，一種是使用 for 循環，一種是使用迭代器（Iterator）。
如果使用的是 for 循環，可想而知 LinkedList 在 get 的時候性能會非常差，因為每一次外層的 for 循環，都要執行一次 node(int) 方法進行前後半段的遍歷。
LinkedList.Node<E> node(int index) {    // assert isElementIndex(index);
    if (index < (size >> 1)) {        LinkedList.Node<E> x = first;        for (int i = 0; i < index; i++)            x = x.next;        return x;    } else {        LinkedList.Node<E> x = last;        for (int i = size - 1; i > index; i--)            x = x.prev;        return x;    }}
那如果使用的是迭代器呢？
LinkedList<String> list = new LinkedList<String>();for (Iterator<String> it = list.iterator(); it.hasNext();) {    it.next();}
迭代器只會調用一次 node(int) 方法，在執行 list.iterator() 的時候：先調用 AbstractSequentialList 類的 iterator() 方法，再調用 AbstractList 類的 listIterator() 方法，再調用 LinkedList 類的 listIterator(int) 方法，如下圖所示。
最後返回的是 LinkedList 類的內部私有類 ListItr 對象：
public ListIterator<E> listIterator(int index) {    checkPositionIndex(index);    return new LinkedList.ListItr(index);}
private class ListItr implements ListIterator<E> {    private LinkedList.Node<E> lastReturned;    private LinkedList.Node<E> next;    private int nextIndex;    private int expectedModCount = modCount;
    ListItr(int index) {        // assert isPositionIndex(index);        next = (index == size) ? null : node(index);        nextIndex = index;    }
    public boolean hasNext() {        return nextIndex < size;    }
    public E next() {        checkForComodification();        if (!hasNext())            throw new NoSuchElementException();
        lastReturned = next;        next = next.next;        nextIndex++;        return lastReturned.item;    }}
執行 ListItr 的構造方法時調用了一次 node(int) 方法，返回第一個節點。在此之後，迭代器就執行 hasNext() 判斷有沒有下一個，執行 next() 方法下一個節點。
由此，可以得出這樣的結論：遍歷 LinkedList 的時候，千萬不要使用 for 循環，要使用迭代器。
也就是說，for 循環遍歷的時候，ArrayList 花費的時間遠小於 LinkedList；迭代器遍歷的時候，兩者性能差不多。
花了兩天時間，終於肝完了！相信看完這篇文章後，再有面試官問你 ArrayList 和 LinkedList 有什麼區別的話，你一定會胸有成竹地和他扯上半小時。