ArrayList VS LinkedList，最后一戰(zhàn)

大家好，我是二哥呀。

這是《Java 程序員進階之路》專欄的第 61 篇，我們來繼續(xù)探討 ArrayList 和 LinkedList，這一篇比上一篇更深入、更全面，源碼講解、性能考量，方方面面都有涉及到了。

首先必須得感謝大家，《Java 程序員進階之路》在 GitHub 上已經(jīng)突破 400 個星標了，感謝感謝，還沒 star 的趕緊安排一波了，沖擊 500 星標了。

https://github.com/itwanger/toBeBetterJavaer

01、ArrayList 是如何實現(xiàn)的？

ArrayList 實現(xiàn)了 List 接口，繼承了 AbstractList 抽象類。

底層是基于數(shù)組實現(xiàn)的，并且實現(xiàn)了動態(tài)擴容

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 還實現(xiàn)了 RandomAccess 接口，這是一個標記接口：

public?interface?RandomAccess?{
}

內(nèi)部是空的，標記“實現(xiàn)了這個接口的類支持快速（通常是固定時間）隨機訪問”。快速隨機訪問是什么意思呢？就是說不需要遍歷，就可以通過下標（索引）直接訪問到內(nèi)存地址。

public?E?get(int?index)?{
????Objects.checkIndex(index,?size);
????return?elementData(index);
}
E?elementData(int?index)?{
????return?(E)?elementData[index];
}

ArrayList 還實現(xiàn)了 Cloneable 接口，這表明 ArrayList 是支持拷貝的。ArrayList 內(nèi)部的確也重寫了 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 還實現(xiàn)了 Serializable 接口，同樣是一個標記接口：

public?interface?Serializable?{
}

內(nèi)部也是空的，標記“實現(xiàn)了這個接口的類支持序列化”。序列化是什么意思呢？Java 的序列化是指，將對象轉(zhuǎn)換成以字節(jié)序列的形式來表示，這些字節(jié)序中包含了對象的字段和方法。序列化后的對象可以被寫到數(shù)據(jù)庫、寫到文件，也可用于網(wǎng)絡(luò)傳輸。

眼睛雪亮的小伙伴可能會注意到，ArrayList 中的關(guān)鍵字段 elementData 使用了 transient 關(guān)鍵字修飾，這個關(guān)鍵字的作用是，讓它修飾的字段不被序列化。

這不前后矛盾嗎？一個類既然實現(xiàn)了 Serilizable 接口，肯定是想要被序列化的，對吧？那為什么保存關(guān)鍵數(shù)據(jù)的 elementData 又不想被序列化呢?

這還得從 “ArrayList 是基于數(shù)組實現(xiàn)的”開始說起。大家都知道，數(shù)組是定長的，就是說，數(shù)組一旦聲明了，長度（容量）就是固定的，不能像某些東西一樣伸縮自如。這就很麻煩，數(shù)組一旦裝滿了，就不能添加新的元素進來了。

ArrayList 不想像數(shù)組這樣活著，它想能屈能伸，所以它實現(xiàn)了動態(tài)擴容。一旦在添加元素的時候，發(fā)現(xiàn)容量用滿了 s == elementData.length，就按照原來數(shù)組的 1.5 倍（oldCapacity >> 1）進行擴容。擴容之后，再將原有的數(shù)組復制到新分配的內(nèi)存地址上 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)];
????}
}

動態(tài)擴容意味著什么？大家伙想一下。嗯，還是我來告訴大家答案吧，有點迫不及待。

意味著數(shù)組的實際大小可能永遠無法被填滿的，總有多余出來空置的內(nèi)存空間。

比如說，默認的數(shù)組大小是 10，當添加第 11 個元素的時候，數(shù)組的長度擴容了 1.5 倍，也就是 15，意味著還有 4 個內(nèi)存空間是閑置的，對吧？

序列化的時候，如果把整個數(shù)組都序列化的話，是不是就多序列化了 4 個內(nèi)存空間。當存儲的元素數(shù)量非常非常多的時候，閑置的空間就非常非常大，序列化耗費的時間就會非常非常多。

于是，ArrayList 做了一個愉快而又聰明的決定，內(nèi)部提供了兩個私有方法 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????????s.writeObject(elementData[i]);
????}

