前言

說真的，在 Java 使用最多的集合類中，List 絕對占有一席之地的，它和 Map 一樣適用于很多場景，非常方便我們的日常開發，畢竟存儲一個列表的需求隨處可見。盡管如此，還是有很多同學沒有弄明白 List 中 ArrayList 和 LinkedList 有什么區別，這簡直太遺憾了，這兩者其實都是數據結構中的基礎內容，這篇文章會從基礎概念開始，分析兩者在 Java 中的具體源碼實現，尋找兩者的不同之處，最后思考它們使用時的注意事項。

這篇文章會包含以下內容。

介紹線性表的概念，詳細介紹線性表中數組和鏈表的數據結構。

進行 ArrayList 的源碼分析，比如存儲結構、擴容機制、數據新增、數據獲取等。

進行 LinkedList 的源碼分析，比如它的存儲結構、數據插入、數據查詢、數據刪除和 LinkedList 作為隊列的使用方式等。

進行 ArrayList 和 LinkedList 的總結。

?

線性表

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

線性表是最基本、最簡單、也是最常用的一種數據結構。線性表（linear list）是數據結構的一種，一個線性表是n個具有相同特性的數據元素的有限序列。

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

線性表

看到這里你可能有疑問了，有線性表，那么肯定有非線性表嘍？沒錯。二叉樹和圖就是典型的非線性結構了。不要被這些花里胡哨的圖嚇到，其實這篇文章非常簡單，希望同學耐心看完點個贊。

非線性接口（圖片來自網絡）

數組

既然知道了什么是線性表，那么理解數組也就很容易了，首先數組是線性表的一種實現。數組是由相同類型元素組成的一種數據結構，數組需要分配一段連續的內存用來存儲。注意關鍵詞，相同類型，連續內存，像這樣。

數組

不好意思放錯圖了，像這樣。

數組概念

上面的圖可以很直觀的體現數組的存儲結構，因為數組內存地址連續，元素類型固定，所有具有快速查找某個位置的元素的特性；同時也因為數組需要一段連續內存，所以長度在初始化長度已經固定，且不能更改。Java 中的 ArrayList 本質上就是一個數組的封裝。

鏈表

鏈表也是一種線性表，和數組不同的是鏈表不需要連續的內存進行數據存儲，而是在每個節點里同時存儲下一個節點的指針，又要注意關鍵詞了，每個節點都有一個指針指向下一個節點。那么這個鏈表應該是什么樣子呢？看圖。

單向鏈表

哦不，放錯圖了，是這樣。

鏈表存儲結構（圖片來自網絡）

上圖很好的展示了鏈表的存儲結構，圖中每個節點都有一個指針指向下一個節點位置，這種我們稱為單向鏈表；還有一種鏈表在每個節點上還有一個指針指向上一個節點，這種鏈表我們稱為雙向鏈表。圖我就不畫了，像下面這樣。

雙向鏈表

可以發現鏈表不必連續內存存儲了，因為鏈表是通過節點指針進行下一個或者上一個節點的，只要找到頭節點，就可以以此找到后面一串的節點。不過也因此，鏈表在查找或者訪問某個位置的節點時，需要**O(n)的時間復雜度。但是插入數據時可以達到O(1)**的復雜度，因為只需要修改節點指針指向。

?

ArratList

上面介紹了線性表的概念，并舉出了兩個線性表的實際實現例子，既數組和鏈表。在 Java 的集合類 ArrayList 里，實際上使用的就是數組存儲結構，ArrayList 對 Array 進行了封裝，并增加了方便的插入、獲取、擴容等操作。因為 ArrayList 的底層是數組，所以存取非常迅速，但是增刪時，因為要移動后面的元素位置，所以增刪效率相對較低。那么它具體是怎么實現的呢？不妨深入源碼一探究竟。

ArrayList 存儲結構

查看 ArrayList 的源碼可以看到它就是一個簡單的數組，用來數據存儲。

