App下載

Java代碼詳解數(shù)據(jù)結(jié)構(gòu)中單鏈表的實現(xiàn)

你是我的所有夢 2021-08-18 10:48:52 瀏覽數(shù) (3310)
反饋

一、圖示

在這里插入圖片描述

二、鏈表的概念及結(jié)構(gòu)

鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)存儲結(jié)構(gòu),數(shù)據(jù)元素的邏輯順序是通過鏈表中的引用鏈接次序?qū)崿F(xiàn)的 。

實際中鏈表的結(jié)構(gòu)非常多樣,以下情況組合起來就有8種鏈表結(jié)構(gòu):

單向、雙向

帶頭、不帶頭

循環(huán)、非循環(huán)

今天,我們實現(xiàn)的是一個 單向 無頭 非循環(huán)的鏈表。

下面是此鏈表的結(jié)構(gòu)組成。

在這里插入圖片描述

三、單鏈表的實現(xiàn)

(1)定義一個節(jié)點類型

我們創(chuàng)建一個 ListNode 的類作為節(jié)點類型,那么我們?nèi)绾味x成員屬性呢?

通過上面的結(jié)構(gòu)分析,我們需要定義兩個成員變量 val --作為該節(jié)點的存儲的數(shù)值, next – 保存下一個節(jié)點的地址/引用。

同時定義之后,他們的默認(rèn)值為 0 ,null ,所以要想賦予這個節(jié)點數(shù)值,要寫一個構(gòu)造方法去首先保存數(shù)值。

在這里插入圖片描述

這里我們提供了兩個構(gòu)造方法,一個是實現(xiàn)提供數(shù)值的節(jié)點,另一個是沒有提供數(shù)值的節(jié)點,方便我們之后使用。

之后我們在 MyListNode 的類中實現(xiàn)單鏈表的各種方法。

在這里插入圖片描述

(2)頭插法

在這里插入圖片描述?

以上述結(jié)構(gòu)為例,這個單鏈表沒有專門的傀儡節(jié)點來充當(dāng)頭節(jié)點,首個節(jié)點就定義為頭節(jié)點,所以頭插法,就是我們定義一個節(jié)點,插在這個鏈表的最前面,作為新的 head。

代碼實現(xiàn):

1.定義一個插入的節(jié)點

 ListNode cur = new ListNode(2);

在這里插入圖片描述

此時我們就創(chuàng)建了一個val 為2 的節(jié)點。

2.插在頭節(jié)點的前面

這里分兩種情況,

第一次插入節(jié)點

不是第一次插入節(jié)點

頭插之后的結(jié)構(gòu):

在這里插入圖片描述

代碼實現(xiàn):

在這里插入圖片描述

(3)尾插法

和頭插法類似,同樣插入一個節(jié)點,在鏈表的最后。

在這里插入圖片描述

這里插入也分為兩種情況

第一次插入節(jié)點

不是第一次插入節(jié)點

代碼實現(xiàn):

在這里插入圖片描述

(4)根據(jù)下標(biāo)插入節(jié)點

第一個數(shù)據(jù)節(jié)點為0號下標(biāo),任意位置插入節(jié)點。

還以上面的鏈表為例,我們想將新的節(jié)點插入到2 號位置

在這里插入圖片描述

如果想插到2號位置,我們需要改變原來的 1號位置節(jié)點和2號位置節(jié)點的相關(guān)屬性。

思路實現(xiàn):

??1.先判斷傳入的 index 下標(biāo)位置是否合法

??2.如果傳入的index==0,頭插法

??3.如果傳入的index==sizeof(),尾插法

??4.如果 sizeof() > index > 0 在鏈表中間插入,我們首先要找到 index-1 位置的節(jié)點 prev

查找 index-1

在這里插入圖片描述

修改 prev節(jié)點的屬性 以及 新節(jié)點的屬性

  node.next = prev.next
     prev.next = node;

代碼實現(xiàn)過程

在這里插入圖片描述

(5)查找關(guān)鍵字

在這里插入圖片描述

以上面的鏈表為例,我們現(xiàn)在要查找這個鏈表中是否出現(xiàn) val=20 的節(jié)點,如果存在,那么返回true,如果不存在,則返回 false.

遍歷鏈表,走過每一個節(jié)點,如果 cur.val == key,則 return ture ,遍歷完后還未找到 key,那么return false.

在這里插入圖片描述

(6)刪除第一次出現(xiàn)的關(guān)鍵字

在這里插入圖片描述

思路實現(xiàn):

在這里插入圖片描述

代碼實現(xiàn):

在這里插入圖片描述

(7)得到單鏈表的長度

在這里插入圖片描述

(8)單鏈表打印展示

在這里插入圖片描述

不能是this.head.next != null 這樣寫 最后一個節(jié)點是不能被打印的

(9)節(jié)點的回收

節(jié)點的回收有兩種方式:

??1.暴力法

直接將head 置空

??2. 挨個置空

遍歷單鏈表,將每一個節(jié)點的next都置為 null.

在這里插入圖片描述

四、完整代碼的展示

在這里插入圖片描述

到這里,本篇關(guān)于Java代碼實現(xiàn)數(shù)據(jù)結(jié)構(gòu)中單鏈表的文章就介紹結(jié)束了,如果您還想要了解更多關(guān)于用Java實現(xiàn)其他數(shù)據(jù)結(jié)構(gòu)的內(nèi)容,可以多多關(guān)注W3Cschool相關(guān)內(nèi)容的文!


1 人點贊