如何理解LinkedList源碼

本篇內(nèi)容主要講解“如何理解LinkedList源碼”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“如何理解LinkedList源碼”吧!

LinkedList類圖如下：

LinkedList底層是由雙向鏈表實(shí)現(xiàn)的。鏈表好比火車，每節(jié)車廂包含了車廂和連接下一節(jié)車廂的連接點(diǎn)。而雙向鏈表的每個(gè)節(jié)點(diǎn)不僅有指向下一個(gè)節(jié)點(diǎn)的指針，還有指向上一個(gè)節(jié)點(diǎn)的指針。 在LinkedList源碼中有一個(gè)Node靜態(tài)類，源碼如下：

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;
    }
}

一個(gè)Node節(jié)點(diǎn)包含三個(gè)部分，分別是

• item：數(shù)據(jù)

• next：下一個(gè)節(jié)點(diǎn)的指針

• prev：上一個(gè)節(jié)點(diǎn)的指針

LinkedList的主要變量如下：

// 集合中的元素?cái)?shù)量
transient int size = 0;

/**
  * 首節(jié)點(diǎn)的指針.
  * Invariant: (first == null && last == null) ||
  *            (first.prev == null && first.item != null)
  */
transient Node<E> first;

/**
  * 尾結(jié)點(diǎn)的指針.
  * Invariant: (first == null && last == null) ||
  *            (last.next == null && last.item != null)
  */
transient Node<E> last;

一 添加元素

LinkedList支持想任意節(jié)點(diǎn)位置添加元素，不僅提供了集合常用的add()方法，還提供了addFirst()和addLast()，add()方法默認(rèn)調(diào)用addLast()方法，也就是默認(rèn)是往鏈表尾部插入元素的。

add()方法源碼：

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

1.1 尾部插入元素

linkLast()源碼如下：

void linkLast(E e) {
    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++;
}

我們來畫張圖演示一下如何給鏈表尾部插入元素：

假如鏈表中沒有元素

對應(yīng)源碼中的if語句，如果沒有元素則新增的這個(gè)節(jié)點(diǎn)為鏈表中唯一的一個(gè)元素，既是首節(jié)點(diǎn)，又是尾結(jié)點(diǎn)，前一個(gè)元素的指針和后一個(gè)元素的指針都是null。這里注意head節(jié)點(diǎn)不是第一個(gè)節(jié)點(diǎn)，head節(jié)點(diǎn)只是標(biāo)識了這個(gè)鏈表的地址。

假如鏈表中有元素

對應(yīng)源碼中else語句。先將新增的元素當(dāng)成Last節(jié)點(diǎn)，然后將原來的Last節(jié)點(diǎn)的next指向新節(jié)點(diǎn)。

else
    l.next = newNode;

一圖勝前言，畫個(gè)圖是不是什么都明白了。

1.2 頭部插入元素

linkFirst()源碼如下：

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++;
}

還是根據(jù)上面的圖來解讀一下源碼，先將第一個(gè)節(jié)點(diǎn)賦值給中間變量f，將新節(jié)點(diǎn)newNode賦值給first節(jié)點(diǎn)。如果鏈表沒有元素，則Last節(jié)點(diǎn)和First節(jié)點(diǎn)都是新插入的節(jié)點(diǎn)newNode，否則，將原來的First節(jié)點(diǎn)的頭指針指向新節(jié)點(diǎn)。

二 刪除元素

LinkedList提供的刪除方法有根據(jù)索引和元素刪除，除此之外還提供刪除第一個(gè)元素和最后一個(gè)元素的方法，這里我們只分析一下根據(jù)索引刪除的方法。

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

checkElementIndex(index)方法就是用來判斷傳輸?shù)乃饕凳欠窈戏?，不合法則拋出數(shù)組越界異常。重點(diǎn)來看一下unlink(node(index))方法是如何刪除元素的。

node(index)方法源碼：

node(index)方法就是根據(jù)索引獲取該索引位置的節(jié)點(diǎn)

Node<E> node(int index) {
    // assert isElementIndex(index);
    // 如果指定下標(biāo) < 一半元素?cái)?shù)量，則從首結(jié)點(diǎn)開始遍歷
    // 否則，從尾結(jié)點(diǎn)開始遍歷
    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;
    }
}

unlink(Node<E> x)源碼如下：

E unlink(Node<E> x) {
    // assert x != null;
    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;
}

畫張圖分析一下刪除是如何進(jìn)行的：

1. 假設(shè)刪除的是第一個(gè)元素：則它的prev==NULL，我們需要將他的后一個(gè)元素（圖中的second）作為第一個(gè)元素

2. 假設(shè)刪除的是最后一個(gè)元素，則它的next==null，我們需要將他的前一個(gè)元素（途中的second）作為最后一個(gè)元素

3. 如果是中間的任意元素，則需要將它的前一個(gè)元素的next指針指向它的后一個(gè)元素，同時(shí)將它的后一個(gè)元素的prev指針指向它的前一個(gè)元素。

到此，相信大家對“如何理解LinkedList源碼”有了更深的了解，不妨來實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！