????if?(modCount?!=?expectedModCount)?{
????????throw?new?ConcurrentModificationException();
????}
}

從 writeObject 方法的源碼中可以看得出，它使用了 ArrayList 的實際大小 size 而不是數(shù)組的長度（elementData.length）來作為元素的上限進行序列化。

此處應(yīng)該有掌聲?。〔皇菫槲?，為 Java 源碼的作者們，他們真的是太厲害了，可以用兩個詞來形容他們——殫精竭慮、精益求精。

02、LinkedList 是如何實現(xiàn)的？

LinkedList 是一個繼承自 AbstractSequentialList 的雙向鏈表，因此它也可以被當作堆棧、隊列或雙端隊列進行操作。

public?class?LinkedList<E>
????extends?AbstractSequentialList<E>
????implements?List<E>,?Deque<E>,?Cloneable,?java.io.Serializable
{
????transient?int?size?=?0;
????transient?Node?first;
????transient?Node?last;
}

LinkedList 內(nèi)部定義了一個 Node 節(jié)點，它包含 3 個部分：元素內(nèi)容 item，前引用 prev 和后引用 next。代碼如下所示：

private?static?class?Node<E>?{
????E?item;
????LinkedList.Node?next;
????LinkedList.Node?prev;

????Node(LinkedList.Node?prev,?E?element,?LinkedList.Node?next)?{
????????this.item?=?element;
????????this.next?=?next;
????????this.prev?=?prev;
????}
}

LinkedList 還實現(xiàn)了 Cloneable 接口，這表明 LinkedList 是支持拷貝的。

LinkedList 還實現(xiàn)了 Serializable 接口，這表明 LinkedList 是支持序列化的。眼睛雪亮的小伙伴可能又注意到了，LinkedList 中的關(guān)鍵字段 size、first、last 都使用了 transient 關(guān)鍵字修飾，這不又矛盾了嗎？到底是想序列化還是不想序列化？

答案是 LinkedList 想按照自己的方式序列化，來看它自己實現(xiàn)的 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?x?=?first;?x?!=?null;?x?=?x.next)
????????s.writeObject(x.item);
}

發(fā)現(xiàn)沒？LinkedList 在序列化的時候只保留了元素的內(nèi)容 item，并沒有保留元素的前后引用。這樣就節(jié)省了不少內(nèi)存空間，對吧？

那有些小伙伴可能就疑惑了，只保留元素內(nèi)容，不保留前后引用，那反序列化的時候怎么辦？

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?????????linkLast((E)s.readObject());
}

void?linkLast(E?e)?{
????final?LinkedList.Node?l?=?last;
????final?LinkedList.Node?newNode?=?new?LinkedList.Node<>(l,?e,?null);
????last?=?newNode;
????if?(l?==?null)
????????first?=?newNode;
????else
????????l.next?=?newNode;
????size++;
????modCount++;
}

注意 for 循環(huán)中的 linkLast() 方法，它可以把鏈表重新鏈接起來，這樣就恢復了鏈表序列化之前的順序。很妙，對吧？

和 ArrayList 相比，LinkedList 沒有實現(xiàn) RandomAccess 接口，這是因為 LinkedList 存儲數(shù)據(jù)的內(nèi)存地址是不連續(xù)的，所以不支持隨機訪問。

03、ArrayList 和 LinkedList 新增元素時究竟誰快？

前面我們已經(jīng)從多個維度了解了 ArrayList 和 LinkedList 的實現(xiàn)原理和各自的特點。那接下來，我們就來聊聊 ArrayList 和 LinkedList 在新增元素時究竟誰快？

1）ArrayList

ArrayList 新增元素有兩種情況，一種是直接將元素添加到數(shù)組末尾，一種是將元素插入到指定位置。

添加到數(shù)組末尾的源碼：

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;
}

先檢查插入的位置是否在合理的范圍之內(nèi)，然后判斷是否需要擴容，再把該位置以后的元素復制到新添加元素的位置之后，最后通過索引將元素添加到指定的位置。這種情況是非常傷的，性能會比較差。

2）LinkedList

LinkedList 新增元素也有兩種情況，一種是直接將元素添加到隊尾，一種是將元素插入到指定位置。

