衆所周知，LinkedList是基于連結清單實作的。
目錄
基本屬性
構造方法
增加元素(插入元素)
删除元素
其他方法
疊代器
總結
基本屬性
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
基本屬性中給出了長度，頭結點和尾結點，都是transient，即 不可序列化。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;
}
}
由定義可以看出，每個結點都包含指向其前一個和後一個結點的兩個結點，還包含一個“資料”，類型為泛型 E
好吧，明擺着雙向連結清單嘛。
構造方法
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
兩個構造方法，無參構造和根據已有Collection構造LinkedList;
根據已有Collection構造LinkedList先是無參構造，再将c全部add進去，既然這裡用到了add，那咱就先看LinkedList元素的增加方法
增加元素(插入元素)
public boolean add(E e) {
linkLast(e);
return true;
}
// 頭插
public void addFirst(E e) {
linkFirst(e);
}
// 尾插
public void addLast(E e) {
linkLast(e);
}
boolean add(E e)
傳回值為boolean類型，增加成功傳回true；add方法是在其最後加入待加元素。
void linkLast(E e) 在list最後插入元素
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++;
}
一句話：原list為空，則參數做新頭；若不為空，則參數加到末節點後。具體如下：
這個方法先拿出原末節點l，根據末節點l和參數建立新節點，更新新末節點last
判斷原末節點是否為空，若是，則證明原先list無元素，新節點為list首節點；若非空，将新節點加到原末節點l後。更新size和modCount，根據上次ArrayList的經驗，modCound應該是在疊代器中做判斷的。
void linkFirst(E e) 在list頭插入元素
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++;
}
思想如上說過的尾插法，因為LinkList基于雙向連結清單實作，是以插入操作隻需改變結點兩個指針指向就行，這點比ArrayList的增加插入要簡便的多！
void add(int index, E element)
在下标位置處插入元素
參數：一個下标，一個元素。
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
首先檢查下标合法性checkPositionIndex(index)
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
當然進行判斷，判斷該下标是不是最後。來決定如何插入。
說說 linkBefore(element, node(index)
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++;
}
傳入參數為一個元素，和一個結點（通過下标得到的）、
取出參數結點的前驅結點，以新元素創造一個新節點，連接配接至前驅結點後參數結點前
再更新各結點指向關系完成操作！
boolean addAll(Collection<? extends E> c)
傳回值boolean，參數為一個集合
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
調用
boolean addAll(int index, Collection<? extends E> c)
另外傳入一個index下标。即插入到該下标位置
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);
// 将參數轉化為數組，若次數組長度為0.則直接傳回false
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
// 準備兩個結點
// 可以了解為：這兩個結點就是參數c的頭和尾
// 頭list連接配接待插元素，尾list連接配接原list下标及之後元素
// 判斷插入的位置是否在原list最後（判斷尾的位置）
// 因為在尾部直接加和在中間插入一段的操作完全不同
// 這裡用到了node(index)方法。取出下标結點，尾list，這個方法我一會說。
// 頭list當然就是尾之前的一個喽
Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
// 思路很簡單了：将參數轉化的數組，依次插入到頭list後；
// 再将尾list接到頭list之後 （當然這裡肯定要分null和非null情況）
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
首先檢查下标合法性checkPositionIndex(index)。上面說過這個方法
代碼如上，因為比較長，以注釋形式寫出了。
這是剛才說到的取下标結點的方法 Node<E> 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;
}
}
很簡單，就是周遊，但增加了一個判斷。用來決定從頭開始還是從尾開始。
删除元素
1.删除頭或尾元素
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
E removeFirst() 和 E removeLast() 兩個方法，字面意思，移除并傳回頭或尾的元素。傳回為泛型E，調用E unlinkLast(Node<E> node)方法和E unlinkFirst(Node<E> node)方法
E unlinkFirst(Node<E> node) 斷開傳入頭結點的連接配接并傳回該結點元素，移除該結點
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
根據傳入結點的得到其元素，以後傳回的就是他。
得到傳入結點的下一個元素，目的是更新頭結點。舊頭結點的各“指針”和 元素 也要更新為null。為什麼？友善GC（垃圾回收裝置）回收，釋放記憶體。
同時新頭結點的資訊（前驅結點）也要更新為null；接着就是更新List的各屬性。
E unlinkLast(Node<E> node) 斷開傳入尾結點的連接配接并傳回該結點元素，移除該結點
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
看，思路同unlinkFirst(Node<E> node)，主要操作：更新結點資訊！置空！友善GC回收！
2.删除List元素（根據下标）
E remove(int index)
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
參數：下标
檢查下标合法，不多說了，要删除就要先找到這個下标結點，Node<E> node(int index)取結點啊，這個方法上面說過！
（回顧一下：根據下标和List的size比較，決定從頭還是尾開始周遊！）
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;
}
}
主要在于E unlink(Node<E> x) 移除傳入結點并傳回結點元素
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) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
思路：得到結點元素，更新傳入結點的指向關系，這個很好了解。此方法兼具删除頭尾結點的功能，注意判斷！
3.删除List元素（根據元素（對象object））
boolean remove(Object o)
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;
}
源碼給出的方法很好了解：判斷參數是否為null，再分别從頭至尾周遊，找出包含此元素的結點，用unlink(Node<E> x)删除之。
我們發現源碼中還有一個boolean removeLastOccurrence(Object o)
public boolean removeLastOccurrence(Object o) {
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
同上，不過是逆向周遊，另！删除逆向找到的第一個元素立刻就傳回了，達到删除最後一個參數元素的目的！
其他方法
clean() 清空List
public void clear() {
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}
從頭開始周遊List，置空，以友善GC回收
E get(int index) 根據下标擷取下标結點元素
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
無容置疑，一旦涉及下标，就要判斷下标合法性，然後通過node(int index)得到下标結點，進而得到結點内的元素
E set(int index，E element) 根據下标擷取并設定下标結點元素
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
當然，檢查下标，通過node(int index)方法獲得下标結點，進而得到其更改前元素，設定新元素，傳回舊元素
另外，源碼中還有，peek，push，pop等一系列簡單的方法，就是基于上面連結清單的增加，和删除操作完成的。
疊代器
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned;
private Node<E> next;
private int nextIndex;
private int expectedModCount = modCount;
ListItr(int index) {
// assert isPositionIndex(index);
next = (index == size) ? null : node(index);
nextIndex = index;
}
public boolean hasNext() {
return nextIndex < size;
}
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
public boolean hasPrevious() {
return nextIndex > 0;
}
public E previous() {
checkForComodification();
if (!hasPrevious())
throw new NoSuchElementException();
lastReturned = next = (next == null) ? last : next.prev;
nextIndex--;
return lastReturned.item;
}
public int nextIndex() {
return nextIndex;
}
public int previousIndex() {
return nextIndex - 1;
}
public void remove() {
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;
unlink(lastReturned);
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}
public void set(E e) {
if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();
lastReturned.item = e;
}
public void add(E e) {
checkForComodification();
lastReturned = null;
if (next == null)
linkLast(e);
else
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}
public void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (modCount == expectedModCount && nextIndex < size) {
action.accept(next.item);
lastReturned = next;
next = next.next;
nextIndex++;
}
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
疊代器采用了以内部類方式實作了Iterator接口
lastReturned;
next;
nextIndex;
用以上三個來更新位置
expectedModCount = modCount;
前面好多方法都有modCount++的原因了 是一個辨別，用來檢查在使用疊代器的同時，LInkedList有沒有被外面修改，如果在使用疊代器的時候對List進行修改，就會抛出異常
hasNext() 隻需檢查遊标有沒有到size，傳回true或者false
如果仍有元素可以疊代或有多個元素，則傳回 true。
next() 傳回疊代的下一個元素。
remove() 從疊代器指向的 collection 中移除疊代器傳回的最後一個元素，并将遊标移動到此處，證明此處是有元素的，這也就 同時解釋了沒有用 == null判斷了
checkForComodification() 用來檢查在使用疊代器的同時，List有沒有被外面修改的方法
疊代器的實作，不管實在ArrayList還是LinkedList中實作的思路都是一樣的。我認為，其核心還是在于為保證安全對modCount的判斷。
總結：
LinkedList是基于雙向連結清單實作的
LinkedList也不是線程安全的
在增加，删除，查找，設定指定下标元素的時候，都要先判斷以決定從頭or從尾開始周遊
相比于ArrayList，LinkedList在增删方面更為出色，ArrayList則需要大量元素的移動，甚至list的複制和擴容，但在取方面，推薦ArrayList。這就是為什麼LinkList中有堆棧的pop和push方法，而ArrayList沒有了。可見，在Java源碼中，堆棧和隊列也是用LinkedList實作的。
![Java小案例——随機數猜測随機數猜測[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)