[源碼分析]ArrayList和LinkedList如何實(shí)現(xiàn)的？我看你還有機(jī)會(huì)！

前言

說(shuō)真的，在 Java 使用最多的集合類(lèi)中，List 絕對(duì)占有一席之地的，它和 Map 一樣適用于很多場(chǎng)景，非常方便我們的日常開(kāi)發(fā)，畢竟存儲(chǔ)一個(gè)列表的需求隨處可見(jiàn)。盡管如此，還是有很多同學(xué)沒(méi)有弄明白 List 中 ArrayList 和 LinkedList 有什么區(qū)別，這簡(jiǎn)直太遺憾了，這兩者其實(shí)都是數(shù)據(jù)結(jié)構(gòu)中的基礎(chǔ)內(nèi)容，這篇文章會(huì)從基礎(chǔ)概念開(kāi)始，分析兩者在 Java 中的具體源碼實(shí)現(xiàn)，尋找兩者的不同之處，最后思考它們使用時(shí)的注意事項(xiàng)。

這篇文章會(huì)包含以下內(nèi)容。

1. 介紹線性表的概念，詳細(xì)介紹線性表中數(shù)組和鏈表的數(shù)據(jù)結(jié)構(gòu)。
2. 進(jìn)行 ArrayList 的源碼分析，比如存儲(chǔ)結(jié)構(gòu)、擴(kuò)容機(jī)制、數(shù)據(jù)新增、數(shù)據(jù)獲取等。
3. 進(jìn)行 LinkedList 的源碼分析，比如它的存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)插入、數(shù)據(jù)查詢、數(shù)據(jù)刪除和 LinkedList 作為隊(duì)列的使用方式等。
4. 進(jìn)行 ArrayList 和 LinkedList 的總結(jié)。

線性表

要研究 ArrayList 和 LinkedList ，首先要弄明白什么是線性表，這里引用百度百科的一段文字。

線性表是最基本、最簡(jiǎn)單、也是最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表（linear list）是數(shù)據(jù)結(jié)構(gòu)的一種，一個(gè)線性表是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。

你肯定看到了，線性表在數(shù)據(jù)結(jié)構(gòu)中是一種最基本、最簡(jiǎn)單、最常用的數(shù)據(jù)結(jié)構(gòu)。它將數(shù)據(jù)一個(gè)接一個(gè)的排成一條線（可能邏輯上），也因此線性表上的每個(gè)數(shù)據(jù)只有前后兩個(gè)方向，而在數(shù)據(jù)結(jié)構(gòu)中，數(shù)組、鏈表、棧、隊(duì)列都是線性表。你可以想象一下整整齊齊排隊(duì)的樣子。

看到這里你可能有疑問(wèn)了，有線性表，那么肯定有非線性表嘍？沒(méi)錯(cuò)。二叉樹(shù)和圖就是典型的非線性結(jié)構(gòu)了。不要被這些花里胡哨的圖嚇到，其實(shí)這篇文章非常簡(jiǎn)單，希望同學(xué)耐心看完點(diǎn)個(gè)贊。

數(shù)組

既然知道了什么是線性表，那么理解數(shù)組也就很容易了，首先數(shù)組是線性表的一種實(shí)現(xiàn)。數(shù)組是由相同類(lèi)型元素組成的一種數(shù)據(jù)結(jié)構(gòu)，數(shù)組需要分配一段連續(xù)的內(nèi)存用來(lái)存儲(chǔ)。注意關(guān)鍵詞，相同類(lèi)型，連續(xù)內(nèi)存，像這樣。

不好意思放錯(cuò)圖了，像這樣。

上面的圖可以很直觀的體現(xiàn)數(shù)組的存儲(chǔ)結(jié)構(gòu)，因?yàn)閿?shù)組內(nèi)存地址連續(xù)，元素類(lèi)型固定，所有具有快速查找某個(gè)位置的元素的特性；同時(shí)也因?yàn)閿?shù)組需要一段連續(xù)內(nèi)存，所以長(zhǎng)度在初始化長(zhǎng)度已經(jīng)固定，且不能更改。Java 中的 ArrayList 本質(zhì)上就是一個(gè)數(shù)組的封裝。

鏈表

