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

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

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

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

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

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

在LinedList中存在一個基本存儲單元，是LinkedList的一個內部類，節點元素存在兩個屬性，分別保存前一個節點和后一個節點的引用。

//靜態內部類
private static class Node {
  //存儲元素的屬性
  E item;
  //前后節點引用
  Node next;
  Node prev;
  Node(Node prev, E element, Node next) {
    this.item = element;
    this.next = next;
    this.prev = prev;
  }
}

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

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

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

打開無參構造方法

public LinkedList() {
}

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

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

圖示初始化

LinkedList list = new LinkedList();
        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 l = last;
 // 調用節點的有參構造方法創建新節點 保存添加的元素 
  final Node 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 succ) {
  // assert succ != null; 假設斷言 succ不為null
  //定義一個節點元素保存succ的prev引用 也就是它的前一節點信息
  final Node pred = succ.prev;
  //創建新節點 節點元素為要插入的元素e prev引用就是pred 也就是插入之前succ的前一個元素 next是succ
  final Node 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 node(int index) {
  //假設下標未越界  實際上也沒有越界 畢竟在此之前執行了下標越界檢查 
  // assert isElementIndex(index);

  //如果index小于size的二分之一  從前開始查找（向后查找）  反之向前查找  
  if (index < (size >> 1)) {//左移 效率高  值得學習
    Node x = first;
    //遍歷
    for (int i = 0; i < index; i++)
      //每一個節點的next都是他的后一個節點引用 遍歷的同時x會不斷的被賦值為節點的下一個元素  遍歷到index是拿到的就是index對應節點的元素
      x = x.next;
    return x;
  } else {
    Node 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 x) {
  //假設x不是null
  // assert x != null;
  //定義一個變量element接受x節點中的元素 最后會最后返回值返回
  final E element = x.item;
  //定義連個節點分別獲得x節點的前后節點引用
  final Node next = x.next;
  final Node 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，數組實現，數組是提前創建好的；LinkedList每次都需要重新new新節點

LinedList需要維護前后節點，會更耗費內存

遍歷，LinedList適合用迭代遍歷；ArrayList適合用循環遍歷

不要使用普通for循環遍歷LinedList

也不要使用迭代遍歷遍歷ArrayList（具體看上篇文章《ArrayList分析》）

刪除和插入就不說了，畢竟ArrayList需要復制數組和擴容。

我不能保證每一個地方都是對的，但是可以保證每一句話，每一行代碼都是經過推敲和斟酌的。希望每一篇文章背后都是自己追求純粹技術人生的態度。
永遠相信美好的事情即將發生。