1. 全栈程序员必看首页

数据结构单链表的算法描述_数据结构创建单链表及其实现

全栈程序员-站长 • • 未分类 • 阅读 14

数据结构单链表的算法描述_数据结构创建单链表及其实现一、什么是链表链表是一种数据结构，跟数组不同，链表不需要连续的内存空间，而是通过指针将零散的内存块连接起来。因此，链表的查找需要通过节点按顺序遍历，而增加与删除通过只需要操作指针指向，这也造成了相

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

一、什么是链表

链表是一种数据结构，跟数组不同，链表不需要连续的内存空间，而是通过指针将零散的内存块连接起来。

因此，链表的查找需要通过节点按顺序遍历，而增加与删除通过只需要操作指针指向，这也造成了相比数组，链表的查找性能消耗大而增加和删除消耗小的特点。

链表由节点组成，一般每个节点最少包含用于储存数据的data区和用于指向下一个节点的指针next，有的链表可能会有头结点或尾结点用于存储链表长度等信息。

数据结构单链表的算法描述_数据结构创建单链表及其实现

二、链表的简单实现

先来实现一个简单的节点类：

/**
 * @Author：huang
 * @Date：2020-06-20 10:19
 * @Description：节点类
 */
public class Node {

    //节点序号
    int num;

    //数据
    Object data;

    //下一个节点
    Node next;

    public Node(int num, Object data) {
        this.num = num;
        this.data = data;
    }
    
    public int getNum() {
        return num;
    }

    public Object getData() {
        return data;
    }

    public void setNum(int num) {
        this.num = num;
    }

    public void setData(Object data) {
        this.data = data;
    }
    
    @Override
    public String toString() {
        return "Node{" +
            "num=" + num +
            ", data=" + data +
            '}';
    }
}

1.插入节点

1.1不按照排序的插入

/**
 * @Author：huang
 * @Date：2020-06-20 10:19
 * @Description：单链表
 */
public class SingleLinkList {
	//默认初始化一个头节点
    private Node head = new Node(0, "我是头结点");

    /**
     * 添加节点到链表
     * @param node
     */
    public void add(Node node) {
        Node temp = head;
        //遍历链表
        while (true) {
            if (temp.next == null) {
                break;
            }
            //不是尾节点就继续遍历下一个节点
            temp = temp.next;
        }
        //将尾节点指向即将插入的新节点
        temp.next = node;
    }
}

1.2按照排序插入

数据结构单链表的算法描述_数据结构创建单链表及其实现

要想按顺序插入节点，需要确定节点的位置，也就是确定新节点的大小，以图为例：

遍历链表，我们把遍历到的节点叫A，A之前的节点叫A-1，A之后的节点叫A+1，要插入的节点叫B，有以下几种情况：

  1. 当A的序号大于B时，就把B插到A前，也就是原本的A和A-1之间
  2. 当A的序号等于B时，抛出异常禁止插入
  3. 当A的序号小于B时，就跳过这个节点，继续遍历，然后对比A+1和B的大小
  4. 当A就是链表最后一个节点时，A还是小于B，那就直接让B插到A后，变成链表的尾节点

按这个思路，我们在原来的类里新增一个方法：

/**
 * 按顺序添加节点到链表
 * @param node 要插入的节点
 */
public void addByOrder(Node node) {
    Node temp = head;
    //遍历链表
    while (true) {
        //如果链表到底了就直接插入
        if (temp.next == null) {
            temp.next = node;
            return;
        }else if (temp.next.num > node.num){
            //如果当前节点比当要插入的节点大，就把新节点插到当前节点之前
            node.next = temp.next;
            temp.next = node;
            return;
        }else if (temp.next.num == node.num){
            //如果有节点序号和要插入的节点重复就抛异常
            throw new RuntimeException("插入节点与已有节点序号重复！");
        }
        //如果当前节点比当要插入的节点小，就继续遍历
        temp = temp.next;
    }
}

2.查找节点

/**
 * 展示链表全部节点
 */
public void show() {
    //判断链表是否为空
    if (head.next == null) {
        throw new RuntimeException("链表为空！");
    }
    Node temp = head.next;
    //遍历链表
    while (true) {
        if (temp == null) {
            break;
        }
        System.out.println(temp.toString());
        temp = temp.next;
    }
}

/**
 * 根据序号获取节点
 * @param num 要获取的节点序号
 * @return
 */
public Node get(int num){
    //判断链表是否为空
    if (head.next == null) {
        throw new RuntimeException("链表为空！");
    }
    Node temp = head.next;
    //遍历链表
    while (true) {
        if (temp == null) {
            throw new RuntimeException("编号为" + num + "的节点不存在！");
        }
        //如果是要获取的节点
        if (temp.num == num) {
            return temp;
        }
        temp = temp.next;
    }
}

3.修改节点

修改节点与按顺序插入逻辑相似，需要先遍历并找到要修改的节点，然后用新节点去替换旧节点，或者干脆直接修改节点内的信息

