摘要：在閱讀源碼之前，我們先對的整體實現進行大致說明實際上是通過雙向鏈表去實現的。獲取的最后一個元素由于是雙向鏈表而表頭不包含數據。實際上是判斷雙向鏈表的當前節點是否達到開頭反向迭代器獲取下一個元素。

LinkedList 是一個繼承于AbstractSequentialList的雙向鏈表。它也可以被當作堆棧、隊列或雙端隊列進行操作。
LinkedList 實現 List 接口，能對它進行隊列操作。
LinkedList 實現 Deque 接口，即能將LinkedList當作雙端隊列使用。
LinkedList 實現了Cloneable接口，即覆蓋了函數clone()，能克隆。
LinkedList 實現java.io.Serializable接口，這意味著LinkedList支持序列化，能通過序列化去傳輸。
LinkedList 是非同步的。

// 默認構造函數
LinkedList()

// 創建一個LinkedList，保護Collection中的全部元素。
LinkedList(Collection collection)

LinkedList的API
boolean       add(E object)
void          add(int location, E object)
boolean       addAll(Collection collection)
boolean       addAll(int location, Collection collection)
void          addFirst(E object)
void          addLast(E object)
void          clear()
Object        clone()
boolean       contains(Object object)
Iterator   descendingIterator()
E             element()
E             get(int location)
E             getFirst()
E             getLast()
int           indexOf(Object object)
int           lastIndexOf(Object object)
ListIterator     listIterator(int location)
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()
 T[]       toArray(T[] contents)
Object[]     toArray()

在介紹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 方法即可。
inkedList實際上是通過雙向鏈表去實現的。既然是雙向鏈表，那么它的順序訪問會非常高效，而隨機訪問效率比較低。

    java.lang.Object
       ?     java.util.AbstractCollection
             ?     java.util.AbstractList
                   ?     java.util.AbstractSequentialList
                         ?     java.util.LinkedList
    
    public class LinkedList
        extends AbstractSequentialList
        implements List, Deque, Cloneable, java.io.Serializable {}
        

LinkedList與Collection關系如下圖：
---------------------------
![272345393446232.jpg][1]


LinkedList的本質是雙向鏈表。
(01) LinkedList繼承于AbstractSequentialList，并且實現了Dequeue接口。 
(02) LinkedList包含兩個重要的成員：header 和 size。
　　header是雙向鏈表的表頭，它是雙向鏈表節點所對應的類Entry的實例。Entry中包含成員變量： previous, next, element。其中，previous是該節點的上一個節點，next是該節點的下一個節點，element是該節點所包含的值。 
　　size是雙向鏈表中節點的個數。
(03)LinkedList數據結構；
![616953-20160322214504120-1558870057.png][2]


  [1]: /img/bVbbtxf
  [2]: /img/bVbbtxw
說明：如上圖所示，LinkedList底層使用的雙向鏈表結構，有一個頭結點和一個尾結點，雙向鏈表意味著我們可以從頭開始正向遍歷，或者是從尾開始逆向遍歷，并且可以針對頭部和尾部進行相應的操作。

為了更了解LinkedList的原理，下面對LinkedList源碼代碼作出分析。

在閱讀源碼之前，我們先對LinkedList的整體實現進行大致說明：

LinkedList實際上是通過雙向鏈表去實現的。既然是雙向鏈表，那么它的順序訪問會非常高效，而隨機訪問效率比較低。
既然LinkedList是通過雙向鏈表的，但是它也實現了List接口{也就是說，它實現了get(int location)、remove(int location)等“根據索引值來獲取、刪除節點的函數”}。LinkedList是如何實現List的這些接口的，如何將“雙向鏈表和索引值聯系起來的”？
實際原理非常簡單，它就是通過一個計數索引值來實現的。例如，當我們調用get(int location)時，首先會比較“location”和“雙向鏈表長度的1/2”；若前者大，則從鏈表頭開始往后查找，直到location位置；否則，從鏈表末尾開始先前查找，直到location位置。

這就是“雙線鏈表和索引值聯系起來”的方法。

好了，接下來開始閱讀源碼(只要理解雙向鏈表，那么LinkedList的源碼很容易理解的)

