1.概述

LinkedList 是 Java 集合框架中一個重要的實現，其底層采用的雙向鏈表結構。和 ArrayList 一樣，LinkedList 也支持空值和重復值。由于 LinkedList 基于鏈表實現，存儲元素過程中，無需像 ArrayList 那樣進行擴容。但有得必有失，LinkedList 存儲元素的節點需要額外的空間存儲前驅和后繼的引用。另一方面，LinkedList 在鏈表頭部和尾部插入效率比較高，但在指定位置進行插入時，效率一般。原因是，在指定位置插入需要定位到該位置處的節點，此操作的時間復雜度為O(N)。最后，LinkedList 是非線程安全的集合類，并發環境下，多個線程同時操作 LinkedList，會引發不可預知的錯誤。

以上是對 LinkedList 的簡單介紹，接下來，我將會對 LinkedList 常用操作展開分析，繼續往下看吧。

?2.繼承體系

LinkedList 的繼承體系較為復雜，繼承自 AbstractSequentialList，同時又實現了 List 和 Deque 接口。繼承體系圖如下（刪除了部分實現的接口）：

LinkedList 繼承自 AbstractSequentialList，AbstractSequentialList 又是什么呢？從實現上，AbstractSequentialList 提供了一套基于順序訪問的接口。通過繼承此類，子類僅需實現部分代碼即可擁有完整的一套訪問某種序列表（比如鏈表）的接口。深入源碼，AbstractSequentialList 提供的方法基本上都是通過 ListIterator 實現的，比如：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

public E get(int index) {try {return listIterator(index).next();} catch (NoSuchElementException exc) {throw new IndexOutOfBoundsException("Index: "+index);} }public void add(int index, E element) {try {listIterator(index).add(element);} catch (NoSuchElementException exc) {throw new IndexOutOfBoundsException("Index: "+index);} }// 留給子類實現 public abstract ListIterator<E> listIterator(int index);

所以只要繼承類實現了 listIterator 方法，它不需要再額外實現什么即可使用。對于隨機訪問集合類一般建議繼承 AbstractList 而不是 AbstractSequentialList。LinkedList 和其父類一樣，也是基于順序訪問。所以 LinkedList 繼承了 AbstractSequentialList，但 LinkedList 并沒有直接使用父類的方法，而是重新實現了一套的方法。

另外，LinkedList 還實現了 Deque (double ended queue)，Deque 又繼承自 Queue 接口。這樣 LinkedList 就具備了隊列的功能。比如，我們可以這樣使用：

1	Queue<T> queue = new LinkedList<>();

除此之外，我們基于 LinkedList 還可以實現一些其他的數據結構，比如棧，以此來替換 Java 集合框架中的 Stack 類（該類實現的不好，《Java 編程思想》一書的作者也對此類進行了吐槽）。

關于 LinkedList 繼承體系先說到這，下面進入源碼分析部分。

?3.源碼分析

?3.1 查找

LinkedList 底層基于鏈表結構，無法向 ArrayList 那樣隨機訪問指定位置的元素。LinkedList 查找過程要稍麻煩一些，需要從鏈表頭結點（或尾節點）向后查找，時間復雜度為?O(N)。相關源碼如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

