作者：小傅哥
博客：https://

沉淀、分享、成長，讓自己和他人都能有所收獲！😄

一、前言

你以為考你個數(shù)據(jù)結(jié)構(gòu)是要造火箭？

🚕汽車75馬力就夠奔跑了，那你怎么還想要2.0渦輪+9AT呢？大橋兩邊的護(hù)欄你每次走的時候都會去摸嗎？那怎么沒有護(hù)欄的大橋你不敢上呢？

很多時候，你額外的能力才是自身價值的體現(xiàn)，不要以為你的能力就只是做個業(yè)務(wù)開發(fā)每天CRUD，并不是產(chǎn)品讓你寫CRUD，而是因為你的能力只能產(chǎn)品功能設(shè)計成CRUD。

就像數(shù)據(jù)結(jié)構(gòu)、算法邏輯、源碼技能，它都是可以為你的業(yè)務(wù)開發(fā)賦能的，也是寫出更好、更易擴(kuò)展程序的根基，所以學(xué)好這份知識非常有必要。

本文涉及了較多的代碼和實踐驗證圖稿，歡迎關(guān)注公眾號：bugstack蟲洞棧，回復(fù)下載得到一個鏈接打開后，找到ID：19🤫獲取！

二、面試題

謝飛機(jī)，ArrayList資料看了吧？嗯，那行問問你哈🦀

問：ArrayList和LinkedList，都用在什么場景呢？

答：啊，這我知道了。ArrayList是基于數(shù)組實現(xiàn)、LinkedList是基于雙向鏈表實現(xiàn)，所以基于數(shù)據(jù)結(jié)構(gòu)的不同，遍歷和查找多的情況下用ArrayList、插入和刪除頻繁的情況下用LinkedList。

問：嗯，那LinkedList的插入效率一定比ArrayList好嗎？

答：對，好！

送你個飛機(jī)?，回去等消息吧！

其實，飛機(jī)回答的也不是不對，只是不全面。出門后不甘心買瓶肥宅水又回來，跟面試官聊了2個點(diǎn)，要到了兩張圖，如下；

如圖，分別是；10萬、100萬、1000萬，數(shù)據(jù)在兩種集合下不同位置的插入效果，所以：，不能說LinkedList插入就快，ArrayList插入就慢，還需要看具體的操作情況。

接下來我們帶著數(shù)據(jù)結(jié)構(gòu)和源碼，具體分析下。

三、數(shù)據(jù)結(jié)構(gòu)

Linked + List = 鏈表 + 列表 = LinkedList = 鏈表列表

LinkedList，是基于鏈表實現(xiàn)，由雙向鏈條next、prev，把數(shù)據(jù)節(jié)點(diǎn)穿插起來。所以，在插入數(shù)據(jù)時，是不需要像我們上一章節(jié)介紹的ArrayList那樣，擴(kuò)容數(shù)組。

但，又不能說所有的插入都是高效，比如中間區(qū)域插入，他還需要遍歷元素找到插入位置。具體的細(xì)節(jié)，我們在下文的源碼分析中進(jìn)行講解，也幫謝飛機(jī)掃除疑惑。

四、源碼分析

1. 初始化

與ArrayList不同，LinkedList初始化不需要創(chuàng)建數(shù)組，因為它是一個鏈表結(jié)構(gòu)。而且也沒有傳給構(gòu)造函數(shù)初始化多少個空間的入?yún)?#xff0c;例如這樣是不可以的，如下；

但是，構(gòu)造函數(shù)一樣提供了和ArrayList一些相同的方式，來初始化入?yún)?#xff0c;如下這四種方式；

@Test
public void test_init() {
    // 初始化方式；普通方式
    LinkedList<String> list01 = new LinkedList<String>();
    list01.add("a");
    list01.add("b");
    list01.add("c");
    System.out.println(list01);
    
    // 初始化方式；Arrays.asList
    LinkedList<String> list02 = new LinkedList<String>(Arrays.asList("a", "b", "c"));
    System.out.println(list02);
    
    // 初始化方式；內(nèi)部類
    LinkedList<String> list03 = new LinkedList<String>()\\{
        {add("a");add("b");add("c");}
    \\};
    System.out.println(list03);
    
    // 初始化方式；Collections.nCopies
    LinkedList<Integer> list04 = new LinkedList<Integer>(Collections.nCopies(10, 0));
    System.out.println(list04);
}

// 測試結(jié)果

