一盗舰、LinkedList 的剖白

大家好，我是 LinkedList桂躏，和 ArrayList 是同門師兄弟钻趋，但我倆練的內(nèi)功卻完全不同。師兄練的是動態(tài)數(shù)組剂习，我練的是鏈表蛮位。

問大家一個問題较沪，知道我為什么要練鏈表這門內(nèi)功嗎？

舉個例子來講吧失仁，假如你們手頭要管理一推票據(jù)尸曼，可能有一張，也可能有一億張萄焦。

該怎么辦呢控轿？

申請一個 10G 的大數(shù)組等著？那萬一票據(jù)只有 100 張呢楷扬？

申請一個默認(rèn)大小的數(shù)組解幽，隨著數(shù)據(jù)量的增大擴(kuò)容？要知道擴(kuò)容是需要重新復(fù)制數(shù)組的烘苹，很耗時間躲株。

關(guān)鍵是，數(shù)組還有一個弊端就是镣衡，假如現(xiàn)在有 500 萬張票據(jù)霜定，現(xiàn)在要從中間刪除一個票據(jù)，就需要把 250 萬張票據(jù)往前移動一格廊鸥。

遇到這種情況的時候望浩，我?guī)熜謳缀跚榫w崩潰，難受的要命惰说。師父不忍心看到師兄這樣痛苦磨德，于是打我進(jìn)入師門那一天，就強(qiáng)迫我練鏈表這門內(nèi)功吆视，一開始我很不理解典挑，害怕師父偏心，不把師門最厲害的內(nèi)功教我啦吧。

直到有一天您觉，我親眼目睹師兄差點因為移動數(shù)據(jù)而走火入魔，我才明白師父的良苦用心授滓。從此以后琳水，我苦練“鏈表”這門內(nèi)功，取得了顯著的進(jìn)步般堆，師父和師兄都夸我有天賦在孝。

鏈表這門內(nèi)功大致分為三個層次：

• 第一層叫做“單向鏈表”，我只有一個后指針淮摔，指向下一個數(shù)據(jù)浑玛；
• 第二層叫做“雙向鏈表”，我有兩個指針噩咪，后指針指向下一個數(shù)據(jù)顾彰，前指針指向上一個數(shù)據(jù)。
• 第三層叫做“二叉樹”胃碾，把后指針去掉涨享，換成左右指針。

但我現(xiàn)在的功力還達(dá)不到第三層仆百，不過師父說我有這個潛力厕隧，練成神功是早晚的事。

先贊后看：《Java 程序員進(jìn)階之路》專欄在 GitHub 上已經(jīng)開源了俄周，有 GitHub 賬號的小伙伴吁讨，來安排一波 star 呀！看能不能沖一波 trending 榜單峦朗，求求各位了建丧。

GitHub 地址：https://github.com/itwanger/toBeBetterJavaer

二、LinkedList 的內(nèi)功心法

好了波势，經(jīng)過我這么樣的一個剖白后翎朱，大家對我應(yīng)該已經(jīng)不陌生了。那么接下來尺铣，我給大家展示一下我的內(nèi)功心法拴曲。

我的內(nèi)功心法主要是一個私有的靜態(tài)內(nèi)部類，叫 Node凛忿，也就是節(jié)點澈灼。

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

它由三部分組成：

• 節(jié)點上的元素
• 下一個節(jié)點
• 上一個節(jié)點

我畫幅圖給你們展示下吧。

image

• 對于第一個節(jié)點來說店溢，prev 為 null叁熔；
• 對于最后一個節(jié)點來說，next 為 null逞怨；
• 其余的節(jié)點呢者疤，prev 指向前一個，next 指向后一個叠赦。

我的內(nèi)功心法就這么簡單驹马，其實我早已經(jīng)牢記在心了。但師父叮囑我除秀，每天早上醒來的時候糯累，每天晚上睡覺的時候，一定要默默地背誦一遍册踩。雖然我有些厭煩泳姐，但我對師父的教誨從來都是言聽計從。

