一、圖示
二、鏈表的概念及結構
鏈表是一種物理存儲結構上非連續(xù)存儲結構，數據元素的邏輯順序是通過鏈表中的引用鏈接次序實現的 。
實際中鏈表的結構非常多樣，以下情況組合起來就有8種鏈表結構：
單向、雙向
帶頭、不帶頭
循環(huán)、非循環(huán)
今天，我們實現的是一個 單向 無頭 非循環(huán)的鏈表。
下面是此鏈表的結構組成。
三、單鏈表的實現
（1）定義一個節(jié)點類型
我們創(chuàng)建一個 ListNode 的類作為節(jié)點類型，那么我們如何定義成員屬性呢？
通過上面的結構分析，我們需要定義兩個成員變量 val --作為該節(jié)點的存儲的數值， next – 保存下一個節(jié)點的地址/引用。
同時定義之后，他們的默認值為 0 ，null ，所以要想賦予這個節(jié)點數值，要寫一個構造方法去首先保存數值。
這里我們提供了兩個構造方法，一個是實現提供數值的節(jié)點，另一個是沒有提供數值的節(jié)點，方便我們之后使用。
之后我們在 MyListNode 的類中實現單鏈表的各種方法。
（2）頭插法
?
以上述結構為例，這個單鏈表沒有專門的傀儡節(jié)點來充當頭節(jié)點，首個節(jié)點就定義為頭節(jié)點，所以頭插法，就是我們定義一個節(jié)點，插在這個鏈表的最前面，作為新的 head。
代碼實現：
1.定義一個插入的節(jié)點
ListNode cur = new ListNode(2);
此時我們就創(chuàng)建了一個val 為2 的節(jié)點。
2.插在頭節(jié)點的前面
這里分兩種情況，
第一次插入節(jié)點
不是第一次插入節(jié)點
頭插之后的結構：
代碼實現：
（3）尾插法
和頭插法類似，同樣插入一個節(jié)點，在鏈表的最后。
這里插入也分為兩種情況
第一次插入節(jié)點
不是第一次插入節(jié)點
代碼實現：
（4）根據下標插入節(jié)點
第一個數據節(jié)點為0號下標，任意位置插入節(jié)點。
還以上面的鏈表為例，我們想將新的節(jié)點插入到2 號位置
如果想插到2號位置，我們需要改變原來的 1號位置節(jié)點和2號位置節(jié)點的相關屬性。
思路實現：
??1.先判斷傳入的 index 下標位置是否合法
??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;代碼實現過程
（5）查找關鍵字
以上面的鏈表為例，我們現在要查找這個鏈表中是否出現 val=20 的節(jié)點，如果存在，那么返回true，如果不存在，則返回 false.
遍歷鏈表，走過每一個節(jié)點，如果 cur.val == key，則 return ture ，遍歷完后還未找到 key，那么return false.
（6）刪除第一次出現的關鍵字
思路實現：
代碼實現：
（7）得到單鏈表的長度
（8）單鏈表打印展示
不能是this.head.next != null 這樣寫 最后一個節(jié)點是不能被打印的
（9）節(jié)點的回收
節(jié)點的回收有兩種方式：
??1.暴力法
直接將head 置空
??2. 挨個置空
遍歷單鏈表，將每一個節(jié)點的next都置為 null.
四、完整代碼的展示
到這里，本篇關于Java代碼實現數據結構中單鏈表的文章就介紹結束了，如果您還想要了解更多關于用Java實現其他數據結構的內容，可以多多關注W3Cschool相關內容的文！