添加到隊尾的源碼：

public?boolean?add(E?e)?{
????linkLast(e);
????return?true;
}
void?linkLast(E?e)?{
????final?LinkedList.Node?l?=?last;
????final?LinkedList.Node?newNode?=?new?LinkedList.Node<>(l,?e,?null);
????last?=?newNode;
????if?(l?==?null)
????????first?=?newNode;
????else
????????l.next?=?newNode;
????size++;
????modCount++;
}

先將隊尾的節(jié)點 last 存放到臨時變量 l 中（不是說不建議使用 I 作為變量名嗎？Java 的作者們明知故犯?。缓笊尚碌?Node 節(jié)點，并賦給 last，如果 l ?為 null，說明是第一次添加，所以 first 為新的節(jié)點；否則將新的節(jié)點賦給之前 last 的 next。

插入到指定位置的源碼：

public?void?add(int?index,?E?element)?{
????checkPositionIndex(index);

????if?(index?==?size)
????????linkLast(element);
????else
????????linkBefore(element,?node(index));
}
LinkedList.Node?node(int?index)?{
????//?assert?isElementIndex(index);

????if?(index?>?1))?{
????????LinkedList.Node?x?=?first;
????????for?(int?i?=?0;?i?????????????x?=?x.next;
????????return?x;
????}?else?{
????????LinkedList.Node?x?=?last;
????????for?(int?i?=?size?-?1;?i?>?index;?i--)
????????????x?=?x.prev;
????????return?x;
????}
}
void?linkBefore(E?e,?LinkedList.Node?succ)?{
????//?assert?succ?!=?null;
????final?LinkedList.Node?pred?=?succ.prev;
????final?LinkedList.Node?newNode?=?new?LinkedList.Node<>(pred,?e,?succ);
????succ.prev?=?newNode;
????if?(pred?==?null)
????????first?=?newNode;
????else
????????pred.next?=?newNode;
????size++;
????modCount++;
}

先檢查插入的位置是否在合理的范圍之內(nèi)，然后判斷插入的位置是否是隊尾，如果是，添加到隊尾；否則執(zhí)行 linkBefore() 方法。

在執(zhí)行 linkBefore() 方法之前，會調(diào)用 node() 方法查找指定位置上的元素，這一步是需要遍歷 LinkedList 的。如果插入的位置靠前前半段，就從隊頭開始往后找；否則從隊尾往前找。也就是說，如果插入的位置越靠近 LinkedList 的中間位置，遍歷所花費的時間就越多。

找到指定位置上的元素（succ）之后，就開始執(zhí)行 linkBefore() 方法了，先將 succ 的前一個節(jié)點（prev）存放到臨時變量 pred 中，然后生成新的 Node 節(jié)點（newNode），并將 succ 的前一個節(jié)點變更為 newNode，如果 pred 為 null，說明插入的是隊頭，所以 first 為新節(jié)點；否則將 pred 的后一個節(jié)點變更為 newNode。

經(jīng)過源碼分析以后，小伙伴們是不是在想：“好像 ArrayList 在新增元素的時候效率并不一定比 LinkedList 低??！”

當兩者的起始長度是一樣的情況下：

• 如果是從集合的頭部新增元素，ArrayList 花費的時間應(yīng)該比 LinkedList 多，因為需要對頭部以后的元素進行復制。

public?class?ArrayListTest?{
????public?static?void?addFromHeaderTest(int?num)?{
????????ArrayList?list?=?new?ArrayList(num);
????????int?i?=?0;

????????long?timeStart?=?System.currentTimeMillis();

????????while?(i?????????????list.add(0,?i?+?"沉默王二");
????????????i++;
????????}
????????long?timeEnd?=?System.currentTimeMillis();

????????System.out.println("ArrayList從集合頭部位置新增元素花費的時間"?+?(timeEnd?-?timeStart));
????}
}

/**
?*?@author?微信搜「沉默王二」，回復關(guān)鍵字?PDF
?*/
public?class?LinkedListTest?{
????public?static?void?addFromHeaderTest(int?num)?{
????????LinkedList?list?=?new?LinkedList();
????????int?i?=?0;
????????long?timeStart?=?System.currentTimeMillis();
????????while?(i?????????????list.addFirst(i?+?"沉默王二");
????????????i++;
????????}
????????long?timeEnd?=?System.currentTimeMillis();

????????System.out.println("LinkedList從集合頭部位置新增元素花費的時間"?+?(timeEnd?-?timeStart));
????}
}

