JDK1.8源碼(六)——java.util.LinkedList 類

JDK1.8源碼(六)——java.util.LinkedList 類

　　上一篇部落格我們介紹了List集合的一種典型實作 ArrayList，我們知道 ArrayList 是由數組構成的，本篇部落格我們介紹 List 集合的另一種典型實作 LinkedList，這是一個由連結清單構成的數組，關于連結清單的介紹，在這篇部落格中 我們也詳細介紹過，本篇部落格我們将介紹 LinkedList 是如何實作的。

1、LinkedList 定義

　　LinkedList 是一個用連結清單實作的集合，元素有序且可以重複。

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

　　和 ArrayList 集合一樣，LinkedList 集合也實作了Cloneable接口和Serializable接口，分别用來支援克隆以及支援序列化。List 接口也不用多說，定義了一套 List 集合類型的方法規範。

　　注意，相對于 ArrayList 集合，LinkedList 集合多實作了一個 Deque 接口，這是一個雙向隊列接口，雙向隊列就是兩端都可以進行增加和删除操作。

2、字段屬性

//連結清單元素（節點）的個數
    transient int size = 0;

    /**
     *指向第一個節點的指針
     */
    transient Node<E> first;

    /**
     *指向最後一個節點的指針
     */
    transient Node<E> last;      

　　注意這裡出現了一個 Node 類，這是 LinkedList 類中的一個内部類，其中每一個元素就代表一個 Node 類對象，LinkedList 集合就是由許多個 Node 對象類似于手拉着手構成。

1     private static class Node<E> {
 2         E item;//實際存儲的元素
 3         Node<E> next;//指向上一個節點的引用
 4         Node<E> prev;//指向下一個節點的引用
 5 
 6         //構造函數
 7         Node(Node<E> prev, E element, Node<E> next) {
 8             this.item = element;
 9             this.next = next;
10             this.prev = prev;
11         }
12     }      

View Code

　　如下圖所示：

　　

　　上圖的 LinkedList 是有四個元素，也就是由 4 個 Node 對象組成，size=4，head 指向第一個elementA,tail指向最後一個節點elementD。

3、構造函數 

public LinkedList() {
    }
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }      

　　LinkedList 有兩個構造函數，第一個是預設的空的構造函數，第二個是将已有元素的集合Collection 的執行個體添加到 LinkedList 中，調用的是 addAll() 方法，這個方法下面我們會介紹。

　　注意：LinkedList 是沒有初始化連結清單大小的構造函數，因為連結清單不像數組，一個定義好的數組是必須要有确定的大小，然後去配置設定記憶體空間，而連結清單不一樣，它沒有确定的大小，通過指針的移動來指向下一個記憶體位址的配置設定。

4、添加元素

　　①、addFirst(E e)

　　将指定元素添加到連結清單頭

1     //将指定的元素附加到連結清單頭節點
 2     public void addFirst(E e) {
 3         linkFirst(e);
 4     }
 5     private void linkFirst(E e) {
 6         final Node<E> f = first;//将頭節點指派給 f
 7         final Node<E> newNode = new Node<>(null, e, f);//将指定元素構造成一個新節點，此節點的指向下一個節點的引用為頭節點
 8         first = newNode;//将新節點設為頭節點，那麼原先的頭節點 f 變為第二個節點
 9         if (f == null)//如果第二個節點為空，也就是原先連結清單是空
10             last = newNode;//将這個新節點也設為尾節點（前面已經設為頭節點了）
11         else
12             f.prev = newNode;//将原先的頭節點的上一個節點指向新節點
13         size++;//節點數加1
14         modCount++;//和ArrayList中一樣，iterator和listIterator方法傳回的疊代器和清單疊代器實作使用。
15     }      

　　②、addLast(E e)和add(E e)

　　将指定元素添加到連結清單尾

1     //将元素添加到連結清單末尾
 2     public void addLast(E e) {
 3         linkLast(e);
 4     }
 5     //将元素添加到連結清單末尾
 6     public boolean add(E e) {
 7         linkLast(e);
 8         return true;
 9     }
10     void linkLast(E e) {
11         final Node<E> l = last;//将l設為尾節點
12         final Node<E> newNode = new Node<>(l, e, null);//構造一個新節點，節點上一個節點引用指向尾節點l
13         last = newNode;//将尾節點設為建立的新節點
14         if (l == null)//如果尾節點為空，表示原先連結清單為空
15             first = newNode;//将頭節點設為新建立的節點（尾節點也是新建立的節點）
16         else
17             l.next = newNode;//将原來尾節點下一個節點的引用指向新節點
18         size++;//節點數加1
19         modCount++;//和ArrayList中一樣，iterator和listIterator方法傳回的疊代器和清單疊代器實作使用。
20     }      

　　③、add(int index, E element)

　　将指定的元素插入此清單中的指定位置

　

//将指定的元素插入此清單中的指定位置
    public void add(int index, E element) {
        //判斷索引 index >= 0 && index <= size中時抛出IndexOutOfBoundsException異常
        checkPositionIndex(index);

        if (index == size)//如果索引值等于連結清單大小
            linkLast(element);//将節點插入到尾節點
        else
            linkBefore(element, node(index));
    }
    void linkLast(E e) {
        final Node<E> l = last;//将l設為尾節點
        final Node<E> newNode = new Node<>(l, e, null);//構造一個新節點，節點上一個節點引用指向尾節點l
        last = newNode;//将尾節點設為建立的新節點
        if (l == null)//如果尾節點為空，表示原先連結清單為空
            first = newNode;//将頭節點設為新建立的節點（尾節點也是新建立的節點）
        else
            l.next = newNode;//将原來尾節點下一個節點的引用指向新節點
        size++;//節點數加1
        modCount++;//和ArrayList中一樣，iterator和listIterator方法傳回的疊代器和清單疊代器實作使用。
    }
    Node<E> node(int index) {
        if (index < (size >> 1)) {//如果插入的索引在前半部分
            Node<E> x = first;//設x為頭節點
            for (int i = 0; i < index; i++)//從開始節點到插入節點索引之間的所有節點向後移動一位
                x = x.next;
            return x;
        } else {//如果插入節點位置在後半部分
            Node<E> x = last;//将x設為最後一個節點
            for (int i = size - 1; i > index; i--)//從最後節點到插入節點的索引位置之間的所有節點向前移動一位
                x = x.prev;
            return x;
        }
    }
    void linkBefore(E e, Node<E> succ) {
        final Node<E> pred = succ.prev;//将pred設為插入節點的上一個節點
        final Node<E> newNode = new Node<>(pred, e, succ);//将新節點的上引用設為pred,下引用設為succ
        succ.prev = newNode;//succ的上一個節點的引用設為新節點
        if (pred == null)//如果插入節點的上一個節點引用為空
            first = newNode;//新節點就是頭節點
        else
            pred.next = newNode;//插入節點的下一個節點引用設為新節點
        size++;
        modCount++;
    }      

　　④、addAll(Collection<? extends E> c)

　　按照指定集合的​​疊代器傳回的順序，将指定集合中的所有元素追加到此清單的末尾

　　此方法還有一個 addAll(int index, Collection<? extends E> c)，将集合 c 中所有元素插入到指定索引的位置。其實 

　　　　addAll(Collection<? extends E> c) ==  addAll(size, Collection<? extends E> c)

　　源碼如下：

