Java集合篇：LinkedList源码分析
（注：本文內(nèi)容基于JDK1.6）
一、概述：
LinkedList與ArrayList一樣實現(xiàn)List接口，只是ArrayList是List接口的大小可變數(shù)組的實現(xiàn)，LinkedList是List接口鏈表的實現(xiàn)。基于鏈表實現(xiàn)的方式使得LinkedList在插入和刪除時更優(yōu)于ArrayList，而隨機訪問則比ArrayList遜色些。
LinkedList實現(xiàn)所有可選的列表操作，并允許所有的元素包括null。
除了實現(xiàn) List 接口外，LinkedList 類還為在列表的開頭及結(jié)尾 get、remove 和 insert 元素提供了統(tǒng)一的命名方法。這些操作允許將鏈接列表用作堆棧、隊列或雙端隊列。
此類實現(xiàn) Deque 接口，為 add、poll 提供先進先出隊列操作，以及其他堆棧和雙端隊列操作。
所有操作都是按照雙重鏈接列表的需要執(zhí)行的。在列表中編索引的操作將從開頭或結(jié)尾遍歷列表（從靠近指定索引的一端）。同時，與ArrayList一樣此實現(xiàn)不是同步的。
?
二、源碼分析：
LinkedList的定義：
public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable?從這段代碼中我們可以清晰地看出LinkedList繼承AbstractSequentialList，實現(xiàn)List、Deque、Cloneable、Serializable。其中AbstractSequentialList提供了 List 接口的骨干實現(xiàn)，從而最大限度地減少了實現(xiàn)受“連續(xù)訪問”數(shù)據(jù)存儲（如鏈接列表）支持的此接口所需的工作,從而以減少實現(xiàn)List接口的復雜度。Deque一個線性 collection，支持在兩端插入和移除元素，定義了雙端隊列的操作。
在LinkedList中提供了兩個基本屬性size、header。
?其中size表示的LinkedList的大小，header表示鏈表的表頭，Entry為節(jié)點對象。
private static class Entry<E> {E element; //元素節(jié)點Entry<E> next; //下一個元素Entry<E> previous; //上一個元素Entry(E element, Entry<E> next, Entry<E> previous) {this.element = element;this.next = next;this.previous = previous;}}?上面為Entry對象的源代碼，Entry為LinkedList的內(nèi)部類，它定義了存儲的元素。該元素的前一個元素、后一個元素，這是典型的雙向鏈表定義方式。
來看?LinkedList的構(gòu)造方法:：
public LinkedList() {header.next = header.previous = header; } public LinkedList(Collection<? extends E> c) {this();addAll(c); }LinkedList提供了兩個構(gòu)造方法。第一個構(gòu)造方法不接受參數(shù)，只是將header節(jié)點的前一節(jié)點和后一節(jié)點都設(shè)置為自身（注意，這個是一個雙向循環(huán)鏈表，如果不是循環(huán)鏈表，空鏈表的情況應(yīng)該是header節(jié)點的前一節(jié)點和后一節(jié)點均為null），這樣整個鏈表其實就只有header一個節(jié)點，用于表示一個空的鏈表。第二個構(gòu)造方法接收一個Collection參數(shù)c，調(diào)用第一個構(gòu)造方法構(gòu)造一個空的鏈表，之后通過addAll將c中的元素全部添加到鏈表中。來看addAll的內(nèi)容。
public boolean addAll(Collection<? extends E> c) {return addAll(size, c); } // index參數(shù)指定collection中插入的第一個元素的位置 public boolean addAll(int index, Collection<? extends E> c) {// 插入位置超過了鏈表的長度或小于0，報IndexOutOfBoundsException異常if (index < 0 || index > size)throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);Object[] a = c.toArray(); int numNew = a.length; // 若需要插入的節(jié)點個數(shù)為0則返回false，表示沒有插入元素if (numNew==0)return false;modCount++;// 保存index處的節(jié)點。插入位置如果是size，則在頭結(jié)點前面插入，否則獲取index處的節(jié)點 Entry<E> successor = (index==size ? header : entry(index)); // 獲取前一個節(jié)點，插入時需要修改這個節(jié)點的next引用 Entry<E> predecessor = successor.previous; // 按順序?qū)數(shù)組中的第一個元素插入到index處，將之后的元素插在這個元素后面for (int i=0; i<numNew; i++) { // 結(jié)合Entry的構(gòu)造方法，這條語句是插入操作，相當于C語言中鏈表中插入節(jié)點并修改指針Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);// 插入節(jié)點后將前一節(jié)點的next指向當前節(jié)點，相當于修改前一節(jié)點的next指針predecessor.next = e;// 相當于C語言中成功插入元素后將指針向后移動一個位置以實現(xiàn)循環(huán)的功能predecessor = e; } // 插入元素前index處的元素鏈接到插入的Collection的最后一個節(jié)點 successor.previous = predecessor; // 修改sizesize += numNew;return true; }構(gòu)造方法中的調(diào)用了addAll(Collection<? extends E> c)方法，而在addAll(Collection<? extends E> c)方法中僅僅是將size當做index參數(shù)調(diào)用了addAll(int index,Collection<? extends E> c)方法。
private Entry<E> entry(int index) {if (index < 0 || index >= size)throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);Entry<E> e = header;// 根據(jù)這個判斷決定從哪個方向遍歷這個鏈表if (index < (size >> 1)) {for (int i = 0; i <= index; i++)e = e.next;} else {// 可以通過header節(jié)點向前遍歷，說明這個一個循環(huán)雙向鏈表，header的previous指向鏈表的最后一個節(jié)點，這也驗證了構(gòu)造方法中對于header節(jié)點的前后節(jié)點均指向自己的解釋for (int i = size; i > index; i--)e = e.previous;}return e;}結(jié)合上面代碼中的注釋及雙向循環(huán)鏈表的知識，應(yīng)該很容易理解LinkedList構(gòu)造方法所涉及的內(nèi)容。下面開始分析LinkedList的其他方法。
add(E e)：
public boolean add(E e) {addBefore(e, header);return true;}從上面的代碼可以看出，add(E e)方法只是調(diào)用了addBefore(E e,Entry<E> entry)方法，并且返回true。
?addBefore(E e,Entry<E> entry)：
private Entry<E> addBefore(E e, Entry<E> entry) {Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);newEntry.previous.next = newEntry;newEntry.next.previous = newEntry;size++;modCount++;return newEntry; }addBefore(E e,Entry<E> entry)方法是個私有方法，所以無法在外部程序中調(diào)用（當然，這是一般情況，你可以通過反射上面的還是能調(diào)用到的）。
addBefore(E e,Entry<E> entry)先通過Entry的構(gòu)造方法創(chuàng)建e的節(jié)點newEntry（包含了將其下一個節(jié)點設(shè)置為entry，上一個節(jié)點設(shè)置為entry.previous的操作，相當于修改newEntry的“指針”），之后修改插入位置后newEntry的前一節(jié)點的next引用和后一節(jié)點的previous引用，使鏈表節(jié)點間的引用關(guān)系保持正確。之后修改和size大小和記錄modCount，然后返回新插入的節(jié)點。
總結(jié)，addBefore(E e,Entry<E> entry)實現(xiàn)在entry之前插入由e構(gòu)造的新節(jié)點。而add(E e)實現(xiàn)在header節(jié)點之前插入由e構(gòu)造的新節(jié)點。
add(int index,E e)：
public void add(int index, E element) {addBefore(element, (index==size ? header : entry(index)));}也是調(diào)用了addBefore(E e,Entry<E> entry)方法，只是entry節(jié)點由index的值決定。
構(gòu)造方法，addAll(Collection<? extends E> c)，add(E e)，addBefor(E e,Entry<E> entry)方法可以構(gòu)造鏈表并在指定位置插入節(jié)點，為了便于理解，下面給出插入節(jié)點的示意圖。
addFirst(E e)：
public void addFirst(E e) {addBefore(e, header.next);}addLast(E e)：
public void addLast(E e) {addBefore(e, header);}看上面的示意圖，結(jié)合addBefore(E e,Entry<E> entry)方法，很容易理解addFrist(E e)只需實現(xiàn)在header元素的下一個元素之前插入，即示意圖中的一號之前。addLast(E e)只需在實現(xiàn)在header節(jié)點前（因為是循環(huán)鏈表，所以header的前一個節(jié)點就是鏈表的最后一個節(jié)點）插入節(jié)點（插入后在2號節(jié)點之后）。
clear()：
public void clear() { Entry<E> e = header.next; // e可以理解為一個移動的“指針”，因為是循環(huán)鏈表，所以回到header的時候說明已經(jīng)沒有節(jié)點了 while (e != header) {// 保留e的下一個節(jié)點的引用Entry<E> next = e.next;// 接觸節(jié)點e對前后節(jié)點的引用e.next = e.previous = null;// 將節(jié)點e的內(nèi)容置空e.element = null;// 將e移動到下一個節(jié)點e = next; } // 將header構(gòu)造成一個循環(huán)鏈表，同構(gòu)造方法構(gòu)造一個空的LinkedList header.next = header.previous = header; // 修改sizesize = 0;modCount++; }上面代碼中的注釋已經(jīng)足以解釋這段代碼的邏輯，需要注意的是提到的“指針”僅僅是概念上的類比，Java并不存在“指針”的概念，而只有引用，為了便于理解所以部分說明使用了“指針”。
contains(Object o)：
public boolean contains(Object o) {return indexOf(o) != -1;}僅僅只是判斷o在鏈表中的索引。先看indexOf(Object o)方法。
public int indexOf(Object o) {int index = 0;if (o==null) {for (Entry e = header.next; e != header; e = e.next) {if (e.element==null)return index;index++;}} else {for (Entry e = header.next; e != header; e = e.next) {if (o.equals(e.element))return index;index++;}}return -1; }indexOf(Object o)判斷o鏈表中是否存在節(jié)點的element和o相等，若相等則返回該節(jié)點在鏈表中的索引位置，若不存在則放回-1。
contains(Object o)方法通過判斷indexOf(Object o)方法返回的值是否是-1來判斷鏈表中是否包含對象o。
?element()：
public E element() {return getFirst();}?getFirst()：
public E getFirst() {if (size==0)throw new NoSuchElementException();return header.next.element;}element()方法調(diào)用了getFirst()返回鏈表的第一個節(jié)點的元素。為什么要提供功能一樣的兩個方法，像是包裝了一下名字？其實這只是為了在不同的上下文“語境”中能通過更貼切的方法名調(diào)用罷了。
get(int index)：
public E get(int index) {return entry(index).element;}get(int index)方法用于獲得指定索引位置的節(jié)點的元素。它通過entry(int index)方法獲取節(jié)點。entry(int index)方法遍歷鏈表并獲取節(jié)點，在上面有說明過，不再陳述。
?set(int index,E element)：
public E set(int index, E element) {Entry<E> e = entry(index);E oldVal = e.element;e.element = element;return oldVal;}先獲取指定索引的節(jié)點，之后保留原來的元素，然后用element進行替換，之后返回原來的元素。
?getLast()：
public E getLast() {if (size==0)throw new NoSuchElementException();return header.previous.element;}getLast()方法和getFirst()方法類似，只是獲取的是header節(jié)點的前一個節(jié)點的元素。因為是循環(huán)鏈表，所以header節(jié)點的前一節(jié)點就是鏈表的最后一個節(jié)點。
lastIndexOf(Object o)：
public int lastIndexOf(Object o) {int index = size;if (o==null) {for (Entry e = header.previous; e != header; e = e.previous) {index--;if (e.element==null)return index;}} else {for (Entry e = header.previous; e != header; e = e.previous) {index--;if (o.equals(e.element))return index;}}return -1; }因為查找的是last index，即最后一次出現(xiàn)的位置，所以采用由后向前的遍歷方式。因為采用了有后向前的遍歷，所以index被賦值為size，并且循環(huán)體內(nèi)執(zhí)行時都進行減操作。分兩種情況判斷是否存在，分別是null和不為空。
?offer(E e)：
public boolean offer(E e) {return add(e);}在鏈表尾部插入元素。
offerFirst(E e)：
public boolean offerFirst(E e) {addFirst(e);return true;}在鏈表開頭插入元素。
offerLast(E e)：
public boolean offerLast(E e) {addLast(e);return true;}在鏈表末尾插入元素。
上面這三個方法都只是調(diào)用了相應(yīng)的add方法，同樣只是提供了不同的方法名在不同的語境下使用。
?peek()：
public E peek() {if (size==0)return null;return getFirst();}peekFirst()：
public E peekFirst() {if (size==0)return null;return getFirst();}?peekLast()：
public E peekLast() {if (size==0)return null;return getLast();}上面的三個方法也很簡單，只是調(diào)用了對應(yīng)的get方法。
poll()：
public E poll() {if (size==0)return null;return removeFirst();}?pollFirst()：
public E pollFirst() {if (size==0)return null;return removeFirst();}pollLast()：
public E pollLast() {if (size==0)return null;return removeLast();}poll相關(guān)的方法都是獲取并移除某個元素。都是和remove操作相關(guān)。
pop()：
public E pop() {return removeFirst();}push(E e)：
public void push(E e) {addFirst(e);}這兩個方法對應(yīng)棧的操作，即彈出一個元素和壓入一個元素，僅僅是調(diào)用了removeFirst()和addFirst()方法。
下面集中看remove相關(guān)操作的方法。
remove()：
public E remove() {return removeFirst();}remove(int index)：
public E remove(int index) {return remove(entry(index));}remove(Object o)：
public boolean remove(Object o) {if (o==null) {for (Entry<E> e = header.next; e != header; e = e.next) {if (e.element==null) {remove(e);return true;}}} else {for (Entry<E> e = header.next; e != header; e = e.next) {if (o.equals(e.element)) {remove(e);return true;}}}return false; }removeFirst()：
public E removeFirst() {return remove(header.next);}removeLast()：
public E removeLast() {return remove(header.previous);}?removeFirstOccurrence()：
public boolean removeFirstOccurrence(Object o) {return remove(o);}removeLastOccurence()：
public boolean removeLastOccurrence(Object o) {if (o==null) {for (Entry<E> e = header.previous; e != header; e = e.previous) {if (e.element==null) {remove(e);return true;}}} else {for (Entry<E> e = header.previous; e != header; e = e.previous) {if (o.equals(e.element)) {remove(e);return true;}}}return false; }幾個remove方法最終都是調(diào)用了一個私有方法：remove(Entry<E> e)，只是其他簡單邏輯上的區(qū)別。下面分析remove(Entry<E> e)方法。
private E remove(Entry<E> e) {if (e == header)throw new NoSuchElementException();// 保留將被移除的節(jié)點e的內(nèi)容 E result = e.element; // 將前一節(jié)點的next引用賦值為e的下一節(jié)點e.previous.next = e.next;// 將e的下一節(jié)點的previous賦值為e的上一節(jié)點e.next.previous = e.previous;// 上面兩條語句的執(zhí)行已經(jīng)導致了無法在鏈表中訪問到e節(jié)點，而下面解除了e節(jié)點對前后節(jié)點的引用 e.next = e.previous = null; // 將被移除的節(jié)點的內(nèi)容設(shè)為null e.element = null; // 修改size大小size--;modCount++;// 返回移除節(jié)點e的內(nèi)容return result; }clone()：
public Object clone() {LinkedList<E> clone = null;try {clone = (LinkedList<E>) super.clone();} catch (CloneNotSupportedException e) {throw new InternalError();}clone.header = new Entry<E>(null, null, null);clone.header.next = clone.header.previous = clone.header;clone.size = 0;clone.modCount = 0;for (Entry<E> e = header.next; e != header; e = e.next)clone.add(e.element);return clone; }調(diào)用父類的clone()方法初始化對象鏈表clone，將clone構(gòu)造成一個空的雙向循環(huán)鏈表，之后將header的下一個節(jié)點開始將逐個節(jié)點添加到clone中。最后返回克隆的clone對象。
toArray()：
public Object[] toArray() {Object[] result = new Object[size];int i = 0;for (Entry<E> e = header.next; e != header; e = e.next)result[i++] = e.element;return result; }創(chuàng)建大小和LinkedList相等的數(shù)組result，遍歷鏈表，將每個節(jié)點的元素element復制到數(shù)組中，返回數(shù)組。
?toArray(T[] a)：
public <T> T[] toArray(T[] a) {if (a.length < size)a = (T[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);int i = 0;Object[] result = a;for (Entry<E> e = header.next; e != header; e = e.next)result[i++] = e.element;if (a.length > size)a[size] = null;return a; }先判斷出入的數(shù)組a的大小是否足夠，若大小不夠則拓展。這里用到了發(fā)射的方法，重新實例化了一個大小為size的數(shù)組。之后將數(shù)組a賦值給數(shù)組result，遍歷鏈表向result中添加的元素。最后判斷數(shù)組a的長度是否大于size，若大于則將size位置的內(nèi)容設(shè)置為null。返回a。
從代碼中可以看出，數(shù)組a的length小于等于size時，a中所有元素被覆蓋，被拓展來的空間存儲的內(nèi)容都是null；若數(shù)組a的length的length大于size，則0至size-1位置的內(nèi)容被覆蓋，size位置的元素被設(shè)置為null，size之后的元素不變。
?
LinkedList的Iterator：
除了Entry，LinkedList還有一個內(nèi)部類：ListItr。ListItr實現(xiàn)了ListIterator接口，可知它是一個迭代器，通過它可以遍歷修改LinkedList。在LinkedList中提供了獲取ListItr對象的方法：listIterator(int index)。
public ListIterator<E> listIterator(int index) {return new ListItr(index);}該方法只是簡單的返回了一個ListItr對象。
LinkedList中還有通過集成獲得的listIterator()方法，該方法只是調(diào)用了listIterator(int index)并且傳入0。
下面詳細分析ListItr。
private class ListItr implements ListIterator<E> { // 最近一次返回的節(jié)點，也是當前持有的節(jié)點private Entry<E> lastReturned = header;// 對下一個元素的引用private Entry<E> next;// 下一個節(jié)點的indexprivate int nextIndex;private int expectedModCount = modCount;// 構(gòu)造方法，接收一個index參數(shù)，返回一個ListItr對象ListItr(int index) {// 如果index小于0或大于size，拋出IndexOutOfBoundsException異常if (index < 0 || index > size)throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);// 判斷遍歷方向if (index < (size >> 1)) {// next賦值為第一個節(jié)點next = header.next;// 獲取指定位置的節(jié)點for (nextIndex=0; nextIndex<index; nextIndex++)next = next.next;} else { // else中的處理和if塊中的處理一致，只是遍歷方向不同next = header;for (nextIndex=size; nextIndex>index; nextIndex--)next = next.previous;}}// 根據(jù)nextIndex是否等于size判斷時候還有下一個節(jié)點（也可以理解為是否遍歷完了LinkedList）public boolean hasNext() {return nextIndex != size;}// 獲取下一個元素public E next() {checkForComodification();// 如果nextIndex==size,則已經(jīng)遍歷完鏈表，即沒有下一個節(jié)點了（實際上是有的，因為是循環(huán)鏈表，任何一個節(jié)點都會有上一個和下一個節(jié)點，這里的沒有下一個節(jié)點只是說所有節(jié)點都已經(jīng)遍歷完了）if (nextIndex == size)throw new NoSuchElementException();// 設(shè)置最近一次返回的節(jié)點為next節(jié)點lastReturned = next;// 將next“向后移動一位”next = next.next;// index計數(shù)加1nextIndex++;// 返回lastReturned的元素return lastReturned.element;}public boolean hasPrevious() {return nextIndex != 0;}// 返回上一個節(jié)點，和next()方法相似public E previous() {if (nextIndex == 0)throw new NoSuchElementException();lastReturned = next = next.previous;nextIndex--;checkForComodification();return lastReturned.element;}public int nextIndex() {return nextIndex;}public int previousIndex() {return nextIndex-1;}// 移除當前Iterator持有的節(jié)點public void remove() {checkForComodification();Entry<E> lastNext = lastReturned.next;try {LinkedList.this.remove(lastReturned);} catch (NoSuchElementException e) {throw new IllegalStateException();}if (next==lastReturned)next = lastNext;elsenextIndex--;lastReturned = header;expectedModCount++;}// 修改當前節(jié)點的內(nèi)容public void set(E e) {if (lastReturned == header)throw new IllegalStateException();checkForComodification();lastReturned.element = e;}// 在當前持有節(jié)點后面插入新節(jié)點public void add(E e) {checkForComodification();// 將最近一次返回節(jié)點修改為headerlastReturned = header;addBefore(e, next);nextIndex++;expectedModCount++;}// 判斷expectedModCount和modCount是否一致，以確保通過ListItr的修改操作正確的反映在LinkedList中final void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();} }下面是一個ListItr的使用實例。
LinkedList<String> list = new LinkedList<String>();list.add("First");list.add("Second");list.add("Thrid");System.out.println(list);ListIterator<String> itr = list.listIterator();while (itr.hasNext()) {System.out.println(itr.next());}try {System.out.println(itr.next());// throw Exception} catch (Exception e) {// TODO: handle exception}itr = list.listIterator();System.out.println(list);System.out.println(itr.next());itr.add("new node1");System.out.println(list);itr.add("new node2");System.out.println(list);System.out.println(itr.next());itr.set("modify node");System.out.println(list);itr.remove();System.out.println(list); 運行結(jié)果： [First, Second, Thrid] First Second Thrid [First, Second, Thrid] First [First, new node1, Second, Thrid] [First, new node1, new node2, Second, Thrid] Second [First, new node1, new node2, modify node, Thrid] [First, new node1, new node2, Thrid]LinkedList還有一個提供Iterator的方法：descendingIterator()。該方法返回一個DescendingIterator對象。DescendingIterator是LinkedList的一個內(nèi)部類。
public Iterator<E> descendingIterator() {return new DescendingIterator();}下面分析詳細分析DescendingIterator類。
private class DescendingIterator implements Iterator {// 獲取ListItr對象 final ListItr itr = new ListItr(size()); // hasNext其實是調(diào)用了itr的hasPrevious方法public boolean hasNext() {return itr.hasPrevious();} // next()其實是調(diào)用了itr的previous方法public E next() {return itr.previous();}public void remove() {itr.remove();} }從類名和上面的代碼可以看出這是一個反向的Iterator，代碼很簡單，都是調(diào)用的ListItr類中的方法。
?
?
原文轉(zhuǎn)自：http://www.cnblogs.com/hzmark/archive/2012/12/25/LinkedList.html
其他比較好的博客：
https://blog.csdn.net/chenssy/article/details/18099417
https://blog.csdn.net/sinat_36246371/article/details/53709625
https://blog.csdn.net/i_lovefish/article/details/8042883
總結(jié)
以上是生活随笔為你收集整理的Java集合篇：LinkedList源码分析的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Java集合篇：集合类介绍
- 下一篇： Java集合篇：HashMap原理详解（