[搞懂Java集合類2]LinkedList和Queue

• 2019 年 10 月 7 日
• 筆記

– Java集合類

今天我們來探索一下LinkedList和Queue，以及Stack的源碼。

本文參考 http://cmsblogs.com/?p=155 和 https://www.jianshu.com/p/0e84b8d3606c

LinkedList概述

LinkedList與ArrayList一樣實現List接口，只是ArrayList是List接口的大小可變數組的實現，LinkedList是List接口鏈表的實現。基於鏈表實現的方式使得LinkedList在插入和刪除時更優於ArrayList，而隨機訪問則比ArrayList遜色些。 LinkedList實現所有可選的列表操作，並允許所有的元素包括null。 除了實現 List 接口外，LinkedList 類還為在列表的開頭及結尾 get、remove 和 insert 元素提供了統一的命名方法。這些操作允許將鏈接列表用作堆棧、隊列或雙端隊列。 此類實現 Deque 接口，為 add、poll 提供先進先出隊列操作，以及其他堆棧和雙端隊列操作。 所有操作都是按照雙重鏈接列表的需要執行的。在列表中編索引的操作將從開頭或結尾遍歷列表（從靠近指定索引的一端）。 同時，與ArrayList一樣此實現不是同步的。 （以上摘自JDK 6.0 API）。

源碼分析

定義

首先我們先看LinkedList的定義：

public class LinkedList<E>      extends AbstractSequentialList<E>      implements List<E>, Deque<E>, Cloneable, java.io.Serializable        從這段代碼中我們可以清晰地看出LinkedList繼承AbstractSequentialList，實現List、Deque、Cloneable、Serializable。其中AbstractSequentialList提供了 List 接口的骨幹實現，從而最大限度地減少了實現受「連續訪問」數據存儲（如鏈接列表）支持的此接口所需的工作,從而以減少實現List接口的複雜度。Deque一個線性 collection，支持在兩端插入和移除元素，定義了雙端隊列的操作。

屬性

在LinkedList中提供了兩個基本屬性size、header。

private transient Entryheader = new Entry(null, null, null); private transient int size = 0; 其中size表示的LinkedList的大小，header表示鏈表的表頭，Entry為節點對象。

