|
+ 目錄認(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語(yǔ)言表示一下單向鏈表的結(jié)構(gòu)：
1 2 3 4 5 6 7 8 | 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還可以定義成泛型的。
雙向鏈表
我們?cè)賮?lái)看一下雙向鏈表的結(jié)構(gòu)：
雙向鏈表中的節(jié)點(diǎn)有數(shù)值域，和指向它前一個(gè)節(jié)點(diǎn)的引用以及指向它后一個(gè)節(jié)點(diǎn)的引用，據(jù)此我們可以定義出
雙向鏈表的結(jié)構(gòu)：
1 2 3 4 5 6 7 8 9 | public class DoubleNode {
public int value;
public DoubleNode pre;
public DoubleNode next;
public DoubleNode(int value) {
this.value = value;
}
}
|
加深對(duì)鏈表結(jié)構(gòu)的理解
實(shí)現(xiàn)單向和雙向鏈表的反轉(zhuǎn)
說(shuō)明：
對(duì)于一個(gè)鏈表如圖所示：
反轉(zhuǎn)的意思是，將原來(lái)鏈表上的節(jié)點(diǎn)指針指向反轉(zhuǎn)，原來(lái)的指向是：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ù)的過(guò)程是調(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)：
1 2 3 4 5 6 7 8 9 10 11 12 | 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;
}
|
我們來(lái)模擬一下這個(gè)函數(shù)的執(zhí)行過(guò)程。
鏈表原始狀態(tài)：
方法開(kā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)從原來(lái)指向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)到原來(lái)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)，代碼如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | 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ù)給不給返回值，返回值是什么？試想，針對(duì)鏈表
3 -> 5 -> 4 -> 3 -> 4 -> 5 ，假如要?jiǎng)h除4，那么新鏈表就是 3 -> 5-> 3 -> 5，頭節(jié)點(diǎn)仍然是原來(lái)的節(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)都要被刪除掉）。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | //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處開(kāi)始往next走，遇到給定值就跳過(guò)。
1 2 3 4 5 6 7 8 9 10 | Node pre = head;
Node cur = head;
while (cur != null) {
if (cur.value == num) {
pre.next = cur.next;
} else {
pre = cur;
}
cur = cur.next;
}
|
這一執(zhí)行過(guò)程圖解如下：
通過(guò)上述分析，寫(xiě)出完整實(shí)現(xiàn)代碼：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | 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é)
針對(duì)鏈表這種數(shù)據(jù)結(jié)構(gòu)進(jìn)行了一些簡(jiǎn)單的分析，通過(guò)兩個(gè)例子熟悉了鏈表的結(jié)構(gòu)。
針對(duì)鏈表的操作，需要注意的就是指針指向以及邊界問(wèn)題，后續(xù)關(guān)于鏈表的算法還會(huì)遇到。
到此這篇關(guān)于Java鏈表數(shù)據(jù)結(jié)構(gòu)及其簡(jiǎn)單使用方法解析的文章就介紹到這了,更多相關(guān)Java鏈表數(shù)據(jù)結(jié)構(gòu)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
|
