Java數據結構之單鏈表是什么

這篇文章給大家分享的是有關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中的集合主要分為四類：1、List列表：有序的，可重復的；2、Queue隊列：有序，可重復的；3、Set集合：不可重復；4、Map映射：無序，鍵唯一，值不唯一。

感謝各位的閱讀！關于“Java數據結構之單鏈表是什么”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！