本文基于corretto-17.0.9源碼，參考本文時請打開相應的源碼對照，否則你會不知道我在說什么

LinkedList簡介

從功能上看，LinkedList同時實現(xiàn)了List接口和Deque接口，也就是說它既可以看作一個順序容器，又可以看作一個隊列(Queue)，同時又可以看作一個棧(Stack)。這樣看來，LinkedList簡直就是個全能冠軍。當你需要使用?；蛘哧犃袝r，可以考慮使用LinkedList，一方面是因為Java官方已經(jīng)聲明不建議使用Stack類，更遺憾的是，Java里根本沒有一個叫做Queue的類(它是個接口名字)。關于?；蜿犃校F(xiàn)在的首選是ArrayDeque，它有著比LinkedList(當作?；蜿犃惺褂脮r)有著更好的性能。

從內部實現(xiàn)來看，LinkedList其實只是對鏈表的封裝，沒什么特別之處，下面代碼分析也會非常簡短。與 ArrayList 相比，LinkedList 的增加和刪除的操作效率更高，而查找和修改的操作效率較低，這些顯然也是鏈表和數(shù)組的區(qū)別。

LinkedList例子

例子就不看了，都是些一眼懂的API

LinkedList繼承結構

LinkedList，作為一個順序列表繼承于AbstractSequentialList，AbstractSequentialList與AbstractList的區(qū)別是，前者一般是不可隨機訪問的列表，或者說隨機訪問效率很低，而后者可以高效地基于下標隨機訪問，LinkedList作為鏈表的封裝，眾所周知鏈表無法隨機訪問元素，因此繼承于AbstractSequentialList。

LinkedList作為List（Sequence），每個元素都對應著一個下標，鏈表頭指針（first）指向的節(jié)點下標為0，尾指針（last）指向的節(jié)點下標為size-1。

其中JCF相關的接口和抽象類不了解的話，可以在參考「博客園」JCF相關基礎類接口/抽象類源碼閱讀。

LinkedList代碼分析

成員變量

LinkedList的成員變量也很少，了解鏈表的話一眼懂：

// 元素個數(shù)
transient int size = 0;
// 鏈表頭指針
transient Node<E> first;
// 鏈表尾指針
transient Node<E> last;

// 鏈表節(jié)點類
private static class Node<E> {
  E item;
  LinkedList.Node<E> next;
  LinkedList.Node<E> prev;

  Node(LinkedList.Node<E> prev, E element, LinkedList.Node<E> next) {
    this.item = element;
    this.next = next;
    this.prev = prev;
  }
}

頭和尾指針指向的都是真實元素節(jié)點，沒有dummy node。注意到Node有next和prev指針，說明是LinkedList維護的是一個雙向鏈表。

方法

首先是構造函數(shù)，沒啥好說，一個無參構造對應空列表，一個根據(jù)Collection接口規(guī)范的用其他集合來初始化本集合的構造函數(shù)：

public LinkedList() {}

public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

下面看一下各個方法，一些鏈表操作或比較簡單的方法就不分析了，只用注釋說明功能，先看一下內部方法：

// 頭插新節(jié)點
private void linkFirst(E e);
// 尾插新節(jié)點
void linkLast(E e);
// 在succ節(jié)點前插入新節(jié)點
void linkBefore(E e, Node<E> succ);
// 刪除頭節(jié)點
private E unlinkFirst(Node<E> f);
// 刪除尾節(jié)點
private E unlinkLast(Node<E> l);
// 刪除節(jié)點
E unlink(Node<E> x);
// 獲取下標為index的節(jié)點
LinkedList.Node<E> node(int index) {
  if (index < (size >> 1)) { // 如果節(jié)點在鏈表前半部分，則從first開始往后遍歷
    LinkedList.Node<E> x = first;
    for (int i = 0; i < index; i++)
      x = x.next;
    return x;
  } else { // 否則從last開始往前遍歷
    LinkedList.Node<E> x = last;
    for (int i = size - 1; i > index; i--)
      x = x.prev;
    return x;
  }
}

再看一下公有方法（太簡單的公有方法略過）

// 按c的迭代器的順序插入鏈表，最先遍歷到的元素下標最小
public boolean addAll(int index, Collection<? extends E> c);
// 清空鏈表，不像ArrayList的置null，這個方法會刪除所有節(jié)點
public void clear();