鏈表也是一種線性表，和數(shù)組不同的是鏈表不需要連續(xù)的內(nèi)存進(jìn)行數(shù)據(jù)存儲(chǔ)，而是在每個(gè)節(jié)點(diǎn)里同時(shí)存儲(chǔ)下一個(gè)節(jié)點(diǎn)的指針，又要注意關(guān)鍵詞了，每個(gè)節(jié)點(diǎn)都有一個(gè)指針指向下一個(gè)節(jié)點(diǎn)。那么這個(gè)鏈表應(yīng)該是什么樣子呢？看圖。

哦不，放錯(cuò)圖了，是這樣。

上圖很好的展示了鏈表的存儲(chǔ)結(jié)構(gòu)，圖中每個(gè)節(jié)點(diǎn)都有一個(gè)指針指向下一個(gè)節(jié)點(diǎn)位置，這種我們稱為單向鏈表；還有一種鏈表在每個(gè)節(jié)點(diǎn)上還有一個(gè)指針指向上一個(gè)節(jié)點(diǎn)，這種鏈表我們稱為雙向鏈表。圖我就不畫(huà)了，像下面這樣。

可以發(fā)現(xiàn)鏈表不必連續(xù)內(nèi)存存儲(chǔ)了，因?yàn)殒湵硎峭ㄟ^(guò)節(jié)點(diǎn)指針進(jìn)行下一個(gè)或者上一個(gè)節(jié)點(diǎn)的，只要找到頭節(jié)點(diǎn)，就可以以此找到后面一串的節(jié)點(diǎn)。不過(guò)也因此，鏈表在查找或者訪問(wèn)某個(gè)位置的節(jié)點(diǎn)時(shí)，需要**O(n)的時(shí)間復(fù)雜度。但是插入數(shù)據(jù)時(shí)可以達(dá)到O(1)**的復(fù)雜度，因?yàn)橹恍枰薷墓?jié)點(diǎn)指針指向。

ArratList

上面介紹了線性表的概念，并舉出了兩個(gè)線性表的實(shí)際實(shí)現(xiàn)例子，既數(shù)組和鏈表。在 Java 的集合類(lèi) ArrayList 里，實(shí)際上使用的就是數(shù)組存儲(chǔ)結(jié)構(gòu)，ArrayList 對(duì) Array 進(jìn)行了封裝，并增加了方便的插入、獲取、擴(kuò)容等操作。因?yàn)?ArrayList 的底層是數(shù)組，所以存取非常迅速，但是增刪時(shí)，因?yàn)橐苿?dòng)后面的元素位置，所以增刪效率相對(duì)較低。那么它具體是怎么實(shí)現(xiàn)的呢？不妨深入源碼一探究竟。

ArrayList 存儲(chǔ)結(jié)構(gòu)

查看 ArrayList 的源碼可以看到它就是一個(gè)簡(jiǎn)單的數(shù)組，用來(lái)數(shù)據(jù)存儲(chǔ)。

/**
?*?The?array?buffer?into?which?the?elements?of?the?ArrayList?are?stored.
?*?The?capacity?of?the?ArrayList?is?the?length?of?this?array?buffer.?Any
?*?empty?ArrayList?with?elementData?==?DEFAULTCAPACITY_EMPTY_ELEMENTDATA
?*?will?be?expanded?to?DEFAULT_CAPACITY?when?the?first?element?is?added.
?*/
transient?Object[]?elementData;?//?non-private?to?simplify?nested?class?access

/**
?*?Shared?empty?array?instance?used?for?default?sized?empty?instances.?We
?*?distinguish?this?from?EMPTY_ELEMENTDATA?to?know?how?much?to?inflate?when
?*?first?element?is?added.
?*/
private?static?final?Object[]?DEFAULTCAPACITY_EMPTY_ELEMENTDATA?=?{};

/**
?*?Default?initial?capacity.
?*/
private?static?final?int?DEFAULT_CAPACITY?=?10;

通過(guò)上面的注釋了解到，ArrayList 無(wú)參構(gòu)造時(shí)是會(huì)共享一個(gè)長(zhǎng)度為 0 的數(shù)組 DEFAULTCAPACITY_EMPTY_ELEMENTDATA. 只有當(dāng)?shù)谝粋€(gè)元素添加時(shí)才會(huì)第一次擴(kuò)容，這樣也防止了創(chuàng)建對(duì)象時(shí)更多的內(nèi)存浪費(fèi)。

ArrayList 擴(kuò)容機(jī)制

