初識LinkedList

上一篇中講解了ArrayList，本篇文章講解一下LinkedList的實現。

LinkedList是基于鏈表實現的，所以先講解一下什么是鏈表。鏈表原先是C/C++的概念，是一種線性的存儲結構，意思是將要存儲的數據存在一個存儲單元里面，這個存儲單元里面除了存放有待存儲的數據以外，還存儲有其下一個存儲單元的地址（下一個存儲單元的地址是必要的，有些存儲結構還存放有其前一個存儲單元的地址），每次查找數據的時候，通過某個存儲單元中的下一個存儲單元的地址尋找其后面的那個存儲單元。

這么講可能有點抽象，先提一句，LinkedList是一種雙向鏈表，雙向鏈表我認為有兩點含義：

1、鏈表中任意一個存儲單元都可以通過向前或者向后尋址的方式獲取到其前一個存儲單元和其后一個存儲單元

2、鏈表的尾節點的后一個節點是鏈表的頭結點，鏈表的頭結點的前一個節點是鏈表的尾節點

LinkedList既然是一種雙向鏈表，必然有一個存儲單元，看一下LinkedList的基本存儲單元，它是LinkedList中的一個內部類：

PRivate static class Entry<E> {E element;Entry<E> next;Entry<E> previous;...}

看到LinkedList的Entry中的"E element"，就是它真正存儲的數據。"Entry<E> next"和"Entry<E> previous"表示的就是這個存儲單元的前一個存儲單元的引用地址和后一個存儲單元的引用地址。用圖表示就是：

四個關注點在LinkedList上的答案

添加元素

首先看下LinkedList添加一個元素是怎么做的，假如我有一段代碼：

1 public static void main(String[] args)2 {3     List<String> list = new LinkedList<String>();4     list.add("111");5     list.add("222");6 }

逐行分析main函數中的三行代碼是如何執行的，首先是第3行，看一下LinkedList的源碼：

 1 public class LinkedList<E> 2     extends AbstractSequentialList<E> 3     implements List<E>, Deque<E>, Cloneable, java.io.Serializable 4 { 5     private transient Entry<E> header = new Entry<E>(null, null, null); 6     private transient int size = 0; 7  8     /** 9      * Constructs an empty list.10      */11     public LinkedList() {12         header.next = header.previous = header;13     }14     ...15 }

看到，new了一個Entry出來名為header，Entry里面的previous、element、next都為null，執行構造函數的時候，將previous和next的值都設置為header的引用地址，還是用畫圖的方式表示。32位JDK的字長為4個字節，而目前64位的JDK一般采用的也是4字長，所以就以4個字長為單位。header引用地址的字長就是4個字節，假設是0x00000000，那么執行完"List<String> list = new LinkedList<String>()"之后可以這么表示：

接著看第4行add一個字符串"111"做了什么：

1 public boolean add(E e) {2 addBefore(e, header);3     return true;4 }

1 private Entry<E> addBefore(E e, Entry<E> entry) {2 Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);3 newEntry.previous.next = newEntry;4 newEntry.next.previous = newEntry;5 size++;6 modCount++;7 return newEntry;8 }

第2行new了一個Entry出來，可能不太好理解，根據Entry的構造函數，我把這句話"翻譯"一下，可能就好理解了：

1、newEntry.element = e;

2、newEntry.next = header.next;

3、newEntry.previous = header.previous;

header.next和header.previous上圖中已經看到了，都是0x00000000，那么假設new出來的這個Entry的地址是0x00000001，繼續畫圖表示：

一共五步，每一步的操作步驟都用數字表示出來了：

1、新的entry的element賦值為111;

2、新的entry的next是header的next，header的next是0x00000000，所以新的entry的next即0x00000000;

3、新的entry的previous是header的previous，header的previous是0x00000000，所以新的entry的next即0x00000000;

4、"newEntry.previous.next = newEntry"，首先是newEntry的previous，由于newEntry的previous為0x00000000，所以newEntry.previous表示的是header，header的next為newEntry，即header的next為0x00000001;

5、"newEntry.next.previous = newEntry"，和4一樣，把header的previous設置為0x00000001;

為什么要這么做？還記得雙向鏈表的兩個特點嗎，一是任意節點都可以向前和向后尋址，二是整個鏈表頭的previous表示的是鏈表的尾Entry，鏈表尾的next表示的是鏈表的頭Entry。現在鏈表頭就是0x00000000這個Entry，鏈表尾就是0x00000001，可以自己看圖觀察、思考一下是否符合這兩個條件。

最后看一下add了一個字符串"222"做了什么，假設新new出來的Entry的地址是0x00000002，畫圖表示：