03暂吉、LinkedList 的招式

和師兄 ArrayList 一樣胖秒，我的招式也無外乎“增刪改查”這 4 種缎患。在此之前，我們都必須得初始化阎肝。

LinkedList<String> list = new LinkedList();

師兄在初始化的時候挤渔，默認(rèn)大小為 10，也可以指定大小风题，依據(jù)要存儲的元素數(shù)量來判导。我就不需要。

1）招式一：增

可以調(diào)用 add 方法添加元素：

list.add("沉默王二");
list.add("沉默王三");
list.add("沉默王四");

add 方法內(nèi)部其實調(diào)用的是 linkLast 方法：

public boolean add(E e) {
    linkLast(e);
    return true;
}

linkLast沛硅，顧名思義眼刃，就是在鏈表的尾部鏈接：

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

• 添加第一個元素的時候，first 和 last 都為 null摇肌。
• 然后新建一個節(jié)點 newNode擂红，它的 prev 和 next 也為 null。
• 然后把 last 和 first 都賦值為 newNode朦蕴。

此時還不能稱之為鏈表篮条，因為前后節(jié)點都是斷裂的。

image

• 添加第二個元素的時候吩抓，first 和 last 都指向的是第一個節(jié)點涉茧。
• 然后新建一個節(jié)點 newNode，它的 prev 指向的是第一個節(jié)點疹娶，next 為 null伴栓。
• 然后把第一個節(jié)點的 next 賦值為 newNode。

此時的鏈表還不完整雨饺。

image

• 添加第三個元素的時候钳垮，first 指向的是第一個節(jié)點，last 指向的是最后一個節(jié)點额港。
• 然后新建一個節(jié)點 newNode饺窿，它的 prev 指向的是第二個節(jié)點，next 為 null移斩。
• 然后把第二個節(jié)點的 next 賦值為 newNode肚医。

此時的鏈表已經(jīng)完整了。

image

我這個增的招式向瓷，還可以演化成另外兩個：

• addFirst() 方法將元素添加到第一位肠套；
• addLast() 方法將元素添加到末尾。

addFirst 內(nèi)部其實調(diào)用的是 linkFirst：

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

linkFirst 負(fù)責(zé)把新的節(jié)點設(shè)為 first猖任，并將新的 first 的 next 更新為之前的 first你稚。

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

addLast 的內(nèi)核其實和 addFirst 差不多，就交給大家自行理解了。

2）招式二：刪

我這個刪的招式還挺多的：

• remove()：刪除第一個節(jié)點
• remove(int)：刪除指定位置的節(jié)點
• remove(Object)：刪除指定元素的節(jié)點
• removeFirst()：刪除第一個節(jié)點
• removeLast()：刪除最后一個節(jié)點

remove 內(nèi)部調(diào)用的是 removeFirst刁赖，所以這兩個招式的功效一樣搁痛。

remove(int) 內(nèi)部其實調(diào)用的是 unlink 方法。

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

unlink 方法其實很好理解乾闰，就是更新當(dāng)前節(jié)點的 next 和 prev落追，然后把當(dāng)前節(jié)點上的元素設(shè)為 null。

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

remove(Object) 內(nèi)部也調(diào)用了 unlink 方法涯肩，只不過在此之前要先找到元素所在的節(jié)點：

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

這內(nèi)部就分為兩種，一種是元素為 null 的時候巢钓，必須使用 == 來判斷病苗；一種是元素為非 null 的時候，要使用 equals 來判斷症汹。equals 是不能用來判 null 的硫朦，會拋出 NPE 錯誤。

removeFirst 內(nèi)部調(diào)用的是 unlinkFirst 方法：

public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

unlinkFirst 負(fù)責(zé)的就是把第一個節(jié)點毀尸滅跡背镇，并且捎帶把后一個節(jié)點的 prev 設(shè)為 null咬展。

private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

3）招式三：改

