LinkedList集合分析

文章目錄

• 前言
• • LinkedList重要源碼分析
  • • 内部私有類Node
    • linkFirst(E e)方法l
    • linkLast(E e)方法
    • linkBefore(E e, Node succ)方法
    • node(int index)方法

前言

說到集合，Java中所有集合的總接口時Collection，Collection規範了集合基本的操作方法，同時限制了所有集合都存在泛型限制。下面是集合的組織架構：

interface Collection<E>
    interface List<E> extends Collection<E>
    	class ArrayList<E> implements List<E>
    	class LinkedList<E> implements List<E>
    	class Vector<E> implements List<E>
    interface Set<E> extends Collection<E>
    	class TreeSet<E> implements Set<E>
    	class HashSet<E> implements Set<E>
           

今天我們要說的是LinkedList集合，LinkedList集合是一種連結清單類型的資料結構，在建立LinkedList節點時，jvm會在記憶體中找到一個足夠的空間存儲，一個節點中包含三部分内容：前趨節點，本節點内的值，後繼節點。前趨節點儲存的是前面一個節點的位址，後繼節點儲存的是後面一個節點的位址 。通過前趨節點和後繼節點組成了一個雙向連結清單（雙向連結清單指的是可以從首節點周遊到尾節點，也可以從尾節點周遊到首節點，我以前一直以為雙向連結清單指的是連結清單的首尾是相連的）。

雙向連結清單的特征是：增删快，查詢慢，并且理論上存儲數量無限制。在記憶體方面，連結清單不需要直接申請連續的空間，而是每當建立一個節點再申請一個節點的空間，相比于ArrayList對記憶體的壓力小。

下面我們來分析一下LinkedList源碼中的幾個重要方法來了解LinkedList。

LinkedList重要源碼分析

内部私有類Node

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}
           

Linkedlist有一個内部私有類Node，這個類就是Linkedlist雙向連結清單的節點，每添加一個資料就會建立一個節點。這個節點由三部分組成：節點内元素，後繼節點，前驅節點。

linkFirst(E e)方法l

在linkFirst方法中有first和last變量，是這樣定義的

transient Node<E> first;
transient Node<E> last;
           

這是雙向連結清單的成員變量，first為連結清單的頭節點（始終指向連結清單的第一個節點），last為連結清單的尾節點（始終指向節點的最後一個節點）

當連結清單為空時，first和last都為null；

當連結清單不為空時，first的前驅節點為空，元素内容必定不為空，last後繼節點必定為空。

下面是linkedList方法源碼（注釋為我自己注釋的，源碼中沒有）

private void linkFirst(E e) {
    // 建立f儲存頭節點
    final Node<E> f = first;
    // 建立新的節點，并将後繼節點指向頭節點
    final Node<E> newNode = new Node<>(null, e, f);
    // 更新頭節點
    first = newNode;
    // 判斷連結清單之前是否為空
    if (f == null)
        // 若插入之前連結清單為空，尾節點也指向新節點
        last = newNode;
    else
        // 若連結清單不為空，不需要考慮尾節點，将插入之前頭節點的前趨節點指向新的節點（更新之前頭節點的前趨）
        f.prev = newNode;
    // 更新連結清單有效節點個數
    size++;
    // 更新連結清單修改次數保護線程安全
    modCount++;
}
           

linkFirst方法是建立一個新的節點插入到頭節點之前，這個節點的後繼節點為插入前的頭節點。在插入完成後更新頭節點指向（如果之前雙向連結清單為空，同時更新尾節點指向）。

linkLast(E e)方法

void linkLast(E e) {
    // 建立儲存尾節點的l節點
    final Node<E> l = last;
    // 建立新的節點，并将新節點的前趨指向尾節點
    final Node<E> newNode = new Node<>(l, e, null);
    // 更新尾節點
    last = newNode;
    // 判斷連結清單是否為空
    if (l == null)
        // 若為空，更新頭節點
        first = newNode;
    else
        // 若連結清單不為空，不需要考慮頭節點，将插入之前尾節點的後繼節點指向新的節點（更新之前尾節點的後繼）
        l.next = newNode;
    // 更新連結清單有效節點個數
    size++;
    // 更新連結清單修改次數保護線程安全
    modCount++;
}
           

linkLast方法是建立一個新的節點到尾節點之後，該節點的前趨節點為插入前的尾節點。在插入完成後更新尾節點指向（如果連結清單在插入前為空，同時更新頭節點）。

linkBefore(E e, Node succ)方法

void linkBefore(E e, Node<E> succ) {
    // 建立pred節點儲存指定節點的前趨節點
    // assert succ != null; 源碼注釋
    final Node<E> pred = succ.prev;
    // 建立新的節點儲存指定元素内容，前趨為儲存的指定節點的前趨節點，後繼節點為指定節點
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 更新指定節點的前趨
    succ.prev = newNode;
    // 判斷指定節點是不是頭指針
    if (pred == null)
        // 如果是，更新頭指針
        first = newNode;
    else
        // 否則，更新指定節點的前趨節點的後繼指向，指向新節點
        pred.next = newNode;
    // 有效節點個數加一
    size++;
    // 修改次數加一
    modCount++;
}
           

linkBefore方法是在指定節點前面插入一個節點。

在連結清單中插入一個元素就是修改要插入位置前後兩節點的指向。如圖，要在指定節點前插入新的元素，就要修改指定節點的前趨節點的後繼，和指定節點的前趨。

在源碼中建立新節點時分别初始化了新節點的前趨和後繼，即線1， 2。

然後通過 succ.prev = newNode; 修改了指定節點的前趨。即線3。

最後判斷指定節點是否為頭指針（判斷指定節點前趨節點是否為空）來修改指定節點前趨節點的後繼，即線4。

node(int index)方法

Node<E> node(int index) {
    // assert isElementIndex(index);
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}
           

node方法是查詢指定下标位置的元素。因為LinkedList查詢是根據前趨後繼查詢，是以查詢速度較慢。

這裡采用折半查找将連結清單根據有效節點個數從中間分開，前半部分從前往後周遊，後半部分從後往前周遊。這樣能夠節省查詢時間。

以上是我對LinkedList幾個關鍵方法的分析，如有錯誤，希望能夠指出，讓我得以查漏補缺，謝謝。