我們都知道數(shù)組的大小一但確定是不能改變的，那么 ArrayList 明顯可以不斷的添加元素，它的底層又是數(shù)組，它是怎么實(shí)現(xiàn)的呢？從上面的 ArrayList 存儲(chǔ)結(jié)構(gòu)以及注釋中了解到，ArrayList 在初始化時(shí)，是共享一個(gè)長(zhǎng)度為 0 的數(shù)組的，當(dāng)?shù)谝粋€(gè)元素添加進(jìn)來(lái)時(shí)會(huì)進(jìn)行第一次擴(kuò)容，我們可以想像出 ArrayList 每當(dāng)空間不夠使用時(shí)就會(huì)進(jìn)行一次擴(kuò)容，那么擴(kuò)容的機(jī)制是什么樣子的呢?

依舊從源碼開(kāi)始，追蹤 add() 方法的內(nèi)部實(shí)現(xiàn)。

/**
?*?Appends?the?specified?element?to?the?end?of?this?list.
?*
?*?@param?e?element?to?be?appended?to?this?list
?*?@return?true?(as?specified?by?{@link?Collection#add})
?*/
public?boolean?add(E?e)?{
????ensureCapacityInternal(size?+?1);??//?Increments?modCount!!
????elementData[size++]?=?e;
????return?true;
}
//?開(kāi)始檢查當(dāng)前插入位置時(shí)數(shù)組容量是否足夠
private?void?ensureCapacityInternal(int?minCapacity)?{
????//?ArrayList?是否未初始化，未初始化是則初始化?ArrayList?，容量給?10.
????if?(elementData?==?DEFAULTCAPACITY_EMPTY_ELEMENTDATA)?{
????????minCapacity?=?Math.max(DEFAULT_CAPACITY,?minCapacity);
????}
????ensureExplicitCapacity(minCapacity);
}
//?比較插入?index?是否大于當(dāng)前數(shù)組長(zhǎng)度，大于就?grow?進(jìn)行擴(kuò)容
private?void?ensureExplicitCapacity(int?minCapacity)?{
????modCount++;
????//?overflow-conscious?code
????if?(minCapacity?-?elementData.length?>?0)
????????grow(minCapacity);
}

/**
?*?Increases?the?capacity?to?ensure?that?it?can?hold?at?least?the
?*?number?of?elements?specified?by?the?minimum?capacity?argument.
?*
?*?@param?minCapacity?the?desired?minimum?capacity
?*/
private?void?grow(int?minCapacity)?{
????//?overflow-conscious?code
????int?oldCapacity?=?elementData.length;
????//?擴(kuò)容規(guī)則是當(dāng)前容量?+?當(dāng)前容量右移1位。也就是1.5倍。
????int?newCapacity?=?oldCapacity?+?(oldCapacity?>>?1);
????if?(newCapacity?-?minCapacity?0)
????????newCapacity?=?minCapacity;
????//?是否大于?Int?最大值，也就是容量最大值
????if?(newCapacity?-?MAX_ARRAY_SIZE?>?0)
????????newCapacity?=?hugeCapacity(minCapacity);
????//?minCapacity?is?usually?close?to?size,?so?this?is?a?win:
????//?拷貝元素到擴(kuò)充后的新的?ArrayList
????elementData?=?Arrays.copyOf(elementData,?newCapacity);
}

通過(guò)源碼發(fā)現(xiàn)擴(kuò)容邏輯還是比較簡(jiǎn)單的，整理下具體的擴(kuò)容流程如下：

1. 開(kāi)始檢查當(dāng)前插入位置時(shí)數(shù)組容量是否足夠

2. ArrayList 是否未初始化，未初始化是則初始化 ArrayList ，容量給 10.

3. 判斷當(dāng)前要插入的下標(biāo)是否大于容量

1. 不大于，插入新增元素，新增流程完畢。

4. 如果所需的容量大于當(dāng)前容量，開(kāi)始擴(kuò)充。

1. 擴(kuò)容規(guī)則是當(dāng)前容量 + 當(dāng)前容量右移1位。也就是1.5倍。

   int newCapacity = oldCapacity + (oldCapacity >> 1);

2. 如果擴(kuò)充之后還是小于需要的最小容量，則把所需最小容量作為容量。

3. 如果容量大于默認(rèn)最大容量，則使用 最大值 Integer 作為容量。