還是執行的那5步，圖中每一步都標注出來了，只要想清楚previous、next各自表示的是哪個節點就不會出問題了。

至此，往一個LinkedList里面添加一個字符串"111"和一個字符串"222"就完成了。從這張圖中應該理解雙向鏈表比較容易：

1、中間的那個Entry，previous的值為0x00000000，即header；next的值為0x00000002，即tail，這就是任意一個Entry既可以向前查找Entry，也可以向后查找Entry

2、頭Entry的previous的值為0x00000002，即tail，這就是雙向鏈表中頭Entry的previous指向的是尾Entry

3、尾Entry的next的值為0x00000000，即header，這就是雙向鏈表中尾Entry的next指向的是頭Entry

查看元素

看一下LinkedList的代碼是怎么寫的：

public E get(int index) {    return entry(index).element;}

 1 private Entry<E> entry(int index) { 2     if (index < 0 || index >= size) 3         throw new IndexOutOfBoundsException("Index: "+index+ 4                                             ", Size: "+size); 5     Entry<E> e = header; 6     if (index < (size >> 1)) { 7         for (int i = 0; i <= index; i++) 8             e = e.next; 9     } else {10         for (int i = size; i > index; i--)11             e = e.previous;12     }13     return e;14 }

這段代碼就體現出了雙向鏈表的好處了。雙向鏈表增加了一點點的空間消耗（每個Entry里面還要維護它的前置Entry的引用），同時也增加了一定的編程復雜度，卻大大提升了效率。

由于LinkedList是雙向鏈表，所以LinkedList既可以向前查找，也可以向后查找，第6行~第12行的作用就是：當index小于數組大小的一半的時候（size >> 1表示size / 2，使用移位運算提升代碼運行效率），向后查找；否則，向前查找。

這樣，在我的數據結構里面有10000個元素，剛巧查找的又是第10000個元素的時候，就不需要從頭遍歷10000次了，向后遍歷即可，一次就能找到我要的元素。

刪除元素

看完了添加元素，我們看一下如何刪除一個元素。和ArrayList一樣，LinkedList支持按元素刪除和按下標刪除，前者會刪除從頭開始匹配的第一個元素。用按下標刪除舉個例子好了，比方說有這么一段代碼：

1 public static void main(String[] args)2 {3     List<String> list = new LinkedList<String>();4     list.add("111");5     list.add("222");6     list.remove(0);7 }

也就是我想刪除"111"這個元素。看一下第6行是如何執行的：

1 public E remove(int index) {2     return remove(entry(index));3 }

 1 private E remove(Entry<E> e) { 2 if (e == header) 3     throw new NoSuchElementException(); 4  5         E result = e.element; 6 e.previous.next = e.next; 7 e.next.previous = e.previous; 8        e.next = e.previous = null; 9        e.element = null;10 size--;11 modCount++;12        return result;13 }

當然，首先是找到元素在哪里，這和get是一樣的。接著，用畫圖的方式來說明比較簡單：

比較簡單，只要找對引用地址就好了，每一步的操作也都詳細標注在圖上了。

這里我提一點，第3步、第4步、第5步將待刪除的Entry的previous、element、next都設置為了null，這三步的作用是讓虛擬機可以回收這個Entry。

但是，這個問題我稍微擴展深入一點：按照Java虛擬機HotSpot采用的垃圾回收檢測算法----根節點搜索算法來說，即使previous、element、next不設置為null也是可以回收這個Entry的，因為此時這個Entry已經沒有任何地方會指向它了，tail的previous與header的next都已經變掉了，所以這塊Entry會被當做"垃圾"對待。之所以還要將previous、element、next設置為null，我認為可能是為了兼容另外一種垃圾回收檢測算法----引用計數法，這種垃圾回收檢測算法，只要對象之間存在相互引用，那么這塊內存就不會被當作"垃圾"對待。

刪除元素

刪除元素就不細講了，看一下刪除元素的源代碼：

public void add(int index, E element) {    addBefore(element, (index==size ? header : entry(index)));}

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;}

如果朋友們理解了前面的內容，我認為這兩個方法對你來說，應該是很容易看懂的。

LinkedList和ArrayList的對比

老生常談的問題了，這里我嘗試以自己的理解盡量說清楚這個問題，順便在這里就把LinkedList的優缺點也給講了。

1、順序插入速度ArrayList會比較快，因為ArrayList是基于數組實現的，數組是事先new好的，只要往指定位置塞一個數據就好了；LinkedList則不同，每次順序插入的時候LinkedList將new一個對象出來，如果對象比較大，那么new的時間勢必會長一點，再加上一些引用賦值的操作，所以順序插入LinkedList必然慢于ArrayList

