《Java集合詳解系列》是我在完成夯實Java基礎篇的系列部落格後準備開始寫的新系列。
這些文章将整理到我在GitHub上的《Java面試指南》倉庫，更多精彩内容請到我的倉庫裡檢視
https://github.com/h2pl/Java-Tutorial
喜歡的話麻煩點下Star、fork哈
文章首發于我的個人部落格：
www.how2playlife.com
本文參考
http://cmsblogs.com/?p=155和
https://www.jianshu.com/p/0e84b8d3606cLinkedList
概述
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 Entry header = 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<? extends E> c)。
/**
* 構造一個空清單。
*/
public LinkedList() {
header.next = header.previous = header;
}
/**
* 構造一個包含指定 collection 中的元素的清單，這些元素按其 collection 的疊代器傳回的順序排列。
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
} LinkedList()構造一個空清單。裡面沒有任何元素，僅僅隻是将header節點的前一個元素、後一個元素都指向自身。
LinkedList(Collection<? extends E> 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(Entry e)，remove(Entry e)為私有方法，是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() 方法中如果元素為空，則會一直保持阻塞。
參考文章
https://blog.csdn.net/Faker_Wang/article/details/80923155 https://blog.csdn.net/m0_37869177/article/details/88847569 https://www.iteye.com/blog/shmilyaw-hotmail-com-1825171 https://blog.csdn.net/weixin_36378917/article/details/81812210微信公衆号
Java技術江湖
如果大家想要實時關注我更新的文章以及分享的幹貨的話，可以關注我的公衆号【Java技術江湖】一位阿裡 Java 工程師的技術小站，作者黃小斜，專注 Java 相關技術：SSM、SpringBoot、MySQL、分布式、中間件、叢集、Linux、網絡、多線程，偶爾講點Docker、ELK，同時也分享技術幹貨和學習經驗，緻力于Java全棧開發！
Java工程師必備學習資源: 一些Java工程師常用學習資源，關注公衆号後，背景回複關鍵字 “Java” 即可免費無套路擷取。
個人公衆号：黃小斜
黃小斜是跨考軟體工程的 985 碩士，自學 Java 兩年，拿到了 BAT 等近十家大廠 offer，從技術小白成長為阿裡工程師。
作者專注于 JAVA 後端技術棧，熱衷于分享程式員幹貨、學習經驗、求職心得和程式人生，目前黃小斜的CSDN部落格有百萬+通路量，知乎粉絲2W+，全網已有10W+讀者。
黃小斜是一個斜杠青年，堅持學習和寫作，相信終身學習的力量，希望和更多的程式員交朋友，一起進步和成長！關注公衆号【黃小斜】後回複【原創電子書】即可領取我原創的電子書《菜鳥程式員修煉手冊：從技術小白到阿裡巴巴Java工程師》
程式員3T技術學習資源： 一些程式員學習技術的資源大禮包，關注公衆号後，背景回複關鍵字 “資料” 即可免費無套路擷取。