至此，實現(xiàn)Deque的方法已經(jīng)介紹完。在JCF介紹一文中提到過繼承AbstractSequentialList的類要么重寫增刪改查，要么重新實現(xiàn)列表迭代器，LinkedList兩者都做了，增刪改查方法很簡單，略過，看一下迭代器：

private class ListItr implements ListIterator<E> {
  // 相當于AbstractList.Itr的lastRet下標對應的節(jié)點
  private Node<E> lastReturned;
  // 相當于AbstractList.Itr的cursor下標對應的節(jié)點
  private Node<E> next;
  // 相當于Abstrac
  private int nextIndex;
  // 期望的修改次數(shù)，用于檢測并發(fā)修改
  private int expectedModCount = modCount;
}

可以發(fā)現(xiàn)LinkedList實現(xiàn)的這個ListIterator沒什么特別的，也還是直接對鏈表進行操作，與AbstractList.ListIterator其實很類似，就不講了。

java 1.6開始還提供了一個反向迭代器，一眼懂：

public Iterator<E> descendingIterator() {
  return new DescendingIterator();
}

private class DescendingIterator implements Iterator<E> {
  private final ListItr itr = new ListItr(size());
  public boolean hasNext() {
    return itr.hasPrevious();
  }
  public E next() {
    return itr.previous();
  }
  public void remove() {
    itr.remove();
  }
}

ArrayDeque簡介

ArrayDeque是雙端隊列接口Deque的實現(xiàn)。出于性能上的考慮，如果你要用FIFO隊列，可以優(yōu)先考慮ArrayDeque而不是LinkedList；如果要使用棧，可以優(yōu)先考慮ArrayDeque而不是LinkedList。ArrayDeque除了個別方法外，基本攤還時間復雜度都是O(1)。這個類的迭代器也是fail-fast的（這個概念在ArrayList那篇中講過）。

ArrayDeque繼承結構

根據(jù)繼承結構可以確定，ArrayDeque就是一個用數(shù)組實現(xiàn)的雙端隊列，并且由于是“雙端”，我們可以進一步推測出應該是用循環(huán)數(shù)組來實現(xiàn)的。

ArrayDeque代碼分析

按照慣例，先搞懂成員變量的含義：

public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>, Cloneable, Serializable {
  // 實際存儲元素的數(shù)組，沒有存元素的話為null
  transient Object[] elements;
  // 循環(huán)數(shù)組的頭指針，指向頭元素
  transient int head;
  // 循環(huán)數(shù)組的尾指針，指向下一個要入隊的尾元素
  transient int tail;
}

注意沒有存元素的位置是null，因此ArrayDeque不能存值為null的元素，至于為什么，看完下面分析就知道了。

先復習一下循環(huán)數(shù)組，當調用addLast的時候，往尾部增加元素；當調用addFirst的時候往頭部增加元素，畫一張圖幫助理解，其中數(shù)字代表元素下標，藍色的代表該位置有元素，其他的不用多解釋了：

要注意的是，tail永遠要指向null，意味著數(shù)組大小為n的話，最多只能存n-1個元素。否則如果存滿數(shù)組的話，最終tail與head相等，此時無法判斷是隊空還是隊滿。

ArrayDeque沒有設size變量保存元素個數(shù)，因為可以用head和tail計算得到。但是循環(huán)數(shù)組中tail可能大于head也可能小于head，因此設計一個概念：循環(huán)距離。首先tail入隊時是遞增的，head入隊下標是遞減的，因此head和tail的循環(huán)距離就是（結合圖來理解）：

• 當tail>=head，為tail-head
• 當tail<head，為tail-head+數(shù)組長度（相當于數(shù)組長度減去空白格子的個數(shù)，得到藍色格子個數(shù)）

因此size就等于循環(huán)距離。ok，關于循環(huán)數(shù)組的原理以及元素出入隊的細節(jié)都搞清楚了，那么由于循環(huán)數(shù)組是個數(shù)組（廢話），總會有容量不夠的時候，下一步就來分析數(shù)組的擴容。擴容的核心方法是grow：