[a, b, c]
[a, b, c]
[a, b, c]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Process finished with exit code 0

• 這些方式都可以初始化操作，按需選擇即可。

2. 插入

LinkedList的插入方法比較多，List中接口中默認(rèn)提供的是add，也可以指定位置插入。但在LinkedList中還提供了頭插addFirst和尾插addLast。

關(guān)于插入這部分就會講到為什么；有的時候LinkedList插入更耗時、有的時候ArrayList插入更好。

2.1 頭插

先來看一張數(shù)據(jù)結(jié)構(gòu)對比圖，回顧下ArrayList的插入也和LinkedList插入做下對比，如下；

看上圖我們可以分析出幾點(diǎn)；

1. ArrayList 頭插時，需要把數(shù)組元素通過Arrays.copyOf的方式把數(shù)組元素移位，如果容量不足還需要擴(kuò)容。
2. LinkedList 頭插時，則不需要考慮擴(kuò)容以及移位問題，直接把元素定位到首位，接點(diǎn)鏈條鏈接上即可。

2.1.1 源碼

這里我們再對照下LinkedList頭插的源碼，如下；

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

• first，首節(jié)點(diǎn)會一直被記錄，這樣就非常方便頭插。
• 插入時候會創(chuàng)建新的節(jié)點(diǎn)元素，new Node<>(null, e, f)，緊接著把新的頭元素賦值給first。
• 之后判斷f節(jié)點(diǎn)是否存在，不存在則把頭插節(jié)點(diǎn)作為最后一個節(jié)點(diǎn)、存在則用f節(jié)點(diǎn)的上一個鏈條prev鏈接。
• 最后記錄size大小、和元素數(shù)量modCount。modCount用在遍歷時做校驗，modCount != expectedModCount

2.1.2 驗證

ArrayList、LinkeList，頭插源碼驗證

@Test
public void test_ArrayList_addFirst() {
    ArrayList<Integer> list = new ArrayList<Integer>();
    long startTime = System.currentTimeMillis();
    for (int i = 0; i < 10000000; i++) {
        list.add(0, i);
    }
    System.out.println("耗時：" + (System.currentTimeMillis() - startTime));
}

@Test
public void test_LinkedList_addFirst() {
    LinkedList<Integer> list = new LinkedList<Integer>();
    long startTime = System.currentTimeMillis();
    for (int i = 0; i < 10000000; i++) {
        list.addFirst(i);
    }
    System.out.println("耗時：" + (System.currentTimeMillis() - startTime));
}

比對結(jié)果：

• 這里我們分別驗證，10萬、100萬、1000萬的數(shù)據(jù)量，在頭插時的一個耗時情況。
• 如我們數(shù)據(jù)結(jié)構(gòu)對比圖中一樣，ArrayList需要做大量的位移和復(fù)制操作，而LinkedList的優(yōu)勢就體現(xiàn)出來了，耗時只是實例化一個對象。

2.2 尾插

先來看一張數(shù)據(jù)結(jié)構(gòu)對比圖，回顧下ArrayList的插入也和LinkedList插入做下對比，如下；

看上圖我們可以分析出幾點(diǎn)；

1. ArrayList 尾插時，是不需要數(shù)據(jù)位移的，比較耗時的是數(shù)據(jù)的擴(kuò)容時，需要拷貝遷移。
2. LinkedList 尾插時，與頭插相比耗時點(diǎn)會在對象的實例化上。

2.2.1 源碼

這里我們再對照下LinkedList尾插的源碼，如下；

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

• 與頭插代碼相比幾乎沒有什么區(qū)別，只是first換成last
• 耗時點(diǎn)只是在創(chuàng)建節(jié)點(diǎn)上，Node<E>

2.2.2 驗證

ArrayList、LinkeList，尾插源碼驗證

@Test
public void test_ArrayList_addLast() {
    ArrayList<Integer> list = new ArrayList<Integer>();
    long startTime = System.currentTimeMillis();
    for (int i = 0; i < 10000000; i++) {
        list.add(i);
    }
    System.out.println("耗時：" + (System.currentTimeMillis() - startTime));
}

@Test
public void test_LinkedList_addLast() {
    LinkedList<Integer> list = new LinkedList<Integer>();
    long startTime = System.currentTimeMillis();
    for (int i = 0; i < 1000000; i++) {
        list.addLast(i);
    }
    System.out.println("耗時：" + (System.currentTimeMillis() - startTime));
}

比對結(jié)果：

