寫在開頭

作為ArrayList的同門師兄弟，LinkedList的師門地位遜色不少，除了在做算法題的時(shí)候我們會(huì)用到它之外，在實(shí)際的開發(fā)工作中我們極少使用它，就連它的創(chuàng)造者都說：“I wrote it，and I never use it”，想想頗有點(diǎn)好笑，但這并不影響我們?nèi)W(xué)習(xí)它，個(gè)人認(rèn)為它底層的鏈表邏輯對(duì)于我們代碼思想的培養(yǎng)還是挺有幫助的。

源碼解析

看過build哥文章的同學(xué)應(yīng)該都知道，俺喜歡通過源碼去學(xué)習(xí)和分析對(duì)象或代碼邏輯，因此，話不多說，直接上源碼！

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

如上為JDK8中LinkedList的繼承實(shí)現(xiàn)關(guān)系,通過這些關(guān)系我們可以大致分析出它所具備的特性：

1. 實(shí)現(xiàn)List接口 表明它是一個(gè)列表，支持添加、刪除、查找等操作，并且可以通過下標(biāo)進(jìn)行訪問；
2. Deque繼承自 Queue 接口，具有雙端隊(duì)列的特性，支持從兩端插入和刪除元素，方便實(shí)現(xiàn)棧和隊(duì)列等數(shù)據(jù)結(jié)構(gòu)；
3. Cloneable ：表明它具有拷貝能力，可以進(jìn)行深拷貝或淺拷貝操作；
4. Serializable : 表明它可以進(jìn)行序列化操作，也就是可以將對(duì)象轉(zhuǎn)換為字節(jié)流進(jìn)行持久化存儲(chǔ)或網(wǎng)絡(luò)傳輸，非常方便。

LinkedList提供了非常多的方法供我們使用，繼續(xù)閱讀源碼可以看到

// 在鏈表尾部插入元素
public boolean add(E e) {
    linkLast(e);
    return true;
}

// 在鏈表指定位置插入元素
public void add(int index, E element) {
    // 下標(biāo)越界檢查
    checkPositionIndex(index);

    // 判斷 index 是不是鏈表尾部位置
    if (index == size)
        // 如果是就直接調(diào)用 linkLast 方法將元素節(jié)點(diǎn)插入鏈表尾部即可
        linkLast(element);
    else
        // 如果不是則調(diào)用 linkBefore 方法將其插入指定元素之前
        linkBefore(element, node(index));
}

// 將元素節(jié)點(diǎn)插入到鏈表尾部
void linkLast(E e) {
    // 將最后一個(gè)元素賦值（引用傳遞）給節(jié)點(diǎn) l
    final Node<E> l = last;
    // 創(chuàng)建節(jié)點(diǎn)，并指定節(jié)點(diǎn)前驅(qū)為鏈表尾節(jié)點(diǎn) last，后繼引用為空
    final Node<E> newNode = new Node<>(l, e, null);
    // 將 last 引用指向新節(jié)點(diǎn)
    last = newNode;
    // 判斷尾節(jié)點(diǎn)是否為空
    // 如果 l 是null 意味著這是第一次添加元素
    if (l == null)
        // 如果是第一次添加，將first賦值為新節(jié)點(diǎn)，此時(shí)鏈表只有一個(gè)元素
        first = newNode;
    else
        // 如果不是第一次添加，將新節(jié)點(diǎn)賦值給l（添加前的最后一個(gè)元素）的next
        l.next = newNode;
    size++;
    modCount++;
}

// 在指定元素之前插入元素
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;斷言 succ不為 null
    // 定義一個(gè)節(jié)點(diǎn)元素保存 succ 的 prev 引用，也就是它的前一節(jié)點(diǎn)信息
    final Node<E> pred = succ.prev;
    // 初始化節(jié)點(diǎn)，并指明前驅(qū)和后繼節(jié)點(diǎn)
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 將 succ 節(jié)點(diǎn)前驅(qū)引用 prev 指向新節(jié)點(diǎn)
    succ.prev = newNode;
    // 判斷尾節(jié)點(diǎn)是否為空，為空表示當(dāng)前鏈表還沒有節(jié)點(diǎn)
    if (pred == null)
        first = newNode;
    else
        // succ 節(jié)點(diǎn)前驅(qū)的后繼引用指向新節(jié)點(diǎn)
        pred.next = newNode;
    size++;
    modCount++;
}
// 獲取鏈表的第一個(gè)元素
public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

