Java數據結構之單鏈表詳解

一、圖示

在這裡插入圖片描述

二、鏈表的概念及結構

鏈表是一種物理存儲結構上非連續存儲結構,數據元素的邏輯順序是通過鏈表中的引用鏈接次序實現的 。

實際中鏈表的結構非常多樣,以下情況組合起來就有8種鏈表結構:

單向、雙向

帶頭、不帶頭

循環、非循環

今天,我們實現的是一個 單向 無頭 非循環的鏈表。

下面是此鏈表的結構組成。

在這裡插入圖片描述

三、單鏈表的實現

(1)定義一個節點類型

我們創建一個 ListNode 的類作為節點類型,那麼我們如何定義成員屬性呢?

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

同時定義之後,他們的默認值為 0 ,null ,所以要想賦予這個節點數值,要寫一個構造方法去首先保存數值。

在這裡插入圖片描述

這裡我們提供瞭兩個構造方法,一個是實現提供數值的節點,另一個是沒有提供數值的節點,方便我們之後使用。

之後我們在 MyListNode 的類中實現單鏈表的各種方法。

在這裡插入圖片描述

(2)頭插法

在這裡插入圖片描述

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

代碼實現:

1.定義一個插入的節點

 ListNode cur = new ListNode(2);

在這裡插入圖片描述

此時我們就創建瞭一個val 為2 的節點。

2.插在頭節點的前面

這裡分兩種情況,

第一次插入節點

不是第一次插入節點

頭插之後的結構:

在這裡插入圖片描述

代碼實現:

在這裡插入圖片描述

(3)尾插法

和頭插法類似,同樣插入一個節點,在鏈表的最後。

在這裡插入圖片描述

這裡插入也分為兩種情況

第一次插入節點

不是第一次插入節點

代碼實現:

在這裡插入圖片描述

(4)根據下標插入節點

第一個數據節點為0號下標,任意位置插入節點。

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

在這裡插入圖片描述

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

思路實現:

  1.先判斷傳入的 index 下標位置是否合法

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

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

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

查找 index-1

在這裡插入圖片描述

修改 prev節點的屬性 以及 新節點的屬性

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

代碼實現過程

在這裡插入圖片描述

(5)查找關鍵字

在這裡插入圖片描述

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

遍歷鏈表,走過每一個節點,如果 cur.val == key,則 return ture ,遍歷完後還未找到 key,那麼return false.

在這裡插入圖片描述

(6)刪除第一次出現的關鍵字

在這裡插入圖片描述

思路實現:

在這裡插入圖片描述

代碼實現:

在這裡插入圖片描述

(7)得到單鏈表的長度

在這裡插入圖片描述

(8)單鏈表打印展示

在這裡插入圖片描述

不能是this.head.next != null 這樣寫 最後一個節點是不能被打印的

(9)節點的回收

節點的回收有兩種方式:

  1.暴力法

直接將head 置空

  2. 挨個置空

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

在這裡插入圖片描述

四、完整代碼的展示

在這裡插入圖片描述

到此這篇關於Java數據結構之單鏈表詳解的文章就介紹到這瞭,更多相關Java單鏈表內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!

推薦閱讀: