Java鏈表數(shù)據(jù)結(jié)構(gòu)及其簡單使用方法解析

第Java鏈表數(shù)據(jù)結(jié)構(gòu)及其簡單使用方法解析目錄認(rèn)識鏈表結(jié)構(gòu)單向鏈表雙向鏈表加深對鏈表結(jié)構(gòu)的理解實(shí)現(xiàn)單向和雙向鏈表的反轉(zhuǎn)實(shí)現(xiàn)把鏈表中給定的值都刪除小結(jié)

認(rèn)識鏈表結(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)：

publicclassNode{

publicintvalue;

publicNodenext;

publicNode(intvalue){

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)：

publicclassDoubleNode{

publicintvalue;

publicDoubleNodepre;

publicDoubleNodenext;

publicDoubleNode(intvalue){

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)：

publicstaticNodereverseNode(Nodehead){

Nodepre=null;

Nodenext=null;

//最終讓head指向null

while(head!=null){

next=head.next;

head.next=pre;

pre=head;

head=next;

returnpre;

}

我們來模擬一下這個(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)于移動head節(jié)點(diǎn)，直到將head節(jié)點(diǎn)移動到原來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)，代碼如下：

publicDoubleNodereverseDoubleNode(DoubleNodehead){

DoubleNodepre=null;

DoubleNodenext=null;

while(head!=null){

next=head.next;

//操作（移動）當(dāng)前節(jié)點(diǎn)

head.next=pre;

head.pre=next;

pre=head;

head=next;

returnpre;

}

實(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(Nodehead,intnum)。函數(shù)給不給返回值，返回值是什么？試想，針對鏈表3-5-4-3-4-5，假如要刪除4，那么新鏈表就是3-5-3-5，頭節(jié)點(diǎn)仍然是原來的節(jié)點(diǎn)3；而如果要刪除值為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移動到第一個(gè)不需要刪除的位置：邊界條件

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)

returnhead;

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

Nodepre=head;

Nodecur=head;

while(cur!=null){

if(cur.value==num){

pre.next=cur.next;

}else{

pre=cur;

cur=cur.next;

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

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

publicstaticNoderemove(Nodehead,intnum){

while(head!=null){

if(head.value!=num){

break;

head=head.next;

Nodepre=head;

Nodecur=head;

while(cur!=null){

if(cur.value==num){

pre.next=cur.