// 最少要增加needed（ArrayList中的grow是最少增加到minCapacity）
private void grow(int needed) {
  final int oldCapacity = elements.length;
  int newCapacity;
  // 這一段是計算擴容后的長度，總體策略是：
  // 如果數(shù)組比較?。ㄐ∮?4）那么擴容到2倍，否則擴容到1.5倍
  int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1);
  if (jump < needed
      || (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0)
    newCapacity = newCapacity(needed, jump);
  // 這一段是擴容
  final Object[] es = elements = Arrays.copyOf(elements, newCapacity);
  if (tail < head || (tail == head && es[head] != null)) {
    int newSpace = newCapacity - oldCapacity;
    System.arraycopy(es, head,
                     es, head + newSpace,
                     oldCapacity - head);
    for (int i = head, to = (head += newSpace); i < to; i++)
      es[i] = null;
  }
}

grow的最后一段代碼是為了處理tail<=head的情況，具體還是看圖，假設從之前那張圖中數(shù)組的最后一個狀態(tài)開始擴容，大小+3（實際上不一定需要擴容，擴容的話也不一定是+3，這里只是為了方便說明這段代碼的最后一個部分）：

由于tail < head的情況下，元素是物理不連續(xù)的（循環(huán)數(shù)組嘛），因此最后一段 if 將后面那段移動到新數(shù)組的尾部，保持循環(huán)數(shù)組中元素的連續(xù)性。

Deque和Collection的一些方法就不說了，都很簡單。挑一點看著相對需要分析的函數(shù)來看一下：

// 刪除從頭到尾的第i個元素
boolean delete(int i) {
  final Object[] es = elements;
  final int capacity = es.length;
  final int h, t;
  // 計算第i個元素與頭的循環(huán)距離
  final int front = sub(i, h = head, capacity);
  // 計算第i個元素與尾的循環(huán)距離
  final int back = sub(t = tail, i, capacity) - 1;
  // 哪個循環(huán)距離小，就移動哪部分。這里意思是，因為是循環(huán)數(shù)組，刪除一個元素之后，可以把前半部分的元素整體往后移動，也可以把后半部分的元素整體往前移動，因此選擇需要移動元素少的那部分。
  if (front < back) {
    if (h <= i) {
      System.arraycopy(es, h, es, h + 1, front);
    } else { // Wrap around
      System.arraycopy(es, 0, es, 1, i);
      es[0] = es[capacity - 1];
      System.arraycopy(es, h, es, h + 1, front - (i + 1));
    }
    es[h] = null;
    head = inc(h, capacity);
    return false;
  } else {
    tail = dec(t, capacity);
    if (i <= tail) {
      System.arraycopy(es, i + 1, es, i, back);
    } else {
      System.arraycopy(es, i + 1, es, i, capacity - (i + 1));
      es[capacity - 1] = es[0];
      System.arraycopy(es, 1, es, 0, t - 1);
    }
    es[tail] = null;
    return true;
  }
}

還有的函數(shù)比如bulkRemoveModified，其實跟ArrayList的removeIf很像了，也是先標記所有將要被刪除的元素，然后再進行逐個刪除，這種做法是為了filter進行逐元素進行判斷時，保持遍歷過程中列表是可重入讀的，在實際進行刪除時使用雙指針法保持元素連續(xù)性。具體可以參考「博客園」ArrayList源碼閱讀。

最后看一眼迭代器吧，因為JCF前幾篇都已經(jīng)詳細介紹過迭代器，ArrayDeque的迭代器實現(xiàn)也沒什么特別的，就不展開講了：

private class DeqIterator implements Iterator<E> {
  int cursor;
  int remaining = size();
  int lastRet = -1;
}

總結

類似ArrayList是對數(shù)組的封裝，LinkedList是對數(shù)組的封裝，代碼看起來也比較簡單，適合編程新手學習一下“封裝”的概念。（又水一篇）。

java 1.6新出了一個ArrayDeque，出于性能上的考慮，如果你要用FIFO隊列，可以優(yōu)先考慮ArrayDeque而不是LinkedList；如果要使用棧，可以優(yōu)先考慮ArrayDeque而不是LinkedList。

參考鏈接

「博客園」JCF相關基礎類接口/抽象類源碼閱讀

「博客園」ArrayList源碼閱讀

「Java全棧知識體系」Collection - LinkedList源碼解析文章來源地址http://www.zghlxwxcb.cn/news/detail-793864.html

到了這里，關于LinkedList & ArrayDeque源碼閱讀的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！