4. 拷貝老數(shù)組元素到擴(kuò)充后的新數(shù)組

5. 插入新增元素，新增流程完畢。

ArrayList ?數(shù)據(jù)新增

上面分析擴(kuò)容時(shí)候已經(jīng)看到了新增一個(gè)元素的具體邏輯，因?yàn)榈讓邮菙?shù)組，所以直接指定下標(biāo)賦值即可，非常簡(jiǎn)單。

public?boolean?add(E?e)?{
????ensureCapacityInternal(size?+?1);??//?Increments?modCount!!
????elementData[size++]?=?e;?//?直接賦值
????return?true;
}

但是還有一種新增數(shù)據(jù)得情況，就是新增時(shí)指定了要加入的下標(biāo)位置。這時(shí)邏輯有什么不同呢？

/**
?*?Inserts?the?specified?element?at?the?specified?position?in?this
?*?list.?Shifts?the?element?currently?at?that?position?(if?any)?and
?*?any?subsequent?elements?to?the?right?(adds?one?to?their?indices).
?*
?*?@param?index?index?at?which?the?specified?element?is?to?be?inserted
?*?@param?element?element?to?be?inserted
?*?@throws?IndexOutOfBoundsException?{@inheritDoc}
?*/
public?void?add(int?index,?E?element)?{
????rangeCheckForAdd(index);
????ensureCapacityInternal(size?+?1);??//?Increments?modCount!!
?????//?指定下標(biāo)開(kāi)始所有元素后移一位
????System.arraycopy(elementData,?index,?elementData,?index?+?1,size?-?index);
????elementData[index]?=?element;
????size++;
}

可以發(fā)現(xiàn)這種新增多了關(guān)鍵的一行，它的作用是把從要插入的坐標(biāo)開(kāi)始的元素都向后移動(dòng)一位，這樣才能給指定下標(biāo)騰出空間，才可以放入新增的元素。

比如你要在下標(biāo)為 3 的位置新增數(shù)據(jù)100，那么下標(biāo)為3開(kāi)始的所有元素都需要后移一位。

由此也可以看到 ArrayList 的一個(gè)缺點(diǎn)，隨機(jī)插入新數(shù)據(jù)時(shí)效率不高。

ArrayList 數(shù)據(jù)獲取

數(shù)據(jù)下標(biāo)獲取元素值，一步到位，不必多言。

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

LinkedList

LinkedList 的底層就是一個(gè)鏈表線性結(jié)構(gòu)了，鏈表除了要有一個(gè)節(jié)點(diǎn)對(duì)象外，根據(jù)單向鏈表和雙向鏈表的不同，還有一個(gè)或者兩個(gè)指針。那么 LinkedList 是單鏈表還是雙向鏈表呢？

LinkedList 存儲(chǔ)結(jié)構(gòu)

依舊深入 LinkedList 源碼一探究竟，可以看到 LinkedList 無(wú)參構(gòu)造里沒(méi)有任何操作，不過(guò)我們通過(guò)查看變量 first、last 可以發(fā)現(xiàn)它們就是存儲(chǔ)鏈表第一個(gè)和最后 一個(gè)的節(jié)點(diǎn)。

transient?int?size?=?0;
/**
?*?Pointer?to?first?node.
?*?Invariant:?(first?==?null?&&?last?==?null)?||
?*????????????(first.prev?==?null?&&?first.item?!=?null)
?*/
transient?Node?first;

/**
?*?Pointer?to?last?node.
?*?Invariant:?(first?==?null?&&?last?==?null)?||
?*????????????(last.next?==?null?&&?last.item?!=?null)
?*/
transient?Node?last;

/**
?*?Constructs?an?empty?list.
?*/
public?LinkedList()?{
}

變量 first 和 last 都是 Node 類(lèi)型，繼而查看 Node 源碼。

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

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

可以看到這就是一個(gè)典型的雙向鏈表結(jié)構(gòu)，item 用來(lái)存放元素值；next 指向下一個(gè) node 節(jié)點(diǎn)，prev 指向上一個(gè) node 節(jié)點(diǎn)。

LinkedList 數(shù)據(jù)獲取

鏈表不像數(shù)組是連續(xù)的內(nèi)存地址，鏈表是通過(guò)next 和 prev 指向記錄鏈接路徑的，所以查找指定位置的 node 只能遍歷查找，查看源碼也是如此。