数据结构单链表的算法描述_数据结构创建单链表及其实现

/**
 * 修改节点
 * @param node 要更新的节点
 */
public void update(Node node) {
    Node temp = head;
    //判断链表是否为空
    if (temp.next == null) {
        throw new RuntimeException("链表为空！");
    }
    //获取要更新的节点序号
    int nodeNum = node.num;
    //遍历链表
    while (true) {
        //如果已经遍历完链表
        if (temp == null) {
            throw new RuntimeException("编号为" + temp.num + "的节点不存在！");
        }
        //如果找到了该节点
        if (temp.num == nodeNum) {
            temp.data = node.data;
            return;
        }
        //继续遍历下一节点
        temp = temp.next;
    }
}

4.删除节点

数据结构单链表的算法描述_数据结构创建单链表及其实现

因为在单向链表中，节点无法知道自己前一个节点的情况，以图为例：

如果我们想要删除节点A，那么就要找到A的前一个节点A-1，根据是否存在A后的节点A+1有以下几种情况：

  1. A节点就是链表尾节点，此时只需让A-1节点的next指向null即可

    nodeA-1.next = null

  2. A节点后有A+1，此时让A-1节点指向A+1节点

    nodeA-1.next = nodeA-1.next.next

按这个思路，在类里新加一个方法：

/**
 * 删除节点
 * @param num 要删除的节点编号
 */
public void delete(int num) {
    Node temp = head;
    //判断链表是否为空
    if (temp.next == null) {
        throw new RuntimeException("链表为空！");
    }
    //遍历链表
    while (true) {
        //如果链表到底了
        if (temp.next == null) {
            throw new RuntimeException("编号为" + num + "的节点不存在！");
        }
        //如果找到了待删除节点的前一个节点
        if (temp.next.num == num) {
            //判断待删除节点是否为尾节点
            if (temp.next.next == null){
                temp.next = null;
            }else {
                temp.next = temp.next.next;
            }
            return;
        }
        //继续遍历下一节点
        temp = temp.next;
    }
}

三、完整实现代码

/**
 * @Author：huang
 * @Date：2020-06-20 10:19
 * @Description：单链表
 */
public class SingleLinkList {

    private Node head = new Node(0, "我是头结点");

    /**
     * 添加节点到链表
     * @param node 要插入的节点
     */
    public void add(Node node) {
        Node temp = head;
        //遍历链表
        while (true) {
            if (temp.next == null) {
                break;
            }
            //不是尾节点就继续遍历下一个节点
            temp = temp.next;
        }
        //将尾节点指向即将插入的新节点
        temp.next = node;
    }

    /**
     * 展示链表
     */
    public void show() {
        //判断链表是否为空
        if (head.next == null) {
            throw new RuntimeException("链表为空！");
        }
        Node temp = head.next;
        //遍历链表
        while (true) {
            if (temp == null) {
                break;
            }
            System.out.println(temp.toString());
            temp = temp.next;
        }
    }

    /**
     * 根据序号获取节点
     * @param num 要获取的节点序号
     * @return
     */
    public Node get(int num){
        //判断链表是否为空
        if (head.next == null) {
            throw new RuntimeException("链表为空！");
        }
        Node temp = head.next;
        //遍历链表
        while (true) {
            if (temp == null) {
                throw new RuntimeException("编号为" + num + "的节点不存在！");
            }
            if (temp.num == num) {
                return temp;
            }
            temp = temp.next;
        }
    }

    /**
     * 按顺序添加节点到链表
     * @param node 要插入的节点
     */
    public void addByOrder(Node node) {
        Node temp = head;
        //遍历链表
        while (true) {
            //如果链表到底了就直接插入
            if (temp.next == null) {
                temp.next = node;
                return;
            }
            else if (temp.next.num > node.num){
                //如果后一节点比当新节点大，就插入当前节点
                node.next = temp.next;
                temp.next = node;
                return;
            }else if (temp.next.num == node.num){
                //如果后一节点等于新节点，抛异常
                throw new RuntimeException("插入节点与已有节点序号重复！");
            }
            //如果后一节点比当前节点小，就继续遍历
            temp = temp.next;
        }
    }

    /**
     * 修改节点
     * @param node 要更新的节点
     */
    public void update(Node node) {
        Node temp = head;
        //判断链表是否为空
        if (temp.next == null) {
            throw new RuntimeException("链表为空！");
        }
        //获取要更新的节点序号
        int nodeNum = node.num;
        //遍历链表
        while (true) {
            //如果已经遍历完链表
            if (temp == null) {
                throw new RuntimeException("编号为" + temp.num + "的节点不存在！");
            }
            //如果找到了该节点
            if (temp.num == nodeNum) {
                temp.data = node.data;
                return;
            }
            //继续遍历下一节点
            temp = temp.next;
        }
    }

