博客 / 詳情

返回

Java LinkedList 簡單源碼分析節選

寫在最前面

這個項目是從20年末就立好的 flag，經過幾年的學習，回過頭再去看很多知識點又有新的理解。所以趁着找實習的準備，結合以前的學習儲備，創建一個主要針對應屆生和初學者的 Java 開源知識項目，專注 Java 後端面試題 + 解析 + 重點知識詳解 + 精選文章的開源項目，希望它能伴隨你我一直進步！

説明：此項目內容參考了諸多博主（已註明出處），資料，N本書籍，以及結合自己理解，重新繪圖，重新組織語言等等所制。個人之力綿薄，或有不足之處，在所難免，但更新/完善會一直進行。大家的每一個 Star 都是對我的鼓勵 ！希望大家能喜歡。

注：所有涉及圖片未使用網絡圖牀，文章等均開源提供給大家。

項目名: Java-Ideal-Interview

Github 地址： Java-Ideal-Interview - Github

Gitee 地址：Java-Ideal-Interview - Gitee（碼雲）

持續更新中，在線閲讀將會在後期提供，若認為 Gitee 或 Github 閲讀不便，可克隆到本地配合 Typora 等編輯器舒適閲讀

若 Github 克隆速度過慢，可選擇使用國內 Gitee 倉庫

  • LinkedList 源碼分析

    • 1. LinkedList 概述

      • 1.1 List 是什麼？
      • 1.2 LinkedList 是什麼？

    • 2. 源碼分析

      • 2.1 類聲明
      • 2.2 成員
      • 2.3 內部私有類 Node 類
      • 2.4 構造方法

      • 2.5 添加方法

        • 2.5.1 add(E e)
        • 2.5.2 add(int index, E element)
        • 2.5.3 addLast(E e)
        • 2.5.4 addFirst(E e)
        • 2.5.5 addAll(Collection c )

      • 2.6 獲取方法

        • 2.6.1 get(int index)
        • 2.6.2 獲取頭結點方法
        • 2.6.3 獲取尾節點方法

        • 2.6.4 根據對象得到索引

          • 2.6.4.1 從頭到尾找
          • 2.6.4.1 從尾到頭找
        • 2.6.5 contains(Object o)

      • 2.7 刪除方法

        • 2.7.1 remove(int index)
        • 2.7.2 remove(Object o)
        • 2.7.3 刪除頭結點

LinkedList 源碼分析

1. LinkedList 概述

1.1 List 是什麼？

List 在 Collection中充當着一個什麼樣的身份呢？——有序的 collection(也稱為序列)

實現這個接口的用户以對列表中每個元素的插入位置進行精確地控制。用户可以根據元素的整數索引（在列表中的位置）訪問元素，並搜索列表中的元素。與 set 不同，列表通常允許重複的元素。

1.2 LinkedList 是什麼？

LinkedList 的本質就是一個雙向鏈表，但是它也可以被當做堆棧、隊列或雙端隊列進行操作。

其特點為：查詢慢，增刪快，線程不安全，效率高。

2. 源碼分析

2.1 類聲明

先來看一下類的聲明，有一個繼承（抽象類）和四個接口關係

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{ 
    // 源碼具體內容... 
}
  • Deque<E> 它實現了Deque接口，使得 LinkedList 類也具有隊列的特性
  • Cloneable ：實現它就可以進行克隆（clone()）
  • java.io.Serializable ：實現它意味着支持序列化，滿足了序列化傳輸的條件

2.2 成員

// 集合的長度
transient int size = 0;

// 雙向鏈表頭部節點
transient Node<E> first;

// 雙向鏈表尾部節點
transient Node<E> last;

2.3 內部私有類 Node 類

從源碼剛開始就提到了 transient Node<E> first; 等內容，這裏就涉及到一個內部私有的類，即 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;
    }
}

2.4 構造方法

/**
 * 無參構造
 */
public LinkedList() {
}

/**
 * 帶參構造，創建一個包含集合 c 的 LinkedList
 */
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

2.5 添加方法

2.5.1 add(E e)
public boolean add(E e) {
    linkLast(e);
    return true;
}

直接跳轉到 linkLast 方法中

/**
 * 鏈接使 e 作為最後一個元素
 */