num 為 10000，代碼實測后的時間如下所示：

ArrayList從集合頭部位置新增元素花費的時間595
LinkedList從集合頭部位置新增元素花費的時間15

ArrayList 花費的時間比 LinkedList 要多很多。

• 如果是從集合的中間位置新增元素，ArrayList 花費的時間搞不好要比 LinkedList 少，因為 LinkedList 需要遍歷。

public?class?ArrayListTest?{
????public?static?void?addFromMidTest(int?num)?{
????????ArrayList?list?=?new?ArrayList(num);
????????int?i?=?0;

????????long?timeStart?=?System.currentTimeMillis();
????????while?(i?????????????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?list?=?new?LinkedList();
????????int?i?=?0;
????????long?timeStart?=?System.currentTimeMillis();
????????while?(i?????????????int?temp?=?list.size();
????????????list.add(temp?/?2,?i?+?"沉默王二");
????????????i++;
????????}
????????long?timeEnd?=?System.currentTimeMillis();

????????System.out.println("LinkedList從集合中間位置新增元素花費的時間"?+?(timeEnd?-?timeStart));
????}
}

num 為 10000，代碼實測后的時間如下所示：

ArrayList從集合中間位置新增元素花費的時間1
LinkedList從集合中間位置新增元素花費的時間101

ArrayList 花費的時間比 LinkedList 要少很多很多。

• 如果是從集合的尾部新增元素，ArrayList 花費的時間應(yīng)該比 LinkedList 少，因為數(shù)組是一段連續(xù)的內(nèi)存空間，也不需要復制數(shù)組；而鏈表需要創(chuàng)建新的對象，前后引用也要重新排列。

public?class?ArrayListTest?{
????public?static?void?addFromTailTest(int?num)?{
????????ArrayList?list?=?new?ArrayList(num);
????????int?i?=?0;

????????long?timeStart?=?System.currentTimeMillis();

????????while?(i?????????????list.add(i?+?"沉默王二");
????????????i++;
????????}

????????long?timeEnd?=?System.currentTimeMillis();

????????System.out.println("ArrayList從集合尾部位置新增元素花費的時間"?+?(timeEnd?-?timeStart));
????}
}

public?class?LinkedListTest?{
????public?static?void?addFromTailTest(int?num)?{
????????LinkedList?list?=?new?LinkedList();
????????int?i?=?0;
????????long?timeStart?=?System.currentTimeMillis();
????????while?(i?????????????list.add(i?+?"沉默王二");
????????????i++;
????????}
????????long?timeEnd?=?System.currentTimeMillis();

????????System.out.println("LinkedList從集合尾部位置新增元素花費的時間"?+?(timeEnd?-?timeStart));
????}
}

num 為 10000，代碼實測后的時間如下所示：

ArrayList從集合尾部位置新增元素花費的時間69
LinkedList從集合尾部位置新增元素花費的時間193

ArrayList 花費的時間比 LinkedList 要少一些。

這樣的結(jié)論和預(yù)期的是不是不太相符？ArrayList 在添加元素的時候如果不涉及到擴容，性能在兩種情況下（中間位置新增元素、尾部新增元素）比 LinkedList 好很多，只有頭部新增元素的時候比 LinkedList 差，因為數(shù)組復制的原因。

當然了，如果涉及到數(shù)組擴容的話，ArrayList 的性能就沒那么可觀了，因為擴容的時候也要復制數(shù)組。

04、ArrayList 和 LinkedList 刪除元素時究竟誰快？

1）ArrayList

ArrayList 刪除元素的時候，有兩種方式，一種是直接刪除元素（remove(Object)），需要直先遍歷數(shù)組，找到元素對應(yīng)的索引；一種是按照索引刪除元素（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?????????????????if?(es[i]?==?null)
????????????????????break?found;
????????}?else?{
????????????for?(;?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;
}

但從本質(zhì)上講，都是一樣的，因為它們最后調(diào)用的都是 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;
}

