問(wèn)題

（1）LinkedList只是一個(gè)List嗎？

成都創(chuàng)新互聯(lián)是一家專業(yè)從事成都網(wǎng)站建設(shè)、成都網(wǎng)站制作的網(wǎng)絡(luò)公司。作為專業(yè)網(wǎng)站制作公司,成都創(chuàng)新互聯(lián)依托的技術(shù)實(shí)力、以及多年的網(wǎng)站運(yùn)營(yíng)經(jīng)驗(yàn),為您提供專業(yè)的成都網(wǎng)站建設(shè)、營(yíng)銷型網(wǎng)站建設(shè)及網(wǎng)站設(shè)計(jì)開發(fā)服務(wù)！

（2）LinkedList還有其它什么特性嗎？

（3）LinkedList為啥經(jīng)常拿出來(lái)跟ArrayList比較？

（4）我為什么把LinkedList放在最后一章來(lái)講？

簡(jiǎn)介

LinkedList是一個(gè)以雙向鏈表實(shí)現(xiàn)的List，它除了作為L(zhǎng)ist使用，還可以作為隊(duì)列或者棧來(lái)使用，它是怎么實(shí)現(xiàn)的呢？讓我們一起來(lái)學(xué)習(xí)吧。

繼承體系

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

源碼分析

主要屬性

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

屬性很簡(jiǎn)單，定義了元素個(gè)數(shù)size和鏈表的首尾節(jié)點(diǎn)。

主要內(nèi)部類

典型的雙鏈表結(jié)構(gòu)。

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òu)造方法

public LinkedList() {
}

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

兩個(gè)構(gòu)造方法也很簡(jiǎn)單，可以看出是一個(gè)×××的隊(duì)列。

添加元素

作為一個(gè)雙端隊(duì)列，添加元素主要有兩種，一種是在隊(duì)列尾部添加元素，一種是在隊(duì)列首部添加元素，這兩種形式在LinkedList中主要是通過(guò)下面兩個(gè)方法來(lái)實(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，說(shuō)明這是一個(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;
}

典型的雙鏈表在首尾添加元素的方法，代碼比較簡(jiǎn)單，這里不作詳細(xì)描述了。

上面是作為雙端隊(duì)列來(lái)看，它的添加元素分為首尾添加元素，那么，作為L(zhǎng)ist呢？

作為L(zhǎng)ist，是要支持在中間添加元素的，主要是通過(guò)下面這個(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)是否為空
    // 如果為空，說(shuō)明是第一個(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));
}

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

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

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

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

刪除元素

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

作為L(zhǎng)ist，又要支持中間刪除元素，所以刪除元素一個(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)為空
    // 說(shuō)明是首節(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)為空
    // 說(shuō)明是尾節(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));
}

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

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

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

棧

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

public void push(E e) {
    addFirst(e);
}

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

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

總結(jié)

（1）LinkedList是一個(gè)以雙鏈表實(shí)現(xiàn)的List；

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

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

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

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

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

彩蛋

java集合部分的源碼分析全部完結(jié)，整個(gè)專題以ArrayList開頭，以LinkedList結(jié)尾，我覺得非常合適，因?yàn)锳rrayList代表了List的典型實(shí)現(xiàn)，LInkedList代表了Deque的典型實(shí)現(xiàn)，同時(shí)LinkedList也實(shí)現(xiàn)了List，通過(guò)這兩個(gè)類一首一尾正好可以把整個(gè)集合貫穿起來(lái)。

還記得我們一共分析了哪些類嗎？

下一章，筆者將對(duì)整個(gè)java集合做一個(gè)總結(jié)，并提出一些閱讀源碼過(guò)程中的問(wèn)題，敬請(qǐng)期待^^

---

歡迎關(guān)注我的公眾號(hào)“彤哥讀源碼”，查看更多源碼系列文章, 與彤哥一起暢游源碼的海洋。

網(wǎng)站名稱：死磕java集合之LinkedList源碼分析
網(wǎng)站路徑：http://jinyejixie.com/article6/jjhhig.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供商城網(wǎng)站、服務(wù)器托管、微信公眾號(hào)、品牌網(wǎng)站設(shè)計(jì)、營(yíng)銷型網(wǎng)站建設(shè)、全網(wǎng)營(yíng)銷推廣

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)