• 這里我們分別驗證，10萬、100萬、1000萬的數(shù)據(jù)量，在尾插時的一個耗時情況。
• 如我們數(shù)據(jù)結(jié)構(gòu)對比圖中一樣，ArrayList 不需要做位移拷貝也就不那么耗時了，而LinkedList則需要創(chuàng)建大量的對象。所以這里ArrayList尾插的效果更好一些。

2.3 中間插

先來看一張數(shù)據(jù)結(jié)構(gòu)對比圖，回顧下ArrayList的插入也和LinkedList插入做下對比，如下；

看上圖我們可以分析出幾點(diǎn)；

1. ArrayList 中間插入，首先我們知道他的定位時間復(fù)雜度是O(1)，比較耗時的點(diǎn)在于數(shù)據(jù)遷移和容量不足的時候擴(kuò)容。
2. LinkedList 中間插入，鏈表的數(shù)據(jù)實際插入時候并不會怎么耗時，但是它定位的元素的時間復(fù)雜度是O(n)，所以這部分以及元素的實例化比較耗時。

2.3.1 源碼

這里看下LinkedList指定位置插入的源碼；

使用add(位置、元素)方法插入：

public void add(int index, E element) {
    checkPositionIndex(index);
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

位置定位node(index)：

Node<E> node(int index) {
    // assert isElementIndex(index);
    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;
    }
}

• size >> 1，這部分的代碼判斷元素位置在左半?yún)^(qū)間，還是右半?yún)^(qū)間，在進(jìn)行循環(huán)查找。

執(zhí)行插入：

void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

• 找到指定位置插入的過程就比較簡單了，與頭插、尾插，相差不大。
• 整個過程可以看到，插入中比較耗時的點(diǎn)會在遍歷尋找插入位置上。

2.3.2 驗證

ArrayList、LinkeList，中間插入源碼驗證

@Test
public void test_ArrayList_addCenter() {
    ArrayList<Integer> list = new ArrayList<Integer>();
    long startTime = System.currentTimeMillis();
    for (int i = 0; i < 10000000; i++) {
        list.add(list.size() >> 1, i);
    }
    System.out.println("耗時：" + (System.currentTimeMillis() - startTime));
}

@Test
public void test_LinkedList_addCenter() {
    LinkedList<Integer> list = new LinkedList<Integer>();
    long startTime = System.currentTimeMillis();
    for (int i = 0; i < 1000000; i++) {
        list.add(list.size() >> 1, i);
    }
    System.out.println("耗時：" + (System.currentTimeMillis() - startTime));
}

比對結(jié)果：

• 這里我們分別驗證，10萬、100萬、1000萬的數(shù)據(jù)量，在中間插時的一個耗時情況。
• 可以看到Linkedlist在中間插入時，遍歷尋找位置還是非常耗時了。所以不同的情況下，需要選擇不同的List集合做業(yè)務(wù)。

3. 刪除

講了這么多插入的操作后，刪除的知識點(diǎn)就很好理解了。與ArrayList不同，刪除不需要拷貝元素，LinkedList是找到元素位置，把元素前后鏈連接上?；救缦聢D；

• 確定出要刪除的元素x，把前后的鏈接進(jìn)行替換。
• 如果是刪除首尾元素，操作起來會更加容易，這也就是為什么說插入和刪除快。但中間位置刪除，需要遍歷找到對應(yīng)位置。

3.1 刪除操作方法

源碼：

@Test
public void test_remove() {
    LinkedList<String> list = new LinkedList<String>();
    list.add("a");
    list.add("b");
    list.add("c");
    
    list.remove();
    list.remove(1);
    list.remove("a");
    list.removeFirst();
    list.removeLast();
    list.removeAll(Arrays.asList("a", "b"));
}

3.2 源碼

刪除操作的源碼都差不多，分為刪除首尾節(jié)點(diǎn)與其他節(jié)點(diǎn)時候，對節(jié)點(diǎn)的解鏈操作。這里我們舉例一個刪除其他位置的源碼進(jìn)行學(xué)習(xí)，如下；

list.remove(“a”);

public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

• 這一部分是元素定位，和unlink(x)解鏈。循環(huán)查找對應(yīng)的元素，這部分沒有什么難點(diǎn)。

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

這部分源碼主要有以下幾個知識點(diǎn)；