1     //按照指定集合的​​疊代器傳回的順序，将指定集合中的所有元素追加到此清單的末尾。
 2     public boolean addAll(Collection<? extends E> c) {
 3         return addAll(size, c);
 4     }
 5     //将集合 c 中所有元素插入到指定索引的位置。
 6     public boolean addAll(int index, Collection<? extends E> c) {
 7         //判斷索引 index >= 0 && index <= size中時抛出IndexOutOfBoundsException異常
 8         checkPositionIndex(index);
 9 
10         Object[] a = c.toArray();//将集合轉換成一個 Object 類型的數組
11         int numNew = a.length;
12         if (numNew == 0)//如果添加的集合為空，直接傳回false
13             return false;
14 
15         Node<E> pred, succ;
16         if (index == size) {//如果插入的位置等于連結清單的長度，就是将原集合元素附加到連結清單的末尾
17             succ = null;
18             pred = last;
19         } else {
20             succ = node(index);
21             pred = succ.prev;
22         }
23 
24         for (Object o : a) {//周遊要插入的元素
25             @SuppressWarnings("unchecked") E e = (E) o;
26             Node<E> newNode = new Node<>(pred, e, null);
27             if (pred == null)
28                 first = newNode;
29             else
30                 pred.next = newNode;
31             pred = newNode;
32         }
33 
34         if (succ == null) {
35             last = pred;
36         } else {
37             pred.next = succ;
38             succ.prev = pred;
39         }
40 
41         size += numNew;
42         modCount++;
43         return true;
44     }      

　　看到上面向 LinkedList 集合中添加元素的各種方式，我們發現LinkedList 每次添加元素隻是改變元素的上一個指針引用和下一個指針引用，而且沒有擴容。，對比于 ArrayList ，需要擴容，而且在中間插入元素時，後面的所有元素都要移動一位，兩者插入元素時的效率差異很大，下一篇部落格會對這兩者的效率，以及何種情況選擇何種集合進行分析。

　　還有，每次進行添加操作，都有modCount++ 的操作，

5、删除元素

　　删除元素和添加元素一樣，也是通過更改指向上一個節點和指向下一個節點的引用即可，這裡就不作圖形展示了。

　　①、remove()和removeFirst()

　　從此清單中移除并傳回第一個元素

1     //從此清單中移除并傳回第一個元素
 2     public E remove() {
 3         return removeFirst();
 4     }
 5     //從此清單中移除并傳回第一個元素
 6     public E removeFirst() {
 7         final Node<E> f = first;//f設為頭結點
 8         if (f == null)
 9             throw new NoSuchElementException();//如果頭結點為空，則抛出異常
10         return unlinkFirst(f);
11     }
12     private E unlinkFirst(Node<E> f) {
13         // assert f == first && f != null;
14         final E element = f.item;
15         final Node<E> next = f.next;//next 為頭結點的下一個節點
16         f.item = null;
17         f.next = null; // 将節點的元素以及引用都設為 null，便于垃圾回收
18         first = next; //修改頭結點為第二個節點
19         if (next == null)//如果第二個節點為空（目前連結清單隻存在第一個元素）
20             last = null;//那麼尾節點也置為 null
21         else
22             next.prev = null;//如果第二個節點不為空，那麼将第二個節點的上一個引用置為 null
23         size--;
24         modCount++;
25         return element;
26     }      

　　②、removeLast()

　　從該清單中删除并傳回最後一個元素

1     //從該清單中删除并傳回最後一個元素
 2     public E removeLast() {
 3         final Node<E> l = last;
 4         if (l == null)//如果尾節點為空，表示目前集合為空，抛出異常
 5             throw new NoSuchElementException();
 6         return unlinkLast(l);
 7     }
 8     
 9     private E unlinkLast(Node<E> l) {
10         // assert l == last && l != null;
11         final E element = l.item;
12         final Node<E> prev = l.prev;
13         l.item = null;
14         l.prev = null; //将節點的元素以及引用都設為 null，便于垃圾回收
15         last = prev;//尾節點為倒數第二個節點
16         if (prev == null)//如果倒數第二個節點為null
17             first = null;//那麼将節點也置為 null
18         else
19             prev.next = null;//如果倒數第二個節點不為空，那麼将倒數第二個節點的下一個引用置為 null
20         size--;
21         modCount++;
22         return element;
23     }      

　　③、remove(int index)

　　删除此清單中指定位置的元素

