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

这篇具有很好参考价值的文章主要介绍了带头节点的单链表的思路及代码实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

带头节点的单链表的思路及代码实现(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'}
// 程序堵塞在这里,无法向下进行!

请思考造成上述问题的原因所在?文章来源地址https://www.toymoban.com/news/detail-403275.html

到了这里,关于带头节点的单链表的思路及代码实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】——单链表的基本操作(带头结点)

            单链表解决了顺序表需要大量连续存储单元的缺点,但单链表附加指针域, 存储密度较顺序表低(考点!!) 。由于单链表的元素离散地分布在存储空间中,所以单链表是 非随机存取 的存储结构,即不能直接找到表中某个特定的结点。当查找某个特定结点时,需要

    2024年02月05日
    浏览(51)
  • 带头结点单链表【详细解析+完整代码】

    它是通过一组任意的储存单元来存储线性表中的数据元素。为建立线性关系,每个结点需要一个指针域以及指向下一结点的指针域。带头结点链表头节点不存储数据。 结点结构: 带头结点链表结构: 保证了每个结点都有前驱结点,因此在链表上第一个结点的操作与其他结点操

    2024年04月15日
    浏览(43)
  • 单链表的基本操作代码实现(C语言版)

    目录 前言: 单链表的基本操作 准备工作(头文件、各种宏定义以及结构体定义) 一.较简单操作 1.单链表的初始化 2.判断单链表是否为空表 3.单链表的销毁 4.单链表的清空 5.求单链表的表长 二.较重要操作 1.单链表的取值 2.单链表元素的查找 3.单链表的结点插入 4.单链表的结

    2024年04月11日
    浏览(41)
  • 【数据结构】反转链表、链表的中间节点、链表的回文结构(单链表OJ题)

    正如标题所说,本文会图文详细解析三道单链表OJ题,分别为:  反转链表 (简单)  链表的中间节点 (简单)  链表的回文结构 (较难) 把他们放在一起讲的原因是:  反转链表 和  链表的中间节点 是  链表的回文结构 的基础 为什么这样说?请往下看: 目录 1. 反转链

    2024年02月13日
    浏览(72)
  • 数据结构:图文详解单链表的各种操作(头插法,尾插法,任意位置插入,删除节点,查询节点,求链表的长度,清空链表)

    目录  一.什么是链表 二.链表的实现 节点的插入 头插法 尾插法 指定位置插入 节点的删除 删除第一次出现的节点 删除所有节点 节点的查找 链表的清空 链表的长度 前言: 在上一篇文章中,我们认识了线性数据结构中的顺序表,而本篇文章则是介绍线性数据结

    2024年02月05日
    浏览(61)
  • 【数据结构】C语言实现单链表(带头结点)

    Single linked list with leading nodes 关于不带头结点的单链表:不带头结点的单链表 结点定义: 接口定义: 初始化需要申请头结点,让头指针指向空的头结点。 将申请结点的代码进行封装: 需要越过头结点 找到尾结点,然后插入到尾结点的后面。 对比不带头结点的单链表的尾插

    2024年02月02日
    浏览(219)
  • 双向带头循环链表的实现

    当我们要学习和了解一个事物时,我们要做的第一步便是对这个事物有一个体的的了解。现在我们要学习双向带头循环链表的第一步也是这个,我们现在先来了解一下这种链表的结构---- 就像该图所呈现的那样,双向循环链表就是长这样。但是你可 千万不要将head当成head。  

    2024年02月05日
    浏览(45)
  • 数据结构三:线性表之单链表(带头结点单向)的设计与实现

            线性表的链式存储结构正是所谓的单链表,何谓单链表?通过地址将每一个数据元素串起来,进行使用,这可以弥补顺序表在进行任意位置的插入和删除需要进行大量的数据元素移动的缺点,只需要修改指针的指向即可;单链表的种类又可划分为很多种,本篇博客详

    2024年02月19日
    浏览(62)
  • 算法: 移除单链表的倒数第N个节点 19. Remove Nth Node From End of List

    Given the head of a linked list, remove the nth node from the end of the list and return its head. Example 1: Example 2: Example 3: Constraints: The number of nodes in the list is sz. 1 = sz = 30 0 = Node.val = 100 1 = n = sz Follow up: Could you do this in one pass? 该方法采用了两次遍历链表的方法。首先,它计算链表的总长度,然后通

    2024年02月13日
    浏览(47)
  • 数据结构-带头双向循环链表的实现

    前言           带头双向循环链表是一种重要的数据结构,它的结构是很完美的,它弥补了单链表的许多不足,让我们一起来了解一下它是如何实现的吧!         它的节点中存储着数据和两个指针,一个 指针_prev 用来记录前一个节点的地址,另一个指针 _next 用来记录后一

    2024年02月13日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包