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

單向鏈表

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

可以看到，一個鏈表的節(jié)點包含數(shù)據(jù)域和指向下一個節(jié)點的引用，鏈表最后一個節(jié)點指向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，以及一個指向下一個節(jié)點的引用next。

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

雙向鏈表

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

雙向鏈表中的節(jié)點有數(shù)值域，和指向它前一個節(jié)點的引用以及指向它后一個節(jié)點的引用，據(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)的理解

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

說明：

對于一個鏈表如圖所示：

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

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

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

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

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

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

代碼實現(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;
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

實現(xiàn)思路：

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

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

head移動到第一個不需要刪除的位置后，head若為null，表示所有節(jié)點都刪除了，直接返回就可以了；若head不為null，借助兩個輔助變量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í)行過程圖解如下：

通過上述分析，寫出完整實現(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)進行了一些簡單的分析，通過兩個例子熟悉了鏈表的結(jié)構(gòu)。

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

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

最新評論