文章目錄
LinkedList是基于雙向連結清單資料結構實作的Java集合(jdk1.8以前基于雙向連結清單)，在閱讀源碼之前，有必要簡單了解一下連結清單。
先了解一下連結清單的概念：連結清單是由一系列非連續的節點組成的存儲結構，簡單分下類的話，連結清單又分為單向連結清單和雙向連結清單，而單向/雙向連結清單又可以分為循環連結清單和非循環連結清單。
- 單向連結清單：單向連結清單就是通過每個結點的指針指向下一個結點進而連結起來的結構，最後一個節點的next指向null。
- 單向循環連結清單：單向循環連結清單和單向清單的不同是，最後一個節點的next不是指向null，而是指向head節點，形成一個“環”。
- 雙向連結清單：向連結清單是包含兩個指針的，pre指向前一個節點，next指向後一個節點，但是第一個節點head的pre指向null，最後一個節點的tail指向null。
圖一：常見連結清單
- 雙向循環連結清單：向循環連結清單和雙向連結清單的不同在于，第一個節點的pre指向最後一個節點，最後一個節點的next指向第一個節點，也形成一個“環”。
圖二：雙向循環連結清單
通過類圖可以看到，LinkedList不僅實作了List接口，而且實作了現了Queue和Deque接口，是以它既能作為List使用，也能作為雙端隊列使用，也可以作為棧使用。
LinkedList有一個靜态内部類，我們看到在雙連結清單中每個節點有前趨、後繼、資料域，節點類實作了這個結構。
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;
}
} 看一下LinkedList的主要屬性。first和last對應了雙連結清單的頭結點和尾結點。
//元素個數
transient int size = 0;
//頭結點
transient Node<E> first;
//尾結點
transient Node<E> last; //無參
public LinkedList() {
}
//從其它集合中構造
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
} 雙向連結清單的靈活處就是連結清單中的一個元素結構就可以向左或者向右開始周遊查找需要的元素結構。是以對于一個有序連結清單，查詢的效率比單連結清單高一些。因為，我們可以記錄上次查找的位置 p，每次查詢時，根據要查找的值與 p 的大小關系，決定是往前還是往後查找，是以平均隻需要查找一半的資料。
連結清單查詢示意圖如下：
//根據索引擷取資料
public E get(int index) {
//越界判斷
checkElementIndex(index);
//根據index擷取節點
return node(index).item;
}
//根據索引擷取節點
Node<E> node(int index) {
// 因為是雙連結清單
// 是以根據index是在前半段還是後半段決定從前周遊還是從後周遊
// 這樣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;
}
}
- 頭插法
private void linkFirst(E e) {
// 首節點
final Node<E> f = first;
// 建立新節點，新節點的next是首節點
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
// 判斷連結清單是不是為空
// 如果是就把last也置為新節點
// 否則把原首節點的prev指針置為新節點
if (f == null)
last = newNode;
else
f.prev = newNode;
//元素個數加1
size++;
// 修改次數 +1，用于 fail-fast 處理
modCount++;
}
public void addFirst(E e) {
linkFirst(e);
} - 尾插法
void linkLast(E e) {
//尾結點
final Node<E> l = last;
//新節點
final Node<E> newNode = new Node<>(l, e, null);
//尾結點置為新節點
last = newNode;
//如果連結清單為空，頭結點指向尾結點
if (l == null)
first = newNode;
else
l.next = newNode;
//元素個數加1
size++;
// 修改次數 +1，用于 fail-fast 處理
modCount++;
}
public void addLast(E e) {
linkLast(e);
}
public boolean add(E e) {
linkLast(e);
return true;
} 在連結清單頭部和尾部插入時間複雜度都是O(1)，頭插法和尾插法的示意圖如下：
- 中間插入法：中間插入需要找到插入位置節點，改變該節點的前趨和該節點前趨節點的後繼
//根據索引插入節點
public void add(int index, E element) {
//判斷是否越界
checkPositionIndex(index);
//未插入
if (index == size)
linkLast(element);
else
//找到索引位置節點，在該節點前插入新節點
linkBefore(element, node(index));
}
// 在節點succ之前添加元素
void linkBefore(E e, Node<E> succ) {
//節點succ的前趨節點
final Node<E> pred = succ.prev;
//新節點
final Node<E> newNode = new Node<>(pred, e, succ);
//改變節點succ的前趨指向
succ.prev = newNode;
// 判斷前置節點是否為空
// 如果為空，說明是第一個添加的元素，頭結點重新指派
// 否則修改前置節點的next為新節點
if (pred == null)
first = newNode;
else
pred.next = newNode;
//元素個數加1
size++;
// 修改次數 +1，用于 fail-fast 處理
modCount++;
}
在中間添加元素效率低一些，首先要先找到插入位置的節點，再修改前後節點的指針，時間複雜度為O(n)。
雙連結清單中删除元素隻需要改變前趨和後繼的指向。
- 删除頭節點
//删除頭節點
public E removeFirst() {
final Node<E> f = first;
//如果連結清單為空，抛出異常
if (f == null)
throw new NoSuchElementException();
// 删除首節點
return unlinkFirst(f);
}
// 删除頭節點
private E unlinkFirst(Node<E> f) {
// 頭結點
final E element = f.item;
//頭結點後繼節點
final Node<E> next = f.next;
//頭結點資料域後繼置空，幫助GC
f.item = null;
f.next = null;
//頭結點置為後繼節點
first = next;
// 如果隻有一個元素，删除了，把last也置為空
// 否則把next的前趨置為空
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
//傳回删除的節點
return element;
} - 删除尾結點
//删除尾結點
public E removeLast() {
//尾結點
final Node<E> l = last;
//連結清單為空，抛出異常
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
//删除尾結點
private E unlinkLast(Node<E> l) {
// 尾結點元素
final E element = l.item;
//尾結點前趨節點
final Node<E> prev = l.prev;
//尾結點資料、前趨置為null，幫助GC
l.item = null;
l.prev = null;
//尾結點置為前趨節點
last = prev;
// 如果隻有一個元素，删除了把first置為空
// 否則把前置節點的next置為空
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
//傳回删除的節點
return element;
} 注意：
不管是上一節的頭插入和未插入，還是這一節的删除頭節點和删除尾結點，都沒有在List中定義。前面提到，LinkedList實作了Deque接口，是以這是作為雙向隊列的LinkedList插入和删除元素的方式。還有擷取頭結點和尾結點的方法getFirst()和getLast()，同樣都是雙向隊列的實作。
- 删除指定位置的節點
//删除指定位置的節點
public E remove(int index) {
//檢查越界情況
checkElementIndex(index);
//根據索引找到節點，删除
return unlink(node(index));
}
//删除指定節點
E unlink(Node<E> x) {
// 删除節點的值
final E element = x.item;
//被删除節點的後繼節點
final Node<E> next = x.next;
//被删除節點的前趨節點
final Node<E> prev = x.prev;
// 如果前趨節點為空
// 說明是首節點，讓first指向x的後繼節點
// 否則修改前置節點的next為x的後繼節點
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
// 如果後繼節點為空
// 說明是尾節點，讓last指向x的前趨節點
// 否則修改後置節點的prev為x的前趨節點
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
// 清空x的元素值，協助GC
x.item = null;
// 元素個數減1
size--;
// 修改次數加1，fail-fast
modCount++;
//傳回删除的元素
return element;
}
删除頭尾節點，時間複雜度為O(1)。
在中間删除元素，首先要找到删除位置的節點，再修改前後指針，時間複雜度為O(n)。
前面還提到，LinkedList可以作為棧使用，棧的特點是先進後出，LinkedList同樣有作為棧的方法實作。
入棧：插入頭節點
public void push(E e) {
addFirst(e);
} 出棧：删除頭結點
public E pop() {
return removeFirst();
} LinkedList作為Java中連結清單的實作，ArrayList作為順序表的實作（
ArrayList源碼閱讀筆記），LinkedList常常被拿來和ArrayList來進行比較。
LinkedList、ArrayList基本操作時間效率對比如下(粗略對比)：
| 操作 | ArrayList | LinkedList |
| get(int index) | O(1) | O(n)，平均 n / 4步 |
| add(E element) | 最壞情況（擴容）O(n) ，平均O(1) | |
| add(int index, E element) | O(n) ,平均n / 2步 | |
| remove(int index) | O(n) 平均n /2步 |
簡而言之，需要頻繁讀取集合中的元素時，使用ArrayList效率較高，而在插入和删除操作較多時，使用LinkedList效率較高。