問題

（1）LinkedList只是一個List嗎？

創(chuàng)新互聯(lián)公司服務項目包括鄂溫克網(wǎng)站建設、鄂溫克網(wǎng)站制作、鄂溫克網(wǎng)頁制作以及鄂溫克網(wǎng)絡營銷策劃等。多年來，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢、行業(yè)經(jīng)驗、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，鄂溫克網(wǎng)站推廣取得了明顯的社會效益與經(jīng)濟效益。目前，我們服務的客戶以成都為中心已經(jīng)輻射到鄂溫克省份的部分城市，未來相信會繼續(xù)擴大服務區(qū)域并繼續(xù)獲得客戶的支持與信任！

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

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

（4）我為什么把LinkedList放在最后一章來講？

簡介

LinkedList是一個以雙向鏈表實現(xiàn)的List，它除了作為List使用，還可以作為隊列或者棧來使用，它是怎么實現(xiàn)的呢？讓我們一起來學習吧。

繼承體系

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

源碼分析

主要屬性

// 元素個數(shù)
transient int size = 0;
// 鏈表首節(jié)點
transient Node first;
// 鏈表尾節(jié)點
transient Node last;

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

主要內(nèi)部類

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

private static class Node {
    E item;
    Node next;
    Node prev;

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

主要構(gòu)造方法

public LinkedList() {
}

public LinkedList(Collection c) {
    this();
    addAll(c);
}

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

添加元素

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

// 從隊列首添加元素
private void linkFirst(E e) {
    // 首節(jié)點
    final Node f = first;
    // 創(chuàng)建新節(jié)點，新節(jié)點的next是首節(jié)點
    final Node newNode = new Node<>(null, e, f);
    // 讓新節(jié)點作為新的首節(jié)點
    first = newNode;
    // 判斷是不是第一個添加的元素
    // 如果是就把last也置為新節(jié)點
    // 否則把原首節(jié)點的prev指針置為新節(jié)點
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    // 元素個數(shù)加1
    size++;
    // 修改次數(shù)加1，說明這是一個支持fail-fast的集合
    modCount++;
}

// 從隊列尾添加元素
void linkLast(E e) {
    // 隊列尾節(jié)點
    final Node l = last;
    // 創(chuàng)建新節(jié)點，新節(jié)點的prev是尾節(jié)點
    final Node newNode = new Node<>(l, e, null);
    // 讓新節(jié)點成為新的尾節(jié)點
    last = newNode;
    // 判斷是不是第一個添加的元素
    // 如果是就把first也置為新節(jié)點
    // 否則把原尾節(jié)點的next指針置為新節(jié)點
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    // 元素個數(shù)加1
    size++;
    // 修改次數(shù)加1
    modCount++;
}

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

public void addLast(E e) {
    linkLast(e);
}

// 作為×××隊列，添加元素總是會成功的
public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}

public boolean offerLast(E e) {
    addLast(e);
    return true;
}

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

上面是作為雙端隊列來看，它的添加元素分為首尾添加元素，那么，作為List呢？

作為List，是要支持在中間添加元素的，主要是通過下面這個方法實現(xiàn)的。

// 在節(jié)點succ之前添加元素
void linkBefore(E e, Node succ) {
    // succ是待添加節(jié)點的后繼節(jié)點
    // 找到待添加節(jié)點的前置節(jié)點
    final Node pred = succ.prev;
    // 在其前置節(jié)點和后繼節(jié)點之間創(chuàng)建一個新節(jié)點
    final Node newNode = new Node<>(pred, e, succ);
    // 修改后繼節(jié)點的前置指針指向新節(jié)點
    succ.prev = newNode;
    // 判斷前置節(jié)點是否為空
    // 如果為空，說明是第一個添加的元素，修改first指針
    // 否則修改前置節(jié)點的next為新節(jié)點
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    // 修改元素個數(shù)
    size++;
    // 修改次數(shù)加1
    modCount++;
}

