LinkedList源碼分析（jdk1.8）

• 2019 年 10 月 3 日
• 筆記

LinkedList概述

​ LinkedList 是 Java 集合框架中一個重要的實現，我們先簡述一下LinkedList的一些特點：

• LinkedList底層採用的雙向鏈表結構；
• LinkedList支援空值和重複值(List的特點)；
• LinkedList實現Deque介面，具有雙端隊列的特性，也可以作為棧來使用；
• LinkedList存儲元素過程中，無需像 ArrayList 那樣進行擴容，但存儲元素的節點需要額外的空間存儲前驅和後繼的引用；
• LinkedList在鏈表頭部和尾部插入效率比較高，但在指定位置進行插入時，需要定位到該位置處的節點，此操作的時間複雜度為O(N)；
• LinkedList是非執行緒安全的集合類，並發環境下，多個執行緒同時操作 LinkedList，會引發不可預知的異常錯誤。

LinkedList繼承體系

​ 直接通過idea查看一下LinkedList的繼承體系，體系結構比較複雜，一點點看。

• 繼承自 AbstractSequentialList；
• 實現了 List 和 Deque 介面；
• 實現序列化介面；
• 實現了Cloneable介面

​ 這裡簡單說一下AbstractSequentialList這個類，該類提供一套基本的基於順序訪問的介面，通過繼承此類，子類僅需實現部分程式碼即可擁有完整的一套訪問某種序列表（比如鏈表）的介面。AbstractSequentialList 提供的方法基本上都是通過 ListIterator 實現的，比如下面的get和add方法。但是雖然LinkedList 繼承了 AbstractSequentialList，卻並沒有直接使用父類的方法，而是重新實現了一套的方法，後面我們會講到這些方法的實現。

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

​ 另外的就是文章開頭概述的，LinkedList實現了Deque介面，具有雙端隊列的特點。

LinkedList的成員屬性

//記錄鏈表中的實際元素個數  transient int size = 0;  //維護鏈表的首結點引用  transient Node<E> first;  //維護鏈表的尾節點引用  transient Node<E> last;

可以看到first和last都是Node類型的，所以我們簡單看一下LinkedList中的這個內部類

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

​ 可以看到Node這個靜態內部類的結構也是比較簡單的，每個結點維護的就是自己存儲的元素資訊+前驅結點引用+後繼節點引用。這裡就不做過多的闡述，下面簡單看看LinkedList的構造方法

LinkedList的構造方法

//構造一個空的集合（鏈表為空）  public LinkedList() {  }  //先調用自己的無參構造方法構造一個空的集合，然後將Collection集合中的所有元素加入該鏈表中  //如果傳入的Collection為空，會拋出空指針異常  public LinkedList(Collection<? extends E> c) {      this();      addAll(c);  }

LinkedList的主要方法

add方法

LinkedList實現的添加方法主要有下面幾種

• 在鏈表尾部添加結點（linkLast方法）

• 在鏈表首部添加元素（linkFirst方法）

• 在鏈表中間添加元素（linkBefore方法）

下面我們看看這三種方法的實現。

（1）linkLast方法

public void addLast(E e) {      linkLast(e);  }

​ 在addLast方法中直接就是調用了linkLast方法實現結點的添加（沒有返回值，所以add方法一定是返回true的），所以下面我們看看這個方法：

