知其然知其所以然之LinkedList常用原始碼閱讀

摘要： Hello大家好，本章我們簡單瞭解一下LinkedList 。有問題可以聯絡我[email protected]。另求各路大神指點，感謝。 說明：本篇文章基於jdk1.8進行閱讀，並針對LinkedList中常用的一些方法進行簡要說明。 一：LinkedList簡介 LinkedLi...

Hello大家好，本章我們簡單瞭解一下LinkedList 。有問題可以聯絡我[email protected]。另求各路大神指點，感謝。

說明：本篇文章基於jdk1.8進行閱讀，並針對LinkedList中常用的一些方法進行簡要說明。

一：LinkedList簡介

LinkedList是一種連結串列型別的資料結構，支援高效的插入和刪除操作。其實現了 Deque 介面，使得 LinkedList具有佇列的特性。LinkedList 類的底層實現的資料結構是一個雙端的連結串列。

二：資料結構圖分析

如圖可以看出LinkedList資料結構使用 雙向連結串列結構 ，有一個頭節點和一個尾節點，第一個節點的前驅節點為null，最後一個節點的後繼節點為null。其中每個節點有兩個指標指向前驅節點和後繼節點，這意味著我們在新增或修改LinkedList時 不必像ArrayList一樣進行擴容 操作。

三：繼承關係分析

public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable複製程式碼

• 繼承於 AbstractSequentialList。而AbstractSequentialList這個類提供了一個基本的 List 介面實現，為實現序列訪問的資料儲存結構的提供了所需要的最小化的介面實現。他採用的是在迭代器的基礎上實現的 get、set、add 和 remove 方法。
• 實現List介面，說明可以對他進行佇列的操作
• 實現Deque介面，可以將 LinkedList 當作雙端佇列使用
• 實現Cloneable介面，說明可以進行克隆
• 實現Serializable介面，說明可以被序列化

四：原始碼分析

1：成員變數

//transient修飾的變數在序列化時不會被序列化
transient int size = 0;

/**
 * Pointer to first node.
 * Invariant: (first == null && last == null) ||
 *(first.prev == null && first.item != null)
 */
transient Node<E> first;

/**
 * Pointer to last node.
 * Invariant: (first == null && last == null) ||
 *(last.next == null && last.item != null)
 */
transient Node<E> last;複製程式碼

LinkedList的成員變數很簡單，只有三個。其中size表示連結串列中實際元素的數量。

根據註釋結合上面的資料結構圖可以看出：

• 當連結串列為空時，first和last一定都為空。
• 當連結串列不為空時，first的前驅結點一定為空，first.item一定不為空。last的後續節點一定為空，last.item一定不為空。

2：內部類

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;
}
}複製程式碼

3：構造方法

//構建一個空列表
public LinkedList() {
}

/**
 * 構建一個包含集合c的列表
 *
 * @paramc the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */ 
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}複製程式碼

4：常用方法

• 新增元素到第一個節點

private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}複製程式碼

分析，通過變數f儲存第一個節點，接下來呼叫Node建立一個新的節點，將新節點作為新first，這時判斷，如果之前的first為空，那說明插入之前該連結串列是空的，那麼新插入的節點不僅是first節點而且還是last節點，所以last要指向新插入的 newNode。

如果之前的first不是空，那麼不動last，將first的前驅結點設為新節點，此時原first節點為連結串列的第二個節點。

最後插入成功，將連結串列節點數量加一

說明：Fail-Fast 機制

變數 modCount 為記錄當前連結串列被修改的次數。我們知道 LinkedList是執行緒不安全的 ，在迭代器遍歷連結串列時，迭代器初始化過程中會將這個值賦給迭代器的 expectedModCount 。在迭代過程中，判斷modCount跟expectedModCount 是否相等，如果不相等就表示已經有其他執行緒修改了。那麼將丟擲 ConcurrentModificationException 。所以當大家遍歷那些非執行緒安全的資料結構時， 儘量使用迭代器進行遍歷 。

重點：向連結串列中新增元素

public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}

