【Java深入研究】2、JDK 1.8 LinkedList源码解析
LinkedList是一個實現了List接口和Deque接口的雙端鏈表。?
有關索引的操作可能從鏈表頭開始遍歷到鏈表尾部，也可能從尾部遍歷到鏈表頭部，這取決于看索引更靠近哪一端。?
LinkedList不是線程安全的，如果想使LinkedList變成線程安全的，可以使用如下方式：
List list=Collections.synchronizedList(new LinkedList(...));
iterator()和listIterator()返回的迭代器都遵循fail-fast機制。?
LinkedList的繼承關系如下圖所示：?
?
從上圖可以看出LinkedList與ArrayList的不同之處，ArrayList直接繼承自AbstractList，而LinkedList繼承自AbstractSequentialList，然后再繼承自AbstractList。另外，LinkedList還實現了Dequeu接口，雙端隊列。
內部結構
LinkedList內部是一個雙端鏈表的結構，結構如下圖：?
從上圖可以看出，LinkedList內部是一個雙端鏈表結構，有兩個變量，first指向鏈表頭部，last指向鏈表尾部。?
LinkedtList內部的成員變量如下：
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
其中size表示當前鏈表中的數據個數。下面是Node節點的定義，Node類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;}}從Node的定義可以看出鏈表是一個雙端鏈表的結構。
構造方法
LinkedList有兩個構造方法，一個用于構造一個空的鏈表，一個用已有的集合創建鏈表。如下：
public LinkedList() {}public LinkedList(Collection<? extends E> c) {this();addAll(c);//添加集合中所有元素}當使用第二個構造方法時，會調用addAll()方法將集合中的元素添加到鏈表中，添加的操作后面會詳細介紹。
添加操作
因為LinkedList即實現了List接口，又實現了Deque接口，所以LinkedList既可以添加將元素添加到尾部，也可以將元素添加到指定索引位置，還可以添加添加整個集合；另外既可以在頭部添加，又可以在尾部添加。下面我們分別從List接口和Deque接口分別介紹。
List接口的添加操作
add(E e)
add(E e)用于將元素添加到鏈表尾部，實現如下:
public boolean add(E e) {linkLast(e);return true;}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++;}從上面代碼可以看到，linkLast方法中就是一個鏈表尾部添加一個雙端節點的操作，但是需要注意對鏈表為空時頭節點的處理。
add(int index,E e)
add(int index,E e)用于在指定位置添加元素。實現如下：
public void add(int index, E element) {checkPositionIndex(index); //檢查索引是否處于[0-size]之間if (index == size)//添加在鏈表尾部 linkLast(element);else//添加在鏈表中間 linkBefore(element, node(index));}從上面代碼可以看到，主要分為3步：?
1. 檢查index的范圍，否則拋出異常?
2. 如果插入位置是鏈表尾部，那么調用linkLast方法?
3. 如果插入位置是鏈表中間，那么調用linkBefore方法
linkLast方法前面已經討論了，下面看一下linkBefore的實現。在看linkBefore之前，先看一下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;}}從上面可以看到，node(int index)方法將根據index是靠近頭部還是尾部選擇不同的遍歷方向。一旦得到了指定索引位置的節點，再看linkBefore()方法，實現如下：
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;elsepred.next = newNode;size++;modCount++;}linkBefore()方法在第二個參數節點之前插入一個新節點。示意圖如下：?
從上圖以及代碼可以看到linkBefore主要分三步：?
1. 創建newNode節點，將newNode的后繼指針指向succ，前驅指針指向pred?
2. 將succ的前驅指針指向newNode?
3. 根據pred是否為null，進行不同操作。?
- 如果pred為null，說明該節點插入在頭節點之前，要重置first頭節點?
- 如果pred不為null，那么直接將pred的后繼指針指向newNode即可
addAll方法
addAll有兩個重載方法，一個參數的方法表示將集合元素添加到鏈表尾部，而兩個參數的方法指定了開始插入的位置。實現如下：
//將集合插入到鏈表尾部，即開始索引位置為size public boolean addAll(Collection<? extends E> c) {return addAll(size, c);}//將集合從指定位置開始插入 public boolean addAll(int index, Collection<? extends E> c) {//Step 1:檢查index范圍 checkPositionIndex(index);//Step 2:得到集合的數據Object[] a = c.toArray();int numNew = a.length;if (numNew == 0)return false;//Step 3：得到插入位置的前驅節點和后繼節點Node<E> pred, succ;//如果插入位置為尾部，前驅節點為last，后繼節點為nullif (index == size) {succ = null;pred = last;}//否則，調用node()方法得到后繼節點，再得到前驅節點else {succ = node(index);pred = succ.prev;}//Step 4：遍歷數據將數據插入for (Object o : a) {@SuppressWarnings("unchecked") E e = (E) o;//創建新節點Node<E> newNode = new Node<>(pred, e, null);//如果插入位置在鏈表頭部if (pred == null)first = newNode;elsepred.next = newNode;pred = newNode;}//如果插入位置在尾部，重置last節點if (succ == null) {last = pred;}//否則，將插入的鏈表與先前鏈表連接起來else {pred.next = succ;succ.prev = pred;}size += numNew;modCount++;return true;}從上面的代碼可以看到，addAll方法主要分為4步：?
1. 檢查index索引范圍?
2. 得到集合數據?
3. 得到插入位置的前驅和后繼節點?
4. 遍歷數據，將數據插入到指定位置
Deque接口的添加操作
addFirst(E e)方法
addFirst()方法用于將元素添加到鏈表頭部，其實現如下:
public void addFirst(E e) {linkFirst(e);}private void linkFirst(E e) {final Node<E> f = first;final Node<E> newNode = new Node<>(null, e, f);//新建節點，以頭節點為后繼節點first = newNode;//如果鏈表為空，last節點也指向該節點if (f == null)last = newNode;//否則，將頭節點的前驅指針指向新節點elsef.prev = newNode;size++;modCount++;}從上面的代碼看到，實現就是在頭節點插入一個節點使新節點成為新節點，但是和linkLast一樣需要注意當鏈表為空時，對last節點的設置。
addLast(E e)方法
addLast()方法用于將元素添加到鏈表尾部，與add()方法一樣。所以實現也一樣，如下：
public void addLast(E e) {linkLast(e);}offer(E e)方法
offer(E e)方法用于將數據添加到鏈表尾部，其內部調用了add(E e)方法，如下：
public boolean offer(E e) {return add(e);}offerFirst(E e)方法
offerFirst()方法用于將數據插入鏈表頭部，與addFirst的區別在于該方法可以返回特定的返回值，而addFirst的返回值為void。
public boolean offerFirst(E e) {addFirst(e);return true;}offerLast(E e)方法
offerLast()與addLast()的區別和offerFirst()和addFirst()的區別一樣，所以這兒就不多說了。
添加操作總結
LinkedList由于實現了List和Deque接口，所以有多種添加方法，下面總結了一下。?
- 將數據插入到鏈表尾部?
- boolean add(E e):?
- void addLast(E e)?
- boolean offerLast(E e)?
- 將數據插入到鏈表頭部?
- void addFirst(E e)?
- boolean offerFirst(E e)?
- 將數據插入到指定索引位置?
- boolean add(int index,E e)
檢索操作
根據位置取數據
獲取任意位置的get(int index)方法
get(int index)方法根據指定索引返回數據，如果索引越界，那么會拋出異常。實現如下：
public E get(int index) {//檢查邊界 checkElementIndex(index);return node(index).item;}從上面的代碼可以看到分為2步：?
1. 檢查index邊界，index>=0&&index
獲得位置為0的頭節點數據
LinkedList中有多種方法可以獲得頭節點的數據，實現大同小異，區別在于對鏈表為空時的處理，是拋出異常還是返回null。主要方法有getFirst()、element()、peek()、peekFirst()、方法。其中getFirst()和element()方法將會在鏈表為空時，拋出異常，它們的實現如下：
public E getFirst() {final Node<E> f = first;if (f == null)throw new NoSuchElementException();return f.item;} public E element() {return getFirst();}從代碼可以看到，element()方法的內部就是使用getFirst()實現的。它們會在鏈表為空時，拋出NoSuchElementException。下面再看peek()和peekFirst()的實現：
public E peek() {final Node<E> f = first;return (f == null) ? null : f.item;}public E peekFirst() {final Node<E> f = first;return (f == null) ? null : f.item;}從代碼可以看到，當鏈表為空時，peek()和peekFirst()方法返回null。
獲得位置為size-1的尾節點數據
獲得尾節點數據的方法有getLast()和peekLast()。getLast()的實現如下：
public E getLast() {final Node<E> l = last;if (l == null)throw new NoSuchElementException();return l.item;}可以看到，getLast()方法在鏈表為空時，會拋出NoSuchElementException，而peekLast()則不會，只是會返回null。實現如下：
public E peekLast() {final Node<E> l = last;return (l == null) ? null : l.item;}根據對象得到索引
根據對象得到索引分為兩種，一種是第一個匹配的索引，一個是最后一個匹配的索引，實現的在于一個從前往后遍歷，一個從后往前遍歷。下面先看idnexOf()方法的實現：
//返回第一個匹配的索引 public int indexOf(Object o) {int index = 0;if (o == null) {//從頭往后遍歷for (Node<E> x = first; x != null; x = x.next) {if (x.item == null)return index;index++;}} else {//從頭往后遍歷for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item))return index;index++;}}return -1;}從上面的代碼可以看到，LinkedList可以包含null元素，遍歷方式都是從前往后，一旦匹配了，就返回索引。?
lastIndexOf()方法返回最后一個匹配的索引，實現為從后往前遍歷，源碼如下：
檢查鏈表是否包含某對象
contains(Object o)方法檢查對象o是否存在于鏈表中，其實現如下：
public boolean contains(Object o) {return indexOf(o) != -1;}從代碼可以看到contains()方法調用了indexOf()方法，只要返回結果不是-1，那就說明該對象存在于鏈表中
檢索操作總結
檢索操作分為按照位置得到對象以及按照對象得到位置兩種方式，其中按照對象得到位置的方法有indexOf()和lastIndexOf()；按照位置得到對象有如下方法：?
- 根據任意位置得到數據的get(int index)方法，當index越界會拋出異常?
- 獲得頭節點數據?
- getFirst()和element()方法在鏈表為空時會拋出NoSuchElementException?
- peek()和peekFirst()方法在鏈表為空時會返回null?
- 獲得尾節點數據?
- getLast()在鏈表為空時會拋出NoSuchElementException?
- peekLast()在鏈表為空時會返回null
刪除操作
刪除操作分為按照位置刪除和按照對象刪除，其中按照位置刪除的方法又有區別，有的只是返回是否刪除成功的標志，有的還需要返回被刪除的元素。下面分別討論。
刪除指定對象
當刪除指定對象時，只需調用remove(Object o)即可，不過該方法一次只會刪除一個匹配的對象，如果刪除了匹配對象，返回true，否則false。其實現如下：
public boolean remove(Object o) {//如果刪除對象為nullif (o == null) {//從前向后遍歷for (Node<E> x = first; x != null; x = x.next) {//一旦匹配，調用unlink()方法和返回trueif (x.item == null) {unlink(x);return true;}}} else {//從前向后遍歷for (Node<E> x = first; x != null; x = x.next) {//一旦匹配，調用unlink()方法和返回trueif (o.equals(x.item)) {unlink(x);return true;}}}return false;}從代碼可以看到，由于LinkedList可以存儲null元素，所以對刪除對象以是否為null做區分。然后從鏈表頭開始遍歷，一旦匹配，就會調用unlink()方法將該節點從鏈表中移除。下面是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) {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;}上面的代碼可以用如下示意圖來解釋：?
第一步：得到待刪除節點的前驅節點和后繼節點?
第二步：刪除前驅節點?
第三步：刪除后繼節點?
經過三步，待刪除的結點就從鏈表中脫離了。需要注意的是刪除位置是頭節點或尾節點時候的處理，上面的示意圖沒有特別指出。
按照位置刪除對象
刪除任意位置的對象
boolean remove(int index)方法用于刪除任意位置的元素，如果刪除成功將返回true，否則返回false。實現如下：
public E remove(int index) {//檢查index范圍 checkElementIndex(index);//將節點刪除return unlink(node(index));}從上面可以看到remove(int index)操作有兩步：?
1. 檢查index范圍，屬于[0,size）?
2. 將索引出節點刪除
刪除頭節點的對象
刪除頭節點的對象的方法有很多，包括remove()、removeFirst()、pop()、poll()、pollFirst()，其中前三個方法在鏈表為空時將拋出NoSuchElementException，后兩個方法在鏈表為空時將返回null。?
remove()、pop()、removeFirst()的實現如下：
從上面代碼可以看到，remove()和pop()內部調用了removeFirst()方法，而removeFirst()在鏈表為空時將拋出NoSuchElementException。?
下面是poll()和pollFirst()的實現：
可以看到poll()和pollFirst()的實現代碼是相同的，在鏈表為空時將返回null。
刪除尾節點的對象
刪除尾節點的對象的方法有removeLast()和pollLast()。removeLast的實現如下：
public E removeLast() {final Node<E> l = last;if (l == null)throw new NoSuchElementException();return unlinkLast(l);}可以看到removeLast()在鏈表為空時將拋出NoSuchElementException。而pollLast()方法則不會，如下：
public E pollLast() {final Node<E> l = last;return (l == null) ? null : unlinkLast(l);}可以看到pollLast()在鏈表為空時會返回null，而不是拋出異常。
刪除操作總結
刪除操作由很多種方法，有：?
- 按照指定對象刪除：boolean remove(Object o)，一次只會刪除一個匹配的對象?
- 按照指定位置刪除?
- 刪除任意位置的對象：E remove(int index),當index越界時會拋出異常?
- 刪除頭節點位置的對象?
- 在鏈表為空時拋出異常：E remove()、E removeFirst()、E pop()?
- 在鏈表為空時返回null：E poll()、E pollFirst()?
- 刪除尾節點位置的對象?
- 在鏈表為空時拋出異常：E removeLast()?
- 在鏈表為空時返回null：E pollLast()
迭代器操作
LinkedList的iterator()方法內部調用了其listIterator()方法，所以可以只分析listIterator()方法。listIterator()提供了兩個重載方法。iterator()方法和listIterator()方法的關系如下：
public Iterator<E> iterator() {return listIterator();}public ListIterator<E> listIterator() {return listIterator(0);}public ListIterator<E> listIterator(int index) {checkPositionIndex(index);return new ListItr(index);}從上面可以看到三者的關系是iterator()——>listIterator(0)——>listIterator(int index)。最終都會調用listIterator(int index)方法，其中參數表示迭代器開始的位置。在ArrayList源碼分析中提到過ListIterator是一個可以指定任意位置開始迭代，并且有兩個遍歷方法。下面直接看ListItr的實現：
private class ListItr implements ListIterator<E> {private Node<E> lastReturned;private Node<E> next;private int nextIndex;private int expectedModCount = modCount;//保存當前modCount，確保fail-fast機制 ListItr(int index) {// assert isPositionIndex(index);next = (index == size) ? null : node(index);//得到當前索引指向的next節點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;}//獲取前一個節點，將next節點向前移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;elsenextIndex--;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);elselinkBefore(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();}}在ListIterator的構造器中，得到了當前位置的節點，就是變量next。next()方法返回當前節點的值并將next指向其后繼節點，previous()方法返回當前節點的前一個節點的值并將next節點指向其前驅節點。由于Node是一個雙端節點，所以這兒用了一個節點就可以實現從前向后迭代和從后向前迭代。另外在ListIterator初始時，exceptedModCount保存了當前的modCount，如果在迭代期間，有操作改變了鏈表的底層結構，那么再操作迭代器的方法時將會拋出ConcurrentModificationException。
例子
由于LinkedList是一個實現了Deque的雙端隊列，所以LinkedList既可以當做Queue，又可以當做Stack，下面的例子將LinkedList成Stack，代碼如下：
public class LinkedStack<E> {private LinkedList<E> linkedList;public LinkedStack() {linkedList = new LinkedList<E>();}//壓入數據public void push(E e) {linkedList.push(e);}//彈出數據，在Stack為空時將拋出異常public E pop() {return linkedList.pop();}//檢索棧頂數據，但是不刪除public E peek() {return linkedList.peek();}}在將LinkedList當做Stack時，使用pop()、push()、peek()方法需要注意的是LinkedList內部是將鏈表頭部當做棧頂，鏈表尾部當做棧底，也就意味著所有的壓入、攤入操作都在鏈表頭部進行。
總結
LinkedList是基于雙端鏈表的List，其內部的實現源于對鏈表的操作，所以適用于頻繁增加、刪除的情況；該類不是線程安全的；另外，由于LinkedList實現了Queue接口，所以LinkedList不止有隊列的接口，還有棧的接口，可以使用LinkedList作為隊列和棧的實現。
出處：http://blog.csdn.net/qq_19431333/article/details/54572876
總結
以上是生活随笔為你收集整理的【Java深入研究】2、JDK 1.8 LinkedList源码解析的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 纯JS实现带小圆点缩略图及左右箭头的轮播
- 下一篇： 将数据转化为API，OpenDataSo