帶頭節點的單鏈表的思路及代碼實作（JAVA）
一、什么是的單鏈表
①標準定義
單鏈表是一種鏈式存取的資料結構，用一組地址任意的存盤單元存放線性表中的資料元素，鏈表中的資料是以結點來表示的，每個結點的構成：元素(資料元素的映象) +指標(指示后繼元素存盤位置，元素就是存盤資料的存盤單元，指標就是連接每個結點的地址資料，）
以上是標準定義不太好讓人對單鏈表有直觀的感受，下面我們通過對單鏈表的構成以及存盤資料的方式說明，來更加深刻的理解一下什么是單鏈表，
②個人理解
鏈表存盤資料的方式：
-
鏈表是以節點的方式來存盤資料的
- 那么節點又是什么呢？節點就是鏈表要存盤的每個資料塊，只不過這個資料塊中不僅包含我們要存盤的data，同時又多了一個next用來指向下一個資料節點所在的位置，
-
每個資料節點包含data域，next域：指向下一個資料節點
-
鏈表的各個節點在實際存盤結構上不一定是連續的
- 鏈表就是在添加資料時不去考慮資料所要添加的實際物理位置，只需要通過next域來確定資料節點的邏輯線性結構即可；
-
串列分帶頭節點的鏈表和不帶頭節點的鏈表，根據實際需求來確定使用哪種鏈表（本文以單鏈表進行舉例說明）
- 那么頭節點的作用又是什么呢？其實頭節點中有效域只有next域，用來指向鏈表中第一個節點所在的位置，
鏈表的實際結構圖示：
鏈表的邏輯結構圖示：
二、代碼實作
①定義資料節點類
// 定義資料節點類
class DataNode {
private String data; // data域，要存盤的資料
private DataNode next; // next域，用于指向下一個資料節點地址
// 資料節點構造器
public DataNode(String data) {
this.data = https://www.cnblogs.com/zhao-XH/archive/2023/04/08/data;
}
@Override
public String toString() {
return"DataNode{" +
"data='" + data + '\'' +
'}';
}
public String getData() {
return data;
}
public void setData(String data) {
this.data = https://www.cnblogs.com/zhao-XH/archive/2023/04/08/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 {
// 先初始化一個頭節點，頭節點不用于存盤資料，只用于指向單鏈表的首元素
private DataNode head = new DataNode("");
/**
* 向單鏈表中增加資料節點
*
* @param dataNode 待增加的資料節點
*/
public void addDataNode(DataNode dataNode) {
// 由于head節點不能更改，只用于指向單鏈表的首元素，所以我們需要一個輔助變數接收head的參考
DataNode temp = head;
// 找到鏈表的最后，即結束
while (temp.getNext() != null) {
// 如果沒有找到，就把下一個資料節點的參考賦值給temp，使temp指向下一個資料節點
temp = temp.getNext();
}
// 將找到的最后一個一個資料節點的next域指向新加入的節點地址
temp.setNext(dataNode);
}
/**
* 顯示鏈表的資訊
*/
public void showList() {
// 判斷鏈表是否為空
if (head.getNext() == null){
System.out.println("鏈表為空");
return;
}
// 由于head節點不能更改，只用于指向單鏈表的首元素，所以我們需要一個輔助變數接收head的參考
DataNode temp = head.getNext();
// 遍歷鏈表并列印鏈表中的資料節點
while (temp != null) {
System.out.println(temp);
temp = temp.getNext();
}
}
}
三、實驗測驗單鏈表的代碼準確性
①單鏈表實作以及測驗的整體代碼
/**
* ClassName: SingleLinkedList
* Package: com.zhao.test
* Description: 定義單向鏈表類
*
* @Author XH-zhao
* @Create 2023/3/26 11:09
* @Version 1.0
*/
public class SingleLinkedList {
// 先初始化一個頭節點，頭節點不用于存盤資料，只用于指向單鏈表的首元素
private DataNode head = new DataNode("");
/**
* 向單鏈表中增加資料節點
*
* @param dataNode 待增加的資料節點
*/
public void addDataNode(DataNode dataNode) {
// 由于head節點不能更改，只用于指向單鏈表的首元素，所以我們需要一個輔助變數接收head的參考
DataNode temp = head;
// 找到鏈表的最后，即結束
while (temp.getNext() != null) {
// 如果沒有找到，就把下一個資料節點的參考賦值給temp，使temp指向下一個資料節點
temp = temp.getNext();
}
// 將找到的最后一個一個資料節點的next域指向新加入的節點地址
temp.setNext(dataNode);
}
/**
* 顯示鏈表的資訊
*/
public void showList() {
// 判斷鏈表是否為空
if (head.getNext() == null){
System.out.println("鏈表為空");
return;
}
// 由于head節點不能更改，只用于指向單鏈表的首元素，所以我們需要一個輔助變數接收head的參考
DataNode temp = head.getNext();
// 遍歷鏈表并列印鏈表中的資料節點
while (temp != null) {
System.out.println(temp);
temp = temp.getNext();
}
}
}
// 定義資料節點類
class DataNode {
private String data; // data域，要存盤的資料
private DataNode next; // next域，用于指向下一個資料節點地址
// 資料節點構造器
public DataNode(String data) {
this.data = https://www.cnblogs.com/zhao-XH/archive/2023/04/08/data;
}
@Override
public String toString() {
return"DataNode{" +
"data='" + data + '\'' +
'}';
}
public String getData() {
return data;
}
public void setData(String data) {
this.data = https://www.cnblogs.com/zhao-XH/archive/2023/04/08/data;
}
public DataNode getNext() {
return next;
}
public void setNext(DataNode next) {
this.next = next;
}
}
// 單鏈表測驗類
class SingleLinkedListTest{
public static void main(String[] args) {
// 創建四個資料節點
DataNode dataNode1 = new DataNode("data1");
DataNode dataNode2 = new DataNode("data2");
DataNode dataNode3 = new DataNode("data3");
DataNode dataNode4 = new DataNode("data4");
// 創建單鏈表物件
SingleLinkedList linkedList1 = new SingleLinkedList();
// 將資料節點依次加入鏈表中
linkedList1.addDataNode(dataNode1);
linkedList1.addDataNode(dataNode2);
linkedList1.addDataNode(dataNode3);
linkedList1.addDataNode(dataNode4);
// 展示鏈表內所有資料節點
linkedList1.showList();
}
}
②實驗結果
DataNode{data='https://www.cnblogs.com/zhao-XH/archive/2023/04/08/data1'}
DataNode{data='https://www.cnblogs.com/zhao-XH/archive/2023/04/08/data2'}
DataNode{data='https://www.cnblogs.com/zhao-XH/archive/2023/04/08/data3'}
DataNode{data='https://www.cnblogs.com/zhao-XH/archive/2023/04/08/data4'}
行程已結束,退出代碼0
從上述結果中，我們就實作了帶頭節點的單鏈表的資料存盤設計，
四、實驗總結
在上述的實驗測驗中我們已經完成了單鏈表存盤資料的基本思想，可以讓資料節點根據添加順序依次添加到單鏈表當中，到這里我們僅僅實作了如何使用單鏈表的方式存盤資料元素，那么如果我們想讓資料節點在存盤時，實作一些我們想要的特殊功能（例如在添加資料節點的同時，按照資料節點中的某一個屬性進行排序加入），我們又該如何實作呢？
這里我們更改一下我們的測驗程式，我們將資料節點以4-1-2-3順序加入鏈表中，希望呈現出來還是以1-2-3-4排序好的效果，
public static void main(String[] args) {
// 創建四個資料節點
DataNode dataNode1 = new DataNode("data1");
DataNode dataNode2 = new DataNode("data2");
DataNode dataNode3 = new DataNode("data3");
DataNode dataNode4 = new DataNode("data4");
// 創建單鏈表物件
SingleLinkedList linkedList1 = new SingleLinkedList();
// 將資料節點以4-1-2-3順序加入鏈表中
linkedList1.addDataNode(dataNode4);
linkedList1.addDataNode(dataNode1);
linkedList1.addDataNode(dataNode2);
linkedList1.addDataNode(dataNode3);
// 展示鏈表內所有資料節點
linkedList1.showList();
}
DataNode{data='https://www.cnblogs.com/zhao-XH/archive/2023/04/08/data4'}
DataNode{data='https://www.cnblogs.com/zhao-XH/archive/2023/04/08/data1'}
DataNode{data='https://www.cnblogs.com/zhao-XH/archive/2023/04/08/data2'}
DataNode{data='https://www.cnblogs.com/zhao-XH/archive/2023/04/08/data3'}
行程已結束,退出代碼0
很顯然，我們的代碼只能按照節點加入順序來加入節點，后續我們將在《JAVA實作節點加入到單鏈表時按需求排序》一文中實作上述我們想要的效果！
番外：重復增添資料節點到新鏈表時BUG思考
如果上述實驗中我們按照如下方式去測驗代碼
public static void main(String[] args) {
// 創建四個資料節點
DataNode dataNode1 = new DataNode("data1");
DataNode dataNode2 = new DataNode("data2");
DataNode dataNode3 = new DataNode("data3");
DataNode dataNode4 = new DataNode("data4");
// 創建單鏈表物件
SingleLinkedList linkedList1 = new SingleLinkedList();
// 將資料節點依次加入鏈表中
linkedList1.addDataNode(dataNode1);
linkedList1.addDataNode(dataNode2);
linkedList1.addDataNode(dataNode3);
linkedList1.addDataNode(dataNode4);
// 展示鏈表內所有資料節點
linkedList1.showList();
// 創建鏈表2
SingleLinkedList linkedList2 = new SingleLinkedList();
// 將資料節點打亂順序加入到鏈表2中
linkedList2.addDataNode(dataNode1);
linkedList2.addDataNode(dataNode4);
linkedList2.addDataNode(dataNode3);
linkedList2.addDataNode(dataNode2);
// 展示鏈表2內所有資料節點
linkedList2.showList();
}
運行結果：
DataNode{data='https://www.cnblogs.com/zhao-XH/archive/2023/04/08/data1'}
DataNode{data='https://www.cnblogs.com/zhao-XH/archive/2023/04/08/data2'}
DataNode{data='https://www.cnblogs.com/zhao-XH/archive/2023/04/08/data3'}
DataNode{data='https://www.cnblogs.com/zhao-XH/archive/2023/04/08/data4'}
// 程式堵塞在這里，無法向下進行！
請思考造成上述問題的原因所在？
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/549524.html
標籤：其他