1     //删除此清單中指定位置的元素
 2     public E remove(int index) {
 3         //判斷索引 index >= 0 && index <= size中時抛出IndexOutOfBoundsException異常
 4         checkElementIndex(index);
 5         return unlink(node(index));
 6     }
 7     E unlink(Node<E> x) {
 8         // assert x != null;
 9         final E element = x.item;
10         final Node<E> next = x.next;
11         final Node<E> prev = x.prev;
12 
13         if (prev == null) {//如果删除節點位置的上一個節點引用為null（表示删除第一個元素）
14             first = next;//将頭結點置為第一個元素的下一個節點
15         } else {//如果删除節點位置的上一個節點引用不為null
16             prev.next = next;//将删除節點的上一個節點的下一個節點引用指向删除節點的下一個節點（去掉删除節點）
17             x.prev = null;//删除節點的上一個節點引用置為null
18         }
19 
20         if (next == null) {//如果删除節點的下一個節點引用為null（表示删除最後一個節點）
21             last = prev;//将尾節點置為删除節點的上一個節點
22         } else {//不是删除尾節點
23             next.prev = prev;//将删除節點的下一個節點的上一個節點的引用指向删除節點的上一個節點
24             x.next = null;//将删除節點的下一個節點引用置為null
25         }
26 
27         x.item = null;//删除節點内容置為null，便于垃圾回收
28         size--;
29         modCount++;
30         return element;
31     }      

　　④、remove(Object o)

　　如果存在，則從該清單中删除指定元素的第一次出現

　　此方法本質上和 remove(int index) 沒多大差別，通過循環判斷元素進行删除，需要注意的是，是删除第一次出現的元素，不是所有的。

1     public boolean remove(Object o) {
 2         if (o == null) {
 3             for (Node<E> x = first; x != null; x = x.next) {
 4                 if (x.item == null) {
 5                     unlink(x);
 6                     return true;
 7                 }
 8             }
 9         } else {
10             for (Node<E> x = first; x != null; x = x.next) {
11                 if (o.equals(x.item)) {
12                     unlink(x);
13                     return true;
14                 }
15             }
16         }
17         return false;
18     }      

 6、修改元素

　　通過調用 set(int index, E element) 方法，用指定的元素替換此清單中指定位置的元素。

public E set(int index, E element) {
        //判斷索引 index >= 0 && index <= size中時抛出IndexOutOfBoundsException異常
        checkElementIndex(index);
        Node<E> x = node(index);//擷取指定索引處的元素
        E oldVal = x.item;
        x.item = element;//将指定位置的元素替換成要修改的元素
        return oldVal;//傳回指定索引位置原來的元素
    }      

　　這裡主要是通過 node(index) 方法擷取指定索引位置的節點，然後修改此節點位置的元素即可。

7、查找元素

　　①、getFirst()

　　傳回此清單中的第一個元素

1     public E getFirst() {
2         final Node<E> f = first;
3         if (f == null)
4             throw new NoSuchElementException();
5         return f.item;
6     }      

　　②、getLast()

　　傳回此清單中的最後一個元素

1     public E getLast() {
2         final Node<E> l = last;
3         if (l == null)
4             throw new NoSuchElementException();
5         return l.item;
6     }      

　　③、get(int index)

　　傳回指定索引處的元素

1     public E get(int index) {
2         checkElementIndex(index);
3         return node(index).item;
4     }      

　　④、indexOf(Object o)

　　傳回此清單中指定元素第一次出現的索引，如果此清單不包含元素，則傳回-1。

1     //傳回此清單中指定元素第一次出現的索引，如果此清單不包含元素，則傳回-1。
 2     public int indexOf(Object o) {
 3         int index = 0;
 4         if (o == null) {//如果查找的元素為null(LinkedList可以允許null值)
 5             for (Node<E> x = first; x != null; x = x.next) {//從頭結點開始不斷向下一個節點進行周遊
 6                 if (x.item == null)
 7                     return index;
 8                 index++;
 9             }
10         } else {//如果查找的元素不為null
11             for (Node<E> x = first; x != null; x = x.next) {
12                 if (o.equals(x.item))
13                     return index;
14                 index++;
15             }
16         }
17         return -1;//找不到傳回-1
18     }      

8、周遊集合

　　①、普通 for 循環

LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("B");
linkedList.add("C");
linkedList.add("D");
for(int i = 0 ; i < linkedList.size() ; i++){
    System.out.print(linkedList.get(i)+" ");//A B C D
}      

　　代碼很簡單，我們就利用 LinkedList 的 get(int index) 方法，周遊出所有的元素。

　　但是需要注意的是， get(int index) 方法每次都要周遊該索引之前的所有元素，這句話這麼了解：

　　比如上面的一個 LinkedList 集合，我放入了 A,B,C,D是個元素。總共需要四次周遊：

　　第一次周遊列印 A：隻需周遊一次。

　　第二次周遊列印 B：需要先找到 A，然後再找到 B 列印。

　　第三次周遊列印 C：需要先找到 A，然後找到 B，最後找到 C 列印。

　　第四次周遊列印 D：需要先找到 A，然後找到 B，然後找到 C，最後找到 D。

　　這樣如果集合元素很多，越查找到後面（當然此處的get方法進行了優化，查找前半部分從前面開始周遊，查找後半部分從後面開始周遊，但是需要的時間還是很多）花費的時間越多。那麼如何改進呢？

　　②、疊代器

1 LinkedList<String> linkedList = new LinkedList<>();
 2 linkedList.add("A");
 3 linkedList.add("B");
 4 linkedList.add("C");
 5 linkedList.add("D");
 6 
 7 
 8 Iterator<String> listIt = linkedList.listIterator();
 9 while(listIt.hasNext()){
10     System.out.print(listIt.next()+" ");//A B C D
11 }
12 
13 //通過擴充卡模式實作的接口，作用是倒叙列印連結清單
14 Iterator<String> it = linkedList.descendingIterator();
15 while(it.hasNext()){
16     System.out.print(it.next()+" ");//D C B A
17 }      

　　在 LinkedList 集合中也有一個内部類 ListItr，方法實作大體上也差不多，通過移動遊标指向每一次要周遊的元素，不用在周遊某個元素之前都要從頭開始。其方法實作也比較簡單：

1     public ListIterator<E> listIterator(int index) {
  2         checkPositionIndex(index);
  3         return new ListItr(index);
  4     }
  5 
  6     private class ListItr implements ListIterator<E> {
  7         private Node<E> lastReturned;
  8         private Node<E> next;
  9         private int nextIndex;
 10         private int expectedModCount = modCount;
 11 
 12         ListItr(int index) {
 13             // assert isPositionIndex(index);
 14             next = (index == size) ? null : node(index);
 15             nextIndex = index;
 16         }
 17 
 18         public boolean hasNext() {
 19             return nextIndex < size;
 20         }
 21 
 22         public E next() {
 23             checkForComodification();
 24             if (!hasNext())
 25                 throw new NoSuchElementException();
 26 
 27             lastReturned = next;
 28             next = next.next;
 29             nextIndex++;
 30             return lastReturned.item;
 31         }
 32 
 33         public boolean hasPrevious() {
 34             return nextIndex > 0;
 35         }
 36 
 37         public E previous() {
 38             checkForComodification();
 39             if (!hasPrevious())
 40                 throw new NoSuchElementException();
 41 
 42             lastReturned = next = (next == null) ? last : next.prev;
 43             nextIndex--;
 44             return lastReturned.item;
 45         }
 46 
 47         public int nextIndex() {
 48             return nextIndex;
 49         }
 50 
 51         public int previousIndex() {
 52             return nextIndex - 1;
 53         }
 54 
 55         public void remove() {
 56             checkForComodification();
 57             if (lastReturned == null)
 58                 throw new IllegalStateException();
 59 
 60             Node<E> lastNext = lastReturned.next;
 61             unlink(lastReturned);
 62             if (next == lastReturned)
 63                 next = lastNext;
 64             else
 65                 nextIndex--;
 66             lastReturned = null;
 67             expectedModCount++;
 68         }
 69 
 70         public void set(E e) {
 71             if (lastReturned == null)
 72                 throw new IllegalStateException();
 73             checkForComodification();
 74             lastReturned.item = e;
 75         }
 76 
 77         public void add(E e) {
 78             checkForComodification();
 79             lastReturned = null;
 80             if (next == null)
 81                 linkLast(e);
 82             else
 83                 linkBefore(e, next);
 84             nextIndex++;
 85             expectedModCount++;
 86         }
 87 
 88         public void forEachRemaining(Consumer<? super E> action) {
 89             Objects.requireNonNull(action);
 90             while (modCount == expectedModCount && nextIndex < size) {
 91                 action.accept(next.item);
 92                 lastReturned = next;
 93                 next = next.next;
 94                 nextIndex++;
 95             }
 96             checkForComodification();
 97         }
 98 
 99         final void checkForComodification() {
100             if (modCount != expectedModCount)
101                 throw new ConcurrentModificationException();
102         }
103     }      

