当前位置： 首页 > news >正文

Java数据结构：单链表的实现与面试题汇总

news 来源：原创 2024/5/20 14:51:38

在这里插入图片描述

文章目录

  • 1 单链表
    • 1.1 单链表介绍
    • 1.2 单链表的实现思路分析
      • 1.2.1 单链表的创建与遍历
      • 1.2.2 单链表节点的插入与修改
      • 1.2.3 单链表节点的删除
    • 1.3 实现代码
  • 2 单链表的面试题
    • 2.1 统计单链表中有效节点数量
    • 2.2 新浪--倒数第k个节点
    • 2.3 腾讯--单链表的反转
    • 2.4 百度--逆序打印单链表
  • 写在最后

1 单链表

1.1 单链表介绍

由于顺序表的插入删除操作需要移动大量的元素，影响了运行效率，因此引入了线性表的链式存储——单链表。单链表通过一组任意的存储单元来存储线性表中的数据元素，不需要使用地址连续的存储单元，因此它 不要求在逻辑上相邻的两个元素在物理位置上也相邻。

物理结构示意图：
在这里插入图片描述

逻辑结构示意图：
在这里插入图片描述

关于单链表的一些说明：

  • 链表是以节点的方式存储的，每个节点包含data和next域，分别表示存储的数据和指向下一个节点；
  • 链表的各个节点不一定是连续存储的；
  • 可以根据实际需求来构造是否带有头节点的链表。

1.2 单链表的实现思路分析

1.2.1 单链表的创建与遍历

单链表的创建：

  1. 先创建一个 head 头节点，表示单链表的头；
  2. 每添加一个节点就直接加入链表的最后；

遍历的思路：

  1. 创建一个辅助指针，用于帮助遍历整个链表；
  2. 当指针指向的节点的next域为null，说明当前节点为最后一个，遍历完成。

1.2.2 单链表节点的插入与修改

示意图如下：
在这里插入图片描述

  1. 首先需要通过遍历找到需要添加节点的位置，图中示意的为a1的位置；
  2. 新的节点的next指向a1.next；
  3. 将该位置，即a1.next指向新的节点。

修改操作相当于上述过程的简化，只需要找到对应的节点直接修改节点对应的属性即可，这里不再赘述。

1.2.3 单链表节点的删除

删除序号为 “2” 的节点示意图如下：
在这里插入图片描述

思路如下：

  1. 找到待删除节点的前一个节点，示例中则找到序号为1的节点；
  2. 让该节点的 temp.next = temp.next.next，即可；
  3. 由于被删除的节点没有其他的指向，则会由Java的垃圾回收机制进行回收，无需处理。

1.3 实现代码

StudentNode.java 节点类：

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * 链表的节点类，包含学生信息和next
 */
public class StudentNode {
    public String no; //学号
    public String name; //姓名
    public int age; //年龄
    public StudentNode next; //指向下一个节点

    //构造器
    public StudentNode(String no, String name, int age ){
        this.no = no;
        this.name = name;
        this.age = age;
    }

