在JDK1.7之前，LinkedList是采用雙向環(huán)形鏈表來實現(xiàn)的，在1.7及之后，Oracle將LinkedList做了優(yōu)化，將環(huán)形鏈表改成了線性鏈表。本文對于LinkedList的源碼分析基于JDK1.8。
LinkedList既然是通過一個雙向線性鏈表來實現(xiàn)，那么肯定就能夠很輕易的找到鏈表的第一個節(jié)點和最后一個節(jié)點，在源碼中可以看到有這兩個字段：
transient Node<E> first; // 鏈表第一個節(jié)點
transient Node<E> last; // 鏈表最后一個節(jié)點
先來看一下什么是節(jié)點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;
}
}
節(jié)點Node中有三個成員：
- item ： 存儲的元素
- next ： 下一個節(jié)點
- prev ： 上一個節(jié)點
節(jié)點中保存有需要存儲的元素，同時持有上一個節(jié)點和下一個節(jié)點的引用，各個節(jié)點依次持有前后節(jié)點的引用就形成了一個鏈，這樣，當(dāng)我們需要查找鏈中某一個節(jié)點保存的元素時，只需要通過第一個節(jié)點或者最后一個節(jié)點依次查找，就可以找到我們需要的節(jié)點。
需要注意的是，在JDK1.7及之后，第一個節(jié)點first的前一個節(jié)點prev為null，最后一個節(jié)點last的后一個節(jié)點next也為null。而在JDK1.6及之前，頭節(jié)點header是一個不保存元素的節(jié)點，header的下一個節(jié)點next是第一個元素節(jié)點，而header的上一個節(jié)點是最后一個元素節(jié)點，這樣使得它形成一個環(huán)形的雙向鏈表。
LinkedList的構(gòu)造函數(shù)有兩個，一個無參，另一個可以傳入一個集合：
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
看下addAll方法的實現(xiàn)：
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
// 檢查是否越界
checkPositionIndex(index);
// 將集合c轉(zhuǎn)化為數(shù)組a
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
// pred為插入元素位置點前一個節(jié)點，succ為插入元素位置的后一個節(jié)點
Node<E> pred, succ;
if (index == size) { // index==size的話，在鏈表的末尾添加元素
succ = null;
pred = last;
} else { // 否則的話，從鏈表中間加入
succ = node(index);
pred = succ.prev;
}
// 遍歷需要加入的元素數(shù)組a
for (Object o : a) {
// 通過元素o構(gòu)造一個節(jié)點Node
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null) // 插入位置的前一個節(jié)點為null，說明需要插入的是first節(jié)點
first = newNode;
else // 插入位置的前一個節(jié)點不為null，即從鏈表中或鏈表末尾插入
// 將要插入的節(jié)點復(fù)制給插入位置的上一個節(jié)點的next
pred.next = newNode;
// 將newNode賦值給下個需要插入的節(jié)點的pred
pred = newNode;
}
if (succ == null) { // succ為null，說明是從末尾添加的元素，將添加的最后一個元素賦值給last
last = pred;
} else { // 從鏈表中某個位置添加的，重新連接上添加元素時斷開的引用鏈
pred.next = succ;
succ.prev = pred;
}
// 更新鏈表的大小
size += numNew;
modCount++;
return true;
}
在構(gòu)造方法中調(diào)用addAll方法，相當(dāng)于是向一個空鏈表中添加集合c中的元素。
如果是在已有元素的鏈表中調(diào)用addAll方法來添加元素的話，就需要判斷指定的添加位置index是否越界，如果越界會拋出異常；如果沒有越界，根據(jù)添加的位置index，斷開鏈表中index位置的節(jié)點前后的引用，加入新元素，重新連上斷開位置的前后節(jié)點的引用。過程如下圖：
add方法:
public boolean add(E e) {
linkLast(e);
return true;
}
直接就調(diào)用了linkLast方法，說明默認(rèn)的add方法是直接將元素添加到已有的鏈表的末尾。
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;
size++;
modCount++;
}
新加入元素的節(jié)點賦值給last節(jié)點，然后判斷了一下加入之前的last節(jié)點是否為空，為空的話，說明鏈表中沒有元素，新加入的就是鏈表的first節(jié)點；不為空直接將之前的最后一個節(jié)點的next引用添加的節(jié)點即可。
還有一個add方法，指定了添加位置：
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
先判斷是否越界，在判斷添加的位置是否在已有鏈表的末尾，如果在末尾就直接添加到末尾，不在末尾的話，調(diào)用linkBefore添加到index位置的節(jié)點之前。
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
pred為null的話，說明succ是添加元素前鏈表的first節(jié)點，加入元素e，更新first節(jié)點，并更改引用鏈。
addFirst和addLast方法中分別調(diào)用了linkFirst方法和linkLast方法：
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++;
}
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;
size++;
modCount++;
}
linkFirst/linkLast方法即是將新節(jié)點添加到鏈表的頭部或者尾部，更新鏈表的prev和next引用。
remove方法：
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;
}
不管需要移除的元素O是否為空，都是遍歷后調(diào)用unlink方法來刪除節(jié)點，繼續(xù)看unlink方法：
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) {
// 如果prev為null的話，那么刪除的是first節(jié)點，將next指定為刪除后的first節(jié)點
first = next;
} else {
// prev不為null，將prev的next引用指向next，并解除x元素對prev的引用
prev.next = next;
x.prev = null;
}
if (next == null) {
// 如果next為null，那么刪除的是last節(jié)點，將prev指定為刪除后的last節(jié)點
last = prev;
} else {
// next不為null，將next的prev引用指向prev，并解除x的next引用
next.prev = prev;
x.next = null;
}
// 置空x節(jié)點中的元素
x.item = null;
size--;
modCount++;
return element;
}
removeFirst和removeLast方法同樣是直接調(diào)用了unlinkFirst和unlinkLast，實現(xiàn)和unlink差不多，不做過多解釋。
set方法，set方法即修改鏈表中指定位置的元素：
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
找到指定位置的節(jié)點x，更改該節(jié)點的item屬性就行了。
獲取節(jié)點的node方法：
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;
}
}
判斷位置index是靠近頭部還是尾部，靠近頭部，則從first節(jié)點往后遍歷，靠近尾部則從last節(jié)點往前遍歷，這種方式可以使得鏈表查找的時候遍歷次數(shù)不會超過鏈表長度的一半，從而提升查找效率。
get、getFirst、getLast方法：
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
getFirst和getLast直接后去first和last節(jié)點中的元素值，get方法則直接調(diào)用了node方法，不再解釋。
LinkedList源碼中的其他方法不再分析了，實現(xiàn)都很容易理解。從LinkedList的增、刪、改、查等方法的實現(xiàn)邏輯可以看出來，LinkedList的增和刪效率相對于改和查要高，因為每次修改和查詢都要從鏈表的頭節(jié)點或尾節(jié)點開始遍歷，而增加和刪除，只需要在制定位置斷開節(jié)點引用，添加和刪除元素后，重新連上引用鏈即可。所以，LinkedList適合用在添加和刪除比較頻繁，而修改和查詢較少的情況下。