從源碼可以看得出，只要刪除的不是最后一個元素，都需要數(shù)組重組。刪除的元素位置越靠前，代價就越大。

2）LinkedList

LinkedList 刪除元素的時候，有四種常用的方式：

• remove(int)，刪除指定位置上的元素

public?E?remove(int?index)?{
????checkElementIndex(index);
????return?unlink(node(index));
}

先檢查索引，再調(diào)用 node(int) 方法（ 前后半段遍歷，和新增元素操作一樣）找到節(jié)點 Node，然后調(diào)用 unlink(Node) 解除節(jié)點的前后引用，同時更新前節(jié)點的后引用和后節(jié)點的前引用：

????E?unlink(Node?x)?{
????????//?assert?x?!=?null;
????????final?E?element?=?x.item;
????????final?Node?next?=?x.next;
????????final?Node?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;
????}

• remove(Object)，直接刪除元素

public?boolean?remove(Object?o)?{
????if?(o?==?null)?{
????????for?(LinkedList.Node?x?=?first;?x?!=?null;?x?=?x.next)?{
????????????if?(x.item?==?null)?{
????????????????unlink(x);
????????????????return?true;
????????????}
????????}
????}?else?{
????????for?(LinkedList.Node?x?=?first;?x?!=?null;?x?=?x.next)?{
????????????if?(o.equals(x.item))?{
????????????????unlink(x);
????????????????return?true;
????????????}
????????}
????}
????return?false;
}

也是先前后半段遍歷，找到要刪除的元素后調(diào)用 unlink(Node)。

• removeFirst()，刪除第一個節(jié)點

public?E?removeFirst()?{
????final?LinkedList.Node?f?=?first;
????if?(f?==?null)
????????throw?new?NoSuchElementException();
????return?unlinkFirst(f);
}
private?E?unlinkFirst(LinkedList.Node?f)?{
????//?assert?f?==?first?&&?f?!=?null;
????final?E?element?=?f.item;
????final?LinkedList.Node?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;
}

刪除第一個節(jié)點就不需要遍歷了，只需要把第二個節(jié)點更新為第一個節(jié)點即可。

• removeLast()，刪除最后一個節(jié)點

刪除最后一個節(jié)點和刪除第一個節(jié)點類似，只需要把倒數(shù)第二個節(jié)點更新為最后一個節(jié)點即可。

可以看得出，LinkedList 在刪除比較靠前和比較靠后的元素時，非常高效，但如果刪除的是中間位置的元素，效率就比較低了。

這里就不再做代碼測試了，感興趣的小伙伴可以自己試試，結(jié)果和新增元素保持一致：

• 從集合頭部刪除元素時，ArrayList 花費的時間比 LinkedList 多很多；

• 從集合中間位置刪除元素時，ArrayList 花費的時間比 LinkedList 少很多；

• 從集合尾部刪除元素時，ArrayList 花費的時間比 LinkedList 少一點。

我本地的統(tǒng)計結(jié)果如下所示，小伙伴們可以作為參考：

ArrayList從集合頭部位置刪除元素花費的時間380
LinkedList從集合頭部位置刪除元素花費的時間4
ArrayList從集合中間位置刪除元素花費的時間381
LinkedList從集合中間位置刪除元素花費的時間5922
ArrayList從集合尾部位置刪除元素花費的時間8
LinkedList從集合尾部位置刪除元素花費的時間12

05、ArrayList 和 LinkedList 遍歷元素時究竟誰快？

1）ArrayList

遍歷 ArrayList 找到某個元素的話，通常有兩種形式：

• get(int)，根據(jù)索引找元素

public?E?get(int?index)?{
????Objects.checkIndex(index,?size);
????return?elementData(index);
}

由于 ArrayList 是由數(shù)組實現(xiàn)的，所以根據(jù)索引找元素非常的快，一步到位。

• indexOf(Object)，根據(jù)元素找索引

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?????????????if?(es[i]?==?null)?{
????????????????return?i;
????????????}
????????}
????}?else?{
????????for?(int?i?=?start;?i?????????????if?(o.equals(es[i]))?{
????????????????return?i;
????????????}
????????}
????}
????return?-1;
}

根據(jù)元素找索引的話，就需要遍歷整個數(shù)組了，從頭到尾依次找。

