基於JDK1.8的LinkedList剖析

之前寫了一篇ArrayList，那麼今天就寫一篇他的姊妹篇，LinkedList。

眾所周知，ArrayList底層數據是數組，可以在O(1)的時間內get到數據，但刪除和插入就要O(n)時間複雜度。

所以出現了鏈表，鏈表可以在O(1)的時間內插入，並且不會浪費記憶體，用多少就鏈接多少即可。

我們從以下幾個方面介紹LinkedList

• Node節點
• add方法
• remove方法
• get方法

(一)Node節點

 1 private static class Node<E> {
 2     E item;
 3     Node<E> next;
 4     Node<E> prev;
 5 
 6     Node(Node<E> prev, E element, Node<E> next) {
 7         this.item = element;
 8         this.next = next;
 9         this.prev = prev;
10     }
11 }

我們可以看出每個結點的組成部分有三個，一個是item數據，一個是prev前驅節點，一個是next後驅節點。

那麼就可以知道LinkedList就是一個雙向鏈表，每個節點既有指向後面的鏈表，也有指向前面的鏈表。如下圖(畫的不好，見諒)

(二)add方法

1 //最基本的add方法，其他方法都是這個方法的變體
2 public boolean add(E e) {
3     linkLast(e);
4     return true;
5 }

直接調用了linkLast方法(也就是說，add方法是預設插入到鏈表的尾端)，然後return 一個 true。

 1 void linkLast(E e) {
 2     //將鏈表的last節點給l
 3     final Node<E> l = last;
 4     final Node<E> newNode = new Node<>(l, e, null);
 5     last = newNode;
 6     //如果是第一個節點
 7     if (l == null)
 8         first = newNode;
 9     //直接加入到尾節點的後面去
10     else
11         l.next = newNode;
12     size++;
13     modCount++;
14 }

我們知道add方法是在隊列尾部添加元素，還是很容易的。首先用變數 l 指向最後一個節點，然後創建一個節點將它的prev指向 l ，這樣newnode成為最後一個節點，使用last指向它，接著使 l 的next指向newnode，這種直接添加在隊列尾部的方式還是很好理解的，我們重點看看如何添加在隊列的中間位置。

 1 public void add(int index, E element) {
 2     //檢查插入位置是否合法
 3     checkPositionIndex(index);
 4 
 5     //如果插入到最後，直接調用linkLast方法
 6     if (index == size)
 7         linkLast(element);
 8     //否則調用linkBefore
 9     else
10         linkBefore(element, node(index));
11 }

直接看註釋。在調用linkBefore之前，調用了node(index)確定插入的位置

 1 Node<E> node(int index) {
 2     // assert isElementIndex(index);
 3 
 4     if (index < (size >> 1)) {
 5         Node<E> x = first;
 6         for (int i = 0; i < index; i++)
 7             x = x.next;
 8         return x;
 9     } else {
10         Node<E> x = last;
11         for (int i = size - 1; i > index; i--)
12             x = x.prev;
13         return x;
14     }
15 }

首先判斷在前半部分還是在後半部分，然後一個for迴圈查找。時間複雜度O(n), 沒辦法，鏈表的缺點。

 1 void linkBefore(E e, Node<E> succ) {
 2     // assert succ != null;
 3     final Node<E> pred = succ.prev;
 4     final Node<E> newNode = new Node<>(pred, e, succ);
 5     succ.prev = newNode;
 6     if (pred == null)
 7         first = newNode;
 8     else
 9         pred.next = newNode;
10     size++;
11     modCount++;
12 }

 (三)remove方法

看完了添加，刪除就顯得簡單些，無非分為兩種，從頭部刪除，從中間刪除，從頭部刪除和從尾部添加一樣簡單，從中間刪除就是把此結點的前一個結點的next指向此結點的後一個結點，並把後一個結點的prev指向此節點的前一個結點，就是跳過此結點，最終將此結點null交給GC大人解決。為了篇幅，我們不再贅述。

 (四)get方法

由於LinkedList是鏈表，get方法必須掃描一遍鏈表，效率極低，所以謹慎使用。

1  public E get(int index) {
2      //檢查是否超過鏈表長度或者負數
3     checkElementIndex(index);
4     //node節點我前面分析過了，O(n)複雜度
5     return node(index).item;
6 }

從源代碼中我們可以清晰的看到，所謂的get方法也就是，調用node方法遍歷整個鏈表，只是其中稍微做了點優化，如果index的值小於size/2從頭部遍歷，否則從尾部遍歷。可見效率一樣低下，所以我們以後寫程式的時候，如果遇到數據量不大但是需要經常遍歷查找的時候使用ArrayList而不是LinkedList，如果數據量非常的大，但是不是很經常的查找時使用LinkedList。