private static class Entry<E> {      E element;        //元素節點      Entry<E> next;    //下一個元素      Entry<E> previous;  //上一個元素        Entry(E element, Entry<E> next, Entry<E> previous) {          this.element = element;          this.next = next;          this.previous = previous;      }  }    上面為Entry對象的源代碼，Entry為LinkedList的內部類，它定義了存儲的元素。該元素的前一個元素、後一個元素，這是典型的雙向鏈表定義方式。

構造方法

LinkedList提供了兩個構造方法：LinkedList()和LinkedList(Collection c)。

/**       *  構造一個空列表。       */      public LinkedList() {          header.next = header.previous = header;      }        /**       *  構造一個包含指定 collection 中的元素的列表，這些元素按其 collection 的迭代器返回的順序排列。       */      public LinkedList(Collection<? extends E> c) {          this();          addAll(c);      }

LinkedList()構造一個空列表。裏面沒有任何元素，僅僅只是將header節點的前一個元素、後一個元素都指向自身。

LinkedList(Collection c)： 構造一個包含指定 collection 中的元素的列表，這些元素按其 collection 的迭代器返回的順序排列。該構造函數首先會調用LinkedList()，構造一個空列表，然後調用了addAll()方法將Collection中的所有元素添加到列表中。以下是addAll()的源代碼：

/**       *  添加指定 collection 中的所有元素到此列表的結尾，順序是指定 collection 的迭代器返回這些元素的順序。       */      public boolean addAll(Collection<? extends E> c) {          return addAll(size, c);      }    /**   * 將指定 collection 中的所有元素從指定位置開始插入此列表。其中index表示在其中插入指定collection中第一個元素的索引   */  public boolean addAll(int index, Collection<? extends E> c) {      //若插入的位置小於0或者大於鏈表長度，則拋出IndexOutOfBoundsException異常      if (index < 0 || index > size)          throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);      Object[] a = c.toArray();      int numNew = a.length;    //插入元素的個數      //若插入的元素為空，則返回false      if (numNew == 0)          return false;      //modCount:在AbstractList中定義的，表示從結構上修改列表的次數      modCount++;      //獲取插入位置的節點，若插入的位置在size處，則是頭節點，否則獲取index位置處的節點      Entry<E> successor = (index == size ? header : entry(index));      //插入位置的前一個節點，在插入過程中需要修改該節點的next引用：指向插入的節點元素      Entry<E> predecessor = successor.previous;      //執行插入動作      for (int i = 0; i < numNew; i++) {          //構造一個節點e，這裡已經執行了插入節點動作同時修改了相鄰節點的指向引用          //          Entry<E> e = new Entry<E>((E) a[i], successor, predecessor);          //將插入位置前一個節點的下一個元素引用指向當前元素          predecessor.next = e;          //修改插入位置的前一個節點，這樣做的目的是將插入位置右移一位，保證後續的元素是插在該元素的後面，確保這些元素的順序          predecessor = e;      }      successor.previous = predecessor;      //修改容量大小      size += numNew;      return true;  }    在addAll()方法中，涉及到了兩個方法，一個是entry(int index)，該方法為LinkedList的私有方法，主要是用來查找index位置的節點元素。    /**       * 返回指定位置(若存在)的節點元素       */      private Entry<E> entry(int index) {          if (index < 0 || index >= size)              throw new IndexOutOfBoundsException("Index: " + index + ", Size: "                      + size);          //頭部節點          Entry<E> e = header;          //判斷遍歷的方向          if (index < (size >> 1)) {              for (int i = 0; i <= index; i++)                  e = e.next;          } else {              for (int i = size; i > index; i--)                  e = e.previous;          }          return e;      }

從該方法有兩個遍歷方向中我們也可以看出LinkedList是雙向鏈表，這也是在構造方法中為什麼需要將header的前、後節點均指向自己。

如果對數據結構有點了解，對上面所涉及的內容應該問題，我們只需要清楚一點：LinkedList是雙向鏈表，其餘都迎刃而解。

由於篇幅有限，下面將就LinkedList中幾個常用的方法進行源碼分析。

增加方法

add(E e): 將指定元素添加到此列表的結尾。    public boolean add(E e) {      addBefore(e, header);          return true;      }        該方法調用addBefore方法，然後直接返回true，對於addBefore()而已，它為LinkedList的私有方法。    private Entry<E> addBefore(E e, Entry<E> entry) {          //利用Entry構造函數構建一個新節點 newEntry，          Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);          //修改newEntry的前後節點的引用，確保其鏈表的引用關係是正確的          newEntry.previous.next = newEntry;          newEntry.next.previous = newEntry;          //容量+1          size++;          //修改次數+1          modCount++;          return newEntry;      }

在addBefore方法中無非就是做了這件事：構建一個新節點newEntry，然後修改其前後的引用。

LinkedList還提供了其他的增加方法：

add(int index, E element)：在此列表中指定的位置插入指定的元素。      addAll(Collection<? extends E> c)：添加指定 collection 中的所有元素到此列表的結尾，順序是指定 collection 的迭代器返回這些元素的順序。      addAll(int index, Collection<? extends E> c)：將指定 collection 中的所有元素從指定位置開始插入此列表。      AddFirst(E e): 將指定元素插入此列表的開頭。      addLast(E e): 將指定元素添加到此列表的結尾。

移除方法

remove(Object o)：從此列表中移除首次出現的指定元素（如果存在）。該方法的源代碼如下：    public boolean remove(Object o) {          if (o==null) {              for (Entry<E> e = header.next; e != header; e = e.next) {                  if (e.element==null) {                      remove(e);                      return true;                  }              }          } else {              for (Entry<E> e = header.next; e != header; e = e.next) {                  if (o.equals(e.element)) {                      remove(e);                      return true;                  }              }          }          return false;      }

該方法首先會判斷移除的元素是否為null，然後迭代這個鏈表找到該元素節點，最後調用remove(Entrye)，remove(Entrye)為私有方法，是LinkedList中所有移除方法的基礎方法，如下：

private E remove(Entry<E> e) {          if (e == header)              throw new NoSuchElementException();            //保留被移除的元素：要返回          E result = e.element;            //將該節點的前一節點的next指向該節點後節點          e.previous.next = e.next;          //將該節點的後一節點的previous指向該節點的前節點          //這兩步就可以將該節點從鏈表從除去：在該鏈表中是無法遍歷到該節點的          e.next.previous = e.previous;          //將該節點歸空          e.next = e.previous = null;          e.element = null;          size--;          modCount++;          return result;      }

其他的移除方法：

clear()： 從此列表中移除所有元素。      remove()：獲取並移除此列表的頭（第一個元素）。      remove(int index)：移除此列表中指定位置處的元素。      remove(Objec o)：從此列表中移除首次出現的指定元素（如果存在）。      removeFirst()：移除並返回此列表的第一個元素。      removeFirstOccurrence(Object o)：從此列表中移除第一次出現的指定元素（從頭部到尾部遍歷列表時）。      removeLast()：移除並返回此列表的最後一個元素。      removeLastOccurrence(Object o)：從此列表中移除最後一次出現的指定元素（從頭部到尾部遍歷列表時）。

查找方法

對於查找方法的源碼就沒有什麼好介紹了，無非就是迭代，比對，然後就是返回當前值。      get(int index)：返回此列表中指定位置處的元素。      getFirst()：返回此列表的第一個元素。      getLast()：返回此列表的最後一個元素。      indexOf(Object o)：返回此列表中首次出現的指定元素的索引，如果此列表中不包含該元素，則返回 -1。      lastIndexOf(Object o)：返回此列表中最後出現的指定元素的索引，如果此列表中不包含該元素，則返回 -1。

Queue

Queue接口定義了隊列數據結構，元素是有序的(按插入順序)，先進先出。Queue接口相關的部分UML類圖如下：

DeQueue

DeQueue(Double-ended queue)為接口，繼承了Queue接口，創建雙向隊列，靈活性更強，可以前向或後向迭代，在隊頭隊尾均可心插入或刪除元素。它的兩個主要實現類是ArrayDeque和LinkedList。

ArrayDeque （底層使用循環數組實現雙向隊列）

創建

public ArrayDeque() {     // 默認容量為16     elements = new Object[16];  }    public ArrayDeque(int numElements) {     // 指定容量的構造函數     allocateElements(numElements);  }  private void allocateElements(int numElements) {          int initialCapacity = MIN_INITIAL_CAPACITY;// 最小容量為8          // Find the best power of two to hold elements.          // Tests "<=" because arrays aren't kept full.          // 如果要分配的容量大於等於8，擴大成2的冪（是為了維護頭、尾下標值）；否則使用最小容量8          if (numElements >= initialCapacity) {              initialCapacity = numElements;              initialCapacity |= (initialCapacity >>>  1);              initialCapacity |= (initialCapacity >>>  2);              initialCapacity |= (initialCapacity >>>  4);              initialCapacity |= (initialCapacity >>>  8);              initialCapacity |= (initialCapacity >>> 16);              initialCapacity++;              if (initialCapacity < 0)   // Too many elements, must back off                  initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements          }          elements = new Object[initialCapacity];      }

add操作

add(E e) 調用 addLast(E e) 方法：  public void addLast(E e) {     if (e == null)        throw new NullPointerException("e == null");     elements[tail] = e; // 根據尾索引，添加到尾端     // 尾索引+1，並與數組（length - 1）進行取『&』運算，因為length是2的冪，所以（length-1）轉換為2進制全是1，     // 所以如果尾索引值 tail 小於等於（length - 1），那麼『&』運算後仍為 tail 本身；如果剛好比（length - 1）大1時，     // 『&』運算後 tail 便為0（即回到了數組初始位置）。正是通過與（length - 1）進行取『&』運算來實現數組的雙向循環。     // 如果尾索引和頭索引重合了，說明數組滿了，進行擴容。     if ((tail = (tail + 1) & (elements.length - 1)) == head)        doubleCapacity();// 擴容為原來的2倍  }      addFirst(E e) 的實現：  public void addFirst(E e) {     if (e == null)        throw new NullPointerException("e == null");     // 此處如果head為0，則-1（1111 1111 1111 1111 1111 1111 1111 1111）與（length - 1）進行取『&』運算，結果必然是（length - 1），即回到了數組的尾部。     elements[head = (head - 1) & (elements.length - 1)] = e;     // 如果尾索引和頭索引重合了，說明數組滿了，進行擴容     if (head == tail)        doubleCapacity();  }

remove操作

remove()方法最終都會調對應的poll()方法：      public E poll() {          return pollFirst();      }      public E pollFirst() {          int h = head;          @SuppressWarnings("unchecked") E result = (E) elements[h];          // Element is null if deque empty          if (result == null)              return null;          elements[h] = null;     // Must null out slot          // 頭索引 + 1          head = (h + 1) & (elements.length - 1);          return result;      }      public E pollLast() {          // 尾索引 - 1          int t = (tail - 1) & (elements.length - 1);          @SuppressWarnings("unchecked") E result = (E) elements[t];          if (result == null)              return null;          elements[t] = null;          tail = t;          return result;      }

PriorityQueue（底層用數組實現堆的結構）

優先隊列跟普通的隊列不一樣，普通隊列是一種遵循FIFO規則的隊列，拿數據的時候按照加入隊列的順序拿取。 而優先隊列每次拿數據的時候都會拿出優先級最高的數據。 優先隊列內部維護着一個堆，每次取數據的時候都從堆頂拿數據（堆頂的優先級最高），這就是優先隊列的原理。

add，添加方法

public boolean add(E e) {      return offer(e); // add方法內部調用offer方法  }  public boolean offer(E e) {      if (e == null) // 元素為空的話，拋出NullPointerException異常          throw new NullPointerException();      modCount++;      int i = size;      if (i >= queue.length) // 如果當前用堆表示的數組已經滿了，調用grow方法擴容          grow(i + 1); // 擴容      size = i + 1; // 元素個數+1      if (i == 0) // 堆還沒有元素的情況          queue[0] = e; // 直接給堆頂賦值元素      else // 堆中已有元素的情況          siftUp(i, e); // 重新調整堆，從下往上調整，因為新增元素是加到最後一個葉子節點      return true;  }  private void siftUp(int k, E x) {      if (comparator != null)  // 比較器存在的情況下          siftUpUsingComparator(k, x); // 使用比較器調整      else // 比較器不存在的情況下          siftUpComparable(k, x); // 使用元素自身的比較器調整  }  private void siftUpUsingComparator(int k, E x) {      while (k > 0) { // 一直循環直到父節點還存在          int parent = (k - 1) >>> 1; // 找到父節點索引，等同於（k - 1）/ 2          Object e = queue[parent]; // 獲得父節點元素          // 新元素與父元素進行比較，如果滿足比較器結果，直接跳出，否則進行調整          if (comparator.compare(x, (E) e) >= 0)              break;          queue[k] = e; // 進行調整，新位置的元素變成了父元素          k = parent; // 新位置索引變成父元素索引，進行遞歸操作      }      queue[k] = x; // 新添加的元素添加到堆中  }

poll，出隊方法

public E poll() {      if (size == 0)          return null;      int s = --size; // 元素個數-1      modCount++;      E result = (E) queue[0]; // 得到堆頂元素      E x = (E) queue[s]; // 最後一個葉子節點      queue[s] = null; // 最後1個葉子節點置空      if (s != 0)          siftDown(0, x); // 從上往下調整，因為刪除元素是刪除堆頂的元素      return result;  }  private void siftDown(int k, E x) {      if (comparator != null) // 比較器存在的情況下          siftDownUsingComparator(k, x); // 使用比較器調整      else // 比較器不存在的情況下          siftDownComparable(k, x); // 使用元素自身的比較器調整  }  private void siftDownUsingComparator(int k, E x) {      int half = size >>> 1; // 只需循環節點個數的一般即可      while (k < half) {          int child = (k << 1) + 1; // 得到父節點的左子節點索引，即（k * 2）+ 1          Object c = queue[child]; // 得到左子元素          int right = child + 1; // 得到父節點的右子節點索引          if (right < size &&              comparator.compare((E) c, (E) queue[right]) > 0) // 左子節點跟右子節點比較，取更大的值              c = queue[child = right];          if (comparator.compare(x, (E) c) <= 0)  // 然後這個更大的值跟最後一個葉子節點比較              break;          queue[k] = c; // 新位置使用更大的值          k = child; // 新位置索引變成子元素索引，進行遞歸操作      }      queue[k] = x; // 最後一個葉子節點添加到合適的位置  }

remove，刪除隊列元素

public boolean remove(Object o) {      int i = indexOf(o); // 找到數據對應的索引      if (i == -1) // 不存在的話返回false          return false;      else { // 存在的話調用removeAt方法，返回true          removeAt(i);          return true;      }  }  private E removeAt(int i) {      modCount++;      int s = --size; // 元素個數-1      if (s == i) // 如果是刪除最後一個葉子節點          queue[i] = null; // 直接置空，刪除即可，堆還是保持特質，不需要調整      else { // 如果是刪除的不是最後一個葉子節點          E moved = (E) queue[s]; // 獲得最後1個葉子節點元素          queue[s] = null; // 最後1個葉子節點置空          siftDown(i, moved); // 從上往下調整          if (queue[i] == moved) { // 如果從上往下調整完畢之後發現元素位置沒變，從下往上調整              siftUp(i, moved); // 從下往上調整              if (queue[i] != moved)                  return moved;          }      }      return null;  }

先執行 siftDown() 下濾過程：

再執行 siftUp() 上濾過程：

總結和同步的問題

1、jdk內置的優先隊列PriorityQueue內部使用一個堆維護數據，每當有數據add進來或者poll出去的時候會對堆做從下往上的調整和從上往下的調整。

2、PriorityQueue不是一個線程安全的類，如果要在多線程環境下使用，可以使用 PriorityBlockingQueue 這個優先阻塞隊列。其中add、poll、remove方法都使用 ReentrantLock 鎖來保持同步，take() 方法中如果元素為空，則會一直保持阻塞。