認(rèn)識(shí)鏈表結(jié)構(gòu)

單向鏈表

單鏈表在內(nèi)存中的表示：

可以看到，一個(gè)鏈表的節(jié)點(diǎn)包含數(shù)據(jù)域和指向下一個(gè)節(jié)點(diǎn)的引用，鏈表最后一個(gè)節(jié)點(diǎn)指向null（空區(qū)域）。

我們可以根據(jù)這一定義，用Java語言表示一下單向鏈表的結(jié)構(gòu)：

public class Node {
    public int value;
    public Node next;
    
    public Node(int value) {
        this.value = value;
    }
}

在鏈表的結(jié)構(gòu)中，有數(shù)據(jù)域value，以及一個(gè)指向下一個(gè)節(jié)點(diǎn)的引用next。

TIP：這里的value還可以定義成泛型的。

雙向鏈表

我們再來看一下雙向鏈表的結(jié)構(gòu)：

雙向鏈表中的節(jié)點(diǎn)有數(shù)值域，和指向它前一個(gè)節(jié)點(diǎn)的引用以及指向它后一個(gè)節(jié)點(diǎn)的引用，據(jù)此我們可以定義出

雙向鏈表的結(jié)構(gòu)：

public class DoubleNode {
    public int value;
    public DoubleNode pre;
    public DoubleNode next;
    
    public DoubleNode(int value) {
        this.value = value;
    }
}

加深對鏈表結(jié)構(gòu)的理解

實(shí)現(xiàn)單向和雙向鏈表的反轉(zhuǎn)

說明：

對于一個(gè)鏈表如圖所示：

反轉(zhuǎn)的意思是，將原來鏈表上的節(jié)點(diǎn)指針指向反轉(zhuǎn)，原來的指向是：a -> b -> c -> d -> null，變成現(xiàn)在的指向：d -> c -> b -> a -> null，

即反轉(zhuǎn)后的結(jié)構(gòu)如圖所示：

這個(gè)題目不難，我們轉(zhuǎn)換一下指針的指向就行了。

設(shè)計(jì)這樣一個(gè)函數(shù)，函數(shù)的過程是調(diào)整鏈表各節(jié)點(diǎn)的指針指向，那么這個(gè)函數(shù)的要素有：

• 返回值是鏈表的新的頭結(jié)點(diǎn)，這樣能保證函數(shù)執(zhí)行完，原鏈表變成一個(gè)有新的頭結(jié)點(diǎn)的鏈表
• 需要傳入一個(gè)鏈表，用頭結(jié)點(diǎn)表示

解題技巧：定義兩個(gè)Node引用輔助我們反轉(zhuǎn)指針指向。

代碼實(shí)現(xiàn)：

public static Node reverseNode(Node head) {
    Node pre = null;
    Node next = null;
    //最終讓head指向null
    while (head != null) {
        next = head.next;
        head.next = pre;
        pre = head;
        head = next;
    }
    return pre;
}

我們來模擬一下這個(gè)函數(shù)的執(zhí)行過程。

鏈表原始狀態(tài)：

方法開始執(zhí)行，此時(shí) head.next 不為空，所以，執(zhí)行如下步驟：

next = head.next：讓next指向head（當(dāng)前節(jié)點(diǎn)）的下一個(gè)節(jié)點(diǎn)，即b

head.next = pre：讓當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指向pre，即null

此時(shí)當(dāng)前節(jié)點(diǎn)從原來指向b，改為指向null。

• pre = head：讓pre指向當(dāng)前節(jié)點(diǎn)
• head = next：讓當(dāng)前節(jié)點(diǎn)指向next，相當(dāng)于移動(dòng)head節(jié)點(diǎn)，直到將head節(jié)點(diǎn)移動(dòng)到原來tail節(jié)點(diǎn)的位置

第一次循環(huán)執(zhí)行結(jié)束，此時(shí) head 為b，不是null，所以繼續(xù)循環(huán)，執(zhí)行流程：

此時(shí) head 為c，不是null，所以繼續(xù)循環(huán)，執(zhí)行流程如下：

同理，此時(shí) head 為d，不是null，繼續(xù)循環(huán)：

