带头节点的单链表的思路及代码实现（JAVA）

一、什么是的单链表

①标准定义

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) +指针(指示后继元素存储位置，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。）

以上是标准定义不太好让人对单链表有直观的感受，下面我们通过对单链表的构成以及存储数据的方式说明，来更加深刻的理解一下什么是单链表。

②个人理解

链表存储数据的方式：

1. 链表是以节点的方式来存储数据的

   • 那么节点又是什么呢？节点就是链表要存储的每个数据块，只不过这个数据块中不仅包含我们要存储的data，同时又多了一个next用来指向下一个数据节点所在的位置。

2. 每个数据节点包含data域，next域：指向下一个数据节点

3. 链表的各个节点在实际存储结构上不一定是连续的

   • 链表就是在添加数据时不去考虑数据所要添加的实际物理位置，只需要通过next域来确定数据节点的逻辑线性结构即可；

4. 列表分带头节点的链表和不带头节点的链表，根据实际需求来确定使用哪种链表（本文以单链表进行举例说明）

   • 那么头节点的作用又是什么呢？其实头节点中有效域只有next域，用来指向链表中第一个节点所在的位置。

链表的实际结构图示：

链表的逻辑结构图示：

二、代码实现

①定义数据节点类

// 定义数据节点类
class DataNode {

    private String data;    // data域，要存储的数据
    private DataNode next;  // next域，用于指向下一个数据节点地址

    // 数据节点构造器
    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 {

    // 先初始化一个头节点，头节点不用于存储数据，只用于指向单链表的首元素
    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 = 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) {

        // 创建四个数据节点
        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='data1'}
DataNode{data='data2'}
DataNode{data='data3'}
DataNode{data='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='data4'}
DataNode{data='data1'}
DataNode{data='data2'}
DataNode{data='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='data1'}
DataNode{data='data2'}
DataNode{data='data3'}
DataNode{data='data4'}
// 程序堵塞在这里，无法向下进行！

请思考造成上述问题的原因所在？