Java集合乾貨——LinkedList源碼分析

前言在上篇文章中我們對ArrayList對了詳細的分析，今天我們來說一說LinkedList。他們之間有什麼區別呢？最大的區別就是底層數據結構的實現不一樣，ArrayList是數組實現的（具體看上一篇文章），LinedList是鏈表實現的。至於其他的一些區別，可以說大部分都是由於本質不同衍生出來的 ...

前言

在上篇文章中我們對ArrayList對了詳細的分析，今天我們來說一說LinkedList。他們之間有什麼區別呢？最大的區別就是底層數據結構的實現不一樣，ArrayList是數組實現的（具體看上一篇文章），LinedList是鏈表實現的。至於其他的一些區別，可以說大部分都是由於本質不同衍生出來的不同應用。

LinkedList

鏈表

在分析LinedList之前先對鏈表做一個簡單的介紹，畢竟鏈表不像數組一樣使用的多，所以很多人不熟悉也在所難免。

鏈表是一種基本的線性數據結構，其和數組同為線性，但是數組是記憶體的物理存儲上呈線性，邏輯上也是線性；而鏈表只是在邏輯上呈線性。在鏈表的每一個存儲單元中不僅存儲有當前的元素，還有下一個存儲單元的地址，這樣的可以通過地址將所有的存儲單元連接在一起。

每次查找的時候，通過第一個存儲單元就可以順藤摸瓜的找到需要的元素。執行刪除操作只需要斷開相關元素的指向就可以了。示意圖如下：

2018-01-10_114030

2018-01-10_114053

2018-01-10_114109

當然了在？LinkedList中使用的並不是最基本的單向鏈表，而是雙向鏈表。

在LinedList中存在一個基本存儲單元，是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;
  }
}

定義

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

在定義上和ArrayList大差不差，但是需要註意的是，LinkedList實現了Deque（間接實現了Qeque介面），Deque是一個雙向對列，為LinedList提供了從對列兩端訪問元素的方法。

初始化

在分析ArrayList的時候我們知道ArrayList使用無參構造方法時的初始化長度是10，並且所有無參構造出來的集合都會指向同一個對象數組（靜態常量，位於方法區），那麼LinkedList的初始化是怎樣的呢？

打開無參構造方法

public LinkedList() {
}

什麼都沒有，那麼只能夠去看屬性了。

//初始化長度為0
transient int size = 0;
//有前後節點
transient Node<E> first;
transient Node<E> last;

圖示初始化

LinkedList<String> list = new LinkedList<String>();
        String s = "sss";
        list.add(s);

方法

add(E e)

public boolean add(E e) {
  linkLast(e);
  return true;
}

從方法中我們知道在調用添加方法之後，並不是立馬添加的，而是調用了linkLast方法，見名知意，新元素的添加位置是集合最後。

void linkLast(E e) {
 // 將最後一個元素賦值（引用傳遞）給節點l final修飾符  修飾的屬性賦值之後不能被改變
  final Node<E> l = last;
 // 調用節點的有參構造方法創建新節點 保存添加的元素 
  final Node<E> newNode = new Node<>(l, e, null);
  //此時新節點是最後一位元素 將新節點賦值給last
  last = newNode;
  //如果l是null 意味著這是第一次添加元素 那麼將first賦值為新節點  這個list只有一個元素 存儲元素 開始元素和最後元素均是同一個元素
  if (l == null)
    first = newNode;
  else
    //如果不是第一次添加，將新節點賦值給l（添加前的最後一個元素）的next
    l.next = newNode;
  //長度+1
  size++;
  //修改次數+1
  modCount++;
}

從以上代碼中我們可以看到其在添加元素的時候並不依賴下標。

而其中的處理是，通過一個last（Node對象）保存最後一個節點的信息（實際上就是最後一個節點），每次通過不斷的變化最後一個元素實現元素的添加。（想要充分理解此處，需要理解java值傳遞和引用傳遞的區別和本質）。

add(int index, E element)

添加到指定的位置

public void add(int index, E element) {
  //下標越界檢查
  checkPositionIndex(index);
//如果是向最後添加 直接調用linkLast
  if (index == size)
    linkLast(element);
  //反之 調用linkBefore
  else
    linkBefore(element, node(index));
}
//在指定元素之前插入元素
void linkBefore(E e, Node<E> succ) {
  // assert succ != null; 假設斷言 succ不為null
  //定義一個節點元素保存succ的prev引用 也就是它的前一節點信息
  final Node<E> pred = succ.prev;
  //創建新節點 節點元素為要插入的元素e prev引用就是pred 也就是插入之前succ的前一個元素 next是succ
  final Node<E> newNode = new Node<>(pred, e, succ);
  //此時succ的上一個節點是插入的新節點 因此修改節點指向
  succ.prev = newNode;
 // 如果pred是null 表明這是第一個元素
  if (pred == null)
    //成員屬性first指向新節點
    first = newNode;
  //反之
  else
    //節點前元素的next屬性指向新節點
    pred.next = newNode;
  //長度+1
  size++;
  modCount++;
}