2）LinkedList

遍歷 LinkedList 找到某個元素的話，通常也有兩種形式：

• get(int)，找指定位置上的元素

public?E?get(int?index)?{
????checkElementIndex(index);
????return?node(index).item;
}

既然需要調(diào)用 node(int) 方法，就意味著需要前后半段遍歷了。

• indexOf(Object)，找元素所在的位置

public?int?indexOf(Object?o)?{
????int?index?=?0;
????if?(o?==?null)?{
????????for?(LinkedList.Node?x?=?first;?x?!=?null;?x?=?x.next)?{
????????????if?(x.item?==?null)
????????????????return?index;
????????????index++;
????????}
????}?else?{
????????for?(LinkedList.Node?x?=?first;?x?!=?null;?x?=?x.next)?{
????????????if?(o.equals(x.item))
????????????????return?index;
????????????index++;
????????}
????}
????return?-1;
}

需要遍歷整個鏈表，和 ArrayList 的 indexOf() 類似。

那在我們對集合遍歷的時候，通常有兩種做法，一種是使用 for 循環(huán)，一種是使用迭代器（Iterator）。

如果使用的是 for 循環(huán)，可想而知 LinkedList 在 get 的時候性能會非常差，因為每一次外層的 for 循環(huán)，都要執(zhí)行一次 node(int) 方法進行前后半段的遍歷。

LinkedList.Node?node(int?index)?{
????//?assert?isElementIndex(index);

????if?(index?>?1))?{
????????LinkedList.Node?x?=?first;
????????for?(int?i?=?0;?i?????????????x?=?x.next;
????????return?x;
????}?else?{
????????LinkedList.Node?x?=?last;
????????for?(int?i?=?size?-?1;?i?>?index;?i--)
????????????x?=?x.prev;
????????return?x;
????}
}

那如果使用的是迭代器呢？

LinkedList?list?=?new?LinkedList();
for?(Iterator?it?=?list.iterator();?it.hasNext();)?{
????it.next();
}

迭代器只會調(diào)用一次 node(int) 方法，在執(zhí)行 list.iterator() 的時候：先調(diào)用 AbstractSequentialList 類的 iterator() 方法，再調(diào)用 AbstractList 類的 listIterator() 方法，再調(diào)用 LinkedList 類的 listIterator(int) 方法，如下圖所示。

最后返回的是 LinkedList 類的內(nèi)部私有類 ListItr 對象：

public?ListIterator?listIterator(int?index)?{
????checkPositionIndex(index);
????return?new?LinkedList.ListItr(index);
}

private?class?ListItr?implements?ListIterator<E>?{
????private?LinkedList.Node?lastReturned;
????private?LinkedList.Node?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?????}

????public?E?next()?{
????????checkForComodification();
????????if?(!hasNext())
????????????throw?new?NoSuchElementException();

????????lastReturned?=?next;
????????next?=?next.next;
????????nextIndex++;
????????return?lastReturned.item;
????}
}

執(zhí)行 ListItr 的構(gòu)造方法時調(diào)用了一次 node(int) 方法，返回第一個節(jié)點。在此之后，迭代器就執(zhí)行 hasNext() 判斷有沒有下一個，執(zhí)行 next() 方法下一個節(jié)點。

由此，可以得出這樣的結(jié)論：遍歷 LinkedList 的時候，千萬不要使用 for 循環(huán)，要使用迭代器。

也就是說，for 循環(huán)遍歷的時候，ArrayList 花費的時間遠小于 LinkedList；迭代器遍歷的時候，兩者性能差不多。

06、總結(jié)

花了兩天時間，終于肝完了！相信看完這篇文章后，再有面試官問你 ArrayList 和 LinkedList 有什么區(qū)別的話，你一定會胸有成竹地和他扯上半小時了。

這是《Java 程序員進階之路》專欄的第 61 篇。Java 程序員進階之路，風趣幽默、通俗易懂，對 Java 初學者極度友好和舒適??，內(nèi)容包括但不限于 Java 語法、Java 集合框架、Java IO、Java 并發(fā)編程、Java 虛擬機等核心知識點。

點擊上方名片，發(fā)送消息「03」 就可以獲取《Java 程序員進階之路》的 PDF 版了，非常硬核。