LinkedList與ArrayList正好相對，同樣是List的實現類，都有增刪改查等方法，但是實現方法跟后者有很大的區別。

先歸納一下LinkedList包含的API

1、構造函數：

①LinkedList()　　起始沒有元素

②LinkedList(Collection<? extends E> collection)　　用另一個集合構造LinkedList

2、增加元素：

①void add(int location, E object)　　在指定索引處新增元素

②boolean add(E object)　　在鏈表末尾添加元素，總是返回true

③boolean addAll(int location, Collection<? extends E> collection)　　在指定索引處添加一個集合的所有元素，添加成功返回true，否則返回false

④boolean addAll(Collection<? extends E> collection)　　在鏈表末尾添加集合的所有元素，添加成功返回true

⑤void addFirst(E object)　　在鏈表首部添加一個元素

⑥void addLast(E object)　　在鏈表末尾添加一個元素

3、刪除元素：

①E remove(int location)　　刪除指定索引處的元素

②boolean remove(Object object)　　刪除參數指定的元素，只刪除第一次出現的那個

③E removeFirst()　　刪除頭部元素

④E removeLast()　　刪除尾部元素

⑤boolean removeFirstOccurrence(Object o)　　同②，刪除第一次出現的元素

⑥boolean removeLastOccurrence(Object o)　　刪除最后一次出現的指定元素

⑦E remove()　　　　同③，刪除頭部元素

⑧void clear()　　　　清空所有元素

4、修改元素：

　E set(int location, E object)　　修改指定位置的元素值嗎，返回修改處舊的元素值

5、查找元素：

①boolean contains(Object object)　　確定是否包含指定的元素

②E get(int location)　　　　獲取指定索引處的元素

③E getFirst()　　　　獲取頭部結點的元素值

④E getLast()　　　　獲取尾部結點的元素值

⑤int indexOf(Object object)　　獲取指定元素第一次出現時的索引，找不到返回-1

⑥int lastIndexOf(Object object)　獲取指定元素最后一次出現時的索引，找不到返回-1

6、隊列相關操作：

(1)boolean offerFirst(E e)　　在隊首添加元素

(2)boolean offerLast(E e)　　在隊尾添加元素

(3)E peekFirst()　　　　獲取隊首元素，沒有元素返回null

(4)EpeekLast()　　　　獲取隊尾元素

(5)E pollFirst()　　　　 刪除隊首元素，并返回被刪元素，沒有元素可刪返回null

(6)E pollLast()　　　　刪除隊尾元素，并返回被刪元素，沒有元素可刪返回null

(7)E pop()　　　　　　 作為棧操作，彈出棧頂元素，即返回并刪除隊首元素

(8)void push(E e)　　　作為棧操作，壓入新元素，即在隊首加入元素

(9)boolean offer(E o)　　將指定元素入隊，即在隊尾加入該元素

(10)E poll()　　　　　　同pollFirst，刪除隊首元素，并返回該元素

(11)E remove()　　　　同pollFirst，刪除隊首元素，并返回該元素

(12)E element()　　　 返回隊首元素，但并不刪除

下面進行API源碼分析

public class LinkedList<E> extends AbstractSequentialList<E> implements        List<E>, Deque<E>, Queue<E>, Cloneable, Serializable

因為LinkedList除了實現List接口，還實現了單、雙向隊列的接口，所以相比ArrayList，還額外包含了大量的隊列操作，雖然這些隊列操作都可以用對應的List操作替換。

LinkedList內部是用雙向鏈表實現的，而且這個鏈表還跟普通的鏈表不太一樣，兩端的兩個null結點被同一個void結點替換掉了，這樣就完全可以用這一個結點代表整個列表，從它出發可以實現所有的操作了。

這我認為是設計得最巧妙的一點。

