Java鏈表數據結構及使用方法實例分析

本篇內容主要講解“Java鏈表數據結構及使用方法實例分析”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“Java鏈表數據結構及使用方法實例分析”吧!

認識鏈表結構

單向鏈表

單鏈表在內存中的表示：

可以看到，一個鏈表的節點包含數據域和指向下一個節點的引用，鏈表最后一個節點指向null（空區域）。

我們可以根據這一定義，用Java語言表示一下單向鏈表的結構：

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

在鏈表的結構中，有數據域value，以及一個指向下一個節點的引用next。

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

雙向鏈表

我們再來看一下雙向鏈表的結構：

雙向鏈表中的節點有數值域，和指向它前一個節點的引用以及指向它后一個節點的引用，據此我們可以定義出

雙向鏈表的結構：

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

加深對鏈表結構的理解

實現單向和雙向鏈表的反轉

說明：

對于一個鏈表如圖所示：

反轉的意思是，將原來鏈表上的節點指針指向反轉，原來的指向是：a -> b -> c -> d -> null，變成現在的指向：d -> c -> b -> a -> null，

即反轉后的結構如圖所示：

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

設計這樣一個函數，函數的過程是調整鏈表各節點的指針指向，那么這個函數的要素有：

• 返回值是鏈表的新的頭結點，這樣能保證函數執行完，原鏈表變成一個有新的頭結點的鏈表

• 需要傳入一個鏈表，用頭結點表示

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

代碼實現：

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

我們來模擬一下這個函數的執行過程。

鏈表原始狀態：

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

next = head.next：讓next指向head（當前節點）的下一個節點，即b

head.next = pre：讓當前節點的下一個節點指向pre，即null

此時當前節點從原來指向b，改為指向null。

• pre = head：讓pre指向當前節點

• head = next：讓當前節點指向next，相當于移動head節點，直到將head節點移動到原來tail節點的位置

第一次循環執行結束，此時 head 為b，不是null，所以繼續循環，執行流程：

此時 head 為c，不是null，所以繼續循環，執行流程如下：

同理，此時 head 為d，不是null，繼續循環：

這是就完成了單鏈表的反轉步驟。

有了單鏈表反轉的經驗，我們很容易就能實現雙向鏈表的反轉，代碼如下：

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

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

實現把鏈表中給定的值都刪除

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

實現思路：

• 要實現的函數需要給我傳一個頭節點以及給定的數值，頭節點確定鏈表。func(Node head, int num)。

• 函數給不給返回值，返回值是什么？試想，針對鏈表 3 -> 5 -> 4 -> 3 -> 4 -> 5 ，假如要刪除4，那么新鏈表就是 3 -> 5-> 3 -> 5，頭節點仍然是原來的節點3；而如果要刪除值為3的節點呢，刪除后就是 5 -> 4 -> 4 -> 5 ，頭節點變了。因此，我們要設計的這個函數需要返回新鏈表的頭節點。

• 上述分析得知，需要返回新鏈表的頭節點，因此也就是要返回第一個不是給定值的節點（因為給定值的節點都要被刪除掉）。

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

head移動到第一個不需要刪除的位置后，head若為null，表示所有節點都刪除了，直接返回就可以了；若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;
}

這一執行過程圖解如下：

通過上述分析，寫出完整實現代碼：

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

到此，相信大家對“Java鏈表數據結構及使用方法實例分析”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！