1. 獲取待刪除節(jié)點(diǎn)的信息；元素item、元素下一個節(jié)點(diǎn)next、元素上一個節(jié)點(diǎn)prev。
2. 如果上個節(jié)點(diǎn)為空則把待刪除元素的下一個節(jié)點(diǎn)賦值給首節(jié)點(diǎn)，否則把待刪除節(jié)點(diǎn)的下一個節(jié)點(diǎn)，賦值給待刪除節(jié)點(diǎn)的上一個節(jié)點(diǎn)的子節(jié)點(diǎn)。
3. 同樣待刪除節(jié)點(diǎn)的下一個節(jié)點(diǎn)next，也執(zhí)行2步驟同樣操作。
4. 最后是把刪除節(jié)點(diǎn)設(shè)置為null，并扣減size和modeCount數(shù)量。

4. 遍歷

接下來說下遍歷，ArrayList與LinkedList的遍歷都是通用的，基本包括5種方式。

這里我們先初始化出待遍歷的集合1千萬數(shù)據(jù)；

int xx = 0;
@Before
public void init() {
    for (int i = 0; i < 10000000; i++) {
        list.add(i);
    }
}

4.1 普通for循環(huán)

@Test
public void test_LinkedList_for0() {
    long startTime = System.currentTimeMillis();
    for (int i = 0; i < list.size(); i++) {
        xx += list.get(i);
    }
    System.out.println("耗時：" + (System.currentTimeMillis() - startTime));
}

4.2 增強(qiáng)for循環(huán)

@Test
public void test_LinkedList_for1() {
    long startTime = System.currentTimeMillis();
    for (Integer itr : list) {
        xx += itr;
    }
    System.out.println("耗時：" + (System.currentTimeMillis() - startTime));
}

4.3 Iterator遍歷

@Test
public void test_LinkedList_Iterator() {
    long startTime = System.currentTimeMillis();
    Iterator<Integer> iterator = list.iterator();
    while (iterator.hasNext()) {
        Integer next = iterator.next();
        xx += next;
    }
    System.out.println("耗時：" + (System.currentTimeMillis() - startTime))
}

4.4 forEach循環(huán)

@Test
public void test_LinkedList_forEach() {
    long startTime = System.currentTimeMillis();
    list.forEach(integer -> {
        xx += integer;
    });
    System.out.println("耗時：" + (System.currentTimeMillis() - startTime));
}

4.5 stream(流)

@Test
public void test_LinkedList_stream() {
    long startTime = System.currentTimeMillis();
    list.stream().forEach(integer -> {
        xx += integer;
    });
    System.out.println("耗時：" + (System.currentTimeMillis() - startTime));
}

那么，以上這5種遍歷方式誰最慢呢？按照我們的源碼學(xué)習(xí)分析下吧，歡迎留下你的答案在評論區(qū)！

五、總結(jié)

• ArrayList與LinkedList都有自己的使用場景，如果你不能很好的確定，那么就使用ArrayList。但如果你能確定你會在集合的首位有大量的插入、刪除以及獲取操作，那么可以使用LinkedList，因為它都有相應(yīng)的方法；addFirst、addLast、removeFirst、removeLast、getFirst、getLast，這些操作的時間復(fù)雜度都是O(1)，非常高效。
• LinkedList的鏈表結(jié)構(gòu)不一定會比ArrayList節(jié)省空間，首先它所占用的內(nèi)存不是連續(xù)的，其次他還需要大量的實例化對象創(chuàng)造節(jié)點(diǎn)。雖然不一定節(jié)省空間，但鏈表結(jié)構(gòu)也是非常優(yōu)秀的數(shù)據(jù)結(jié)構(gòu)，它能在你的程序設(shè)計中起著非常優(yōu)秀的作用，例如可視化的鏈路追蹤圖，就是需要鏈表結(jié)構(gòu)，并需要每個節(jié)點(diǎn)自旋一次，用于串聯(lián)業(yè)務(wù)。
• 程序的精髓往往就是數(shù)據(jù)結(jié)構(gòu)的設(shè)計，這能為你的程序開發(fā)提供出非常高的效率改變?？赡苣壳澳氵€不能用到，但萬一有一天你需要去造🚀火箭了呢？

六、系列文章

• ArrayList也這么多知識？一個指定位置插入就把謝飛機(jī)面暈了！
• HashMap核心知識，擾動函數(shù)、負(fù)載因子、擴(kuò)容鏈表拆分，深度學(xué)習(xí)
• 簡歷寫成這樣，誰要你呀!
• 工作5年的學(xué)習(xí)路線資源匯總
• 懂設(shè)計模式才能面試到20k以上