下面來看鏈表中的結點類定義：

    PRivate static final class Link<ET> {        ET data;          //實際的元素值，也就是我們的結點核心部分        Link<ET> previous, next;    //同時定義了前向指針和后向指針，分別指向前一個結點和后一個結點，這樣正向遍歷和反向遍歷都能簡單地實現了        Link(ET o, Link<ET> p, Link<ET> n) {    //構造函數，傳入元素值、前向結點、后向結點            data = o;            previous = p;            next = n;        }    }

LinkedList的結點可以包含很多個，但是其中有一個特殊的結點是必不可少的，它就是void結點

transient Link<E> voidLink;

因為所有操作都是從voidLink這個結點出發的，所以構造函數的工作就只要構造void結點就可以了

    //void結點結構跟其他結點的唯一區別就是data數值部分為空，不包含任何值，只有前后向指針    //初始化的時候把所有指針指向自己，后續有結點添加進來再指向其他結點    public LinkedList() {        voidLink = new Link<E>(null, null, null);        voidLink.previous = voidLink;        voidLink.next = voidLink;    }    public LinkedList(Collection<? extends E> collection) {        this();        addAll(collection);    }

下面來看添加元素部分，這應該是LinkedList相對于ArrayList最大的優勢了，因為鏈表長度可以無限延長，不像數組存在空間不夠，需重新開辟內存空間的問題，更關鍵的是，省去了擴展空間后大批量元素復制的冗余操作，可以說性能已經大大提升了。同時，鏈表找到添加位置后，不存在之后的元素全部后移的問題。當然，因為用鏈表添加元素需要先找到添加位置，尋找添加位置也要花去O(n)的時間(如果提供索引，ArrayList只要O(1)時間就找到)，這可能是LinkedList唯一的性能瓶頸吧。

但是LinkedList也提供了一個量記錄元素個數

transient int size = 0;

這樣，在提供索引的情況下，可以與size進行比較，確定要插入的位置是離頭結點近，還是離尾結點近（當然這里void結點充當了兩個角色）。又因為是雙向鏈表，這樣就可以從最近的端點開始循著指針尋找插入位置，大大提高了性能，這可能是設計者選用雙向鏈表而不是單向鏈表的初衷吧。來看代碼：

    @Override    public void add(int location, E object) {        if (location >= 0 && location <= size) {            Link<E> link = voidLink;    //定義一個移動的結點指針，從頭結點開始            if (location < (size / 2)) {    //如果小于總長度的一半，意味著離頭結點更近。話說這里為什么不用位操作提升下性能？                for (int i = 0; i <= location; i++) {                    link = link.next;    //循著next指針順序找到插入點                }            } else {   //離尾結點更近                for (int i = size; i > location; i--) {                    link = link.previous;    //循著previous指針逆序找到插入點                }            }            //下面就是大學數據結構課本上面練習了n多遍的結點插入操作，要改變哪些指針一定要小心。不過話說當時我為什么沒好好學這門課呢？/(ㄒoㄒ)/~~            Link<E> previous = link.previous;    //記錄下前向結點            Link<E> newLink = new Link<E>(object, previous, link);  //開辟一段新的內存空間，存儲新創建的結點            previous.next = newLink;    //前向結點的next域指向新結點            link.previous = newLink;    //后向結點的previous域指向新結點            size++;    //元素個數加1            modCount++;    //鏈表修改次數加1        } else {            throw new IndexOutOfBoundsException();        }    }

當然，如果不指定索引，只要求往后順序插入，或者插到頭部位置，那就只有優勢，沒有任何性能瓶頸了，因為只要O(1)時間，且不用擔心任何溢出問題。

    @Override    public boolean add(E object) {        return addLastImpl(object);    }        //這里將尾部插入的方法抽象了出來，以支持后面出現的隊列操作addLast、offer、offerLast，雖然這些操作跟add操作代碼相同    private boolean addLastImpl(E object) {        Link<E> oldLast = voidLink.previous;      //記錄下最后一個非void結點         Link<E> newLink = new Link<E>(object, oldLast, voidLink);  //創建新結點        voidLink.previous = newLink;   //void尾結點的前向指針指向新結點        oldLast.next = newLink;        size++;        modCount++;        return true;    }

頭部插入代碼類似

    public void addFirst(E object) {        addFirstImpl(object);    }    //抽象出這段頭部插入代碼是為了同時支持后面的offerFirst以及棧的push操作    private boolean addFirstImpl(E object) {        Link<E> oldFirst = voidLink.next;   //記錄下頭部第一個非void結點        Link<E> newLink = new Link<E>(object, voidLink, oldFirst);  //創建新結點        voidLink.next = newLink;   //void頭結點的后向指針指向新結點        oldFirst.previous = newLink;  //原來的第一個含元素的結點修改前向指針，退居二線        size++;        modCount++;        return true;   //永遠返回true    }

下面來看元素的刪除操作

相比于ArrayList，LinkedList也是占據優勢的，因為只要修改相鄰結點的指針即可，而ArrayList存在大量元素前移的操作。如果是給出索引刪除結點，LinkedList存在尋找位置的過程，優勢不大；但是如果給結點值，兩種List都存在沿著路徑查找的操作，反而LinkedList更占優勢。

    @Override    public E remove(int location) {        if (location >= 0 && location < size) {            Link<E> link = voidLink;            if (location < (size / 2)) {  //仍然先確定從哪端開始較近，更快找到                for (int i = 0; i <= location; i++) {                    link = link.next;                }            } else {                for (int i = size; i > location; i--) {                    link = link.previous;                }            }            //下面只要把刪除點相鄰的兩個結點連接即可，只要O(1)時間            //被刪的結點因為沒有索引再指向它，會被jvm垃圾回收器自動回收內存            Link<E> previous = link.previous;            Link<E> next = link.next;            previous.next = next;            next.previous = previous;            size--;            modCount++;            return link.data;  //返回被刪結點的值        }        throw new IndexOutOfBoundsException();    }

修改操作就不展示代碼了，與上面一樣，只要先循著路徑找到索引位置，修改值就可以了

LinkedList最大的劣勢在于根據索引查找操作，與上面添加操作的查找過程類似

    @Override    public E get(int location) {        if (location >= 0 && location < size) {            Link<E> link = voidLink;            if (location < (size / 2)) {                for (int i = 0; i <= location; i++) {                    link = link.next;                }            } else {                for (int i = size; i > location; i--) {                    link = link.previous;                }            }            return link.data;        }        throw new IndexOutOfBoundsException();    }

總結：在容器類最基本的增刪改查的操作中，借助于鏈表的LinkedList有優勢有劣勢。

　　　優勢：①對于增刪操作，只要找到了操作位置，都只要O(1)時間就能執行完成。而ArrayList必須進行大量元素一個個前移或后移的操作，要花費O(n)時間。

　　　　　?、贚inkedList可以靈活地增加元素，而完全不用考慮處理溢出問題。而ArrayList的事先規定的容量是有限的，一旦達到容量上限需要擴容，代價極大，首先要額外再 開辟另一片更大的內存空間，接著要把原來所有的元素“集體移民”，一個一個復制到新地址空間，這對時間和空間都是極大的損耗。

劣勢：①在增刪改查的操作中，查找元素位置的代價較大，不管給沒給索引，都要對鏈表進行O(n)時間的遍歷。當然，先行判斷起始查找點改善了一些性能。而ArrayList只 要給出索引就可以在O(1)時間找到指定位置。

　　　 ②每個結點都必須加上兩個指針進行包裝，大大損耗了內存空間。學過C++的知道，指針也是占用內存空間的，一個指針占4個字節。隨著元素個數增加，光指針占用 的內存就會急劇增長。而ArrayList的每個結點都只有實際的元素值，不用加任何包裝。

另外，查看LinkedList的源碼讓我第一次真正感受到了數據結構的重要性，當學會棧、隊列、鏈表、二叉樹等常見的操作后，看這些代碼就是小菜一碟。也難怪應屆生校園招聘的時候，大公司就喜歡出數據結構的題來考我們呢！大二的時候我馬馬虎虎地對待這門課真是不應該。