public?E?get(int?index)?{
????checkElementIndex(index);
????return?node(index).item;
}
/**
?*?Returns?the?(non-null)?Node?at?the?specified?element?index.
?*/
//?遍歷查找?index?位置的節(jié)點(diǎn)信息
Node?node(int?index)?{
????//?assert?isElementIndex(index);
????//?這里判斷?index?是在當(dāng)前鏈表的前半部分還是后半部分，然后決定是從
????// first 向后查找還是從 last 向前查找。
????if?(index?>?1))?{
????????Node?x?=?first;
????????for?(int?i?=?0;?i?????????????x?=?x.next;
????????return?x;
????}?else?{
????????Node?x?=?last;
????????for?(int?i?=?size?-?1;?i?>?index;?i--)
????????????x?=?x.prev;
????????return?x;
????}
}

查找指定位置的 node 對(duì)象，這個(gè)部分要注意的是，查找會(huì)首先判斷 index 是在當(dāng)前鏈表的前半部分還是后半部分，然后決定是從 first 向后查找還是從 last 向前查找。這樣可以增加查找速度。從這里也可以看出鏈表在查找指定位置元素時(shí)，效率不高。

LinkedList 數(shù)據(jù)新增

因?yàn)?LinkedList 是鏈表，所以 LinkedList 的新增也就是鏈表的數(shù)據(jù)新增了，這時(shí)候要根據(jù)要插入的位置的區(qū)分操作。

1. 尾部插入

   public?boolean?add(E?e)?{
   ????linkLast(e);
   ????return?true;
   }
   void?linkLast(E?e)?{
   ????final?Node?l?=?last;
   ????//?新節(jié)點(diǎn)，prev?為當(dāng)前尾部節(jié)點(diǎn)，e為元素值，next?為?null，
   ????final?Node?newNode?=?new?Node<>(l,?e,?null);
   ????last?=?newNode;
   ????if?(l?==?null)
   ????????first?=?newNode;
   ????else
   ?????????//?目前的尾部節(jié)點(diǎn)?next?指向新的節(jié)點(diǎn)
   ????????l.next?=?newNode;
   ????size++;
   ????modCount++;
   }
   

   默認(rèn)的 add 方式就是尾部新增了，尾部新增的邏輯很簡(jiǎn)單，只需要?jiǎng)?chuàng)建一個(gè)新的節(jié)點(diǎn)，新節(jié)點(diǎn)的 prev 設(shè)置現(xiàn)有的末尾節(jié)點(diǎn)，現(xiàn)有的末尾 Node 指向新節(jié)點(diǎn) Node，新節(jié)點(diǎn)的 next 設(shè)為 null 即可。

2. 中間新增

   下面是在指定位置新增元素，涉及到的源碼部分。

   public?void?add(int?index,?E?element)?{
   ????checkPositionIndex(index);
   ????if?(index?==?size)
   ????????//?如果位置就是當(dāng)前鏈表尾部，直接尾插
   ????????linkLast(element);
   ????else
   ????????//?獲取?index?位置的節(jié)點(diǎn)，插入新的元素
   ????????linkBefore(element,?node(index));
   }
   
   /**
   ?*?Inserts?element?e?before?non-null?Node?succ.
   ?*/
   //?在指定節(jié)點(diǎn)處新增元素，修改指定元素的下一個(gè)節(jié)點(diǎn)為新增元素，新增元素的下一個(gè)節(jié)點(diǎn)是查找到得?node?的next節(jié)點(diǎn)指向，
   //?新增元素的上一個(gè)節(jié)點(diǎn)為查找到的?node?節(jié)點(diǎn)，查找到的?node?節(jié)點(diǎn)的?next?指向?node?的?prev?修改為新?Node
   void?linkBefore(E?e,?Node?succ)?{
   ????//?assert?succ?!=?null;
   ????final?Node?pred?=?succ.prev;
   ????final?Node?newNode?=?new?Node<>(pred,?e,?succ);
   ????succ.prev?=?newNode;
   ????if?(pred?==?null)
   ????????first?=?newNode;
   ????else
   ????????pred.next?=?newNode;
   ????size++;
   ????modCount++;
   }
   
   

   可以看到指定位置插入元素主要分為兩個(gè)部分，第一個(gè)部分是查找 node 節(jié)點(diǎn)部分，這部分就是上面介紹的 LinkedList 數(shù)據(jù)獲取部分，

   第二個(gè)部分是在查找到得 node 對(duì)象后插入元素。主要就是修改 node 的 next 指向?yàn)樾鹿?jié)點(diǎn)，新節(jié)點(diǎn)的 prev 指向?yàn)椴檎业降?node 節(jié)點(diǎn)，新節(jié)點(diǎn)的 next 指向?yàn)椴檎业降?node 節(jié)點(diǎn)的 next 指向。查找到的 node 節(jié)點(diǎn)的 next 指向的 node 節(jié)點(diǎn)的 prev 修改為新節(jié)點(diǎn)。

   

