Java集合之LinkedList源碼解析

更新時(shí)間：2023年12月19日 09:35:50 作者：初念初戀

這篇文章主要介紹了Java集合之LinkedList源碼解析,LinkedList和ArrayList數(shù)據(jù)結(jié)構(gòu)是完全不一樣的,ArrayList 底層是數(shù)組的結(jié)構(gòu),而 LinkedList 的底層則是鏈表的結(jié)構(gòu), 它可以進(jìn)行高效的插入和移除的操作,它基于的是一個(gè)雙向鏈表的結(jié)構(gòu),需要的朋友可以參考下

簡介

本章我們來聊聊LinkedList的使用及源碼，LinkedList和ArrayList數(shù)據(jù)結(jié)構(gòu)是完全不一樣的，

ArrayList 底層是數(shù)組的結(jié)構(gòu)，而 LinkedList 的底層則是鏈表的結(jié)構(gòu)，它可以進(jìn)行高效的插入和移除的操作，它基于的是一個(gè)雙向鏈表的結(jié)構(gòu)。

LinkedList的整體結(jié)構(gòu)圖

從圖中也能看出，LinkedList 有好多的Node，并且還有first和last這兩個(gè)變量保存頭部和尾部節(jié)點(diǎn)的信息；還有就是它不是一個(gè)循環(huán)的雙向鏈表，因?yàn)樗昂蠖际莕ull，這個(gè)也是我們需要注意的地方。

繼承體系

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{...}

通過繼承體系，我們可以看到 LinkedList 不僅實(shí)現(xiàn)了List接口，還實(shí)現(xiàn)了Queue和Deque接口，所以它既能作為 List 使用，也能作為雙端隊(duì)列使用，當(dāng)然也可以作為棧使用。

源碼分析

主要屬性

// 元素個(gè)數(shù)
transient int size = 0;
// 鏈表首節(jié)點(diǎn)
transient Node<E> first;
// 鏈表尾節(jié)點(diǎn)
transient Node<E> last;

Node節(jié)點(diǎn)

private static class Node<E> {
    //值
    E item;
    //后繼 指向下一個(gè)的引用
    Node<E> next;
    //前驅(qū) 指向前一個(gè)的引用
    Node<E> prev;
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

構(gòu)造方法

public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
    this();
    //將集合C中的所有的元素都插入到鏈表中
    addAll(c);
}

添加元素

作為一個(gè)雙端隊(duì)列，添加元素主要有兩種，一種是在隊(duì)列尾部添加元素，一種是在隊(duì)列首部添加元素，這兩種形式在LinkedList中主要是通過下面兩個(gè)方法來實(shí)現(xiàn)的。

// 從隊(duì)列首添加元素
private void linkFirst(E e) {
    // 首節(jié)點(diǎn)
    final Node<E> f = first;
    // 創(chuàng)建新節(jié)點(diǎn)，新節(jié)點(diǎn)的next是首節(jié)點(diǎn)
    final Node<E> newNode = new Node<>(null, e, f);
    // 讓新節(jié)點(diǎn)作為新的首節(jié)點(diǎn)
    first = newNode;
    // 判斷是不是第一個(gè)添加的元素
    // 如果是就把last也置為新節(jié)點(diǎn)
    // 否則把原首節(jié)點(diǎn)的prev指針置為新節(jié)點(diǎn)
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    // 元素個(gè)數(shù)加1
    size++;
    // 修改次數(shù)加1，說明這是一個(gè)支持fail-fast的集合
    modCount++;
}
// 從隊(duì)列尾添加元素
void linkLast(E e) {
    // 隊(duì)列尾節(jié)點(diǎn)
    final Node<E> l = last;
    // 創(chuàng)建新節(jié)點(diǎn)，新節(jié)點(diǎn)的prev是尾節(jié)點(diǎn)
    final Node<E> newNode = new Node<>(l, e, null);
    // 讓新節(jié)點(diǎn)成為新的尾節(jié)點(diǎn)
    last = newNode;
    // 判斷是不是第一個(gè)添加的元素
    // 如果是就把first也置為新節(jié)點(diǎn)
    // 否則把原尾節(jié)點(diǎn)的next指針置為新節(jié)點(diǎn)
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    // 元素個(gè)數(shù)加1
    size++;
    // 修改次數(shù)加1
    modCount++;
}
public void addFirst(E e) {
    linkFirst(e);
}
public void addLast(E e) {
    linkLast(e);
}
// 作為無界隊(duì)列，添加元素總是會(huì)成功的
public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}
public boolean offerLast(E e) {
    addLast(e);
    return true;
}

上面是作為雙端隊(duì)列來看，它的添加元素分為首尾添加元素，作為List，是要支持在中間添加元素的，主要是通過下面這個(gè)方法實(shí)現(xiàn)的。