void linkLast(E e) {
    // 拿到當前的尾部節點 last
    final Node<E> l = last;
    // new 一個節點出來，通過帶參構造賦值，達到添加到尾部的效果
    final Node<E> newNode = new Node<>(l, e, null);
    // 此時不管這個鏈表只有一個還是多個元素它都是尾部節點
    last = newNode;
    // 根據判斷做出不同的操作
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

不同情況的討論

  • 當前鏈表為空，添加進來的 node 節點自然就是 first，也是 last，也正因為這一點，在滴啊參構造函數賦值的時候，就已經確定了其 prev 和 next 都為 null
  • 當前鏈表不為空，那麼添加進來的 node 節點就是 last ，node 的 prev 指向以前的最後一個元素（舊的 last），node 的 next，自然也是 null
2.5.2 add(int index, E element)
/**
 * 在指定 index 位置添加元素
 */
public void add(int index, E element) {
    // 跳轉，檢查索引是否處於[0-size]之間
    checkPositionIndex(index);
    // 指定下標在尾部，直接調用 linkLast 放在尾部
    if (index == 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;
    }
  • 調用 linkBefore(element, node(index))方法中，需要調用 node(int index) 通過傳入的 index 來定位到要插入的位置，這個是比較耗時間的
/**
 * 在一個非空節點前插入一個元素
 */
void linkBefore(E e, Node<E> succ) {
    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++;
}

其實這裏和前面 add 到末尾是沒什麼區別的，只是多了一個定位插入位置的過程。

2.5.3 addLast(E e)

不解釋了，和 add(E e) 是一樣的，將元素添加到鏈表尾部

public void addLast(E e) {
    linkLast(e);
}
2.5.4 addFirst(E e)
/**
 * 將元素添加到鏈表頭部
 */
private void linkFirst(E e) {
    // 拿到當前鏈表的頭部節點
    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++;
}

如果有了 add(E e) 的理解，就會發現這些都是一回事，這裏先拿到的是頭部節點，然後再帶參構造函數賦值的時候，以頭節點做為後繼節點

  • 如果鏈表為空，則頭尾部節點就都是這個新節點 newNode
  • 如果不為空，則將頭節點的前驅指針指向新節點，也就是指向前一個元素
2.5.5 addAll(Collection c )
/**
 * 將集合插入到鏈表尾部
 */
public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}

來直接跳轉到邏輯方法中去，addAll(int index, Collection c)

/**
 * 將集合從指定位置開始插入
 */
public boolean addAll(int index, Collection<? extends E> c) {
    // 跳轉，檢查索引是否處於[0-size]之間
    checkPositionIndex(index);
    
    // 把集合轉成數組
    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0)
        return false;
    
    // 獲取插入位置的前驅和後驅節點
    Node<E> pred, succ;
    // 如果插入位置為尾部。前驅結點自然是尾部節點，後繼沒有了就是 null
    if (index == size) {
        succ = null;
        pred = last;
    // 插入位置非尾部，則先通過 node 方法得到後繼節點，再拿到前驅結點
    } else {
        succ = node(index);
        pred = succ.prev;
    }
    
    // 遍歷插入數據
    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;
    }
    // 如果插入在尾部，重置一下 last 節點
    if (succ == null) {
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }

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

2.6 獲取方法

2.6.1 get(int index)
/**
 *  根據指定索引返回元素
 */
public E get(int index) {
    // 檢查index範圍是否在size之內
    checkElementIndex(index);
    // 通過 node 方法找到對應的節點然後返回它的值
    return node(index).item;
}


Node<E> node(int 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;
    }
}
2.6.2 獲取頭結點方法
public E getFirst() {
    final Node<E> f = first;
    // 為空拋異常
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

public E element() {
    // 為空拋異常
    return getFirst();
}

public E peek() {
    final Node<E> f = first;
    // 為空返回 null
    return (f == null) ? null : f.item;
}

public E peekFirst() {
    final Node<E> f = first;
    / 為空返回 null
    return (f == null) ? null : f.item;
}
2.6.3 獲取尾節點方法
public E getLast() {
    final Node<E> l = last;
    // 為空返回 null
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

public E peekLast() {
    final Node<E> l = last;
    // 為空返回 null
    return (l == null) ? null : l.item;
}
2.6.4 根據對象得到索引
2.6.4.1 從頭到尾找
public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        // 從 first 遍歷 -> next
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        // 從 first 遍歷 -> next
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}
2.6.4.1 從尾到頭找
public int lastIndexOf(Object o) {
    int index = size;
    if (o == null) {
        //從 last 遍歷 -> prev
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (x.item == null)
                return index;
        }
    } else {
        //從 last 遍歷 -> prev
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (o.equals(x.item))
                return index;
        }
    }
    return -1;
}
2.6.5 contains(Object o)
/**
 *  檢查對象 o 是否存在於此鏈表中
 */
public boolean contains(Object o) {
    return indexOf(o) != -1;
}

2.7 刪除方法

2.7.1 remove(int index)
/**
 *  刪除指定下標元素
 */
public E remove(int index) {
    // 檢查index範圍
    checkElementIndex(index);
    // 先用 node 找到節點，然後將節點刪除
    return unlink(node(index));
}
2.7.2 remove(Object o)
/**
 *  刪除指定元素
 */
public boolean remove(Object o) {
    // 如果為null
    if (o == null) {
        //從 first 開始遍歷
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                // 從鏈表中移除找到的元素
                unlink(x);
                return true;
            }
        }
    } else {
        // 從 first 開始遍歷
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                // 從鏈表中移除找到的元素
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

其中調用了 unlink(Node<E> x) 方法，來看一下

E unlink(Node<E> x) {
    final E element = x.item;
    // 得到後繼節點
    final Node<E> next = x.next;
    // 得到前驅節點
    final Node<E> 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;
}
2.7.3 刪除頭結點

幾個方法套娃，最後都是調用的 unlinkFirst() 方法

public E pop() {
    return removeFirst();
}

public E remove() {
    return removeFirst();
}

public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    // 取出頭結點中的值，用於方法返回
    final E element = f.item;
    // 取出頭結點的下一個節點的引用並賦予變量next
    final Node<E> next = f.next;
    // 將頭結點的item以及next屬性設為null，幫助垃圾回收
    f.item = null;
    f.next = null; // help GC
    // 將next賦予first（將原先節點下一個節點變為頭結點）
    first = next;
    // 判斷next是否為空，如果為空，則説明原先集合中只有一個元素，需要將last設置為null
    if (next == null)
        last = null;
    else
        // 如果next不為空，則將next的prev設置為null（因為prev指向原先的頭結點，頭節點的prev值肯定為null）
        next.prev = null;
    size--;
    modCount++;
    return element;
}
2.7.4 刪除尾結點
public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

public E pollLast() {
    final Node<E> l = last;
    return (l == null) ? null : unlinkLast(l);
}

// 與上面 unlinkFirst 同理
private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    final E element = l.item;
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null; // help GC
    last = prev;
    if (prev == null)
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}
java-se
user avatar
0 位用戶收藏了這個故事！

發佈 評論

Some HTML is okay.