package java.util;
    
    public class LinkedList
        extends AbstractSequentialList
        implements List, Deque, Cloneable, java.io.Serializable
    {
        // 鏈表的表頭，表頭不包含任何數據。Entry是個鏈表類數據結構。
        private transient Entry header = new Entry(null, null, null);
    
        // LinkedList中元素個數
        private transient int size = 0;
    
        // 默認構造函數：創建一個空的鏈表
        public LinkedList() {
            header.next = header.previous = header;
        }
    
        // 包含“集合”的構造函數:創建一個包含“集合”的LinkedList
        public LinkedList(Collection c) {
            this();
            addAll(c);
        }
    
        // 獲取LinkedList的第一個元素
        public E getFirst() {
            if (size==0)
                throw new NoSuchElementException();
    
            // 鏈表的表頭header中不包含數據。
            // 這里返回header所指下一個節點所包含的數據。
            return header.next.element;
        }
    
        // 獲取LinkedList的最后一個元素
        public E getLast()  {
            if (size==0)
                throw new NoSuchElementException();
    
            // 由于LinkedList是雙向鏈表；而表頭header不包含數據。
            // 因而，這里返回表頭header的前一個節點所包含的數據。
            return header.previous.element;
        }
    
        // 刪除LinkedList的第一個元素
        public E removeFirst() {
            return remove(header.next);
        }
    
        // 刪除LinkedList的最后一個元素
        public E removeLast() {
            return remove(header.previous);
        }
    
        // 將元素添加到LinkedList的起始位置
        public void addFirst(E e) {
            addBefore(e, header.next);
        }
    
        // 將元素添加到LinkedList的結束位置
        public void addLast(E e) {
            addBefore(e, header);
        }
    
        // 判斷LinkedList是否包含元素(o)
        public boolean contains(Object o) {
            return indexOf(o) != -1;
        }
    
        // 返回LinkedList的大小
        public int size() {
            return size;
        }
    
        // 將元素(E)添加到LinkedList中
        public boolean add(E e) {
            // 將節點(節點數據是e)添加到表頭(header)之前。
            // 即，將節點添加到雙向鏈表的末端。
            addBefore(e, header);
            return true;
        }
    
        // 從LinkedList中刪除元素(o)
        // 從鏈表開始查找，如存在元素(o)則刪除該元素并返回true；
        // 否則，返回false。
        public boolean remove(Object o) {
            if (o==null) {
                // 若o為null的刪除情況
                for (Entry e = header.next; e != header; e = e.next) {
                    if (e.element==null) {
                        remove(e);
                        return true;
                    }
                }
            } else {
                // 若o不為null的刪除情況
                for (Entry e = header.next; e != header; e = e.next) {
                    if (o.equals(e.element)) {
                        remove(e);
                        return true;
                    }
                }
            }
            return false;
        }
    
        // 將“集合(c)”添加到LinkedList中。
        // 實際上，是從雙向鏈表的末尾開始，將“集合(c)”添加到雙向鏈表中。
        public boolean addAll(Collection c) {
            return addAll(size, c);
        }
    
        // 從雙向鏈表的index開始，將“集合(c)”添加到雙向鏈表中。
        public boolean addAll(int index, Collection c) {
            if (index < 0 || index > size)
                throw new IndexOutOfBoundsException("Index: "+index+
                                                    ", Size: "+size);
            Object[] a = c.toArray();
            // 獲取集合的長度
            int numNew = a.length;
            if (numNew==0)
                return false;
            modCount++;
    
            // 設置“當前要插入節點的后一個節點”
            Entry successor = (index==size ? header : entry(index));
            // 設置“當前要插入節點的前一個節點”
            Entry predecessor = successor.previous;
            // 將集合(c)全部插入雙向鏈表中
            for (int i=0; i e = new Entry((E)a[i], successor, predecessor);
                predecessor.next = e;
                predecessor = e;
            }
            successor.previous = predecessor;
    
            // 調整LinkedList的實際大小
            size += numNew;
            return true;
        }
    
        // 清空雙向鏈表
        public void clear() {
            Entry e = header.next;
            // 從表頭開始，逐個向后遍歷；對遍歷到的節點執行一下操作：
            // (01) 設置前一個節點為null 
            // (02) 設置當前節點的內容為null 
            // (03) 設置后一個節點為“新的當前節點”
            while (e != header) {
                Entry next = e.next;
                e.next = e.previous = null;
                e.element = null;
                e = next;
            }
            header.next = header.previous = header;
            // 設置大小為0
            size = 0;
            modCount++;
        }
    
        // 返回LinkedList指定位置的元素
        public E get(int index) {
            return entry(index).element;
        }
    
        // 設置index位置對應的節點的值為element
        public E set(int index, E element) {
            Entry e = entry(index);
            E oldVal = e.element;
            e.element = element;
            return oldVal;
        }
     
        // 在index前添加節點，且節點的值為element
        public void add(int index, E element) {
            addBefore(element, (index==size ? header : entry(index)));
        }
    
        // 刪除index位置的節點
        public E remove(int index) {
            return remove(entry(index));
        }
    
        // 獲取雙向鏈表中指定位置的節點
        private Entry entry(int index) {
            if (index < 0 || index >= size)
                throw new IndexOutOfBoundsException("Index: "+index+
                                                    ", Size: "+size);
            Entry e = header;
            // 獲取index處的節點。
            // 若index < 雙向鏈表長度的1/2,則從前先后查找;
            // 否則，從后向前查找。
            if (index < (size >> 1)) {
                for (int i = 0; i <= index; i++)
                    e = e.next;
            } else {
                for (int i = size; i > index; i--)
                    e = e.previous;
            }
            return e;
        }
    
        // 從前向后查找，返回“值為對象(o)的節點對應的索引”
        // 不存在就返回-1
        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;
        }
    
        // 從后向前查找，返回“值為對象(o)的節點對應的索引”
        // 不存在就返回-1
        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;
        }
    
        // 返回第一個節點
        // 若LinkedList的大小為0,則返回null
        public E peek() {
            if (size==0)
                return null;
            return getFirst();
        }
    
        // 返回第一個節點
        // 若LinkedList的大小為0,則拋出異常
        public E element() {
            return getFirst();
        }
    
        // 刪除并返回第一個節點
        // 若LinkedList的大小為0,則返回null
        public E poll() {
            if (size==0)
                return null;
            return removeFirst();
        }
    
        // 將e添加雙向鏈表末尾
        public boolean offer(E e) {
            return add(e);
        }
    
        // 將e添加雙向鏈表開頭
        public boolean offerFirst(E e) {
            addFirst(e);
            return true;
        }
    
        // 將e添加雙向鏈表末尾
        public boolean offerLast(E e) {
            addLast(e);
            return true;
        }
    
        // 返回第一個節點
        // 若LinkedList的大小為0,則返回null
        public E peekFirst() {
            if (size==0)
                return null;
            return getFirst();
        }
    
        // 返回最后一個節點
        // 若LinkedList的大小為0,則返回null
        public E peekLast() {
            if (size==0)
                return null;
            return getLast();
        }
    
        // 刪除并返回第一個節點
        // 若LinkedList的大小為0,則返回null
        public E pollFirst() {
            if (size==0)
                return null;
            return removeFirst();
        }
    
        // 刪除并返回最后一個節點
        // 若LinkedList的大小為0,則返回null
        public E pollLast() {
            if (size==0)
                return null;
            return removeLast();
        }
    
        // 將e插入到雙向鏈表開頭
        public void push(E e) {
            addFirst(e);
        }
    
        // 刪除并返回第一個節點
        public E pop() {
            return removeFirst();
        }
    
        // 從LinkedList開始向后查找，刪除第一個值為元素(o)的節點
        // 從鏈表開始查找，如存在節點的值為元素(o)的節點，則刪除該節點
        public boolean removeFirstOccurrence(Object o) {
            return remove(o);
        }
    
        // 從LinkedList末尾向前查找，刪除第一個值為元素(o)的節點
        // 從鏈表開始查找，如存在節點的值為元素(o)的節點，則刪除該節點
        public boolean removeLastOccurrence(Object o) {
            if (o==null) {
                for (Entry e = header.previous; e != header; e = e.previous) {
                    if (e.element==null) {
                        remove(e);
                        return true;
                    }
                }
            } else {
                for (Entry e = header.previous; e != header; e = e.previous) {
                    if (o.equals(e.element)) {
                        remove(e);
                        return true;
                    }
                }
            }
            return false;
        }
    
        // 返回“index到末尾的全部節點”對應的ListIterator對象(List迭代器)
        public ListIterator listIterator(int index) {
            return new ListItr(index);
        }
    
        // List迭代器
        private class ListItr implements ListIterator {
            // 上一次返回的節點
            private Entry lastReturned = header;
            // 下一個節點
            private Entry next;
            // 下一個節點對應的索引值
            private int nextIndex;
            // 期望的改變計數。用來實現fail-fast機制。
            private int expectedModCount = modCount;
    
            // 構造函數。
            // 從index位置開始進行迭代
            ListItr(int index) {
                // index的有效性處理
                if (index < 0 || index > size)
                    throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size);
                // 若 “index 小于 ‘雙向鏈表長度的一半’”，則從第一個元素開始往后查找；
                // 否則，從最后一個元素往前查找。
                if (index < (size >> 1)) {
                    next = header.next;
                    for (nextIndex=0; nextIndexindex; nextIndex--)
                        next = next.previous;
                }
            }
    
            // 是否存在下一個元素
            public boolean hasNext() {
                // 通過元素索引是否等于“雙向鏈表大小”來判斷是否達到最后。
                return nextIndex != size;
            }
    
            // 獲取下一個元素
            public E next() {
                checkForComodification();
                if (nextIndex == size)
                    throw new NoSuchElementException();
    
                lastReturned = next;
                // next指向鏈表的下一個元素
                next = next.next;
                nextIndex++;
                return lastReturned.element;
            }
    
            // 是否存在上一個元素
            public boolean hasPrevious() {
                // 通過元素索引是否等于0，來判斷是否達到開頭。
                return nextIndex != 0;
            }
    
            // 獲取上一個元素
            public E previous() {
                if (nextIndex == 0)
                throw new NoSuchElementException();
    
                // next指向鏈表的上一個元素
                lastReturned = next = next.previous;
                nextIndex--;
                checkForComodification();
                return lastReturned.element;
            }
    
            // 獲取下一個元素的索引
            public int nextIndex() {
                return nextIndex;
            }
    
            // 獲取上一個元素的索引
            public int previousIndex() {
                return nextIndex-1;
            }
    
            // 刪除當前元素。
            // 刪除雙向鏈表中的當前節點
            public void remove() {
                checkForComodification();
                Entry lastNext = lastReturned.next;
                try {
                    LinkedList.this.remove(lastReturned);
                } catch (NoSuchElementException e) {
                    throw new IllegalStateException();
                }
                if (next==lastReturned)
                    next = lastNext;
                else
                    nextIndex--;
                lastReturned = header;
                expectedModCount++;
            }
    
            // 設置當前節點為e
            public void set(E e) {
                if (lastReturned == header)
                    throw new IllegalStateException();
                checkForComodification();
                lastReturned.element = e;
            }
    
            // 將e添加到當前節點的前面
            public void add(E e) {
                checkForComodification();
                lastReturned = header;
                addBefore(e, next);
                nextIndex++;
                expectedModCount++;
            }
    
            // 判斷 “modCount和expectedModCount是否相等”，依次來實現fail-fast機制。
            final void checkForComodification() {
                if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            }
        }
    
        // 雙向鏈表的節點所對應的數據結構。
        // 包含3部分：上一節點，下一節點，當前節點值。
        private static class Entry {
            // 當前節點所包含的值
            E element;
            // 下一個節點
            Entry next;
            // 上一個節點
            Entry previous;
    
            /**
             * 鏈表節點的構造函數。
             * 參數說明：
             *   element  —— 節點所包含的數據
             *   next      —— 下一個節點
             *   previous —— 上一個節點
             */
            Entry(E element, Entry next, Entry previous) {
                this.element = element;
                this.next = next;
                this.previous = previous;
            }
        }
    
        // 將節點(節點數據是e)添加到entry節點之前。
        private Entry addBefore(E e, Entry entry) {
            // 新建節點newEntry，將newEntry插入到節點e之前；并且設置newEntry的數據是e
            Entry newEntry = new Entry(e, entry, entry.previous);
            newEntry.previous.next = newEntry;
            newEntry.next.previous = newEntry;
            // 修改LinkedList大小
            size++;
            // 修改LinkedList的修改統計數：用來實現fail-fast機制。
            modCount++;
            return newEntry;
        }
    
        // 將節點從鏈表中刪除
        private E remove(Entry e) {
            if (e == header)
                throw new NoSuchElementException();
    
            E result = e.element;
            e.previous.next = e.next;
            e.next.previous = e.previous;
            e.next = e.previous = null;
            e.element = null;
            size--;
            modCount++;
            return result;
        }
    
        // 反向迭代器
        public Iterator descendingIterator() {
            return new DescendingIterator();
        }
    
        // 反向迭代器實現類。
        private class DescendingIterator implements Iterator {
            final ListItr itr = new ListItr(size());
            // 反向迭代器是否下一個元素。
            // 實際上是判斷雙向鏈表的當前節點是否達到開頭
            public boolean hasNext() {
                return itr.hasPrevious();
            }
            // 反向迭代器獲取下一個元素。
            // 實際上是獲取雙向鏈表的前一個節點
            public E next() {
                return itr.previous();
            }
            // 刪除當前節點
            public void remove() {
                itr.remove();
            }
        }
    
    
        // 返回LinkedList的Object[]數組
        public Object[] toArray() {
        // 新建Object[]數組
        Object[] result = new Object[size];
            int i = 0;
            // 將鏈表中所有節點的數據都添加到Object[]數組中
            for (Entry e = header.next; e != header; e = e.next)
                result[i++] = e.element;
        return result;
        }
    
        // 返回LinkedList的模板數組。所謂模板數組，即可以將T設為任意的數據類型
        public  T[] toArray(T[] a) {
            // 若數組a的大小 < LinkedList的元素個數(意味著數組a不能容納LinkedList中全部元素)
            // 則新建一個T[]數組，T[]的大小為LinkedList大小，并將該T[]賦值給a。
            if (a.length < size)
                a = (T[])java.lang.reflect.Array.newInstance(
                                    a.getClass().getComponentType(), size);
            // 將鏈表中所有節點的數據都添加到數組a中
            int i = 0;
            Object[] result = a;
            for (Entry e = header.next; e != header; e = e.next)
                result[i++] = e.element;
    
            if (a.length > size)
                a[size] = null;
    
            return a;
        }
    
    
        // 克隆函數。返回LinkedList的克隆對象。
        public Object clone() {
            LinkedList clone = null;
            // 克隆一個LinkedList克隆對象
            try {
                clone = (LinkedList) super.clone();
            } catch (CloneNotSupportedException e) {
                throw new InternalError();
            }
    
            // 新建LinkedList表頭節點
            clone.header = new Entry(null, null, null);
            clone.header.next = clone.header.previous = clone.header;
            clone.size = 0;
            clone.modCount = 0;
    
            // 將鏈表中所有節點的數據都添加到克隆對象中
            for (Entry e = header.next; e != header; e = e.next)
                clone.add(e.element);
    
            return clone;
        }
    
        // java.io.Serializable的寫入函數
        // 將LinkedList的“容量，所有的元素值”都寫入到輸出流中
        private void writeObject(java.io.ObjectOutputStream s)
            throws java.io.IOException {
            // Write out any hidden serialization magic
            s.defaultWriteObject();
    
            // 寫入“容量”
            s.writeInt(size);
    
            // 將鏈表中所有節點的數據都寫入到輸出流中
            for (Entry e = header.next; e != header; e = e.next)
                s.writeObject(e.element);
        }
    
        // java.io.Serializable的讀取函數：根據寫入方式反向讀出
        // 先將LinkedList的“容量”讀出，然后將“所有的元素值”讀出
        private void readObject(java.io.ObjectInputStream s)
            throws java.io.IOException, ClassNotFoundException {
            // Read in any hidden serialization magic
            s.defaultReadObject();
    
            // 從輸入流中讀取“容量”
            int size = s.readInt();
    
            // 新建鏈表表頭節點
            header = new Entry(null, null, null);
            header.next = header.previous = header;
    
            // 從輸入流中將“所有的元素值”并逐個添加到鏈表中
            for (int i=0; i
總結：
(01) LinkedList 實際上是通過雙向鏈表去實現的。它包含一個非常重要的內部類：Entry。Entry是雙向鏈表節點所對應的數據結構，它包括的屬性有：當前節點所包含的值，上一個節點，下一個節點。
(02) 從LinkedList的實現方式中可以發現，它不存在LinkedList容量不足的問題。
(03) LinkedList的克隆函數，即是將全部元素克隆到一個新的LinkedList對象中。
(04) LinkedList實現java.io.Serializable。當寫入到輸出流時，先寫入“容量”，再依次寫入“每一個節點保護的值”；當讀出輸入流時，先讀取“容量”，再依次讀取“每一個元素”。
(05) 由于LinkedList實現了Deque，而Deque接口定義了在雙端隊列兩端訪問元素的方法。提供插入、移除和檢查元素的方法。每種方法都存在兩種形式：一種形式在操作失敗時拋出異常，另一種形式返回一個特殊值（null 或 false，具體取決于操作）。