// 在節(jié)點(diǎn)succ之前添加元素
void linkBefore(E e, Node<E> succ) {
    // succ是待添加節(jié)點(diǎn)的后繼節(jié)點(diǎn)
    // 找到待添加節(jié)點(diǎn)的前置節(jié)點(diǎn)
    final Node<E> pred = succ.prev;
    // 在其前置節(jié)點(diǎn)和后繼節(jié)點(diǎn)之間創(chuàng)建一個(gè)新節(jié)點(diǎn)
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 修改后繼節(jié)點(diǎn)的前置指針指向新節(jié)點(diǎn)
    succ.prev = newNode;
    // 判斷前置節(jié)點(diǎn)是否為空
    // 如果為空，說明是第一個(gè)添加的元素，修改first指針
    // 否則修改前置節(jié)點(diǎn)的next為新節(jié)點(diǎn)
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    // 修改元素個(gè)數(shù)
    size++;
    // 修改次數(shù)加1
    modCount++;
}
// 尋找index位置的節(jié)點(diǎn)
Node<E> node(int index) {
    // 因?yàn)槭请p鏈表
    // 所以根據(jù)index是在前半段還是后半段決定從前遍歷還是從后遍歷
    // 這樣index在后半段的時(shí)候可以少遍歷一半的元素
    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;
    }
}
// 在指定index位置處添加元素
public void add(int index, E element) {
    // 判斷是否越界
    checkPositionIndex(index);
    // 如果index是在隊(duì)列尾節(jié)點(diǎn)之后的一個(gè)位置
    // 把新節(jié)點(diǎn)直接添加到尾節(jié)點(diǎn)之后
    // 否則調(diào)用linkBefore()方法在中間添加節(jié)點(diǎn)
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

在中間添加元素的方法也很簡單，典型的雙鏈表在中間添加元素的方法。

添加元素的三種方式大致如下圖所示：

qrcode

在隊(duì)列首尾添加元素很高效，時(shí)間復(fù)雜度為O(1)。

在中間添加元素比較低效，首先要先找到插入位置的節(jié)點(diǎn)，再修改前后節(jié)點(diǎn)的指針，時(shí)間復(fù)雜度為O(n)。

刪除元素

作為雙端隊(duì)列，刪除元素也有兩種方式，一種是隊(duì)列首刪除元素，一種是隊(duì)列尾刪除元素。

作為List，又要支持中間刪除元素，所以刪除元素一個(gè)有三個(gè)方法，分別如下。

// 刪除首節(jié)點(diǎn)
private E unlinkFirst(Node<E> f) {
    // 首節(jié)點(diǎn)的元素值
    final E element = f.item;
    // 首節(jié)點(diǎn)的next指針
    final Node<E> next = f.next;
    // 添加首節(jié)點(diǎn)的內(nèi)容，協(xié)助GC
    f.item = null;
    f.next = null; // help GC
    // 把首節(jié)點(diǎn)的next作為新的首節(jié)點(diǎn)
    first = next;
    // 如果只有一個(gè)元素，刪除了，把last也置為空
    // 否則把next的前置指針置為空
    if (next == null)
        last = null;
    else
        next.prev = null;
    // 元素個(gè)數(shù)減1
    size--;
    // 修改次數(shù)加1
    modCount++;
    // 返回刪除的元素
    return element;
}
// 刪除尾節(jié)點(diǎn)
private E unlinkLast(Node<E> l) {
    // 尾節(jié)點(diǎn)的元素值
    final E element = l.item;
    // 尾節(jié)點(diǎn)的前置指針
    final Node<E> prev = l.prev;
    // 清空尾節(jié)點(diǎn)的內(nèi)容，協(xié)助GC
    l.item = null;
    l.prev = null; // help GC
    // 讓前置節(jié)點(diǎn)成為新的尾節(jié)點(diǎn)
    last = prev;
    // 如果只有一個(gè)元素，刪除了把first置為空
    // 否則把前置節(jié)點(diǎn)的next置為空
    if (prev == null)
        first = null;
    else
        prev.next = null;
    // 元素個(gè)數(shù)減1
    size--;
    // 修改次數(shù)加1
    modCount++;
    // 返回刪除的元素
    return element;
}
// 刪除指定節(jié)點(diǎn)x
E unlink(Node<E> x) {
    // x的元素值
    final E element = x.item;
    // x的前置節(jié)點(diǎn)
    final Node<E> next = x.next;
    // x的后置節(jié)點(diǎn)
    final Node<E> prev = x.prev;
    // 如果前置節(jié)點(diǎn)為空
    // 說明是首節(jié)點(diǎn)，讓first指向x的后置節(jié)點(diǎn)
    // 否則修改前置節(jié)點(diǎn)的next為x的后置節(jié)點(diǎn)
    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }
    // 如果后置節(jié)點(diǎn)為空
    // 說明是尾節(jié)點(diǎn)，讓last指向x的前置節(jié)點(diǎn)
    // 否則修改后置節(jié)點(diǎn)的prev為x的前置節(jié)點(diǎn)
    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }
    // 清空x的元素值，協(xié)助GC
    x.item = null;
    // 元素個(gè)數(shù)減1
    size--;
    // 修改次數(shù)加1
    modCount++;
    // 返回刪除的元素
    return element;
}
// remove的時(shí)候如果沒有元素拋出異常
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}
// remove的時(shí)候如果沒有元素拋出異常
public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}
// poll的時(shí)候如果沒有元素返回null
public E pollFirst() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}
// poll的時(shí)候如果沒有元素返回null
public E pollLast() {
    final Node<E> l = last;
    return (l == null) ? null : unlinkLast(l);
}
// 刪除中間節(jié)點(diǎn)
public E remove(int index) {
    // 檢查是否越界
    checkElementIndex(index);
    // 刪除指定index位置的節(jié)點(diǎn)
    return unlink(node(index));
}

