以下內容基於jdk1.7.0_79源碼；
List接口的鏈表實現，並提供了一些隊列，棧，雙端隊列操作的方法；
與ArrayList對比，LinkedList插入和刪除操作更加高效，隨機訪問速度慢；
可以作為棧、隊列、雙端隊列數據結構使用；
非同步，線程不安全；
與ArrayList、Vector一樣，LinkedList的內部迭代器存在“快速失敗行為”；
支持null元素、有順序、元素可以重復；
以上接口和類中，關於Iterable接口、Collection接口、List接口、 Cloneable、 java.io.Serializable接口、AbstractCollection類、AbstractList類的相關說明，在介紹ArrayList的時候，已經有了個大概說明，這裡將主要了解下Queue接口、Deque接口、AbstractSequentialList類以及LinkedList類；
隊列接口，定義了一些隊列的基本操作，
注意使用時優先選擇以下藍色字體方法（offer、poll、peek），隊列通常不允許null元素，因為我們通常調用poll方法是否返回null來判斷隊列是否為空，但是LinkedList是允許null元素的，所以，在使用LinkedList最為隊列的實現時，不應該將null元素插入隊列；
boolean add(E e);
將對象e插入隊列尾部，成功返回true，失敗（沒有空間）拋出異常IllegalStateException；
boolean offer(E e);
將對象e插入隊列尾部，成功返回true，失敗（沒有空間）返回false；
E remove();
獲取並移除隊列頭部元素，如果隊列為空，拋出NoSuchElementException異常；
E poll();
獲取並移除隊列頭部元素，如果隊列為空，返回null；
E element();
獲取但不移除隊列頭部元素，如果隊列為空，拋出NoSuchElementException異常；
E peek();
獲取但不移除隊列頭部元素，如果隊列為空，返回null；
舉個簡單的例子，基於LinkedList實現的隊列，代碼如下：
package com.pichen.basis.col;
import java.util.LinkedList;
import java.util.Queue;
public class LinkListTest {
public static void main(String[] args) {
Queue<Integer> linkedListQueue = new LinkedList<Integer>();
//入隊
linkedListQueue.offer(3);
linkedListQueue.offer(4);
linkedListQueue.offer(2);
linkedListQueue.offer(1);
//出隊
Integer tmp;
while((tmp = linkedListQueue.poll()) != null){
System.out.println(tmp);
}
System.out.println(linkedListQueue.peek());
}
}
雙端隊列接口，繼承隊列接口，支持在隊列兩端進行入隊和出隊操作；
除了Collection接口Queue接口中定義的方法外，Deque還包括以下方法
void addFirst(E e);
將對象e插入到雙端隊列頭部，容間不足時，拋出IllegalStateException異常；
void addLast(E e);
將對象e插入到雙端隊列尾部，容間不足時，拋出IllegalStateException異常；
boolean offerFirst(E e);
將對象e插入到雙端隊列頭部
boolean offerLast(E e);
將對象e插入到雙端隊列尾部；
E removeFirst();
獲取並移除隊列第一個元素，隊列為空，拋出NoSuchElementException異常；
E removeLast();
獲取並移除隊列最後一個元素，隊列為空，拋出NoSuchElementException異常；
E pollFirst();
獲取並移除隊列第一個元素，隊列為空，返回null；
E pollLast();
獲取並移除隊列最後一個元素，隊列為空，返回null；
E getFirst();
獲取隊列第一個元素，但不移除，隊列為空，拋出NoSuchElementException異常；
E getLast();
獲取隊列最後一個元素，但不移除，隊列為空，拋出NoSuchElementException異常；
E peekFirst();
獲取隊列第一個元素，隊列為空，返回null；
E peekLast();
獲取隊列最後一個元素，隊列為空，返回null；
boolean removeFirstOccurrence(Object o);
移除第一個滿足 (o==null ? e==null : o.equals(e)) 的元素
boolean removeLastOccurrence(Object o);
移除最後一個滿足 (o==null ? e==null : o.equals(e)) 的元素
void push(E e);
將對象e插入到雙端隊列頭部；
E pop();
移除並返回雙端隊列的第一個元素
Iterator<E> descendingIterator();
雙端隊列尾部到頭部的一個迭代器；
一個抽象類，基於迭代器實現數據的隨機訪問,以下方法的含義, 之前也說過，簡單地說，就是數據的隨機存取（利用了一個索引index）；
public E get(int index)
public E set(int index, E element)
public void add(int index, E element)
public E remove(int index)
public boolean addAll(int index, Collection<? extends E> c)
LinkedList的具體實現，
LinkedList中有兩個關鍵成員屬性，隊頭結點和隊尾結點：
transient Node<E> first; //隊頭節點 transient Node<E> last; //隊尾節點
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;
}
}
至於LinkedList提供的每個方法的含義，在前面隊列、雙端隊列、集合等接口中都有說明了，這裡簡單的舉一兩個方法的具體實現，對照源碼了解下，其實就是鏈表的操作：
poll方法,出隊操作
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
/**
* Unlinks non-null first node f.
*/
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;
}
獲取並移除雙端隊列頭部元素，如上代碼，主要實現在unlinkFirst方法內，首先直接獲取被刪節點，臨時存儲其具體引用的對象element和下個引用next，然後將被刪節點對象引用和下個節點引用置null給gc回收，改變雙端隊列隊頭結點為被刪節點的下個引用next，如果next為空，將雙端隊列的隊尾結點last置null，否則將next節點的前引用置null；隊列長度減減，操作次數加加（快速失敗機制），返回被刪節點引用的具體對象；
public E get(int index)方法，隨機訪問方法
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
/**
* Returns the (non-null) Node at the specified element 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;
}
}
LinkedList隨機訪問性能較差，首先是判斷索引index合法性，然後調用node(int index)方法，在node方法中，做了一點優化，先判斷要訪問節點的索引是在隊列的前半部分還是後半部分，如果在前半部分則從隊頭開始遍歷，否則從隊尾開始遍歷，如上代碼所示。
適用場合很重要，注意和ArrayList區分開來，根據集合的各自特點以及具體場景，選擇合適的List實現；
這裡舉個簡單例子，分別使用ArrayList和LinkedList，測試下兩個集合隨機訪問的性能，可以發現使用LinkedList隨機訪問的效率較ArrayList差很多；
package com.pichen.basis.col;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Stack;
import java.util.Vector;
public class Test {
public static void main(String[] args) {
//初始化linkedList和arrayList數據
LinkedList<Integer> linkedList = new LinkedList<Integer>();
for(int i = 0; i < 10000; i++){
linkedList.offerLast(i);
}
List<Integer> arrayList = new ArrayList<Integer>();
for(int i = 0; i < 10000; i++){
arrayList.add(i);
}
long s, e;
s = System.currentTimeMillis();
for(int i = 0; i < 10000; i++){
linkedList.get(i);
}
e = System.currentTimeMillis();
System.out.println("linkedList:" + (e - s) + "ms");
s = System.currentTimeMillis();
for(int i = 0; i < 10000; i++){
arrayList.get(i);
}
e = System.currentTimeMillis();
System.out.println("arrayList:" + (e - s) + "ms");
}
}
結果打印：
linkedList:56ms arrayList:1ms