LinkedList 數(shù)據(jù)刪除

依舊查看源碼進(jìn)行分析，源碼中看到如果節(jié)點(diǎn)是頭結(jié)點(diǎn)或者尾節(jié)點(diǎn)，刪除比較簡(jiǎn)單。我們主要看刪除中間一個(gè)節(jié)點(diǎn)時(shí)的操作

public?E?remove(int?index)?{
????checkElementIndex(index);
????return?unlink(node(index));
}
/**
?*?Unlinks?non-null?node?x.
?*/
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;
}

node(index) 方法依舊是二分查找目標(biāo)位置，然后進(jìn)行刪除操作。比如要?jiǎng)h除的節(jié)點(diǎn)叫做 X，刪除操作主要是修改 X 節(jié)點(diǎn)的 prev 節(jié)點(diǎn)的 next 指向?yàn)?X 節(jié)點(diǎn)的 next 指向，修改 X 節(jié)點(diǎn)的 next 節(jié)點(diǎn)的 prev 指向?yàn)?X 節(jié)點(diǎn)的 prev 指向，最后把 X 節(jié)點(diǎn)的 prev 和 next 指向清空。如果理解起來(lái)有點(diǎn)費(fèi)勁，可以看下面這個(gè)圖，可能會(huì)比較明白。

擴(kuò)展

你以為 LinkedList 只是一個(gè) List，其他它不僅實(shí)現(xiàn)了 List 接口，還實(shí)現(xiàn)了 Deque ，所以它表面上是一個(gè) List，其實(shí)它還是一個(gè)隊(duì)列。

public?class?LinkedList<E>?extends?AbstractSequentialList<E>
????implements?List<E>,?Deque<E>,?Cloneable,?java.io.Serializable

體驗(yàn)一下先進(jìn)先出的隊(duì)列。

Queue?queue?=?new?LinkedList<>();
queue.add("a");
queue.add("b");
queue.add("c");
queue.add("d");
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());
// result：
//?a
//?b
//?c
//?d

同學(xué)可以思考一下這個(gè)隊(duì)列是怎么實(shí)現(xiàn)的，其實(shí)很簡(jiǎn)單對(duì)不對(duì)，就是先進(jìn)先出嘛，poll 時(shí)刪除 first 節(jié)點(diǎn)不就完事了嘛。

總結(jié)

不管是 ArrayList 還是 LinkedList 都是開(kāi)發(fā)中常用的集合類(lèi)，這篇文章分析了兩者的底層實(shí)現(xiàn)，通過(guò)對(duì)底層實(shí)現(xiàn)的分析我們可以總結(jié)出兩者的主要優(yōu)缺點(diǎn)。

1. 遍歷，ArrayList 每次都是直接定位，LinkedList 通過(guò) next 節(jié)點(diǎn)定位，不相上下。這里要注意的是 LinkedList ?只有使用迭代器的方式遍歷才會(huì)使用 next 節(jié)點(diǎn)。如果使用 get ，則因?yàn)楸闅v查找效率低下。
2. 新增，ArrayList 可能會(huì)需要擴(kuò)容，中間插入時(shí)，ArrayList 需要后移插入位置之后的所有元素。LinkedList 直接修改 node 的 prev, next 指向，LinkedList 勝出。
3. 刪除，同 2.
4. 隨機(jī)訪問(wèn)指定位置，ArrayList 直接定位，LinkedList 從頭會(huì)尾開(kāi)始查找，數(shù)組勝出。

綜上所述，ArrayList 適合存儲(chǔ)和訪問(wèn)數(shù)據(jù)，LinkedList 則更適合數(shù)據(jù)的處理，希望你以后在使用時(shí)可以合理的選擇 List 結(jié)構(gòu)。