void linkLast(E e) {      //（1）獲得當前鏈表實例的全局後繼節點      final Node<E> l = last;      //（2）創建一個新的結點，從Node的構造方法我們就能知道      //這個新的結點中存放的元素item為當前傳入的泛型引用，前驅結點為全局後繼結點，後繼節點為null      //(即相當於要將這個新節點作為鏈表的新的後繼節點)      final Node<E> newNode = new Node<>(l, e, null);// Node(Node<E> prev, E element, Node<E> next){}      //（3）更新全局後繼節點的引用      last = newNode;      //（4）如果原鏈表的後繼結點為null，那麼也需要將全局頭節點引用指向這個新的結點      if (l == null)          first = newNode;      //（5）不為null，因為是雙向鏈表，創建新節點的時候只是將newNode的prev設置為原last結點。這裡就需要將原last      //結點的後繼結點設置為newNode      else          l.next = newNode;      //（6）更新當前鏈表中的size個數      size++;      //（7）這裡是fast-fail機制使用的參數      modCount++;  }

​ 我們通過一個示例圖來簡單模擬這個過程

• 當鏈表初始時為空的時候，我么調用add方法添加一個新的結點

• 鏈表不為空，此時調用add方法在鏈表尾部添加結點的時候

（2）linkFirst方法

​ 該方法是一個private方法，通過addFirst方法調用暴露給使用者。

public void addFirst(E e) {      linkFirst(e);  }

​ 我們還是主要看看linkFirst方法的實現邏輯

private void linkFirst(E e) {      //（1）獲取全局頭節點      final Node<E> f = first;      //（2）創建一個新節點，其前驅結點為null，後繼結點為當前的全局首結點      final Node<E> newNode = new Node<>(null, e, f);      //（3）更新全局首結點引用      first = newNode;      //（4）如果首結點為null，last結點指向新建的結點      if (f == null)          last = newNode;      //（5）不為null，原頭節點的前驅結點為newNode      else          f.prev = newNode;      size++;      modCount++;  }

​ 上面的邏輯也比較簡單，就是將新添加的結點設置為頭節點，然後更新鏈表中結點之間的指向，我們通過下面這個圖簡單理解一下（鏈表初始為null就不做演示了，和上面圖示的差不多，這裡假設已經存在結點）

（3）linkBefore方法

public void add(int index, E element) {      //檢查index的合法性：大於等於0小於等於size，不合法會拋出異常      checkPositionIndex(index);      //index等於size，就在尾部插入新節點，linkLast方法上面說到過      if (index == size)          linkLast(element);      //否則就在指定index處插入結點，先找到index處的結點（調用的是node(index方法)）      else          linkBefore(element, node(index));  }  private void checkPositionIndex(int index) {      if (!isPositionIndex(index))          throw new IndexOutOfBoundsException(outOfBoundsMsg(index));  }  private boolean isPositionIndex(int index) {      return index >= 0 && index <= size;  }

​ add(index,element)方法中主要的邏輯還是linkBefore，我們下面看看這個方法，在此之前調用的是node(index)方法，找到index處的結點

Node<E> node(int index) {      //index < size/2 （index在鏈表的前半部分）      if (index < (size >> 1)) {          //使用全局頭節點去查找（遍歷鏈表）          Node<E> x = first;          for (int i = 0; i < index; i++)              x = x.next;          return x;      } else {          //index > size / 2 （index在鏈表的後半部分）          Node<E> x = last;          //使用全局尾節點向前查找          for (int i = size - 1; i > index; i--)              x = x.prev;          return x;      }  }

​ node方法實現利用雙向鏈表以及記錄了鏈表總長度的這兩個特點，分為前後兩部分去遍歷查詢jindex位置處的結點。查找這個結點後，就會作為參數調用linkBefore方法，如下所示

void linkBefore(E e, Node<E> succ) {      //succ != null;succ就是指定位置處的結點      //傳入的結點element=succ      final Node<E> pred = succ.prev;      //創建新的結點      //前驅結點是傳入的結點的前驅結點      //後繼結點是傳入的結點      final Node<E> newNode = new Node<>(pred, e, succ);      //更新index處結點的前驅結點引用      succ.prev = newNode;      //index處結點的前驅結點為null，那麼就相當於在頭部插入結點，並且更新first      if (pred == null)          first = newNode;      //不為null，那麼它的後繼結點就是新的結點      else          pred.next = newNode;      size++;      modCount++;  }

​ 這個方法的邏輯也比較簡單，就是在succ和succ.prev兩個結點之間插入一個新的結點，我們通過簡單的圖示理解這個過程

刪除

​ 作為雙端隊列，刪除元素也有兩種方式隊列首刪除元素、隊列尾刪除元素；作為List，又要支援中間刪除元素，所以刪除元素一個有三個方法。

（1）unlinkFirst方法

​ 下面是調用unlinkFirst方法的兩個public方法（Deque介面的方法實現），主要區別就是removeFirst方法執行時候，first為null的時候會拋出異常，而pollFirst返回null。

// remove的時候如果沒有元素拋出異常  public E removeFirst() {      final Node<E> f = first;      if (f == null)          throw new NoSuchElementException();      return unlinkFirst(f);  }  // poll的時候如果沒有元素返回null  public E pollFirst() {      final Node<E> f = first;      return (f == null) ? null : unlinkFirst(f);  }

​ 主要還是看unlinkFirst這個方法的實現

private E unlinkFirst(Node<E> f) {      // assert f == first && f != null;      //獲取頭結點的元素值      final E element = f.item;      //獲取頭結點的後繼結點      final Node<E> next = f.next;      //刪除頭節點中存放的元素item和後繼結點，GC      f.item = null;      f.next = null; // help GC      //更新頭節點引用（原頭節點的後繼結點）      first = next;      //鏈表中只有一個結點，那麼尾節點也是null了      if (next == null)          last = null;      //將新的頭節點的前驅結點設置為null      else          next.prev = null;      //更新size和modCount      size--;      modCount++;      //返回原頭節點的值      return element;  }

（2）unlinkLast方法

​ 下面是調用unlinkLast方法的兩個public方法（Deque介面的方法實現），主要區別就是removeLast方法執行時候，first為null的時候會拋出異常，而pollLast返回null。

// remove的時候如果沒有元素拋出異常  public E removeLast() {      final Node<E> l = last;      if (l == null)          throw new NoSuchElementException();      return unlinkLast(l);  }    // poll的時候如果沒有元素返回null  public E pollLast() {      final Node<E> l = last;      return (l == null) ? null : unlinkLast(l);  }

​ 下面是unlinkLast方法的實現

// 刪除尾節點  private E unlinkLast(Node<E> l) {      // 尾節點的元素值      final E element = l.item;      // 尾節點的前置指針      final Node<E> prev = l.prev;      // 清空尾節點的內容，協助GC      l.item = null;      l.prev = null; // help GC      // 讓前置節點成為新的尾節點      last = prev;      // 如果只有一個元素，刪除了把first置為空      // 否則把前置節點的next置為空      if (prev == null)          first = null;      else          prev.next = null;      // 更新size和modCount      size--;      modCount++;      // 返回刪除的元素      return element;  }

（4）unlink方法

// 刪除中間節點  public E remove(int index) {      // 檢查是否越界      checkElementIndex(index);      // 刪除指定index位置的節點      return unlink(node(index));  }

// 刪除指定節點x  E unlink(Node<E> x) {      // x的元素值      final E element = x.item;      // x的前置節點      final Node<E> next = x.next;      // x的後置節點      final Node<E> prev = x.prev;      // 如果前置節點為空      // 說明是首節點，讓first指向x的後置節點      // 否則修改前置節點的next為x的後置節點      if (prev == null) {          first = next;      } else {          prev.next = next;          x.prev = null;      }      // 如果後置節點為空      // 說明是尾節點，讓last指向x的前置節點      // 否則修改後置節點的prev為x的前置節點      if (next == null) {          last = prev;      } else {          next.prev = prev;          x.next = null;      }      // 清空x的元素值，協助GC      x.item = null;      // 元素個數減1      size--;      // 修改次數加1      modCount++;      // 返回刪除的元素      return element;  }

查找

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

public E get(int index) {      checkElementIndex(index); //還是先檢驗index的合法性，這裡上面已經說過      //調用node方法遍歷查詢index處的結點，然後返回結點存放的值item，node方法上面已經說過      return node(index).item;  }

遍歷

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

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;          nextIndex++;          return lastReturned.item;      }      //...other method  }

​ 這裡主要說下遍歷 LinkedList 需要注意的一個點。LinkedList 不擅長隨機位置訪問，如果大家用隨機訪問的方式遍歷 LinkedList，效率會很差。比如下面的程式碼：

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  }

​ 當鏈表中存儲的元素很多時，上面的遍歷方式對於效率肯定是非常低的。原因在於，通過上面的方式每獲取一個元素(調用get(i)方法，上面說到了這個方法的實現)，LinkedList 都需要從頭節點（或尾節點）進行遍歷(node()方法的實現)，效率低，上面的遍歷方式在大數據量情況下，效率很差。在日常使用中應該盡量避免這種用法。

總結

最後總結一下面試常問的ArrayList和LinkedList的區別，關於ArrayList請參考我上一篇ArrayList源碼分析。

• ArrayList是基於動態數組實現的，LinkedList是基於雙向鏈表實現的；

• 對於隨機訪問來說，ArrayList(數組下標訪問)要優於LinkedList(遍歷鏈表訪問)；

• 不考慮直接在尾部添加數據的話，ArrayList按照指定的index添加/刪除數據是通過複製數組實現。LinkedList通過定址改變節點指向實現；所以添加元素的話LinkedList（改變結點的next和prev指向即可）要優於ArrayList（移動數組元素）。

• LinkedList在數據存儲上不存在浪費空間的情況。ArrayList動態擴容會導致有一部分空間是浪費的。