LinkedList是java集合架構下的成員，底層資料基礎為雙向連結清單，非線程安全集合
從源碼看LinkedList
- 1 LinkedList的繼承實作
- 2 LinkedList的資料基礎
- 2 LinkedList的初始化
-
- 2.1 無參構造
- 2.1 帶有初始元素集合的構造
- 3 LinkedList的元素新增示例
-
- 3.M.1 addAll(int index, Collection<? extends E> c)
- 3.M.2 add(int index, E element)
- 4 LinkedList的元素删除示例
-
- 4.M.1 remove(int index)
- 5 LinkedList的元素擷取示例
-
- 5.M.1 get(int index)
- 5.M.2 getFirst()
- 6 LinkedList的元素修改示例
-
- 6.M.1 set(int index, E element)
- 7 LinkedList的疊代器
-
- 7.1 雙向疊代器
- 7.2 逆向疊代器
- 7.3 可分割疊代器
- 8 總結
1 LinkedList的繼承實作
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
AbstractSequentialList
對僅允許順序通路的資料存儲方式（如連結清單，不支援随機通路）提供了最低限度的随機通路架構實作，當然對于允許随機通路的資料存儲形式（如數組，支援随機通路），
AbstractSequentialList
是劣于
AbstractList
的。LinkedList繼承了
AbstractSequentialList
抽象類，是以LinkedList也具有可以随機通路的特性。
List
接口為List集合基礎接口。
Cloneable
接口的實作說明LinkedList能夠被克隆
java.io.Serializable
接口的實作說明LinkedList能夠被序列化
Deque
為雙向隊列的基礎接口，實作
Deque
意味着LinkedList可以作為一個雙向隊列使用。
2 LinkedList的資料基礎
LinkedList采用雙向連結清單進行資料存儲。
LinkedList定義了
first
記錄雙向連結清單的頭節點：
last
雙向連結清單的尾節點：
雙向連結清單的節點類型為内部類
Node
：
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;
}
}
定義了
size
實時記錄元素數量
2 LinkedList的初始化
2.1 無參構造
/**
* Constructs an empty list.
*/
public LinkedList() {
}
LinkedList的無參構造沒有進行任何動作。
2.1 帶有初始元素集合的構造
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
調用無參構造，然後調用
addAll
方法進行元素新增。
addAll
為一個公共方法，留到下面元素新增環節再分析。
3 LinkedList的元素新增示例
元素新增方面選用單條新增方法
add(int index, E element)
與批量新增方法
addAll(int index, Collection<? extends E> c)
作為新增邏輯的示例方法：
3.M.1 addAll(int index, Collection<? extends E> c)
描述：從指定位置，将指定集合中的所有元素按照指定集合的疊代器傳回的順序追加到目前LinkedList的末尾
源碼：
public boolean addAll(int index, Collection<? extends E> c) {
// index的合法性校驗，要求index >= 0 && index <= size,否則抛出IndexOutOfBoundsException:
checkPositionIndex(index);
// 轉為數組形式
Object[] a = c.toArray();
// 獲得元素數量
int numNew = a.length;
// 指定集合為空的話就直接傳回
if (numNew == 0)
return false;
// pred為插入點的前一個元素
// succ為原插入點元素
Node<E> pred, succ;
// index == size意味着從尾巴鍊入
if (index == size) { // 剛好在末尾的話
succ = null; // size處元素是null
pred = last; // size上一個就是size-1，也就是last
} else { // 從中間鍊入
succ = node(index); // 擷取node處的元素，見3.M.5.1 node(int index)
pred = succ.prev; // 記錄pred
}
// 周遊數組o
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
// 構造新節點，前一個節點就是pred，後一個節點還未生成，暫定null
Node<E> newNode = new Node<>(pred, e, null);
// 如果pred為空，也就是原來集合内沒有元素，那麼這個節點就是頭節點
if (pred == null)
first = newNode;
else // 否則的話newNode連結到pred的next上
pred.next = newNode;
pred = newNode; // 重置pred,新元素成為pred,作為下一個元素的上一個元素
}
// succ是斷開處，如果斷開處為空，說明是從末尾插入的，就要修正last
if (succ == null) {
last = pred;
} else { // 否則的話就要把succ連結上
pred.next = succ;
succ.prev = pred;
}
size += numNew; // 修正size
modCount++; // modCount記錄
return true;
}
3.M.1.1 node(int index)
描述：傳回指定元素索引處的（非空）節點
源碼：
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;
}
}
備注：通過一次中分周遊減少周遊次數，可以看到雙向連結清單的随機通路隻能從頭節點或者尾節點一步步周遊過去，效率較低
3.M.2 add(int index, E element)
描述：在指定位置插入指定元素
源碼：
public void add(int index, E element) {
// index的合法性校驗，要求index >= 0 && index <= size,否則抛出IndexOutOfBoundsException:
checkPositionIndex(index);
// ==size就是從末尾插入，直接調用3.M.2.1 linkLast(E e)
if (index == size)
linkLast(element);
else // 否則調用linkBefore
linkBefore(element, node(index));
}
3.M.2.1 linkLast(E e)
描述：将e作為最後一個元素連入集合
源碼：
void linkLast(E e) {
// 記錄原末尾last
final Node<E> l = last;
// 建立節點：因為是首元素，是以上一個節點為原last，下一個節點為null
final Node<E> newNode = new Node<>(l, e, null);
// last屬性指向新的尾節點
last = newNode;
// 如果是第一個元素，那麼他即是尾節點，又是首節點
if (l == null)
first = newNode;
else // 修正原last節點的next為新節點
l.next = newNode;
size++; // 修正size
modCount++; // modCount記錄
}
3.M.2.2 linkBefore(E e, Node<E> succ)
描述：在非空節點succ之前插入元素e
源碼：
void linkBefore(E e, Node<E> succ) {
// succ一定要不為空，否則就NullPointerException了
final Node<E> pred = succ.prev;
// newNode的後一個元素就是succ,前一個元素就是succ的prev
final Node<E> newNode = new Node<>(pred, e, succ);
// 修正succ的prev
succ.prev = newNode;
// pred為空說明succ原來是第一個元素，那麼在succ前插入元素也要修改first
if (pred == null)
first = newNode;
else //否則的話要修正pred的next，由succ改為newNode
pred.next = newNode;
size++; // 修正size
modCount++; // modCount記錄
}
備注：可以看到，連結清單的插入隻是一個斷鍊與連結的過程，比數組的複制移位效率高多了
4 LinkedList的元素删除示例
元素移除方面選用定點移出方法
remove(int index)
作為移除邏輯的示例方法：
4.M.1 remove(int index)
描述：删除此集合中指定位置的元素
源碼：
public E remove(int index) {
// index合法性校驗，要求index >= 0 && index < size，否則抛出IndexOutOfBoundsException
checkElementIndex(index);
// node方法即為3.M.1.1 node(int index)，獲得指定位置的元素
return unlink(node(index));
}
4.M.1.1 unlink(Node<E> x)
備注:斷開非空節點x
源碼：
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
// 獲得x的next和prev
final Node<E> next = x.next;
final Node<E> prev = x.prev;
// prev 為null說明x是首元素
if (prev == null) {
first = next;
} else { // 否則的話prev的next由x改為x的next， x.prev也要斷鍊
prev.next = next;
x.prev = null;
}
// next同理
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
// 斷開x對實際資料的強連結
x.item = null;
size--; //修正size
modCount++; // modCount記錄
return element;
}
備注：移除操作，隻需重置前一個元素的next和後一個元素的prev，并清除x的指向，即可移除一個元素，無需移動元素。
5 LinkedList的元素擷取示例
元素新增方面選用随機通路方法
get(int index)
以及首節點通路方法
getFirst()
作為擷取邏輯的示例方法：
5.M.1 get(int index)
備注：傳回此集合中指定位置的元素
源碼：
public E get(int index) {
// index合法性校驗，要求index >= 0 && index < size，否則抛出IndexOutOfBoundsException
checkElementIndex(index);
// 直接調用3.M.1.1 node(int index)
return node(index).item;
}
備注：随機通路需要從端部進行周遊，相較于數組的直接找到目标位置，是一個比較耗時的操作
5.M.2 getFirst()
備注：傳回此集合中的第一個元素
源碼：
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item; //直接傳回firs
}
備注：因為LinkedList分别用
first
與
last
記錄了首尾元素，是以LinkedList的端部通路還是很迅速的，LinkedList的查詢慢僅限于随機通路。
6 LinkedList的元素修改示例
元素修改方面選用
set(int index, E element)
作為修改邏輯的示例方法：
6.M.1 set(int index, E element)
描述：用指定的元素替換此集合中指定位置的元素
源碼：
public E set(int index, E element) {
// index合法性校驗，要求index >= 0 && index < size，否則抛出IndexOutOfBoundsException
checkElementIndex(index);
// 直接調用3.M.1.1 node(int index)獲得目标元素x
Node<E> x = node(index);
// 直接修改x.item,連斷鍊與重見node都不需要
E oldVal = x.item;
x.item = element;
return oldVal;
}
7 LinkedList的疊代器
7.1 雙向疊代器
LinkedList中可以通過
listIterator(int index)
方法獲得集合的雙向疊代器：
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
LinkedList的雙向疊代器是通過内部類
ListItr
實作的：
private class ListItr implements ListIterator<E> {
// 上一個傳回的節點
private Node<E> lastReturned;
// 下一個要傳回的節點
private Node<E> next;
// 下一個要傳回的節點下标
private int nextIndex;
// modCount記錄
private int expectedModCount = modCount;
ListItr(int index) {
// assert isPositionIndex(index);
// index == size的話直接就是尾端了,next就null
next = (index == size) ? null : node(index);
nextIndex = index;
}
public boolean hasNext() {
return nextIndex < size;
}
// 通過next.next覆寫next的操作後移
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
... ... // 後續省略
}
可以看到ListItr是通過記錄
next
節點，然後通過
next
節點的
next
屬性與
prev
屬性進行前移或者後移。
lastReturned
節點的記錄主要是用來remove。
ListItr設定有
expectedModCount
屬性，這說明LinkedList在疊代期間也是不允許修改集合元素的，若要修改隻能通過ListItr的相關方法操作，邏輯思路和LinkedList相關方法類似，隻是多了
expectedModCount
修正，使得修改之後ListItr可以繼續疊代，而不會抛出
ConcurrentModificationException
。
7.2 逆向疊代器
LinkedList中可以通過
descendingIterator()
方法獲得集合的逆向疊代器：
public Iterator<E> descendingIterator() {
return new DescendingIterator();
}
逆向疊代器通過内部類
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();
}
}
DescendingIterator
是直接使用的雙向疊代器
ListItr
實作的。
7.3 可分割疊代器
LinkedList中可以通過
spliterator()
方法獲得集合的可分割疊代器：
@Override
public Spliterator<E> spliterator() {
return new LLSpliterator<E>(this, -1, 0);
}
可分割疊代器通過内部類LLSpliterator實作，但是LLSpliterator并不是采用記錄頭和尾節點，并在
trySplit
時修改頭尾節點的方式進行切割，而是通過LLSpliterator+ArraySpliterator方式實作的，
通過LLSpliterator的源碼進行分析：
7.3.M.1 構造方法
先看其構造方法：
LLSpliterator(LinkedList<E> list, int est, int expectedModCount) {
this.list = list;
this.est = est;
this.expectedModCount = expectedModCount;
}
指派了三個屬性，這三個屬性被定義為：
final LinkedList<E> list; // null OK unless traversed
int est; // size estimate; -1 until first needed
int expectedModCount; // initialized when est set
-
list
-
est
-
expectedModCount
而
spliterator()
方法調用構造方法時是
new LLSpliterator<E>(this, -1, 0)
。可以看到，除了第一個入參
list
入參為
this
表面時目前LinkedList集合，後面的
est=-1
與
expectedModCount=0
其實隻是相當于一個标記，标記着這個LLSpliterator還沒有初始化，和ArrayList的
ArrayListSpliterator
是一樣的，采用懶加載的方式，這麼做的好處是在spliterator實際使用前，LinkedList依然可以任意的修改自己的元素。
est
和
expectedModCount
的實際初始化時在LLSpliterator第一次使用時，通過
getEst()
方法進行初始化.
7.3.M.2 擷取剩餘元素數 - getEst()
final int getEst() {
int s; // force initialization
final LinkedList<E> lst;
if ((s = est) < 0) { // 未初始化
if ((lst = list) == null) // 空集合
s = est = 0;
else {
expectedModCount = lst.modCount;
current = lst.first; // 未切割時起點就是目前切割位置
s = est = lst.size; // 指派est
}
}
return s;
}
可以看到如果
est
小于0，意味未初始化，就執行
expectedModCount = lst.modCount;
，
current = lst.first;
，
est = lst.size;
就是很簡單的初始化，經曆這一步，LinkedList自身已經不可任意修改元素了。
最後傳回s,也就是est
7.3.M.3 切割-trySplit() - 核心方法
接下來看核心的
trySplit()
方法：
但是在分析切割邏輯之前先看一下LLSpliterator内的幾個屬性：
static final int BATCH_UNIT = 1 << 10; // batch array size increment
static final int MAX_BATCH = 1 << 25; // max batch array size;
int batch; // batch size for splits
Node<E> current; // current node; null until initialized
-
BATCH_UNIT
BATCH_UNIT
-
MAX_BATCH
MAX_BATCH
-
batch
-
current
了解了這個，接下來繼續分析
trySplit()
方法：
public Spliterator<E> trySplit() {
Node<E> p;
int s = getEst(); // getEst()上面已經分析過了，實際初始化以及獲得長度est
if (s > 1 && (p = current) != null) {
int n = batch + BATCH_UNIT; // 上一批的量加批次單元量，就得出這次的批次量
if (n > s) // 如果剩餘的元素小于這次的批次量，那麼批次量就重置為剩餘量
n = s;
if (n > MAX_BATCH) // 保證批次量最大為MAX_BATCH
n = MAX_BATCH;
Object[] a = new Object[n]; // n長度的數組
int j = 0; // 周遊下标
// 前面有p = current，這裡就是從current開始找n個資料放到數組a裡面
do { a[j++] = p.item; } while ((p = p.next) != null && j < n);
current = p; // 修正current到新的節點
batch = j; // 這一批的元素量
est = s - j; // 修正剩餘元素量
// 傳回的是ArraySpliterator
return Spliterators.spliterator(a, 0, j, Spliterator.ORDERED);
}
return null;
}
可以看到LLSpliterator的每次
trySplit()
,批次量都會以
BATCH_UNIT
為單元量進行遞增，直到
MAX_BATCH
或者剩餘元素量低于批次量
n
，也就是說在元素量足夠大的情況下：
- 那麼第一次調用
LLSpliterator.trySplit()
- 第二次調用
LLSpliterator.trySplit()
為什麼LLSpliterator對于已經切出去的資料使用ArraySpliterator管理而不是繼續自己管理呢，還是因為連結清單随機通路能力效率較低的原因，Spliterator的切割方式采用中位切割的方式，切割時很重要的一步就是找到中位，數組可以通過計算下标直接鎖定中位，但是連結清單不行，連結清單必須從頭周遊，周遊一半的元素才能鎖定中位，Spliterator一旦使用，很大可能會經曆不隻一次切割，是以使用ArraySpliterator以獲得更高的切割效率，這是一種以空間換效率的方式。
7.3.M.4 forEachRemaining與tryAdvance
源碼：
public void forEachRemaining(Consumer<? super E> action) {
Node<E> p; int n;
if (action == null) throw new NullPointerException();
if ((n = getEst()) > 0 && (p = current) != null) {
current = null; // 全周遊的current就到頭了，就不一步步修改了，直接一步到位
est = 0; // est也是直接沒了，一步到位設為0
do {
E e = p.item;
p = p.next; // 用next周遊
action.accept(e);
} while (p != null && --n > 0);
}
if (list.modCount != expectedModCount)
throw new ConcurrentModificationException();
}
分析：這裡隻放了
forEachRemaining
的源碼，是因為
forEachRemaining
與
tryAdvance
的邏輯差異不大，都是通過節點的
next
屬性後移執行，屬于連結清單周遊的基本方式，并沒有特别的地方。
8 總結
- LinkedList以雙向連結清單作為底層資料結構進行資料存儲，這使得其增删快速且無需擴容操作，但是随機通路的效率較差
- LinkedList是一個有序集合，這個有序是指其元素順序與插入順序一緻
- LinkedList不是線程安全的集合
- LinkedList不允許在疊代的過程中直接修改集合資料，但是可以通過疊代器進行間接修改
- LinkedList的可分割疊代器通過ArraySpliterator + LLSpliterator共同實作，以獲得更高的切割效率
- LinkedList可以作為一個雙向隊列使用，可以進行雙向周遊
- LinkedList可以實作FIFO（先進先出）與LIFO（後進先出）
PS：
【JAVA核心知識】系列導航 [持續更新中…]
上篇導航：7: 從源碼看ArrayList:一文看懂ArrayList
下篇導航：9: 從源碼看HashMap:一文看懂HashMap
歡迎關注
![Java小案例——随機數猜測随機數猜測[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)