1 LinkedList
1.1 底層結(jié)構(gòu)
底層的數(shù)據(jù)結(jié)構(gòu)是雙向鏈表結(jié)構(gòu)，有一個頭結(jié)點和一個尾結(jié)點，雙向鏈表意味著我們可以從頭開始正向遍歷，或者是從尾開始逆向遍歷，并且可以針對頭部和尾部進行相應(yīng)的操作。
1.2 優(yōu)缺點
雙向鏈表實現(xiàn)，增刪快，查找慢
2 四個關(guān)注點
| 關(guān)注點 | 結(jié)論 |
|---|---|
| LinkedList是否允許空 | 允許 |
| LinkedList是否允許重復(fù)數(shù)據(jù) | 允許 |
| LinkedList是否有序 | 有序 |
| LinkedList是否線程安全 | 非線程安全 |
3 LinkedList源碼解析
3.1 類的繼承關(guān)系
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
說明：LinkedList的類繼承結(jié)構(gòu)很有意思，我們著重要看是Deque接口，Deque接口表示是一個雙端隊列，那么也意味著LinkedList是雙端隊列的一種實現(xiàn)，所以，基于雙端隊列的操作在LinkedList中全部有效。
3.2 類的內(nèi)部類
private static class Node<E> {
E item; // 數(shù)據(jù)域
Node<E> next; // 后繼
Node<E> prev; // 前驅(qū)
// 構(gòu)造函數(shù)，賦值前驅(qū)后繼
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
說明：內(nèi)部類Node就是實際的結(jié)點，用于存放實際元素的地方。
3.3 類的屬性
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
// 實際元素個數(shù)
transient int size = 0;
// 頭結(jié)點
transient Node<E> first;
// 尾結(jié)點
transient Node<E> last;
}
說明：LinkedList的屬性非常簡單，一個頭結(jié)點、一個尾結(jié)點、一個表示鏈表中實際元素個數(shù)的變量。注意，頭結(jié)點、尾結(jié)點都有transient關(guān)鍵字修飾，這也意味著在序列化時該域是不會序列化的。
3.4 類的構(gòu)造函數(shù)
1. LinkedList()型構(gòu)造函數(shù)
public LinkedList() {
}
2. LinkedList(Collection<? extends E>)型構(gòu)造函數(shù)
public LinkedList(Collection<? extends E> c) {
// 調(diào)用無參構(gòu)造函數(shù)
this();
// 添加集合中所有的元素
addAll(c);
}
說明：會調(diào)用無參構(gòu)造函數(shù)，并且會把集合中所有的元素添加到LinkedList中。
3.5 核心函數(shù)分析
1.add函數(shù)
public boolean add(E e) {
// 添加到末尾
linkLast(e);
return true;
}
說明：add函數(shù)用于向LinkedList中添加一個元素，并且添加到鏈表尾部。具體添加到尾部的邏輯是由linkLast函數(shù)完成的。
void linkLast(E e) {
// 保存尾結(jié)點，l為final類型，不可更改
final Node<E> l = last;
// 新生成結(jié)點的前驅(qū)為l,后繼為null
final Node<E> newNode = new Node<>(l, e, null);
// 重新賦值尾結(jié)點
last = newNode;
if (l == null) // 尾結(jié)點為空
first = newNode; // 賦值頭結(jié)點
else // 尾結(jié)點不為空
l.next = newNode; // 尾結(jié)點的后繼為新生成的結(jié)點
// 大小加1
size++;
// 結(jié)構(gòu)性修改加1
modCount++;
}
說明：對于添加一個元素至鏈表中會調(diào)用add方法 -> linkLast方法。
示例（向LinkedList中添加兩個元素）
List<Integer> lists = new LinkedList<Integer>();
lists.add(5);
lists.add(6);
2.addAll函數(shù)
addAll有兩個重載函數(shù)，addAll(Collection<? extends E>)型和addAll(int, Collection<? extends E>)型，我們平時習(xí)慣調(diào)用的addAll(Collection<? extends E>)型可轉(zhuǎn)化為addAll(int, Collection<? extends E>)型，所以我們著重分析此函數(shù)即可。
// 添加一個集合
public boolean addAll(int index, Collection<? extends E> c) {
// 檢查插入的的位置是否合法
checkPositionIndex(index);
// 將集合轉(zhuǎn)化為數(shù)組
Object[] a = c.toArray();
// 保存集合大小
int numNew = a.length;
if (numNew == 0) // 集合為空，直接返回
return false;
Node<E> pred, succ; // 前驅(qū)，后繼
if (index == size) { // 如果插入位置為鏈表末尾，則后繼為null，前驅(qū)為尾結(jié)點
succ = null;
pred = last;
} else { // 插入位置為其他某個位置
succ = node(index); // 尋找到該結(jié)點
pred = succ.prev; // 保存該結(jié)點的前驅(qū)
}
for (Object o : a) { // 遍歷數(shù)組
@SuppressWarnings("unchecked") E e = (E) o; // 向下轉(zhuǎn)型
// 生成新結(jié)點
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null) // 表示在第一個元素之前插入(索引為0的結(jié)點)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
if (succ == null) { // 表示在最后一個元素之后插入
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
// 修改實際元素個數(shù)
size += numNew;
// 結(jié)構(gòu)性修改加1
modCount++;
return true;
}
說明：參數(shù)中的index表示在索引下標(biāo)為index的結(jié)點（實際上是第index + 1個結(jié)點）的前面插入。在addAll函數(shù)中，addAll函數(shù)中還會調(diào)用到node函數(shù)，get函數(shù)也會調(diào)用到node函數(shù)，此函數(shù)是根據(jù)索引下標(biāo)找到該結(jié)點并返回，具體代碼如下
Node<E> node(int index) {
// 判斷插入的位置在鏈表前半段或者是后半段
if (index < (size >> 1)) { // 插入位置在前半段
Node<E> x = first;
for (int i = 0; i < index; i++) // 從頭結(jié)點開始正向遍歷
x = x.next;
return x; // 返回該結(jié)點
} else { // 插入位置在后半段
Node<E> x = last;
for (int i = size - 1; i > index; i--) // 從尾結(jié)點開始反向遍歷
x = x.prev;
return x; // 返回該結(jié)點
}
}
說明：在根據(jù)索引查找結(jié)點時，會有一個小優(yōu)化，結(jié)點在前半段則從頭開始遍歷，在后半段則從尾開始遍歷，這樣就保證了只需要遍歷最多一半結(jié)點就可以找到指定索引的結(jié)點。
示例
3. remove函數(shù)
public boolean remove(Object o) {
if (o == null) { //刪除的元素為空
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else { //刪除的元素不為空
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
說明：在調(diào)用remove移除結(jié)點時，會調(diào)用到unlink函數(shù)，unlink函數(shù)具體如下：
E unlink(Node<E> x) {
// 保存結(jié)點的元素
final E element = x.item;
// 保存x的后繼
final Node<E> next = x.next;
// 保存x的前驅(qū)
final Node<E> prev = x.prev;
if (prev == null) { // 前驅(qū)為空，表示刪除的結(jié)點為頭結(jié)點
first = next; // 重新賦值頭結(jié)點
} else { // 刪除的結(jié)點不為頭結(jié)點
prev.next = next; // 賦值前驅(qū)結(jié)點的后繼
x.prev = null; // 結(jié)點的前驅(qū)為空，切斷結(jié)點的前驅(qū)指針
}
if (next == null) { // 后繼為空，表示刪除的結(jié)點為尾結(jié)點
last = prev; // 重新賦值尾結(jié)點
} else { // 刪除的結(jié)點不為尾結(jié)點
next.prev = prev; // 賦值后繼結(jié)點的前驅(qū)
x.next = null; // 結(jié)點的后繼為空，切斷結(jié)點的后繼指針
}
x.item = null; // 結(jié)點元素賦值為空
// 減少元素實際個數(shù)
size--;
// 結(jié)構(gòu)性修改加1
modCount++;
// 返回結(jié)點的舊元素
return element;
}