public E get(int index) {checkElementIndex(index);return node(index).item; }Node<E> node(int index) {/** 則從頭節點開始查找，否則從尾節點查找* 查找位置 index 如果小于節點數量的一半，*/ if (index < (size >> 1)) {Node<E> x = first;// 循環向后查找，直至 i == indexfor (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;} }

上面的代碼比較簡單，主要是通過遍歷的方式定位目標位置的節點。獲取到節點后，取出節點存儲的值返回即可。這里面有個小優化，即通過比較 index 與節點數量 size/2 的大小，決定從頭結點還是尾節點進行查找。查找操作的代碼沒什么復雜的地方，這里先講到這里。

?3.2 遍歷

鏈表的遍歷過程也很簡單，和上面查找過程類似，我們從頭節點往后遍歷就行了。但對于 LinkedList 的遍歷還是需要注意一些，不然可能會導致代碼效率低下。通常情況下，我們會使用 foreach 遍歷 LinkedList，而 foreach 最終轉換成迭代器形式。所以分析 LinkedList 的遍歷的核心就是它的迭代器實現，相關代碼如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

public ListIterator<E> listIterator(int index) {checkPositionIndex(index);return new ListItr(index); }private class ListItr implements ListIterator<E> {private Node<E> lastReturned;private Node<E> next;private int nextIndex;private int expectedModCount = modCount;/** 構造方法將 next 引用指向指定位置的節點 */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; // 調用 next 方法后，next 引用都會指向他的后繼節點nextIndex++;return lastReturned.item;}// 省略部分方法 }

上面的方法很簡單，大家應該都能很快看懂，這里就不多說了。下面來說說遍歷 LinkedList 需要注意的一個點。

我們都知道 LinkedList 不擅長隨機位置訪問，如果大家用隨機訪問的方式遍歷 LinkedList，效率會很差。比如下面的代碼：

1 2 3 4 5 6 7 8

List<Integet> list = new LinkedList<>(); list.add(1) list.add(2) ...... for (int i = 0; i < list.size(); i++) {Integet item = list.get(i);// do something }

當鏈表中存儲的元素很多時，上面的遍歷方式對于效率來說就是災難。原因在于，通過上面的方式每獲取一個元素，LinkedList 都需要從頭節點（或尾節點）進行遍歷，效率不可謂不低。在我的電腦（MacBook Pro Early 2015, 2.7 GHz Intel Core i5）實測10萬級的數據量，耗時約7秒鐘。20萬級的數據量耗時達到了約34秒的時間。50萬級的數據量耗時約250秒。從測試結果上來看，上面的遍歷方式在大數據量情況下，效率很差。大家在日常開發中應該盡量避免這種用法。

?3.3 插入

LinkedList 除了實現了 List 接口相關方法，還實現了 Deque 接口的很多方法，所以我們有很多種方式插入元素。但這里，我只打算分析 List 接口中相關的插入方法，其他的方法大家自己看吧。LinkedList 插入元素的過程實際上就是鏈表鏈入節點的過程，學過數據結構的同學對此應該都很熟悉了。這里簡單分析一下，先看源碼吧：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

/** 在鏈表尾部插入元素 */ public boolean add(E e) {linkLast(e);return true; }/** 在鏈表指定位置插入元素 */ public void add(int index, E element) {checkPositionIndex(index);// 判斷 index 是不是鏈表尾部位置，如果是，直接將元素節點插入鏈表尾部即可if (index == size)linkLast(element);elselinkBefore(element, node(index)); }/** 將元素節點插入到鏈表尾部 */ void linkLast(E e) {final Node<E> l = last;// 創建節點，并指定節點前驅為鏈表尾節點 last，后繼引用為空final Node<E> newNode = new Node<>(l, e, null);// 將 last 引用指向新節點last = newNode;// 判斷尾節點是否為空，為空表示當前鏈表還沒有節點if (l == null)first = newNode;elsel.next = newNode; // 讓原尾節點后繼引用 next 指向新的尾節點size++;modCount++; }/** 將元素節點插入到 succ 之前的位置 */ void linkBefore(E e, Node<E> succ) {// assert succ != null;final Node<E> pred = succ.prev;// 1. 初始化節點，并指明前驅和后繼節點final Node<E> newNode = new Node<>(pred, e, succ);// 2. 將 succ 節點前驅引用 prev 指向新節點succ.prev = newNode;// 判斷尾節點是否為空，為空表示當前鏈表還沒有節點 if (pred == null)first = newNode;elsepred.next = newNode; // 3. succ 節點前驅的后繼引用指向新節點size++;modCount++; }

上面是插入過程的源碼，我對源碼進行了比較詳細的注釋，應該不難看懂。上面兩個 add 方法只是對操作鏈表的方法做了一層包裝，核心邏輯在 linkBefore 和 linkLast 中。這里以 linkBefore 為例，它的邏輯流程如下：

創建新節點，并指明新節點的前驅和后繼

將 succ 的前驅引用指向新節點

如果 succ 的前驅不為空，則將 succ 前驅的后繼引用指向新節點

對應于下圖：

以上就是插入相關的源碼分析，并不復雜，就不多說了。繼續往下分析。

?3.4 刪除

如果大家看懂了上面的插入源碼分析，那么再看刪除操作實際上也很簡單了。刪除操作通過解除待刪除節點與前后節點的鏈接，即可完成任務。過程比較簡單，看源碼吧：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

public boolean remove(Object o) {if (o == null) {for (Node<E> x = first; x != null; x = x.next) {if (x.item == null) {unlink(x);return true;}}} else {// 遍歷鏈表，找到要刪除的節點for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item)) {unlink(x); // 將節點從鏈表中移除return true;}}}return false; }public E remove(int index) {checkElementIndex(index);// 通過 node 方法定位節點，并調用 unlink 將節點從鏈表中移除return unlink(node(index)); }/** 將某個節點從鏈表中移除 */ 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;// prev 為空，表明刪除的是頭節點if (prev == null) {first = next;} else {// 將 x 的前驅的后繼指向 x 的后繼prev.next = next;// 將 x 的前驅引用置空，斷開與前驅的鏈接x.prev = null;}// next 為空，表明刪除的是尾節點if (next == null) {last = prev;} else {// 將 x 的后繼的前驅指向 x 的前驅next.prev = prev;// 將 x 的后繼引用置空，斷開與后繼的鏈接x.next = null;}// 將 item 置空，方便 GC 回收x.item = null;size--;modCount++;return element; }

和插入操作一樣，刪除操作方法也是對底層方法的一層保證，核心邏輯在底層 unlink 方法中。所以長驅直入，直接分析 unlink 方法吧。unlink 方法的邏輯如下（假設刪除的節點既不是頭節點，也不是尾節點）：

將待刪除節點 x 的前驅的后繼指向 x 的后繼

將待刪除節點 x 的前驅引用置空，斷開與前驅的鏈接

將待刪除節點 x 的后繼的前驅指向 x 的前驅

將待刪除節點 x 的后繼引用置空，斷開與后繼的鏈接

對應下圖：

結合上圖，理解 LInkedList 刪除操作應該不難。好了，LinkedList 的刪除源碼分析就講到這。

?4.總結

通過上面的分析，大家對 LinkedList 的底層實現應該很清楚了。總體來看 LinkedList 的源碼并不復雜，大家耐心看一下，一般都能看懂。同時，通過本文，向大家展現了使用 LinkedList 的一個坑，希望大家在開發中盡量避免。好了，本文到這里就結束了，感謝閱讀！

• 本文鏈接：?https://www.tianxiaobo.com/2018/01/31/LinkedList-源碼分析-JDK-1-8/

from:?http://www.tianxiaobo.com/2018/01/31/LinkedList-%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90-JDK-1-8/?

總結

以上是生活随笔為你收集整理的LinkedList 源码分析(JDK 1.8)的全部內容，希望文章能夠幫你解決所遇到的問題。

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