一、圖示

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

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

實(shí)際中鏈表的結(jié)構(gòu)非常多樣，以下情況組合起來(lái)就有8種鏈表結(jié)構(gòu)：

單向、雙向

帶頭、不帶頭

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

今天，我們實(shí)現(xiàn)的是一個(gè) 單向 無(wú)頭 非循環(huán)的鏈表。

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

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

（1）定義一個(gè)節(jié)點(diǎn)類(lèi)型

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

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

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

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

之后我們?cè)?MyListNode 的類(lèi)中實(shí)現(xiàn)單鏈表的各種方法。

（2）頭插法

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

代碼實(shí)現(xiàn)：

1.定義一個(gè)插入的節(jié)點(diǎn)

 ListNode cur = new ListNode(2);

此時(shí)我們就創(chuàng)建了一個(gè)val 為2 的節(jié)點(diǎn)。

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

這里分兩種情況，

第一次插入節(jié)點(diǎn)

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

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

代碼實(shí)現(xiàn)：

（3）尾插法

和頭插法類(lèi)似，同樣插入一個(gè)節(jié)點(diǎn)，在鏈表的最后。

這里插入也分為兩種情況

第一次插入節(jié)點(diǎn)

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

代碼實(shí)現(xiàn)：

（4）根據(jù)下標(biāo)插入節(jié)點(diǎn)

第一個(gè)數(shù)據(jù)節(jié)點(diǎn)為0號(hào)下標(biāo)，任意位置插入節(jié)點(diǎn)。

還以上面的鏈表為例，我們想將新的節(jié)點(diǎn)插入到2 號(hào)位置

如果想插到2號(hào)位置，我們需要改變?cè)瓉?lái)的 1號(hào)位置節(jié)點(diǎn)和2號(hào)位置節(jié)點(diǎn)的相關(guān)屬性。

思路實(shí)現(xiàn)：

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

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

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

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

查找 index-1

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

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

代碼實(shí)現(xiàn)過(guò)程

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

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

遍歷鏈表，走過(guò)每一個(gè)節(jié)點(diǎn)，如果 cur.val == key，則 return ture ，遍歷完后還未找到 key，那么return false.

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

思路實(shí)現(xiàn)：

代碼實(shí)現(xiàn)：

（7）得到單鏈表的長(zhǎng)度

（8）單鏈表打印展示

不能是this.head.next != null 這樣寫(xiě) 最后一個(gè)節(jié)點(diǎn)是不能被打印的

（9）節(jié)點(diǎn)的回收

節(jié)點(diǎn)的回收有兩種方式：

  1.暴力法

直接將head 置空

  2. 挨個(gè)置空

遍歷單鏈表，將每一個(gè)節(jié)點(diǎn)的next都置為 null.

四、完整代碼的展示

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

最新評(píng)論