刪除元素的三種方法都是典型的雙鏈表刪除元素的方法，大致流程如下圖所示。

qrcode

在隊(duì)列首尾刪除元素很高效，時(shí)間復(fù)雜度為O(1)。

在中間刪除元素比較低效，首先要找到刪除位置的節(jié)點(diǎn)，再修改前后指針，時(shí)間復(fù)雜度為O(n)。

棧

前面我們說了，LinkedList是雙端隊(duì)列，還記得雙端隊(duì)列可以作為棧使用嗎？

/**
 * 利用LinkedList來模擬棧
 * 棧的特點(diǎn)：先進(jìn)后出
 */
public class Test {
    private LinkedList<String> linkList = new LinkedList<String>();
    // 壓棧
    public void push(String str){
        linkList.addFirst(str);
    }
    // 出棧
    public String pop(){
        return linkList.removeFirst();
    }
    // 查看
    public String peek(){
        return linkList.peek();
    }
    // 判斷是否為空
    public boolean isEmpty(){
        return linkList.isEmpty();
    }
}
class Test1 {
    public static void main(String[] args) {
        // 測試棧
        Test test = new Test();
        test.push("我是第1個(gè)進(jìn)去的");
        test.push("我是第2個(gè)進(jìn)去的");
        test.push("我是第3個(gè)進(jìn)去的");
        test.push("我是第4個(gè)進(jìn)去的");
        test.push("我是第5個(gè)進(jìn)去的");
        // 取出
        while (!test.isEmpty()){
            String pop = test.pop();
            System.out.println(pop);
        }
        // 打印結(jié)果
        /*我是第5個(gè)進(jìn)去的
        我是第4個(gè)進(jìn)去的
        我是第3個(gè)進(jìn)去的
        我是第2個(gè)進(jìn)去的
        我是第1個(gè)進(jìn)去的*/
    }
}

棧的特性是LIFO(Last In First Out)，所以作為棧使用也很簡單，添加刪除元素都只操作隊(duì)列首節(jié)點(diǎn)即可。

總結(jié)

（1）LinkedList是一個(gè)以雙鏈表實(shí)現(xiàn)的List，因此不存在容量不足的問題，所以沒有擴(kuò)容的方法。

（2）LinkedList還是一個(gè)雙端隊(duì)列，具有隊(duì)列、雙端隊(duì)列、棧的特性。

（3）LinkedList在隊(duì)列首尾添加、刪除元素非常高效，時(shí)間復(fù)雜度為O(1)。

（4）LinkedList在中間添加、刪除元素比較低效，時(shí)間復(fù)雜度為O(n)。

（5）LinkedList不支持隨機(jī)訪問，所以訪問非隊(duì)列首尾的元素比較低效。

（6）LinkedList在功能上等于ArrayList + ArrayDeque。

（7）LinkedList是非線程安全的。

（8）LinkedList能存儲(chǔ)null值。

經(jīng)典面試題

談?wù)凙rrayList和LinkedList的區(qū)別。

可以分兩部分答：一個(gè)是數(shù)組與鏈表底層實(shí)現(xiàn)的不同，另一個(gè)是答ArrayList和LinkedList的實(shí)現(xiàn)細(xì)節(jié)。

ArrayList的底層是數(shù)組，LinkedList的底層是雙向鏈表。
數(shù)組擁有O(1)的查詢效率，可以通過下標(biāo)直接定位元素；鏈表在查詢?cè)氐臅r(shí)候只能通過遍歷的方式查詢，效率比數(shù)組低。
數(shù)組增刪元素的效率比較低，通常要伴隨拷貝數(shù)組的操作；鏈表增刪元素的效率很高，只需要調(diào)整對(duì)應(yīng)位置的指針即可。

以上是數(shù)組和鏈表的通俗對(duì)比，在日常的使用中，兩者都能很好地在自己的適用場景發(fā)揮作用。

我們常常用ArrayList代替數(shù)組，因?yàn)榉庋b了許多易用的api，而且它內(nèi)部實(shí)現(xiàn)了自動(dòng)擴(kuò)容機(jī)制，由于它內(nèi)部維護(hù)了一個(gè)當(dāng)前容量的指針size，直接往ArrayList中添加元素的時(shí)間復(fù)雜度是O(1)的，使用非常方便。而LinkedList常常被用作Queue隊(duì)列的實(shí)現(xiàn)類，由于底層是雙向鏈表，能夠輕松地提供先入先出的操作。

到此這篇關(guān)于Java集合之LinkedList源碼解析的文章就介紹到這了,更多相關(guān)LinkedList源碼解析內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: