LinkedList 源碼解析

語言: CN / TW / HK

highlight: atom-one-dark theme: fancy


類結構

LinkedList底層採用雙向鏈表結構存儲數據,允許重複數據和null值,長度沒有限制:

lkl01.png

每個節點用內部類Node表示:

```java private static class Node { E item; // 存儲數據 Node next; // 後繼節點 Node prev; // 前繼節點

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

} ```

Node節點包含item(存儲數據),next(後繼節點)和prev(前繼節點)。數組內存地址必須連續,而鏈表就沒有這個限制了,Node可以分佈於各個內存地址,它們之間的關係通過prev和next維護。

LinkedList類關係圖:

lkl02.png

可以看到LinkedList類並沒有實現RandomAccess接口,額外實現了Deque接口,所以包含一些隊列方法。

LinkedList包含如下成員變量:

```java // 元素個數,默認為0 transient int size = 0;

// 表示第一個節點,第一個節點必須滿足(first == null && last == null) || (first.prev == null && first.item != null) transient Node first;

// 表示最後一個節點,最後一個節點必須滿足(first == null && last == null) || (last.next == null && last.item != null) transient Node last; ```

方法解析

構造函數

LinkedList()

java public LinkedList() {}

空參構造函數,默認size為0,每次添加新元素都要創建Node節點。

LinkedList(Collection<? extends E> c)

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

public boolean addAll(Collection<? extends E> c) { return addAll(size, c); }

public boolean addAll(int index, Collection<? extends E> c) { checkPositionIndex(index);

Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
    return false;

Node<E> pred, succ;
if (index == size) {
    succ = null;
    pred = last;
} else {
    succ = node(index);
    pred = succ.prev;
}
// 循環創建節點,設置prev,next指向
for (Object o : a) {
    @SuppressWarnings("unchecked") E e = (E) o;
    Node<E> newNode = new Node<>(pred, e, null);
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    pred = newNode;
}

if (succ == null) {
    last = pred;
} else {
    pred.next = succ;
    succ.prev = pred;
}

size += numNew;
modCount++;
return true;

} ```

該構造函數用於創建LinkedList,並往裏添加指定集合元素。

add(int index, E element)

add(int index, E element)指定下標插入元素:

```java public void add(int index, E element) { // 下標合法性檢查 checkPositionIndex(index);

if (index == size)
    // 如果插入下標等於size,説明是在尾部插入,執行尾部插入操作
    linkLast(element);
else
    // 如果不是尾插入,則在指定下標節點前插入
    linkBefore(element, node(index));

}

private void checkPositionIndex(int index) { if (!isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }

private boolean isPositionIndex(int index) { return index >= 0 && index <= size; }

void linkLast(E e) { // 獲取最後一個節點 final Node l = last; // 創建一個新節點,prev為原鏈表最後一個節點,next為null final Node newNode = new Node<>(l, e, null); // 更新last為新節點 last = newNode; if (l == null) // 如果原鏈表最後一個節點為null,説明原鏈表沒有節點,將新節點賦給first first = newNode; else // 否則更新原鏈表最後一個節點的next為新節點 l.next = newNode; // size遞增 size++; // 模數遞增,用於快速失敗 modCount++; }

void linkBefore(E e, Node succ) { // succ為原鏈表指定index位置的節點,獲取其prev節點 final Node pred = succ.prev; // 創建新節點,prev為原鏈表指定index位置的節點的prev節點,next為原鏈表指定index位置的節點 final Node newNode = new Node<>(pred, e, succ); // 將原鏈表指定index位置的節點的prev更新為新節點 succ.prev = newNode; if (pred == null) // 如果鏈表指定index位置的節點的prev為null,説明原鏈表沒有節點,將新節點賦給first first = newNode; else // 否則更新原鏈表指定index位置的節點的prev的next節點為新節點 pred.next = newNode; // size遞增 size++; // 模數遞增,用於快速失敗 modCount++; }

// 採用二分法遍歷每個Node節點,直到找到index位置的節點 Node 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;
}

} ```

無非就是設置節點的prev和next關係。可以看到,除了頭插和尾插外,在鏈表別的位置插入新節點,涉及到節點遍歷操作,所以我們常説的鏈表插入速度快,指的是插入節點改變前後節點的引用過程很快。

get(int index)

get(int index)獲取指定下標元素:

```java public E get(int index) { checkElementIndex(index); return node(index).item; }

// 採用二分法遍歷每個Node節點,直到找到index位置的節點 Node 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函數查找指定index下標Node,然後獲取其item屬性值,節點查找需要遍歷。

set(int index, E element)

set(int index, E element)設置指定下標節點的item為指定值:

```java public E set(int index, E element) { // 下標合法性檢查 checkElementIndex(index); // 獲取index下標節點 Node x = node(index); // 獲取舊值 E oldVal = x.item; // 設置新值 x.item = element; // 返回舊值 return oldVal; }

// 採用二分法遍歷每個Node節點,直到找到index位置的節點 Node 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;
}

} ```

可以看到,set方法也需要通過遍歷查找目標節點。

remove(int index)

remove(int index)刪除指定下標節點:

```java public E remove(int index) { checkElementIndex(index); return unlink(node(index)); }

E unlink(Node x) { // assert x != null; final E element = x.item; final Node next = x.next; final Node prev = x.prev;

if (prev == null) {
    first = next;
} else {
    prev.next = next;
    x.prev = null;
}

if (next == null) {
    last = prev;
} else {
    next.prev = prev;
    x.next = null;
}

x.item = null;
size--;
modCount++;
return element;

} ```

remove(int index)通過node方法找到需要刪除的節點,然後調用unlink方法改變刪除節點的prev和next節點的前繼和後繼節點。

剩下的方法可以自己閲讀源碼。

RandomAccess接口

RandomAccess接口是一個空接口,不包含任何方法,只是作為一個標識:

```java package java.util;

public interface RandomAccess {} ```

實現該接口的類説明其支持快速隨機訪問,比如ArrayList實現了該接口,説明ArrayList支持快速隨機訪問。所謂快速隨機訪問指的是通過元素的下標即可快速獲取元素對象,無需遍歷,而LinkedList則沒有這個特性,元素獲取必須遍歷鏈表。

在Collections類的binarySearch(List<? extends Comparable<? super T>> list, T key)方法中,可以看到RandomAccess的應用:

java public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) { if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD) return Collections.indexedBinarySearch(list, key); else return Collections.iteratorBinarySearch(list, key); }

當list實現了RandomAccess接口時,調用indexedBinarySearch方法,否則調用iteratorBinarySearch。所以當我們遍歷集合時,如果集合實現了RandomAccess接口,優先選擇普通for循環,其次foreach;遍歷未實現RandomAccess的接口,優先選擇iterator遍歷。