// 尋找index位置的節(jié)點
Node node(int index) {
    // 因為是雙鏈表
    // 所以根據(jù)index是在前半段還是后半段決定從前遍歷還是從后遍歷
    // 這樣index在后半段的時候可以少遍歷一半的元素
    if (index < (size >> 1)) {
        // 如果是在前半段
        // 就從前遍歷
        Node x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        // 如果是在后半段
        // 就從后遍歷
        Node 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是在隊列尾節(jié)點之后的一個位置
    // 把新節(jié)點直接添加到尾節(jié)點之后
    // 否則調(diào)用linkBefore()方法在中間添加節(jié)點
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

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

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

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

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

刪除元素

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

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

// 刪除首節(jié)點
private E unlinkFirst(Node f) {
    // 首節(jié)點的元素值
    final E element = f.item;
    // 首節(jié)點的next指針
    final Node next = f.next;
    // 添加首節(jié)點的內(nèi)容，協(xié)助GC
    f.item = null;
    f.next = null; // help GC
    // 把首節(jié)點的next作為新的首節(jié)點
    first = next;
    // 如果只有一個元素，刪除了，把last也置為空
    // 否則把next的前置指針置為空
    if (next == null)
        last = null;
    else
        next.prev = null;
    // 元素個數(shù)減1
    size--;
    // 修改次數(shù)加1
    modCount++;
    // 返回刪除的元素
    return element;
}
// 刪除尾節(jié)點
private E unlinkLast(Node l) {
    // 尾節(jié)點的元素值
    final E element = l.item;
    // 尾節(jié)點的前置指針
    final Node prev = l.prev;
    // 清空尾節(jié)點的內(nèi)容，協(xié)助GC
    l.item = null;
    l.prev = null; // help GC
    // 讓前置節(jié)點成為新的尾節(jié)點
    last = prev;
    // 如果只有一個元素，刪除了把first置為空
    // 否則把前置節(jié)點的next置為空
    if (prev == null)
        first = null;
    else
        prev.next = null;
    // 元素個數(shù)減1
    size--;
    // 修改次數(shù)加1
    modCount++;
    // 返回刪除的元素
    return element;
}
// 刪除指定節(jié)點x
E unlink(Node x) {
    // x的元素值
    final E element = x.item;
    // x的前置節(jié)點
    final Node next = x.next;
    // x的后置節(jié)點
    final Node prev = x.prev;

    // 如果前置節(jié)點為空
    // 說明是首節(jié)點，讓first指向x的后置節(jié)點
    // 否則修改前置節(jié)點的next為x的后置節(jié)點
    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    // 如果后置節(jié)點為空
    // 說明是尾節(jié)點，讓last指向x的前置節(jié)點
    // 否則修改后置節(jié)點的prev為x的前置節(jié)點
    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    // 清空x的元素值，協(xié)助GC
    x.item = null;
    // 元素個數(shù)減1
    size--;
    // 修改次數(shù)加1
    modCount++;
    // 返回刪除的元素
    return element;
}
// remove的時候如果沒有元素拋出異常
public E removeFirst() {
    final Node f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}
// remove的時候如果沒有元素拋出異常
public E removeLast() {
    final Node l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}
// poll的時候如果沒有元素返回null
public E pollFirst() {
    final Node f = first;
    return (f == null) ? null : unlinkFirst(f);
}
// poll的時候如果沒有元素返回null
public E pollLast() {
    final Node l = last;
    return (l == null) ? null : unlinkLast(l);
}
// 刪除中間節(jié)點
public E remove(int index) {
    // 檢查是否越界
    checkElementIndex(index);
    // 刪除指定index位置的節(jié)點
    return unlink(node(index));
}

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

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

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

棧

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

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

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

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

總結(jié)

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

（2）LinkedList還是一個雙端隊列，具有隊列、雙端隊列、棧的特性；

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

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

（5）LinkedList不支持隨機訪問，所以訪問非隊列首尾的元素比較低效；

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

彩蛋

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

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

下一章，筆者將對整個java集合做一個總結(jié)，并提出一些閱讀源碼過程中的問題，敬請期待^^

---

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

創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務器，動態(tài)BGP最優(yōu)骨干路由自動選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡助力業(yè)務部署。公司持有工信部辦法的idc、isp許可證， 機房獨有T級流量清洗系統(tǒng)配攻擊溯源，準確進行流量調(diào)度，確保服務器高可用性。佳節(jié)活動現(xiàn)已開啟，新人活動云服務器買多久送多久。

網(wǎng)頁標題：死磕java集合之LinkedList源碼分析-創(chuàng)新互聯(lián)
URL網(wǎng)址：http://weahome.cn/article/dcisgc.html