2、基于上一點，因為LinkedList里面不僅維護了待插入的元素，還維護了Entry的前置Entry和后繼Entry，如果一個LinkedList中的Entry非常多，那么LinkedList將比ArrayList更耗費一些內存

3、數據遍歷的速度，看最后一部分，這里就不細講了，結論是：使用各自遍歷效率最高的方式，ArrayList的遍歷效率會比LinkedList的遍歷效率高一些

4、有些說法認為LinkedList做插入和刪除更快，這種說法其實是不準確的：

（1）LinkedList做插入、刪除的時候，慢在尋址，快在只需要改變前后Entry的引用地址

（2）ArrayList做插入、刪除的時候，慢在數組元素的批量copy，快在尋址

所以，如果待插入、刪除的元素是在數據結構的前半段尤其是非常靠前的位置的時候，LinkedList的效率將大大快過ArrayList，因為ArrayList將批量copy大量的元素；越往后，對于LinkedList來說，因為它是雙向鏈表，所以在第2個元素后面插入一個數據和在倒數第2個元素后面插入一個元素在效率上基本沒有差別，但是ArrayList由于要批量copy的元素越來越少，操作速度必然追上乃至超過LinkedList。

從這個分析看出，如果你十分確定你插入、刪除的元素是在前半段，那么就使用LinkedList；如果你十分確定你刪除、刪除的元素在比較靠后的位置，那么可以考慮使用ArrayList。如果你不能確定你要做的插入、刪除是在哪兒呢？那還是建議你使用LinkedList吧，因為一來LinkedList整體插入、刪除的執行效率比較穩定，沒有ArrayList這種越往后越快的情況；二來插入元素的時候，弄得不好ArrayList就要進行一次擴容，記住，ArrayList底層數組擴容是一個既消耗時間又消耗空間的操作，在我的文章Java代碼優化中，第9點有詳細的解讀。

最后一點，一切都是紙上談兵，在選擇了List后，有條件的最好可以做一些性能測試，比如在你的代碼上下文記錄List操作的時間消耗。

對LinkedList以及ArrayList的迭代

在我的Java代碼優化一文中，第19點，專門提到過，ArrayList使用最普通的for循環遍歷，LinkedList使用foreach循環比較快，看一下兩個List的定義：

public class ArrayList<E> extends AbstractList<E>        implements List<E>, Randomaccess, Cloneable, java.io.Serializable

public class LinkedList<E>    extends AbstractSequentialList<E>    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

注意到ArrayList是實現了RandomAccess接口而LinkedList則沒有實現這個接口，關于RandomAccess這個接口的作用，看一下JDK API上的說法：

為此，我寫一段代碼證明一下這一點，注意，雖然上面的例子用的Iterator，但是做foreach循環的時候，編譯器默認會使用這個集合的Iterator，具體可參見foreach循環原理。測試代碼如下：

public class TestMain{    private static int SIZE = 111111;        private static void loopList(List<Integer> list)    {        long startTime = System.currentTimeMillis();        for (int i = 0; i < list.size(); i++)        {            list.get(i);        }        System.out.println(list.getClass().getSimpleName() + "使用普通for循環遍歷時間為" +                 (System.currentTimeMillis() - startTime) + "ms");                startTime = System.currentTimeMillis();        for (Integer i : list)        {                    }        System.out.println(list.getClass().getSimpleName() + "使用foreach循環遍歷時間為" +                 (System.currentTimeMillis() - startTime) + "ms");    }        public static void main(String[] args)    {        List<Integer> arrayList = new ArrayList<Integer>(SIZE);        List<Integer> linkedList = new LinkedList<Integer>();                for (int i = 0; i < SIZE; i++)        {            arrayList.add(i);            linkedList.add(i);        }                loopList(arrayList);        loopList(linkedList);        System.out.println();    }}

我截取三次運行結果：

ArrayList使用普通for循環遍歷時間為6msArrayList使用foreach循環遍歷時間為12msLinkedList使用普通for循環遍歷時間為38482msLinkedList使用foreach循環遍歷時間為11ms

ArrayList使用普通for循環遍歷時間為5msArrayList使用foreach循環遍歷時間為12msLinkedList使用普通for循環遍歷時間為43287msLinkedList使用foreach循環遍歷時間為9ms

ArrayList使用普通for循環遍歷時間為4msArrayList使用foreach循環遍歷時間為12msLinkedList使用普通for循環遍歷時間為22370msLinkedList使用foreach循環遍歷時間為5ms

有了JDK API的解釋，這個結果并不讓人感到意外，最最想要提出的一點是：如果使用普通for循環遍歷LinkedList，其遍歷速度將慢得令人發指。