1 LinkedList
1.1 底層結(jié)構(gòu)
底層的數(shù)據(jù)結(jié)構(gòu)是雙向鏈表結(jié)構(gòu)矫俺，有一個(gè)頭結(jié)點(diǎn)和一個(gè)尾結(jié)點(diǎn)，雙向鏈表意味著我們可以從頭開始正向遍歷，或者是從尾開始逆向遍歷，并且可以針對(duì)頭部和尾部進(jìn)行相應(yīng)的操作蔗包。
1.2 優(yōu)缺點(diǎn)
雙向鏈表實(shí)現(xiàn)，增刪快慧邮，查找慢
2 四個(gè)關(guān)注點(diǎn)
| 關(guān)注點(diǎ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接口表示是一個(gè)雙端隊(duì)列误澳，那么也意味著LinkedList是雙端隊(duì)列的一種實(shí)現(xiàn)耻矮，所以，基于雙端隊(duì)列的操作在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就是實(shí)際的結(jié)點(diǎn)，用于存放實(shí)際元素的地方。
3.3 類的屬性
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
// 實(shí)際元素個(gè)數(shù)
transient int size = 0;
// 頭結(jié)點(diǎn)
transient Node<E> first;
// 尾結(jié)點(diǎn)
transient Node<E> last;
}
說明：LinkedList的屬性非常簡單哨免，一個(gè)頭結(jié)點(diǎn)勾扭、一個(gè)尾結(jié)點(diǎn)、一個(gè)表示鏈表中實(shí)際元素個(gè)數(shù)的變量铁瞒。注意，頭結(jié)點(diǎn)桅滋、尾結(jié)點(diǎn)都有transient關(guān)鍵字修飾慧耍，這也意味著在序列化時(shí)該域是不會(huì)序列化的。
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);
}
說明：會(huì)調(diào)用無參構(gòu)造函數(shù)丐谋，并且會(huì)把集合中所有的元素添加到LinkedList中芍碧。
3.5 核心函數(shù)分析
1.add函數(shù)
public boolean add(E e) {
// 添加到末尾
linkLast(e);
return true;
}
說明：add函數(shù)用于向LinkedList中添加一個(gè)元素，并且添加到鏈表尾部号俐。具體添加到尾部的邏輯是由linkLast函數(shù)完成的泌豆。
void linkLast(E e) {
// 保存尾結(jié)點(diǎn)，l為final類型吏饿，不可更改
final Node<E> l = last;
// 新生成結(jié)點(diǎn)的前驅(qū)為l,后繼為null
final Node<E> newNode = new Node<>(l, e, null);
// 重新賦值尾結(jié)點(diǎn)
last = newNode;
if (l == null) // 尾結(jié)點(diǎn)為空
first = newNode; // 賦值頭結(jié)點(diǎn)
else // 尾結(jié)點(diǎn)不為空
l.next = newNode; // 尾結(jié)點(diǎn)的后繼為新生成的結(jié)點(diǎn)
// 大小加1
size++;
// 結(jié)構(gòu)性修改加1
modCount++;
}
說明：對(duì)于添加一個(gè)元素至鏈表中會(huì)調(diào)用add方法 -> linkLast方法踪危。
示例（向LinkedList中添加兩個(gè)元素）
List<Integer> lists = new LinkedList<Integer>();
lists.add(5);
lists.add(6);
2.addAll函數(shù)
addAll有兩個(gè)重載函數(shù)，addAll(Collection<? extends E>)型和addAll(int, Collection<? extends E>)型猪落，我們平時(shí)習(xí)慣調(diào)用的addAll(Collection<? extends E>)型可轉(zhuǎn)化為addAll(int, Collection<? extends E>)型贞远，所以我們著重分析此函數(shù)即可。
// 添加一個(gè)集合
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é)點(diǎn)
succ = null;
pred = last;
} else { // 插入位置為其他某個(gè)位置
succ = node(index); // 尋找到該結(jié)點(diǎn)
pred = succ.prev; // 保存該結(jié)點(diǎn)的前驅(qū)
}
for (Object o : a) { // 遍歷數(shù)組
@SuppressWarnings("unchecked") E e = (E) o; // 向下轉(zhuǎn)型
// 生成新結(jié)點(diǎn)
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null) // 表示在第一個(gè)元素之前插入(索引為0的結(jié)點(diǎn))
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
if (succ == null) { // 表示在最后一個(gè)元素之后插入
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
// 修改實(shí)際元素個(gè)數(shù)
size += numNew;
// 結(jié)構(gòu)性修改加1
modCount++;
return true;
}
說明：參數(shù)中的index表示在索引下標(biāo)為index的結(jié)點(diǎn)（實(shí)際上是第index + 1個(gè)結(jié)點(diǎn)）的前面插入袱结。在addAll函數(shù)中，addAll函數(shù)中還會(huì)調(diào)用到node函數(shù)途凫，get函數(shù)也會(huì)調(diào)用到node函數(shù)垢夹，此函數(shù)是根據(jù)索引下標(biāo)找到該結(jié)點(diǎn)并返回，具體代碼如下
Node<E> node(int index) {
// 判斷插入的位置在鏈表前半段或者是后半段
if (index < (size >> 1)) { // 插入位置在前半段
Node<E> x = first;
for (int i = 0; i < index; i++) // 從頭結(jié)點(diǎn)開始正向遍歷
x = x.next;
return x; // 返回該結(jié)點(diǎn)
} else { // 插入位置在后半段
Node<E> x = last;
for (int i = size - 1; i > index; i--) // 從尾結(jié)點(diǎn)開始反向遍歷
x = x.prev;
return x; // 返回該結(jié)點(diǎn)
}
}
說明：在根據(jù)索引查找結(jié)點(diǎn)時(shí)颖榜，會(huì)有一個(gè)小優(yōu)化棚饵，結(jié)點(diǎn)在前半段則從頭開始遍歷，在后半段則從尾開始遍歷掩完，這樣就保證了只需要遍歷最多一半結(jié)點(diǎn)就可以找到指定索引的結(jié)點(diǎn)噪漾。
示例
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ǎn)時(shí)，會(huì)調(diào)用到unlink函數(shù)且蓬，unlink函數(shù)具體如下：
E unlink(Node<E> x) {
// 保存結(jié)點(diǎn)的元素
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é)點(diǎn)為頭結(jié)點(diǎn)
first = next; // 重新賦值頭結(jié)點(diǎn)
} else { // 刪除的結(jié)點(diǎn)不為頭結(jié)點(diǎn)
prev.next = next; // 賦值前驅(qū)結(jié)點(diǎn)的后繼
x.prev = null; // 結(jié)點(diǎn)的前驅(qū)為空，切斷結(jié)點(diǎn)的前驅(qū)指針
}
if (next == null) { // 后繼為空恶阴，表示刪除的結(jié)點(diǎn)為尾結(jié)點(diǎn)
last = prev; // 重新賦值尾結(jié)點(diǎn)
} else { // 刪除的結(jié)點(diǎn)不為尾結(jié)點(diǎn)
next.prev = prev; // 賦值后繼結(jié)點(diǎn)的前驅(qū)
x.next = null; // 結(jié)點(diǎn)的后繼為空诈胜，切斷結(jié)點(diǎn)的后繼指針
}
x.item = null; // 結(jié)點(diǎn)元素賦值為空
// 減少元素實(shí)際個(gè)數(shù)
size--;
// 結(jié)構(gòu)性修改加1
modCount++;
// 返回結(jié)點(diǎn)的舊元素
return element;
}