　　這裡需要重點注意的是 modCount 字段，前面我們在增加和删除元素的時候，都會進行自增操作 modCount，這是因為如果想一邊疊代，一邊用集合自帶的方法進行删除或者新增操作，都會抛出異常。（使用疊代器的增删方法不會抛異常）

final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }      

　　比如：

1 LinkedList<String> linkedList = new LinkedList<>();
 2 linkedList.add("A");
 3 linkedList.add("B");
 4 linkedList.add("C");
 5 linkedList.add("D");
 6 
 7 
 8 Iterator<String> listIt = linkedList.listIterator();
 9 while(listIt.hasNext()){
10     System.out.print(listIt.next()+" ");//A B C D
11     //linkedList.remove();//此處會抛出異常
12     listIt.remove();//這樣可以進行删除操作
13 }      

　　疊代器的另一種形式就是使用 foreach 循環，底層實作也是使用的疊代器，這裡我們就不做介紹了。

LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("B");
linkedList.add("C");
linkedList.add("D");
for(String str : linkedList){
    System.out.print(str + "");
}      

9、疊代器和for循環效率差異

1 LinkedList<Integer> linkedList = new LinkedList<>();
 2 for(int i = 0 ; i < 10000 ; i++){//向連結清單中添加一萬個元素
 3     linkedList.add(i);
 4 }
 5 long beginTimeFor = System.currentTimeMillis();
 6 for(int i = 0 ; i < 10000 ; i++){
 7     System.out.print(linkedList.get(i));
 8 }
 9 long endTimeFor = System.currentTimeMillis();
10 System.out.println("使用普通for循環周遊10000個元素需要的時間："+ (endTimeFor - beginTimeFor));
11 
12 
13 long beginTimeIte = System.currentTimeMillis();
14 Iterator<Integer> it = linkedList.listIterator();
15 while(it.hasNext()){
16     System.out.print(it.next()+" ");
17 }
18 long endTimeIte = System.currentTimeMillis();
19 System.out.println("使用疊代器周遊10000個元素需要的時間："+ (endTimeIte - beginTimeIte));      

　　列印結果為：

　　一萬個元素兩者之間都相差一倍多的時間，如果是十萬，百萬個元素，那麼兩者之間相差的速度會越來越大。下面通過圖形來解釋：

　　普通for循環：每次周遊一個索引的元素之前，都要通路之間所有的索引。

　　疊代器：每次通路一個元素後，都會用遊标記錄目前通路元素的位置，周遊一個元素，記錄一個位置。

參考文檔：https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html#

作者：IT可樂

出處：http://www.cnblogs.com/ysocean/

資源：微信搜【IT可樂】關注我，回複 【電子書】有我特别篩選的免費電子書。

本文版權歸作者所有，歡迎轉載，但未經作者同意不能轉載，否則保留追究法律責任的權利。