//新增指定集合到指定位置
public boolean addAll(int index, Collection<? extends E> c) {
//判斷需要插入的位置是否合法index>=0且index小於等於當前連結串列節點數量
checkPositionIndex(index);
//將集合轉換為陣列
Object[] a = c.toArray();
//儲存集合長度
int numNew = a.length;
if (numNew == 0)
return false;

//建立節點前驅節點，後續節點
Node<E> pred, succ;
//如果插入的節點為連結串列的末端，則前驅節點為尾節點，後續節點為空
if (index == size) {
succ = null;
pred = last;
} else {
//根據節點位置獲取該節點下面分析
succ = node(index);
//儲存該節點的前驅節點，這裡我們將連結串列斷開，準備將集合插入指定位置succ儲存index後的連結串列
pred = succ.prev;
}
//遍歷陣列
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
//建立新節點
Node<E> newNode = new Node<>(pred, e, null);
//在第一個元素之前插入
if (pred == null)
first = newNode;
else
//前驅節點的後續節點指向新節點
pred.next = newNode;
//將前驅改成當前節點，以便後續新增c中其它的元素
pred = newNode;
}

//還是兩種判斷 如果succ為空，說明插入的節點位置是該連結串列的尾節點的後面
//這時通過上面的遍歷我們可以知道，pred肯定指向當前連結串列最後一個節點，所以將last指向pred
if (succ == null) {
last = pred;
} else {
//此時我們需要將之前斷開的連結串列的後半部分拼接上。pred為當前重組的尾節點，
//則尾節點的後續節點指向succ，succ的前驅節點指向pred
pred.next = succ;
succ.prev = pred;
}
//連結串列長度增加
size += numNew;
//操作次數增加
modCount++;
return true;
}複製程式碼

獲取指定位置的節點

//這裡我們可以看到對此查詢，LinkedList是做了優化的，
//並沒有盲目的去全部遍歷，而是判斷要查詢的座標離頭節點近還是尾節點近，來判斷是從頭遍歷還是從尾開始遍歷
Node<E> node(int index) {
// assert isElementIndex(index);

if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}複製程式碼

刪除一個元素（元素不為空

E unlink(Node<E> x) {
// assert x != null;
//當前節點 最後要把這個節點返回去
final E element = x.item;
//儲存待刪除節點的後續節點
final Node<E> next = x.next;
//儲存待刪除節點的前驅節點
final Node<E> prev = x.prev;
//如果待刪除節點的前一個節點為空，表明待刪除的節點為頭結點。
//需要把待刪除節點的後一個節點設定為頭結點。
if (prev == null) {
first = next;
} else {
//把待刪除的節點的前、後節點連結起來
prev.next = next;
x.prev = null;
}

//如果待刪除節點是尾節點
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}

x.item = null;
//元素長度減一
size--;
//操作次數加一
modCount++;
return element;
}複製程式碼

刪除 LinkedList 中第一個節點（私有

//根據註釋我們可以看出元素必須是第一個元素且不能為空
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
//儲存待刪除節點的值，用作刪除成功返回帶=待刪除節點的值
final E element = f.item;
//儲存待刪除節點的後續節點
final Node<E> next = f.next;
//把f的值和它的next設定為空
f.item = null;
f.next = null; // help GC
//將他的下一個節點設定為頭節點
first = next;
//判斷next是否為空，如果為空證明原連結串列只有一個節點，刪除之後是空連結串列
if (next == null)
//將last也需要設定為空號
last = null;
else
//這是next已經為頭節點，需要將頭節點的前驅節點設定為空
next.prev = null;
//連結串列元素數量減一
size--;
//操作次數加一
modCount++;
return element;
}複製程式碼

刪除 LinkedList 的最後一個節點。（該節點不為空

private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
//儲存待刪除元素的值，用作返回
final E element = l.item;
//儲存待刪除元素的前驅節點
final Node<E> prev = l.prev;
//將待刪除節點的內容，前驅節點設定為空
l.item = null;
l.prev = null; // help GC
//將他的下一個節點設定為尾節點
last = prev;
//判斷prev是否為空，如果為空證明原連結串列只有一個節點，刪除之後是空連結串列
if (prev == null)
first = null;
else
//將尾節點的後續節點設定為空
prev.next = null;
size--;
modCount++;
return element;
}複製程式碼

工具函式

public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}

/**
* Removes and returns the last element from this list.
*
* @return the last element from this list
* @throws NoSuchElementException if this list is empty
*/
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}複製程式碼

五：總結

元素原始碼我們可以看出LinkedList在新增刪除元素時，不需要像ArrayList一樣去擴容。而在根據元素所在位置去查詢元素時又不像ArrayList中一樣直接去取，而是需要遍歷。所以LinkedList更多的適用於頻繁新增刪除，而查詢不多的場景下。

根據位置查詢元素時先判斷離頭節點近還是尾節點近這種優化方式我們也可以用於日常的程式碼中

LinkedList是執行緒不安全的，在遍歷的過程中我們儘量使用迭代器進行遍歷