/***?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;

通過上面的注釋了解到，ArrayList 無參構造時是會共享一個長度為 0 的數組 DEFAULTCAPACITY_EMPTY_ELEMENTDATA. 只有當第一個元素添加時才會第一次擴容，這樣也防止了創建對象時更多的內存浪費。

ArrayList 擴容機制

我們都知道數組的大小一但確定是不能改變的，那么 ArrayList 明顯可以不斷的添加元素，它的底層又是數組，它是怎么實現的呢？從上面的 ArrayList 存儲結構以及注釋中了解到，ArrayList 在初始化時，是共享一個長度為 0 的數組的，當第一個元素添加進來時會進行第一次擴容，我們可以想像出 ArrayList 每當空間不夠使用時就會進行一次擴容，那么擴容的機制是什么樣子的呢?

依舊從源碼開始，追蹤 add() 方法的內部實現。

/***?Appends?the?specified?element?to?the?end?of?this?list.**?@param?e?element?to?be?appended?to?this?list*?@return?<tt>true</tt>?(as?specified?by?{@link?Collection#add})*/ public?boolean?add(E?e)?{ensureCapacityInternal(size?+?1);??//?Increments?modCount!!elementData[size++]?=?e;return?true; } //?開始檢查當前插入位置時數組容量是否足夠 private?void?ensureCapacityInternal(int?minCapacity)?{//?ArrayList?是否未初始化，未初始化是則初始化?ArrayList?，容量給?10.if?(elementData?==?DEFAULTCAPACITY_EMPTY_ELEMENTDATA)?{minCapacity?=?Math.max(DEFAULT_CAPACITY,?minCapacity);}ensureExplicitCapacity(minCapacity); } //?比較插入?index?是否大于當前數組長度，大于就?grow?進行擴容 private?void?ensureExplicitCapacity(int?minCapacity)?{modCount++;//?overflow-conscious?codeif?(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?codeint?oldCapacity?=?elementData.length;//?擴容規則是當前容量?+?當前容量右移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://?拷貝元素到擴充后的新的?ArrayListelementData?=?Arrays.copyOf(elementData,?newCapacity); }

通過源碼發現擴容邏輯還是比較簡單的，整理下具體的擴容流程如下：

開始檢查當前插入位置時數組容量是否足夠

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

判斷當前要插入的下標是否大于容量

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

如果所需的容量大于當前容量，開始擴充。

擴容規則是當前容量 + 當前容量右移1位。也就是1.5倍。

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

如果擴充之后還是小于需要的最小容量，則把所需最小容量作為容量。

如果容量大于默認最大容量，則使用 最大值 Integer 作為容量。

拷貝老數組元素到擴充后的新數組

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

ArrayList ?數據新增

上面分析擴容時候已經看到了新增一個元素的具體邏輯，因為底層是數組，所以直接指定下標賦值即可，非常簡單。

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

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

/***?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!!//?指定下標開始所有元素后移一位System.arraycopy(elementData,?index,?elementData,?index?+?1,size?-?index);elementData[index]?=?element;size++; }

可以發現這種新增多了關鍵的一行，它的作用是把從要插入的坐標開始的元素都向后移動一位，這樣才能給指定下標騰出空間，才可以放入新增的元素。

比如你要在下標為 3 的位置新增數據100，那么下標為3開始的所有元素都需要后移一位。

ArrayList 隨機新增數據

由此也可以看到 ArrayList 的一個缺點，隨機插入新數據時效率不高。

ArrayList 數據獲取

數據下標獲取元素值，一步到位，不必多言。

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

?

LinkedList

LinkedList 的底層就是一個鏈表線性結構了，鏈表除了要有一個節點對象外，根據單向鏈表和雙向鏈表的不同，還有一個或者兩個指針。那么 LinkedList 是單鏈表還是雙向鏈表呢？

LinkedList 存儲結構

依舊深入 LinkedList 源碼一探究竟，可以看到 LinkedList 無參構造里沒有任何操作，不過我們通過查看變量 first、last 可以發現它們就是存儲鏈表第一個和最后 一個的節點。

transient?int?size?=?0; /***?Pointer?to?first?node.*?Invariant:?(first?==?null?&&?last?==?null)?||*????????????(first.prev?==?null?&&?first.item?!=?null)*/ transient?Node<E>?first;/***?Pointer?to?last?node.*?Invariant:?(first?==?null?&&?last?==?null)?||*????????????(last.next?==?null?&&?last.item?!=?null)*/ transient?Node<E>?last;/***?Constructs?an?empty?list.*/ public?LinkedList()?{ }

變量 first 和 last 都是 Node 類型，繼而查看 Node 源碼。

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

可以看到這就是一個典型的雙向鏈表結構，item 用來存放元素值；next 指向下一個 node 節點，prev 指向上一個 node 節點。

雙向鏈表（圖片來自 appcoda.com）

LinkedList 數據獲取

鏈表不像數組是連續的內存地址，鏈表是通過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?位置的節點信息 Node<E>?node(int?index)?{//?assert?isElementIndex(index);//?這里判斷?index?是在當前鏈表的前半部分還是后半部分，然后決定是從// first 向后查找還是從 last 向前查找。if?(index?<?(size?>>?1))?{Node<E>?x?=?first;for?(int?i?=?0;?i?<?index;?i++)x?=?x.next;return?x;}?else?{Node<E>?x?=?last;for?(int?i?=?size?-?1;?i?>?index;?i--)x?=?x.prev;return?x;} }

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

LinkedList 數據新增

因為 LinkedList 是鏈表，所以 LinkedList 的新增也就是鏈表的數據新增了，這時候要根據要插入的位置的區分操作。

尾部插入

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

默認的 add 方式就是尾部新增了，尾部新增的邏輯很簡單，只需要創建一個新的節點，新節點的 prev 設置現有的末尾節點，現有的末尾 Node 指向新節點 Node，新節點的 next 設為 null 即可。

中間新增

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

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

可以看到指定位置插入元素主要分為兩個部分，第一個部分是查找 node 節點部分，這部分就是上面介紹的 LinkedList 數據獲取部分，

第二個部分是在查找到得 node 對象后插入元素。主要就是修改 node 的 next 指向為新節點，新節點的 prev 指向為查找到的 node 節點，新節點的 next 指向為查找到的 node 節點的 next 指向。查找到的 node 節點的 next 指向的 node 節點的 prev 修改為新節點。

LinkedLst 插入元素

LinkedList 數據刪除

依舊查看源碼進行分析，源碼中看到如果節點是頭結點或者尾節點，刪除比較簡單。我們主要看刪除中間一個節點時的操作

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

node(index) 方法依舊是二分查找目標位置，然后進行刪除操作。比如要刪除的節點叫做 X，刪除操作主要是修改 X 節點的 prev 節點的 next 指向為 X 節點的 next 指向，修改 X 節點的 next 節點的 prev 指向為 X 節點的 prev 指向，最后把 X 節點的 prev 和 next 指向清空。如果理解起來有點費勁，可以看下面這個圖，可能會比較明白。

LinkedList 刪除數據

擴展

你以為 LinkedList 只是一個 List，其他它不僅實現了 List 接口，還實現了 Deque ，所以它表面上是一個 List，其實它還是一個隊列。

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

體驗一下先進先出的隊列。

Queue<String>?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

同學可以思考一下這個隊列是怎么實現的，其實很簡單對不對，就是先進先出嘛，poll 時刪除 first 節點不就完事了嘛。

?

總結

不管是 ArrayList 還是 LinkedList 都是開發中常用的集合類，這篇文章分析了兩者的底層實現，通過對底層實現的分析我們可以總結出兩者的主要優缺點。

遍歷，ArrayList 每次都是直接定位，LinkedList 通過 next 節點定位，不相上下。這里要注意的是 LinkedList ?只有使用迭代器的方式遍歷才會使用 next 節點。如果使用 get ，則因為遍歷查找效率低下。

新增，ArrayList 可能會需要擴容，中間插入時，ArrayList 需要后移插入位置之后的所有元素。LinkedList 直接修改 node 的 prev, next 指向，LinkedList 勝出。

刪除，同 2.

隨機訪問指定位置，ArrayList 直接定位，LinkedList 從頭會尾開始查找，數組勝出。

綜上所述，ArrayList 適合存儲和訪問數據，LinkedList 則更適合數據的處理，希望你以后在使用時可以合理的選擇 List 結構。

有道無術，術可成；有術無道，止于術

歡迎大家關注Java之道公眾號

好文章，我在看??

總結

以上是生活随笔為你收集整理的ArrayList和LinkedList如何实现的？我看你还有机会！的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。