LinkedList簡介
LinkedList 是一個繼承於AbstractSequentialList的雙向鏈表。它也可以被當作堆棧、隊列或雙端隊列進行操作。
LinkedList 實現 List 接口，能對它進行隊列操作。
LinkedList 實現 Deque 接口，即能將LinkedList當作雙端隊列使用。
LinkedList 實現了Cloneable接口，即覆蓋了函數clone()，能克隆。
LinkedList 實現java.io.Serializable接口，這意味著LinkedList支持序列化，能通過序列化去傳輸。
LinkedList 是非同步的。
LinkedList構造函數
// 默認構造函數
LinkedList()
// 創建一個LinkedList，保護Collection中的全部元素。
LinkedList(Collection extends E> collection)
LinkedList的API
boolean add(E object)
void add(int location, E object)
boolean addAll(Collection extends E> collection)
boolean addAll(int location, Collection extends E> collection)
void addFirst(E object)
void addLast(E object)
void clear()
Object clone()
boolean contains(Object object)
Iterator
E element()
E get(int location)
E getFirst()
E getLast()
int indexOf(Object object)
int lastIndexOf(Object object)
ListIterator
boolean offer(E o)
boolean offerFirst(E e)
boolean offerLast(E e)
E peek()
E peekFirst()
E peekLast()
E poll()
E pollFirst()
E pollLast()
E pop()
void push(E e)
E remove()
E remove(int location)
boolean remove(Object object)
E removeFirst()
boolean removeFirstOccurrence(Object o)
E removeLast()
boolean removeLastOccurrence(Object o)
E set(int location, E object)
int size()
Object[] toArray()
AbstractSequentialList簡介
在介紹LinkedList的源碼之前，先介紹一下AbstractSequentialList。畢竟，LinkedList是AbstractSequentialList的子類。
AbstractSequentialList 實現了get(int index)、set(int index, E element)、add(int index, E element) 和 remove(int index)這些函數。這些接口都是隨機訪問List的，LinkedList是雙向鏈表；既然它繼承於AbstractSequentialList，就相當於已經實現了“get(int index)這些接口”。
此外，我們若需要通過AbstractSequentialList自己實現一個列表，只需要擴展此類，並提供 listIterator() 和 size() 方法的實現即可。若要實現不可修改的列表，則需要實現列表迭代器的 hasNext、next、hasPrevious、previous 和 index 方法即可。
LinkedList與Collection關係如下圖：
LinkedList的本質是雙向鏈表。
(01) LinkedList繼承於AbstractSequentialList，並且實現了Dequeue接口。
(02) LinkedList包含兩個重要的成員：header 和 size。
header是雙向鏈表的表頭，它是雙向鏈表節點所對應的類Entry的實例。Entry中包含成員變量： previous, next, element。其中，previous是該節點的上一個節點，next是該節點的下一個節點，element是該節點所包含的值。
size是雙向鏈表中節點的個數。
LinkedList遍歷方式
LinkedList支持多種遍歷方式。建議不要採用隨機訪問的方式去遍歷LinkedList，而採用逐個遍歷的方式。
(01) 第一種，通過迭代器遍歷。即通過Iterator去遍歷。
for(Iterator iter = list.iterator(); iter.hasNext();)
iter.next();
(02) 通過快速隨機訪問遍歷LinkedList
int size = list.size();
for (int i=0; i list.get(i); } (03) 通過另外一種for循環來遍歷LinkedList for (Integer integ:list) ; (04) 通過pollFirst()來遍歷LinkedList while(list.pollFirst() != null) ; (05) 通過pollLast()來遍歷LinkedList while(list.pollLast() != null) ; (06) 通過removeFirst()來遍歷LinkedList try { while(list.removeFirst() != null) ; } catch (NoSuchElementException e) { } (07) 通過removeLast()來遍歷LinkedList try { while(list.removeLast() != null) ; } catch (NoSuchElementException e) { } 測試這些遍歷方式效率的代碼如下： View Code 執行結果： iteratorLinkedListThruIterator：8 ms iteratorLinkedListThruForeach：3724 ms iteratorThroughFor2：5 ms iteratorThroughPollFirst：8 ms iteratorThroughPollLast：6 ms iteratorThroughRemoveFirst：2 ms iteratorThroughRemoveLast：2 ms 由此可見，遍歷LinkedList時，使用removeFist()或removeLast()效率最高。但用它們遍歷時，會刪除原始數據；若單純只讀取，而不刪除，應該使用第3種遍歷方式。 無論如何，千萬不要通過隨機訪問去遍歷LinkedList！ 出處：http://www.cnblogs.com/skywang12345/p/3308807.html
閱讀更多 JAVA熊 的文章
