淺析 ArrayList 和 LinkedList 有什么區(qū)別

更新時(shí)間：2020年10月14日 09:54:07 作者：沉默不二

ArrayList 和 LinkedList 有什么區(qū)別，是面試官非常喜歡問(wèn)的一個(gè)問(wèn)題。今天通過(guò)本文給大家詳細(xì)介紹下，感興趣的朋友跟隨小編一起看看吧

ArrayList 和 LinkedList 有什么區(qū)別，是面試官非常喜歡問(wèn)的一個(gè)問(wèn)題。可能大部分小伙伴和我一樣，能回答出“ArrayList 是基于數(shù)組實(shí)現(xiàn)的，LinkedList 是基于雙向鏈表實(shí)現(xiàn)的?！?/p>

關(guān)于這一點(diǎn)，我之前的文章里也提到過(guò)了。但說(shuō)實(shí)話，這樣蒼白的回答并不能令面試官感到滿意，他還想知道的更多。

那假如小伙伴們繼續(xù)做出下面這樣的回答：

“ArrayList 在新增和刪除元素時(shí)，因?yàn)樯婕暗綌?shù)組復(fù)制，所以效率比 LinkedList 低，而在遍歷的時(shí)候，ArrayList 的效率要高于 LinkedList。”

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

為什么會(huì)這樣呢？為什么為什么？回答的不對(duì)嗎？

暴躁的小伙伴請(qǐng)喝口奶茶冷靜一下。冷靜下來(lái)后，請(qǐng)隨我來(lái)，讓我們一起肩并肩、手拉手地深入地研究一下 ArrayList 和 LinkedList 的數(shù)據(jù)結(jié)構(gòu)、實(shí)現(xiàn)原理以及源碼，可能神秘的面紗就揭開了。

ArrayList 是如何實(shí)現(xiàn)的？

ArrayList 實(shí)現(xiàn)了 List 接口，繼承了 AbstractList 抽象類，底層是基于數(shù)組實(shí)現(xiàn)的，并且實(shí)現(xiàn)了動(dòng)態(tài)擴(kuò)容。

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

public interface RandomAccess {
}

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

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

ArrayList 還實(shí)現(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 還實(shí)現(xiàn)了 Serializable 接口，同樣是一個(gè)標(biāo)記接口：

public interface Serializable {
}

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

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

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

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

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

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

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

比如說(shuō)，默認(rèn)的數(shù)組大小是 10，當(dāng)添加第 11 個(gè)元素的時(shí)候，數(shù)組的長(zhǎng)度擴(kuò)容了 1.5 倍，也就是 15，意味著還有 4 個(gè)內(nèi)存空間是閑置的，對(duì)吧？

序列化的時(shí)候，如果把整個(gè)數(shù)組都序列化的話，是不是就多序列化了 4 個(gè)內(nèi)存空間。當(dāng)存儲(chǔ)的元素?cái)?shù)量非常非常多的時(shí)候，閑置的空間就非常非常大，序列化耗費(fèi)的時(shí)間就會(huì)非常非常多。

于是，ArrayList 做了一個(gè)愉快而又聰明的決定，內(nèi)部提供了兩個(gè)私有方法 writeObject 和 readObject 來(lái)完成序列化和反序列化。

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 的實(shí)際大小 size 而不是數(shù)組的長(zhǎng)度（elementData.length）來(lái)作為元素的上限進(jìn)行序列化。

此處應(yīng)該有掌聲??！不是為我，為 Java 源碼的作者們，他們真的是太厲害了，可以用兩個(gè)詞來(lái)形容他們——?dú)椌邞]、精益求精。

LinkedList 是如何實(shí)現(xiàn)的？

LinkedList 是一個(gè)繼承自 AbstractSequentialList 的雙向鏈表，因此它也可以被當(dāng)作堆棧、隊(duì)列或雙端隊(duì)列進(jìn)行操作。

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 內(nèi)部定義了一個(gè) Node 節(jié)點(diǎn)，它包含 3 個(gè)部分：元素內(nèi)容 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 還實(shí)現(xiàn)了 Cloneable 接口，這表明 LinkedList 是支持拷貝的。

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

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

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

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

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 循環(huán)中的 linkLast() 方法，它可以把鏈表重新鏈接起來(lái)，這樣就恢復(fù)了鏈表序列化之前的順序。很妙，對(duì)吧？

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

ArrayList 和 LinkedList 新增元素時(shí)究竟誰(shuí)快？

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

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

很簡(jiǎn)單，先判斷是否需要擴(kuò)容，然后直接通過(guò)索引將元素添加到末尾。

插入到指定位置的源碼：

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)，然后判斷是否需要擴(kuò)容，再把該位置以后的元素復(fù)制到新添加元素的位置之后，最后通過(guò)索引將元素添加到指定的位置。這種情況是非常傷的，性能會(huì)比較差。

2）LinkedList

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

添加到隊(duì)尾的源碼：

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