這是就完成了單鏈表的反轉(zhuǎn)步驟。

有了單鏈表反轉(zhuǎn)的經(jīng)驗(yàn)，我們很容易就能實(shí)現(xiàn)雙向鏈表的反轉(zhuǎn)，代碼如下：

public DoubleNode reverseDoubleNode(DoubleNode head) {
    DoubleNode pre = null;
    DoubleNode next = null;
    while (head != null) {
        next = head.next;
        //操作（移動(dòng)）當(dāng)前節(jié)點(diǎn)
        head.next = pre;
        head.pre = next;

        pre = head;
        head = next;
    }
    return pre;
}

實(shí)現(xiàn)把鏈表中給定的值都刪除

題如：給定一個(gè)單鏈表頭節(jié)點(diǎn)head，以及一個(gè)整數(shù)，要求把鏈表中值為給定整數(shù)的節(jié)點(diǎn)都刪除。

實(shí)現(xiàn)思路：

• 要實(shí)現(xiàn)的函數(shù)需要給我傳一個(gè)頭節(jié)點(diǎn)以及給定的數(shù)值，頭節(jié)點(diǎn)確定鏈表。func(Node head, int num)。
• 函數(shù)給不給返回值，返回值是什么？試想，針對鏈表 3 -> 5 -> 4 -> 3 -> 4 -> 5 ，假如要?jiǎng)h除4，那么新鏈表就是 3 -> 5-> 3 -> 5，頭節(jié)點(diǎn)仍然是原來的節(jié)點(diǎn)3；而如果要?jiǎng)h除值為3的節(jié)點(diǎn)呢，刪除后就是 5 -> 4 -> 4 -> 5 ，頭節(jié)點(diǎn)變了。因此，我們要設(shè)計(jì)的這個(gè)函數(shù)需要返回新鏈表的頭節(jié)點(diǎn)。
• 上述分析得知，需要返回新鏈表的頭節(jié)點(diǎn)，因此也就是要返回第一個(gè)不是給定值的節(jié)點(diǎn)（因?yàn)榻o定值的節(jié)點(diǎn)都要被刪除掉）。

//head移動(dòng)到第一個(gè)不需要?jiǎng)h除的位置：邊界條件
while (head != null) {
    if (head.value != num) {
        break;
    }
    //head右移
    head = head.next;
}
//跳出循環(huán)之后，head的情況：
//1. head = null，這種情況是鏈表中的值全部是給定值，全刪了
//2. head != null
// 中間操作
//最終返回head：第一個(gè)不是給定值的節(jié)點(diǎn)
return head;

head移動(dòng)到第一個(gè)不需要?jiǎng)h除的位置后，head若為null，表示所有節(jié)點(diǎn)都刪除了，直接返回就可以了；若head不為null，借助兩個(gè)輔助變量Node pre和cur，從head處開始往next走，遇到給定值就跳過。

Node pre = head;
Node cur = head;
while (cur != null) {
    if (cur.value == num) {
        pre.next = cur.next;
    } else {
        pre = cur;
    }
    cur = cur.next;
}

這一執(zhí)行過程圖解如下：

通過上述分析，寫出完整實(shí)現(xiàn)代碼：

public static Node remove (Node head, int num) {
    while (head != null) {
        if (head.value != num) {
            break;
        }
        head = head.next;
    }

    Node pre = head;
    Node cur = head;

    while (cur != null) {
        if (cur.value == num) {
            pre.next = cur.next;
        } else {
            pre = cur;
        }
        cur = cur.next;
    }
    return head;
}

小結(jié)

針對鏈表這種數(shù)據(jù)結(jié)構(gòu)進(jìn)行了一些簡單的分析，通過兩個(gè)例子熟悉了鏈表的結(jié)構(gòu)。

針對鏈表的操作，需要注意的就是指針指向以及邊界問題，后續(xù)關(guān)于鏈表的算法還會(huì)遇到。

到此這篇關(guān)于Java鏈表數(shù)據(jù)結(jié)構(gòu)及其簡單使用方法解析的文章就介紹到這了,更多相關(guān)Java鏈表數(shù)據(jù)結(jié)構(gòu)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論