節點元素插入圖示

在上面的代碼中我們應該註意到了，LinkedList在插入元素的時候也要進行一定的驗證，也就是下標越界驗證，下麵我們看一下具體的實現。

private void checkPositionIndex(int index) {
  if (!isPositionIndex(index))
    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//如果輸入的index在範圍之內返回ture
private boolean isPositionIndex(int index) {
  return index >= 0 && index <= size;
}

通過對兩個添加方法的分析，我們可以很明顯的感受到LinkedList添加元素的效率，不需要擴容，不需要複製數組。

get

public E get(int index) {
  //檢查下標元素是否存在 實際上就是檢查下標是否越界
  checkElementIndex(index);
  //如果沒有越界就返回對應下標節點的item 也就是對應的元素
  return node(index).item;
}

//下標越界檢查 如果越界就拋異常
private void checkElementIndex(int index) {
  if (!isElementIndex(index))
    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(int index) {
  return index >= 0 && index < size;
}
//該方法是用來返回指定下標的非空節點
Node<E> node(int index) {
  //假設下標未越界  實際上也沒有越界 畢竟在此之前執行了下標越界檢查 
  // assert isElementIndex(index);

  //如果index小於size的二分之一  從前開始查找（向後查找）  反之向前查找  
  if (index < (size >> 1)) {//左移 效率高  值得學習
    Node<E> x = first;
    //遍歷
    for (int i = 0; i < index; i++)
      //每一個節點的next都是他的後一個節點引用 遍歷的同時x會不斷的被賦值為節點的下一個元素  遍歷到index是拿到的就是index對應節點的元素
      x = x.next;
    return x;
  } else {
    Node<E> x = last;
    for (int i = size - 1; i > index; i--)
      x = x.prev;
    return x;
  }
}

在這段代碼中充分體現了雙向鏈表的優越性，可以從前也可以從後開始遍歷，通過對index範圍的判斷能夠顯著的提高效率。但是在遍歷的時候也可以很明顯的看到LinkedList get方法獲取元素的低效率，時間複雜度O(n)。

remove(int index)

所謂刪除節點就是把節點的前後引用置為null，並且保證沒有任何其他節點指向被刪除節點。

public E remove(int index) {
  //下標越界檢查
  checkElementIndex(index);
  //此處的返回值實際上是執行了兩個方法
  //node獲取制定下標非空節點
  //unlink 斷開指定節點的聯繫
  return unlink(node(index));
}
E unlink(Node<E> x) {
  //假設x不是null
  // assert x != null;
  //定義一個變數element接受x節點中的元素 最後會最後返回值返回
  final E element = x.item;
  //定義連個節點分別獲得x節點的前後節點引用
  final Node<E> next = x.next;
  final Node<E> prev = x.prev;
  //如果節點前引用為null 說明這是第一個節點
  if (prev == null) {
    //x是第一個節點 即將被刪除  那麼first需要被重新賦值
    first = next;
  } else {
    //如果不是x不是第一個節點  將prev（x的前一個節點）的next指向x的後一個節點（繞過x）
    prev.next = next;
    //x的前引用賦值null
    x.prev = null;
  }
//如果節點後引用為null 說明這是最後一個節點  一系列類似前引用的處理方式 不再贅述
  if (next == null) {
    last = prev;
  } else {
    next.prev = prev;
    x.next = null;
  }
//將x節點中的元素賦值null
  x.item = null;
  size--;
  modCount++;
  return element;
}

說明

prev，item，next均置為null 是為了讓虛擬機回收
我們可以看到LinkedList刪除元素的效率也不錯

LinkedList總結

查詢速度不行，每次查找都需要遍歷，這就是在ArrayList分析時提到過的順序下標遍歷
添加元素，刪除都很有速度優勢
實現對列介面

ArrayList和LinkedList的區別

順序插入，兩者速度都很快，但是ArrayList稍快於LinkedList，數組實現，數組是提前創建好的；LinkedList每次都需要重新new新節點
LinedList需要維護前後節點，會更耗費記憶體
遍歷，LinedList適合用迭代遍歷；ArrayList適合用迴圈遍歷
1. 不要使用普通for迴圈遍歷LinedList
2. 也不要使用迭代遍歷遍歷ArrayList（具體看上篇文章《ArrayList分析》）
刪除和插入就不說了，畢竟ArrayList需要複製數組和擴容。