    //为了显示方便
    @Override
    public String toString() {
        return "StudentNode{" +
                "no='" + no + '\'' +
                ", name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

StudentLinkedList.java 链表的实现类：

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * 链表的实现类，用于管理众多StudentNode节点
 */
public class StudentLinkedList {
    //初始化头节点
    private StudentNode head = new StudentNode("", "", 0);

	  //获取头节点
    public StudentNode getHead() {
        return head;
    }

    //添加节点
    //1.找到当前链表的最后节点
    //2.将最后节点的next指向新的节点
    public void add(StudentNode studentNode) {
        StudentNode temp = head;
        //遍历链表找到最后的节点
        while (temp.next != null) {
            //没有找到，就后移
            temp = temp.next;
        }
        //最后的节点的next指向新节点
        temp.next = studentNode;
    }

    //遍历 显示链表
    public void showList(){
        //判断链表是否为空
        if (head.next == null){
            System.out.println("当前链表为空");
            return;
        }
        //遍历 使用辅助指针
        StudentNode temp = head;
        while (temp != null){
            //更新指针
            temp = temp.next;
            if (temp.next == null){
                System.out.print(temp);
                break;
            }
            System.out.print(temp + "--->");
        }
    }

    //插入节点
    //根据学号顺序查找添加的位置, 如果存在, 则提示错误信息
    public void addByOrder(StudentNode studentNode){
        //寻找的temp应该为添加位置的前一个节点
        StudentNode temp = head;
        boolean flag = false; //标识新添加的no是否已经存在
        while (true){
            if (temp.next == null){
                //已经在链表的尾部
                break;
            }
            if (Integer.parseInt(temp.next.no) > Integer.parseInt(studentNode.no)){
                //位置找到 插入到temp后
                break;
            }else if (Integer.parseInt(temp.next.no) == Integer.parseInt(studentNode.no)){
                //已经存在
                flag = true;
                break;
            }
            //移动指针
            temp = temp.next;
        }
        if (flag){
            System.out.println("\n准备插入的学生信息: " + studentNode.no + "，该学号已经存在，不可添加！");
        }else {
            studentNode.next = temp.next;
            temp.next = studentNode;
        }
    }

    //根据no学号修改学生信息
    public void update(StudentNode studentNode){
        if (head.next == null){
            System.out.println("当前链表为空, 无法修改");
            return;
        }
        StudentNode temp = head.next;
        boolean flag = false; //表示是否找到节点
        while (true){
            if (temp == null){
                break;
            }
            if (temp.no == studentNode.no){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            temp.name = studentNode.name;
            temp.age = studentNode.age;
        }else {
            System.out.println("没有找到");
        }
    }

    //删除节点
    public void delete(String no){
        StudentNode temp = head;
        boolean flag = false; //标志是否找到
        //查找到待删除节点的前一个节点进行删除操作
        while (true){
            if (temp.next == null){
                //到达尾部
                break;
            }
            if (temp.next.no == no){
                //找到了
                flag = true;
                break;
            }
            //遍历
            temp = temp.next;
        }
        //删除操作
        if (flag){
            temp.next = temp.next.next;
            System.out.println("删除成功！");
        }else {
            System.out.println("要删除的节点不存在！");
        }
    }
}

测试类：

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * 测试链表
 */
public class StudentListTest {

    public static void main(String[] args) {
        StudentNode node1 = new StudentNode("1", "黄小黄", 21);
        StudentNode node2 = new StudentNode("2", "懒羊羊", 21);
        StudentNode node3 = new StudentNode("3", "沸羊羊", 22);
        //创建单链表 录入数据 输出
        StudentLinkedList list = new StudentLinkedList();
        list.add(node1);
        list.add(node2);
        list.add(node3);
        System.out.println("遍历链表:");
        list.showList();
        //测试插入数据方法
        StudentNode node5 = new StudentNode("5", "美羊羊", 19);
        StudentNode node4 = new StudentNode("4", "暖羊羊", 19);
        list.addByOrder(node5);
        list.addByOrder(node4);
        System.out.println("\n依次插入学号为5、4的学生后:");
        list.showList();
        //测试修改方法
        System.out.println("\n测试修改方法:");
        list.update(new StudentNode("1", "祢豆子", 10));
        list.showList();
        //测试删除方法
        System.out.println("\n测试删除方法:");
        list.delete("1");
        list.delete("5");
        list.showList();
    }
}

实现结果：

遍历链表:
StudentNode{no='1', name='黄小黄', age=21}--->StudentNode{no='2', name='懒羊羊', age=21}--->StudentNode{no='3', name='沸羊羊', age=22}
依次插入学号为5、4的学生后:
StudentNode{no='1', name='黄小黄', age=21}--->StudentNode{no='2', name='懒羊羊', age=21}--->StudentNode{no='3', name='沸羊羊', age=22}--->StudentNode{no='4', name='暖羊羊', age=19}--->StudentNode{no='5', name='美羊羊', age=19}
测试修改方法:
StudentNode{no='1', name='祢豆子', age=10}--->StudentNode{no='2', name='懒羊羊', age=21}--->StudentNode{no='3', name='沸羊羊', age=22}--->StudentNode{no='4', name='暖羊羊', age=19}--->StudentNode{no='5', name='美羊羊', age=19}
测试删除方法:
删除成功！
删除成功！
StudentNode{no='2', name='懒羊羊', age=21}--->StudentNode{no='3', name='沸羊羊', age=22}--->StudentNode{no='4', name='暖羊羊', age=19}
Process finished with exit code 0

2 单链表的面试题

2.1 统计单链表中有效节点数量

 /**
     * 
     * @param head 头节点
     * @return 返回有效节点个数
     */
    public static int getLength(StudentNode head){
        if (head.next == null){
            return 0;
        }
        int length = 0;
        StudentNode temp = head.next;
        while (temp != null){
            length++;
            temp = temp.next;
        }
        return length;
    }

2.2 新浪–倒数第k个节点

查找链表中倒数第k个节点

思路分析：

  1. 编写一个方法，接收head头节点和index，index表示k；
  2. 链表从头到尾遍历，求出长度（链表节点个数）size；
  3. 从第一个节点，遍历size-length次，即可找到倒数第k个节点。

参考代码：

/**
     * 获取单链表中倒数第k个节点
     * @param head 链表的头节点
     * @param index 倒数第 k 个元素
     * @return 返回倒数第 k 个元素，或者 null
     */
    public static StudentNode findLastIndexNode(StudentNode head, int index){
        //如果链表为空
        if (head.next == null){
            return null;
        }
        //得到链表的长度(节点个数)
        int size = getLength(head);
        //遍历 size-index次 得到倒数第index个节点
        //数据校验
        if (index <= 0 || index > size){
            return null;
        }
        //遍历
        StudentNode current = head.next;
        for (int i = 0; i < size - index; i++) {
            current = current.next;
        }
        return current;
    }

2.3 腾讯–单链表的反转

反转单链表

思路分析：

  1. 可以使用头插法；
  2. 以原链表为模板，每遍历一个节点，取出，并接在新链表的最前端；
  3. 原head头节点，指向新的节点；
  4. 直到遍历完为止。

参考代码：

	/**
     * 头插法反转链表
     * @param head 接收待反转的链表
     * @return 返回一个反转后的新链表
     */
    public static StudentLinkedList reverseList(StudentNode head){
        if (head.next == null){
            return null;
        }
        StudentNode old = head.next; //用于遍历旧链表
        //创建新链表，新链表根据原链表遍历得到
        StudentLinkedList newList = new StudentLinkedList();
        StudentNode newHead = newList.getHead(); //新链表的头节点
        //遍历构造
        boolean flag = true; //标记是否为第一次添加
        while (old != null){
            //头插法加入到新链表中
            StudentNode newNode = new StudentNode(old.no, old.name, old.age);
            if(flag){
                newHead.next = newNode;
                newNode.next = null;
                flag = false;
            }else {
                newNode.next = newHead.next;
                newHead.next = newNode;
            }
            old = old.next;
        }
        return newList;
    }

以上方式虽然可以实现链表的反转，但是是以返回一个新的反转链表的形式，并没有真正意义上实现原地反转，下面介绍另一种方式：

双指针:

	/**
     * 双指针就地反转链表
     * @param head 接收链表的头节点，方法中会将链表反转
     */
    public static void reverse(StudentNode head){
        //如果当前链表为空 或者只有一个节点 直接返回即可
        if (head.next == null || head.next.next == null){
            return;
        }
        //辅助指针遍历原来的链表
        StudentNode cur = head.next; //当前节点
        StudentNode next = null; //指向cur的下一个节点
        StudentNode reverseHead = new StudentNode("", "", 0);
        //遍历原来的链表，每遍历一个节点，就取出，放在新链表的最前端
        while (cur != null){
            next = cur.next; //暂时保存当前节点的下一个节点
            cur.next = reverseHead.next; //讲cur下一个节点放在链表最前端
            reverseHead.next = cur;
            cur = next; //cur后移动
        }
        head.next = reverseHead.next;
        return;
    }

2.4 百度–逆序打印单链表

从尾到头打印单链表

方式一： 先将单链表反转，然后再打印。但是这样会破坏掉原有单链表的结构，而题目要求仅仅是打印，因此不建议！

方式二： 利用栈模拟

将单链表的各个节点压入栈中，利用栈先进后出的特点，实现逆序打印。

参考代码：

    /**
     * 利用栈模拟 实现链表的逆序打印
     * @param head 链表的头节点
     */
    public static void reversePrintList(StudentNode head){
        if (head.next == null){
            return; //空链表无法打印
        }
        //创建栈模拟逆序打印
        Stack<StudentNode> stack = new Stack<>(); //栈
        StudentNode cur = head.next;
        //将链表的所有节点压入栈
        while (cur != null){
            stack.push(cur);
            cur = cur.next;
        }
        //逆序打印
        while (!stack.empty()){
            //出栈
            System.out.println(stack.pop());
        }
        return;
    }

写在最后

 本文被 Java数据结构 收录点击订阅专栏 ， 持续更新中。
 创作不易，如果你有任何问题，欢迎私信，感谢您的支持！
在这里插入图片描述
在这里插入图片描述

相关文章：

  • 2022年都说软件测试不香了？在职3年月薪16k我满意了，你们觉得前景怎么样？
  • python做了个自动关机工具，再也不会耽误我下班啦
  • BUUCTF NewStarCTF 公开赛赛道Week5 Writeup
  • @Conditional注解详解
  • 动态路由协议解析（rip）
  • 38、Java 中的正则表达式（单字符匹配和预定义字符）
  • 电气论文实现：基于优化算法和python-pandapower的配电网重构（IEEE33节点算例）
  • 刚来的00后真的卷，听说工作还没两年，跳到我们公司直接起薪20k...
  • 【云原生 · Docker】Docker 镜像操作、容器操作常用指令
  • 基于粒子群优化算法的无人机路径规划与轨迹算法的实现（Matlab代码实现）
  • Spring Cloud基本介绍
  • 【目标检测】使用TensorRT加速YOLOv5
  • python数据分析及可视化（九）pandas数据规整（分组聚合、数据透视表、时间序列、数据分析流程）
  • 到了30岁，我才有了深刻的感悟：千万不要一辈子靠技术生存
  • 过滤器和拦截器的区别
  • 【407天】跃迁之路——程序员高效学习方法论探索系列（实验阶段164-2018.03.19）...
  • 【附node操作实例】redis简明入门系列—字符串类型
  • 2017-08-04 前端日报
  • Angularjs之国际化
  • JavaScript HTML DOM
  • Netty 4.1 源代码学习：线程模型
  • Unix命令
  • Vue ES6 Jade Scss Webpack Gulp
  • vue脚手架vue-cli
  • vue--为什么data属性必须是一个函数
  • 记一次和乔布斯合作最难忘的经历
  • 两列自适应布局方案整理
  • 如何将自己的网站分享到QQ空间，微信，微博等等
  • 数据库写操作弃用“SELECT ... FOR UPDATE”解决方案
  • 一道闭包题引发的思考
  • 一些关于Rust在2019年的思考
  • 移动端高清、多屏适配方案
  • #微信小程序：微信小程序常见的配置传旨
  • （附源码）springboot教学评价 毕业设计 641310
  • （机器学习-深度学习快速入门）第三章机器学习-第二节：机器学习模型之线性回归
  • （论文阅读笔记）Network planning with deep reinforcement learning
  • （亲测）设​置​m​y​e​c​l​i​p​s​e​打​开​默​认​工​作​空​间...
  • ＊Django中的Ajax 纯js的书写样式1
  • .[hudsonL@cock.li].mkp勒索加密数据库完美恢复---惜分飞
  • .NET Core 网络数据采集 -- 使用AngleSharp做html解析
  • .Net Core和.Net Standard直观理解
  • .NET Remoting Basic(10)-创建不同宿主的客户端与服务器端
  • .NET Windows：删除文件夹后立即判断，有可能依然存在
  • .NET/C# 异常处理：写一个空的 try 块代码，而把重要代码写到 finally 中（Constrained Execution Regions）
  • .NET高级面试指南专题十一【 设计模式介绍，为什么要用设计模式】
  • .vue文件怎么使用_我在项目中是这样配置Vue的
  • [].shift.call( arguments ) 和 [].slice.call( arguments )
  • [android] 练习PopupWindow实现对话框
  • [android] 天气app布局练习
  • [AutoSar]BSW_Com07 CAN报文接收流程的函数调用
  • [bzoj1324]Exca王者之剑_最小割
  • [C++] 如何使用Visual Studio 2022 + QT6创建桌面应用
  • [CodeForces-759D]Bacterial Melee
  • [Java][Liferay] File system in liferay
  • [LeetCode] Wildcard Matching