可以調(diào)用 set() 方法來更新元素：

list.set(0, "沉默王五");

來看一下 set() 方法：

public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

首先對指定的下標(biāo)進(jìn)行檢查，看是否越界瞒斩；然后根據(jù)下標(biāo)查找原有的節(jié)點：

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：也就是右移一位破婆，相當(dāng)于除以 2。對于計算機(jī)來說胸囱，移位比除法運(yùn)算效率更高祷舀，因為數(shù)據(jù)在計算機(jī)內(nèi)部都是二進(jìn)制存儲的。

換句話說烹笔，node 方法會對下標(biāo)進(jìn)行一個初步判斷裳扯，如果靠近前半截，就從下標(biāo) 0 開始遍歷谤职；如果靠近后半截饰豺，就從末尾開始遍歷。

找到指定下標(biāo)的節(jié)點就簡單了允蜈，直接把原有節(jié)點的元素替換成新的節(jié)點就 OK 了冤吨，prev 和 next 都不用改動。

4）招式四：查

我這個查的招式可以分為兩種：

• indexOf(Object)：查找某個元素所在的位置
• get(int)：查找某個位置上的元素

indexOf 的內(nèi)部分為兩種陷寝，一種是元素為 null 的時候锅很，必須使用 == 來判斷；一種是元素為非 null 的時候凤跑，要使用 equals 來判斷爆安。因為 equals 是不能用來判 null 的，會拋出 NPE 錯誤仔引。

public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}

get 方法的內(nèi)核其實還是 node 方法扔仓，這個之前已經(jīng)說明過了褐奥，這里略過。

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

其實翘簇，查這個招式還可以演化為其他的一些撬码，比如說：

• getFirst() 方法用于獲取第一個元素；
• getLast() 方法用于獲取最后一個元素版保；
• poll() 和 pollFirst() 方法用于刪除并返回第一個元素（兩個方法盡管名字不同呜笑，但方法體是完全相同的）；
• pollLast() 方法用于刪除并返回最后一個元素彻犁；
• peekFirst() 方法用于返回但不刪除第一個元素叫胁。

四、LinkedList 的挑戰(zhàn)

說句實在話汞幢，我不是很喜歡和師兄 ArrayList 拿來比較驼鹅，因為我們各自修煉的內(nèi)功不同，沒有孰高孰低森篷。

雖然師兄經(jīng)常喊我一聲師弟输钩，但我們之間其實挺和諧的。但我知道仲智，在外人眼里买乃，同門師兄弟，總要一較高下的坎藐。

比如說为牍，我們倆在增刪改查時候的時間復(fù)雜度。

也許這就是命運(yùn)吧岩馍，從我進(jìn)入師門的那天起碉咆，這種爭論就一直沒有停息過。

無論外人怎么看待我們蛀恩，在我眼里疫铜，師兄永遠(yuǎn)都是一哥，我敬重他双谆，他也愿意保護(hù)我壳咕。

好了，LinkedList 這篇就到這了顽馋。

如果大家有閑情逸致的話谓厘，建議手撕一下鏈表，可以從單向鏈表開始撕起寸谜。

叨逼叨：我已經(jīng)輸出了近百篇 Java 方面的系列文章竟稳，應(yīng)很多小伙伴的請求，現(xiàn)已開源到 GitHub 上了。

image

有 Java 核心語法他爸、Java 集合框架聂宾、Java IO、Java 并發(fā)編程诊笤、Java 虛擬機(jī)等系谐，只講重點，累計已有 10 萬+字讨跟，通俗易懂纪他、風(fēng)趣幽默，很多小伙伴都發(fā)來私信表示感謝晾匠。

GitHub 開源地址（如果你也需要止喷，歡迎 star）：https://github.com/itwanger/toBeBetterJavaer

希望大家能點贊下，給我注入一點點更新的動力混聊。我也會不斷地提升品質(zhì)，給大家?guī)砀埠说募夹g(shù)文章乾巧，筆芯~