    /**
     * 删除节点
     * @param num 要删除的节点编号
     */
    public void delete(int num) {
        Node temp = head;
        //判断链表是否为空
        if (temp.next == null) {
            throw new RuntimeException("链表为空！");
        }
        //遍历链表
        while (true) {
            //如果链表到底了
            if (temp.next == null) {
                throw new RuntimeException("编号为" + num + "的节点不存在！");
            }
            //如果找到了待删除节点的前一个节点
            if (temp.next.num == num) {
                //判断待删除节点是否为尾节点
                if (temp.next.next == null){
                    temp.next = null;
                }else {
                    temp.next = temp.next.next;
                }
                return;
            }
            //继续遍历下一节点
            temp = temp.next;
        }
    }
}

四、环形链表

循环链表是一种特殊单链表，他跟单链表的区别在于尾节点的尾指针指向了链表的头结点，也就是相当于将链表连接成了一个环形。

环形链表可以用于处理能描述为环形的数据，典型的比如约瑟夫问题。

数据结构单链表的算法描述_数据结构创建单链表及其实现

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/170818.html原文链接：https://javaforall.net

赞 (0)
0 0

关于作者

全栈程序员-站长的头像

全栈程序员-站长

133.5K 文章
3 粉丝
本网站汇聚当前互联网主流语音，持续更新，欢迎关注公众号“全栈程序员社区”
上一篇 2022年8月16日 下午8:46
下一篇 2022年8月16日 下午9:00


相关推荐

  • 什么是MVC三层架构？「建议收藏」

    什么是MVC三层架构？「建议收藏」

    什么是MVC三层架构？「建议收藏」1.1、什么是MVC MVC是模型(Model)、视图(View)、控制器(Controller)的简写，是一种软件设计规范。 是将业务逻辑、数据、显示分离的方法来组织代码。 MVC主要作用是降低了视图与业务逻辑间的双向偶合。 MVC不是一种设计模式，MVC是一种架构模式。当然不同的MVC存在差异。 Model（模型）：数据模型，提供要展示的数据，因此包含数据和行为，可以认为是领域模型或JavaBean组件（包含数据和行为），不过现在一般都分离开来：ValueObj

    全栈程序员-站长的头像 全栈程序员-站长
    2022年6月25日
    27
  • safe-point(safepoint 安全点) 和 safe-region(安全区域)「建议收藏」

    safe-point(safepoint 安全点) 和 safe-region(安全区域)「建议收藏」

    safe-point(safepoint 安全点) 和 safe-region(安全区域)「建议收藏」safe-point(safepoint 安全点) 和 safe-region(安全区域)

    全栈程序员-站长的头像 全栈程序员-站长
    2022年4月21日
    84
  • Animation的使用「建议收藏」

    Animation的使用「建议收藏」

    Animation的使用「建议收藏」Animation(动画)有两种分类：补间动画(Tween)和帧动画(Frame)补间动画主要有以下几种：旋转(RotateAnimation)平移(TranslateAnimation)拉伸(ScaleAnimation)透明度(AlphaAnimation)实现的方式：1.实例相应的动画对象2.加载资源中的动画文件动画的属性d

    全栈程序员-站长的头像 全栈程序员-站长
    2025年6月17日
    4
  • windows10产品密钥永久(windows激活密钥)

    windows10产品密钥永久(windows激活密钥)

    使用WindowsKeyViewer一键轻松查看当前计算机的产品密钥。查看当前计算机的产品密钥偶尔需要用到，分享给大家。软件介绍通过使用WindowsKeyViewer，可以轻松确定当前的计算机产品密钥。在某些情况下，例如在重新安装计算机时，了解产品密钥非常重要。通常，可以在Windows安装工具包或计算机的标签上找到产品密钥。该标签经常会损坏并变得难以辨认，并且在使用多台计算机时，安装包…

    全栈程序员-站长的头像 全栈程序员-站长
    2022年4月13日
    63
  • springboot下载文件功能

    springboot下载文件功能

    springboot下载文件功能下载功能其实就是用户输入指定文件路径信息 然后把文件返回给用户 不同于上传的概念 同时需要考虑下文件的类型 从而选择使用字符流还是字节流操作 如果传输图片 用的是字符流 可能会造成文件内容缺失 毕竟是字符为单位传输的 无论什么文件 使用字节流肯定没错 实现步骤 pom 文件中引入了 springboot tater web 依赖新建 cotroller 类 其中的 RequestMappi 方法的方法参数中配置 HttpServletR 类方法中实现读取服务器文件流操作类 servlet 写入流操

    全栈程序员-站长的头像 全栈程序员-站长
    2026年3月17日
    2
  • Navicat 15 for MySQL 激活码(破解版激活) idea

    Navicat 15 for MySQL 激活码(破解版激活)

    Navicat 15 for MySQL 激活码(破解版激活)，https://javaforall.net/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧！

    全栈程序员-站长的头像 全栈程序员-站长
    2022年3月16日
    180

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号