// 獲取鏈表的最后一個(gè)元素
public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

// 獲取鏈表指定位置的元素
public E get(int index) {
  // 下標(biāo)越界檢查，如果越界就拋異常
  checkElementIndex(index);
  // 返回鏈表中對(duì)應(yīng)下標(biāo)的元素
  return node(index).item;
}

更多的API方法可以參考:LinkedList全量方法

使用LinkedList

在Java中我們寫一個(gè)小測(cè)試代碼來用一下LinkedList的增刪改查

【代碼示例1】

  // 創(chuàng)建LinkedList集合
  LinkedList link = new LinkedList();
  // 1、添加元素
  link.add("happy");
  link.add("new");
  link.offer("year"); // 向集合尾部追加元素
  link.push("javabuild"); // 向集合頭部添加元素
  System.out.println(link); // 輸出集合中的元素
  // 2、獲取元素
  Object object = link.peek(); //獲取集合第一個(gè)元素
  System.out.println(object); // 輸出集合中的元素
  // 3、刪除元素
  link.removeFirst(); // 刪除集合第一個(gè)元素
  link.pollLast(); // 刪除集合最后一個(gè)元素
  System.out.println(link);

輸出：

[javabuild, happy, new, year]
javabuild
[happy, new]

對(duì)比ArrayList

1. ArrayList 和 LinkedList 都是不同步的，也就是不保證線程安全；
2. ArrayList 底層使用的是 Object 數(shù)組；LinkedList 底層使用的是雙向鏈表數(shù)據(jù)結(jié)構(gòu)；
3. LinkedList 不支持高效的隨機(jī)元素訪問，而 ArrayList（實(shí)現(xiàn)了 RandomAccess 接口） 支持。
4. ArrayList存在擴(kuò)容問題，LinkedList不存在，直接放在集合尾部，修改指針即可；

提問：為什么LinkedList不支持高效的隨機(jī)訪問，或者說為什么不去實(shí)現(xiàn)RandomAccess 接口？

我們看過RandomAccess 接口的底層的同學(xué)知道，這個(gè)接口也是個(gè)標(biāo)識(shí)性接口，只要實(shí)現(xiàn)了這個(gè)接口就意味著支持通過索引訪問元素。由于 LinkedList 底層數(shù)據(jù)結(jié)構(gòu)是鏈表，內(nèi)存地址不連續(xù)，只能通過指針來定位，不支持隨機(jī)快速訪問，所以不能實(shí)現(xiàn) RandomAccess 接口。
但是！
在LinkedList中依舊提供了get(int index)：獲取鏈表指定位置的元素。

// 獲取鏈表指定位置的元素
public E get(int index) {
  // 下標(biāo)越界檢查，如果越界就拋異常
  checkElementIndex(index);
  // 返回鏈表中對(duì)應(yīng)下標(biāo)的元素
  return node(index).item;
}

源碼中g(shù)et方法實(shí)現(xiàn)通過位置獲取元素的核心是node(index)方法，我們跟進(jìn)去繼續(xù)看一下！

// 返回指定下標(biāo)的非空節(jié)點(diǎn)
Node<E> node(int index) {
    // 斷言下標(biāo)未越界
    // assert isElementIndex(index);
    // 如果index小于size的二分之一  從前開始查找（向后查找）  反之向前查找
    if (index < (size >> 1)) {
        Node<E> x = first;
        // 遍歷，循環(huán)向后查找，直至 i == index
        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參數(shù)和size的1/2進(jìn)行比較，小于則從鏈表頭向后查找，否則從鏈表尾向前遍歷查找，這與ArrayList中的get(index)方法還是有本質(zhì)上的區(qū)別！

結(jié)尾彩蛋

如果本篇博客對(duì)您有一定的幫助，大家記得留言+點(diǎn)贊+收藏呀。原創(chuàng)不易，轉(zhuǎn)載請(qǐng)聯(lián)系Build哥！

文章來源地址http://www.zghlxwxcb.cn/news/detail-825559.html

到了這里，關(guān)于Java集合篇之深入解析LinkedList的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！