帶頭節(jié)點的單鏈表的思路及代碼實現(xiàn)（JAVA）
一、什么是的單鏈表
①標(biāo)準(zhǔn)定義
單鏈表是一種鏈?zhǔn)酱嫒〉臄?shù)據(jù)結(jié)構(gòu)，用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)元素。鏈表中的數(shù)據(jù)是以結(jié)點來表示的，每個結(jié)點的構(gòu)成：元素(數(shù)據(jù)元素的映象) +指針(指示后繼元素存儲位置，元素就是存儲數(shù)據(jù)的存儲單元，指針就是連接每個結(jié)點的地址數(shù)據(jù)。）
以上是標(biāo)準(zhǔn)定義不太好讓人對單鏈表有直觀的感受，下面我們通過對單鏈表的構(gòu)成以及存儲數(shù)據(jù)的方式說明，來更加深刻的理解一下什么是單鏈表。
②個人理解
鏈表存儲數(shù)據(jù)的方式：
-
鏈表是以節(jié)點的方式來存儲數(shù)據(jù)的
- 那么節(jié)點又是什么呢？節(jié)點就是鏈表要存儲的每個數(shù)據(jù)塊，只不過這個數(shù)據(jù)塊中不僅包含我們要存儲的data，同時又多了一個next用來指向下一個數(shù)據(jù)節(jié)點所在的位置。
-
每個數(shù)據(jù)節(jié)點包含data域，next域：指向下一個數(shù)據(jù)節(jié)點
-
鏈表的各個節(jié)點在實際存儲結(jié)構(gòu)上不一定是連續(xù)的
- 鏈表就是在添加數(shù)據(jù)時不去考慮數(shù)據(jù)所要添加的實際物理位置，只需要通過next域來確定數(shù)據(jù)節(jié)點的邏輯線性結(jié)構(gòu)即可；
-
列表分帶頭節(jié)點的鏈表和不帶頭節(jié)點的鏈表，根據(jù)實際需求來確定使用哪種鏈表（本文以單鏈表進(jìn)行舉例說明）
- 那么頭節(jié)點的作用又是什么呢？其實頭節(jié)點中有效域只有next域，用來指向鏈表中第一個節(jié)點所在的位置。
鏈表的實際結(jié)構(gòu)圖示：
鏈表的邏輯結(jié)構(gòu)圖示：
二、代碼實現(xiàn)
①定義數(shù)據(jù)節(jié)點類
// 定義數(shù)據(jù)節(jié)點類
class DataNode {
private String data; // data域，要存儲的數(shù)據(jù)
private DataNode next; // next域，用于指向下一個數(shù)據(jù)節(jié)點地址
// 數(shù)據(jù)節(jié)點構(gòu)造器
public DataNode(String data) {
this.data = data;
}
@Override
public String toString() {
return "DataNode{" +
"data='" + data + '\'' +
'}';
}
public String getData() {
return data;
}
public void setData(String data) {
this.data = data;
}
public DataNode getNext() {
return next;
}
public void setNext(DataNode next) {
this.next = next;
}
}
②定義單鏈表類
/**
* ClassName: SingleLinkedList
* Package: com.zhao.test
* Description: 定義單向鏈表類
*
* @Author XH-zhao
* @Create 2023/3/26 11:09
* @Version 1.0
*/
public class SingleLinkedList {
// 先初始化一個頭節(jié)點，頭節(jié)點不用于存儲數(shù)據(jù)，只用于指向單鏈表的首元素
private DataNode head = new DataNode("");
/**
* 向單鏈表中增加數(shù)據(jù)節(jié)點
*
* @param dataNode 待增加的數(shù)據(jù)節(jié)點
*/
public void addDataNode(DataNode dataNode) {
// 由于head節(jié)點不能更改，只用于指向單鏈表的首元素，所以我們需要一個輔助變量接收head的引用
DataNode temp = head;
// 找到鏈表的最后，即結(jié)束
while (temp.getNext() != null) {
// 如果沒有找到，就把下一個數(shù)據(jù)節(jié)點的引用賦值給temp，使temp指向下一個數(shù)據(jù)節(jié)點
temp = temp.getNext();
}
// 將找到的最后一個一個數(shù)據(jù)節(jié)點的next域指向新加入的節(jié)點地址
temp.setNext(dataNode);
}
/**
* 顯示鏈表的信息
*/
public void showList() {
// 判斷鏈表是否為空
if (head.getNext() == null){
System.out.println("鏈表為空");
return;
}
// 由于head節(jié)點不能更改，只用于指向單鏈表的首元素，所以我們需要一個輔助變量接收head的引用
DataNode temp = head.getNext();
// 遍歷鏈表并打印鏈表中的數(shù)據(jù)節(jié)點
while (temp != null) {
System.out.println(temp);
temp = temp.getNext();
}
}
}
三、實驗測試單鏈表的代碼準(zhǔn)確性
①單鏈表實現(xiàn)以及測試的整體代碼
/**
* ClassName: SingleLinkedList
* Package: com.zhao.test
* Description: 定義單向鏈表類
*
* @Author XH-zhao
* @Create 2023/3/26 11:09
* @Version 1.0
*/
public class SingleLinkedList {
// 先初始化一個頭節(jié)點，頭節(jié)點不用于存儲數(shù)據(jù)，只用于指向單鏈表的首元素
private DataNode head = new DataNode("");
/**
* 向單鏈表中增加數(shù)據(jù)節(jié)點
*
* @param dataNode 待增加的數(shù)據(jù)節(jié)點
*/
public void addDataNode(DataNode dataNode) {
// 由于head節(jié)點不能更改，只用于指向單鏈表的首元素，所以我們需要一個輔助變量接收head的引用
DataNode temp = head;
// 找到鏈表的最后，即結(jié)束
while (temp.getNext() != null) {
// 如果沒有找到，就把下一個數(shù)據(jù)節(jié)點的引用賦值給temp，使temp指向下一個數(shù)據(jù)節(jié)點
temp = temp.getNext();
}
// 將找到的最后一個一個數(shù)據(jù)節(jié)點的next域指向新加入的節(jié)點地址
temp.setNext(dataNode);
}
/**
* 顯示鏈表的信息
*/
public void showList() {
// 判斷鏈表是否為空
if (head.getNext() == null){
System.out.println("鏈表為空");
return;
}
// 由于head節(jié)點不能更改，只用于指向單鏈表的首元素，所以我們需要一個輔助變量接收head的引用
DataNode temp = head.getNext();
// 遍歷鏈表并打印鏈表中的數(shù)據(jù)節(jié)點
while (temp != null) {
System.out.println(temp);
temp = temp.getNext();
}
}
}
// 定義數(shù)據(jù)節(jié)點類
class DataNode {
private String data; // data域，要存儲的數(shù)據(jù)
private DataNode next; // next域，用于指向下一個數(shù)據(jù)節(jié)點地址
// 數(shù)據(jù)節(jié)點構(gòu)造器
public DataNode(String data) {
this.data = data;
}
@Override
public String toString() {
return "DataNode{" +
"data='" + data + '\'' +
'}';
}
public String getData() {
return data;
}
public void setData(String data) {
this.data = data;
}
public DataNode getNext() {
return next;
}
public void setNext(DataNode next) {
this.next = next;
}
}
// 單鏈表測試類
class SingleLinkedListTest{
public static void main(String[] args) {
// 創(chuàng)建四個數(shù)據(jù)節(jié)點
DataNode dataNode1 = new DataNode("data1");
DataNode dataNode2 = new DataNode("data2");
DataNode dataNode3 = new DataNode("data3");
DataNode dataNode4 = new DataNode("data4");
// 創(chuàng)建單鏈表對象
SingleLinkedList linkedList1 = new SingleLinkedList();
// 將數(shù)據(jù)節(jié)點依次加入鏈表中
linkedList1.addDataNode(dataNode1);
linkedList1.addDataNode(dataNode2);
linkedList1.addDataNode(dataNode3);
linkedList1.addDataNode(dataNode4);
// 展示鏈表內(nèi)所有數(shù)據(jù)節(jié)點
linkedList1.showList();
}
}
②實驗結(jié)果
DataNode{data='data1'}
DataNode{data='data2'}
DataNode{data='data3'}
DataNode{data='data4'}
進(jìn)程已結(jié)束,退出代碼0
從上述結(jié)果中，我們就實現(xiàn)了帶頭節(jié)點的單鏈表的數(shù)據(jù)存儲設(shè)計。
四、實驗總結(jié)
在上述的實驗測試中我們已經(jīng)完成了單鏈表存儲數(shù)據(jù)的基本思想。可以讓數(shù)據(jù)節(jié)點根據(jù)添加順序依次添加到單鏈表當(dāng)中。到這里我們僅僅實現(xiàn)了如何使用單鏈表的方式存儲數(shù)據(jù)元素。那么如果我們想讓數(shù)據(jù)節(jié)點在存儲時，實現(xiàn)一些我們想要的特殊功能（例如在添加數(shù)據(jù)節(jié)點的同時，按照數(shù)據(jù)節(jié)點中的某一個屬性進(jìn)行排序加入），我們又該如何實現(xiàn)呢？
這里我們更改一下我們的測試程序，我們將數(shù)據(jù)節(jié)點以4-1-2-3順序加入鏈表中，希望呈現(xiàn)出來還是以1-2-3-4排序好的效果。
public static void main(String[] args) {
// 創(chuàng)建四個數(shù)據(jù)節(jié)點
DataNode dataNode1 = new DataNode("data1");
DataNode dataNode2 = new DataNode("data2");
DataNode dataNode3 = new DataNode("data3");
DataNode dataNode4 = new DataNode("data4");
// 創(chuàng)建單鏈表對象
SingleLinkedList linkedList1 = new SingleLinkedList();
// 將數(shù)據(jù)節(jié)點以4-1-2-3順序加入鏈表中
linkedList1.addDataNode(dataNode4);
linkedList1.addDataNode(dataNode1);
linkedList1.addDataNode(dataNode2);
linkedList1.addDataNode(dataNode3);
// 展示鏈表內(nèi)所有數(shù)據(jù)節(jié)點
linkedList1.showList();
}
DataNode{data='data4'}
DataNode{data='data1'}
DataNode{data='data2'}
DataNode{data='data3'}
進(jìn)程已結(jié)束,退出代碼0
很顯然，我們的代碼只能按照節(jié)點加入順序來加入節(jié)點。后續(xù)我們將在《JAVA實現(xiàn)節(jié)點加入到單鏈表時按需求排序》一文中實現(xiàn)上述我們想要的效果！
番外：重復(fù)增添數(shù)據(jù)節(jié)點到新鏈表時BUG思考
如果上述實驗中我們按照如下方式去測試代碼
public static void main(String[] args) {
// 創(chuàng)建四個數(shù)據(jù)節(jié)點
DataNode dataNode1 = new DataNode("data1");
DataNode dataNode2 = new DataNode("data2");
DataNode dataNode3 = new DataNode("data3");
DataNode dataNode4 = new DataNode("data4");
// 創(chuàng)建單鏈表對象
SingleLinkedList linkedList1 = new SingleLinkedList();
// 將數(shù)據(jù)節(jié)點依次加入鏈表中
linkedList1.addDataNode(dataNode1);
linkedList1.addDataNode(dataNode2);
linkedList1.addDataNode(dataNode3);
linkedList1.addDataNode(dataNode4);
// 展示鏈表內(nèi)所有數(shù)據(jù)節(jié)點
linkedList1.showList();
// 創(chuàng)建鏈表2
SingleLinkedList linkedList2 = new SingleLinkedList();
// 將數(shù)據(jù)節(jié)點打亂順序加入到鏈表2中
linkedList2.addDataNode(dataNode1);
linkedList2.addDataNode(dataNode4);
linkedList2.addDataNode(dataNode3);
linkedList2.addDataNode(dataNode2);
// 展示鏈表2內(nèi)所有數(shù)據(jù)節(jié)點
linkedList2.showList();
}
運行結(jié)果：文章來源：http://www.zghlxwxcb.cn/news/detail-403275.html
DataNode{data='data1'}
DataNode{data='data2'}
DataNode{data='data3'}
DataNode{data='data4'}
// 程序堵塞在這里，無法向下進(jìn)行！
請思考造成上述問題的原因所在？文章來源地址http://www.zghlxwxcb.cn/news/detail-403275.html
到了這里，關(guān)于帶頭節(jié)點的單鏈表的思路及代碼實現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