先將隊(duì)尾的節(jié)點(diǎn) last 存放到臨時(shí)變量 l 中（不是說(shuō)不建議使用 I 作為變量名嗎？Java 的作者們明知故犯啊），然后生成新的 Node 節(jié)點(diǎn)，并賦給 last，如果 l 為 null，說(shuō)明是第一次添加，所以 first 為新的節(jié)點(diǎn)；否則將新的節(jié)點(diǎn)賦給之前 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++;
}

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

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

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

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

當(dāng)兩者的起始長(zhǎng)度是一樣的情況下：

如果是從集合的頭部新增元素，ArrayList 花費(fèi)的時(shí)間應(yīng)該比 LinkedList 多，因?yàn)樾枰獙?duì)頭部以后的元素進(jìn)行復(fù)制。

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從集合頭部位置新增元素花費(fèi)的時(shí)間" + (timeEnd - timeStart));
 }
}

/**
 * @author 微信搜「沉默王二」，回復(fù)關(guān)鍵字 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從集合頭部位置新增元素花費(fèi)的時(shí)間" + (timeEnd - timeStart));
 }
}

num 為 10000，代碼實(shí)測(cè)后的時(shí)間如下所示：

ArrayList從集合頭部位置新增元素花費(fèi)的時(shí)間595
LinkedList從集合頭部位置新增元素花費(fèi)的時(shí)間15

ArrayList 花費(fèi)的時(shí)間比 LinkedList 要多很多。

如果是從集合的中間位置新增元素，ArrayList 花費(fèi)的時(shí)間搞不好要比 LinkedList 少，因?yàn)?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從集合中間位置新增元素花費(fèi)的時(shí)間" + (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從集合中間位置新增元素花費(fèi)的時(shí)間" + (timeEnd - timeStart));
 }
}

num 為 10000，代碼實(shí)測(cè)后的時(shí)間如下所示：

ArrayList從集合中間位置新增元素花費(fèi)的時(shí)間1
LinkedList從集合中間位置新增元素花費(fèi)的時(shí)間101

ArrayList 花費(fèi)的時(shí)間比 LinkedList 要少很多很多。

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

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從集合尾部位置新增元素花費(fèi)的時(shí)間" + (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從集合尾部位置新增元素花費(fèi)的時(shí)間" + (timeEnd - timeStart));
 }
}

num 為 10000，代碼實(shí)測(cè)后的時(shí)間如下所示：

ArrayList從集合尾部位置新增元素花費(fèi)的時(shí)間69
LinkedList從集合尾部位置新增元素花費(fèi)的時(shí)間193

ArrayList 花費(fèi)的時(shí)間比 LinkedList 要少一些。

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

當(dāng)然了，如果涉及到數(shù)組擴(kuò)容的話，ArrayList 的性能就沒那么可觀了，因?yàn)閿U(kuò)容的時(shí)候也要復(fù)制數(shù)組。

ArrayList 和 LinkedList 刪除元素時(shí)究竟誰(shuí)快？

1）ArrayList

ArrayList 刪除元素的時(shí)候，有兩種方式，一種是直接刪除元素（remove(Object)），需要直先遍歷數(shù)組，找到元素對(duì)應(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 < 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;
}

但從本質(zhì)上講，都是一樣的，因?yàn)樗鼈冏詈笳{(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;
}

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

2）LinkedList

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

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

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

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

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

remove(Object)，直接刪除元素

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

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

removeFirst()，刪除第一個(gè)節(jié)點(diǎn)

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

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

removeLast()，刪除最后一個(gè)節(jié)點(diǎn)

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

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

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

從集合頭部刪除元素時(shí)，ArrayList 花費(fèi)的時(shí)間比 LinkedList 多很多；
從集合中間位置刪除元素時(shí)，ArrayList 花費(fèi)的時(shí)間比 LinkedList 少很多；
從集合尾部刪除元素時(shí)，ArrayList 花費(fèi)的時(shí)間比 LinkedList 少一點(diǎn)。

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

ArrayList從集合頭部位置刪除元素花費(fèi)的時(shí)間380
LinkedList從集合頭部位置刪除元素花費(fèi)的時(shí)間4
ArrayList從集合中間位置刪除元素花費(fèi)的時(shí)間381
LinkedList從集合中間位置刪除元素花費(fèi)的時(shí)間5922
ArrayList從集合尾部位置刪除元素花費(fèi)的時(shí)間8
LinkedList從集合尾部位置刪除元素花費(fèi)的時(shí)間12

ArrayList 和 LinkedList 遍歷元素時(shí)究竟誰(shuí)快？

1）ArrayList

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

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

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

由于 ArrayList 是由數(shù)組實(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 < 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;
}

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

2）LinkedList

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

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

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

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

如果使用的是 for 循環(huán)，可想而知 LinkedList 在 get 的時(shí)候性能會(huì)非常差，因?yàn)槊恳淮瓮鈱拥?for 循環(huán)，都要執(zhí)行一次 node(int) 方法進(jìn)行前后半段的遍歷。

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

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

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

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

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

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

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

總結(jié)

到此這篇關(guān)于淺析 ArrayList 和 LinkedList 有什么區(qū)別的文章就介紹到這了,更多相關(guān)ArrayList和LinkedList區(qū)別內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: