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

目录
  • 1 单链表
    • 1.1 单链表介绍
    • 1.2 单链表的实现思路分析
    • 1.3 实现代码
  • 2 单链表的面试题
    • 2.1 统计单链表中有效节点数量
    • 2.2 新浪–倒数第k个节点
    • 2.3 腾讯–单链表的反转
    • 2.4 百度–逆序打印单链表

1 单链表

1.1 单链表介绍

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

物理结构示意图:

逻辑结构示意图:

关于单链表的一些说明:

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

1.2 单链表的实现思路分析

1.2.1 单链表的创建与遍历

单链表的创建:

先创建一个 head 头节点,表示单链表的头;

每添加一个节点就直接加入链表的最后;

遍历的思路:

创建一个辅助指针,用于帮助遍历整个链表;

当指针指向的节点的next域为null,说明当前节点为最后一个,遍历完成。 1.2.2 单链表节点的插入与修改

示意图如下:

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

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

1.2.3 单链表节点的删除

删除序号为 “2” 的节点示意图如下:

思路如下:

  • 找到待删除节点的前一个节点,示例中则找到序号为1的节点;
  • 让该节点的 temp.next = temp.next.next,即可;
  • 由于被删除的节点没有其他的指向,则会由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个节点

思路分析:

  • 编写一个方法,接收head头节点和index,index表示k;
  • 链表从头到尾遍历,求出长度(链表节点个数)size;
  • 从第一个节点,遍历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 腾讯–单链表的反转

反转单链表

思路分析:

  • 可以使用头插法;
  • 以原链表为模板,每遍历一个节点,取出,并接在新链表的最前端;
  • 原head头节点,指向新的节点;
  • 直到遍历完为止。

参考代码:

	/**
     * 头插法反转链表
     * @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数据结构之单链表的实现与面试题汇总的详细内容,更多关于Java单链表的资料请关注我们其它相关文章!

(0)

相关推荐

  • Java单链表的增删改查与面试题详解

    目录 一.单链表的增删改查 1.创建结点 2.单链表的添加操作 3.单链表的删除操作 4.单链表的有效结点的个数 二.大厂面试题 一.单链表的增删改查 1.创建结点 单链表是由结点连接而成,所以我们首先要创建结点类,用于对结点进行操作.定义data属性 表示序号,定义name属性表示结点存放的数据信息,定义next属性表示指向下一个结点.构造器只需要放入data属性和name属性,重写toString方法方便打印结点信息. public class Node { public int data;

  • Java经典面试题最全汇总208道(四)

    目录 前言 126.Spring 框架中的单例 Beans 是线程安全的么? 127.请解释 Spring Bean 的自动装配? 129.什么是 Spring Batch? 130.spring mvc 和 struts 的区别是什么? 131.请举例解释@Required 注解? 132.Spring常用注解 133.项目中是如何实现权限验证的,权限验证需要几张表 134.谈谈controller,接口调用的路径问题 135.如何防止表单重复提交 136.Spring中都应用了哪些设计模式

  • Java经典面试题最全汇总208道(六)

    目录 前言 181.什么是类加载器,类加载器有哪些? 182.说一下类加载的执行过程? 183.JVM的类加载机制是什么? 184.什么是双亲委派模型? 185.怎么判断对象是否可以被回收? 186.说一下 jvm 有哪些垃圾回收算法? 187.说一下 jvm 有哪些垃圾回收器? 188.JVM栈堆概念,何时销毁对象 189.新生代垃圾回收器和老生代垃圾回收器都有哪些?有什么区别? 190.详细介绍一下 CMS 垃圾回收器? 191.简述分代垃圾回收器是怎么工作的? 192.Redis是什么?

  • Java经典面试题最全汇总208道(一)

    目录 前言 1.JDK 和 JRE 有什么区别? 2.== 和 equals 的区别是什么? 3.final 在 java 中有什么作用? 4.java 中的 Math.round(-1.5) 等于多少? 5.String 属于基础的数据类型吗? 6.String str="i"与 String str=new String(“i”)一样吗? 7.如何将字符串反转? 8.String 类的常用方法都有那些? 9.new String("a") + new Strin

  • Java经典面试题最全汇总208道(五)

    目录 前言 152.什么是 YAML? 153.如何使用 Spring Boot 实现分页和排序? 154.如何使用 Spring Boot 实现异常处理? 155.单点登录 156.Spring Boot比Spring多哪些注解 157.打包和部署 158.Spring Boot如何访问不同的数据库 159.查询网站在线人数 160.easyExcel如何实现 161.什么是 Swagger?你用 Spring Boot 实现了它吗? 162.数据库的三范式是什么? 163.一张自增表里面总共

  • java面试题解LeetCode27二叉树的镜像实例

    目录 正文 解题思路 方法一:递归法 方法二:辅助栈(或队列) 正文 LeetCode27. 二叉树的镜像 请完成一个函数,输入一个二叉树,该函数输出它的镜像. 例如输入: 4 /2 7 / \ /1 3 6 9 镜像输出: 4 /7 2 / \ /9 6 3 1 示例 1: 输入:root = [4,2,7,1,3,6,9] 输出:[4,7,2,9,6,3,1] 限制: 0 <= 节点个数 <= 1000 解题思路 方法一:递归法 根据二叉树镜像的定义,考虑递归遍历(dfs)二叉树,交换每个

  • Java面试题之MD5加密的安全性详解

    目录 1.彩虹表 什么是彩虹表 2.解决方案 3.实现代码 总结 MD5 是 Message Digest Algorithm 的缩写,译为信息摘要算法,它是 Java 语言中使用很广泛的一种加密算法.MD5 可以将任意字符串,通过不可逆的字符串变换算法,生成一个唯一的 MD5 信息摘要,这个信息摘要也就是我们通常所说的 MD5 字符串.那么问题来了,MD5 加密安全吗? 这道题看似简单,其实是一道送命题,很多人尤其是一些新入门的同学会觉得,安全啊,MD5 首先是加密的字符串,其次是不可逆的,所

  • Java经典面试题最全汇总208道(二)

    目录 前言 53.concurrentHashMap和HashTable有什么区别 54.HasmMap和HashSet的区别 55.请谈谈 ReadWriteLock 和 StampedLock 56.线程的run()和start()有什么区别? 57.为什么我们调用 start() 方法时会执行 run() 方法,为什么我们不能直接调用 run() 方法? 58.Synchronized 用过吗,其原理是什么? 59.JVM 对 Java 的原生锁做了哪些优化? 60.为什么 wait(),

  • Java经典面试题最全汇总208道(三)

    目录 前言 websocket应用的是哪个协议 106.说一下 tcp 粘包是怎么产生的? 107.请列举出在 JDK 中几个常用的设计模式? 108.什么是设计模式?你是否在你的代码里面使用过任何设计模式? 110.在 Java 中,什么叫观察者设计模式(observer design pattern)? 111.使用工厂模式最主要的好处是什么?在哪里使用? 112.请解释自动装配模式的区别? 113.举一个用 Java 实现的装饰模式(decorator design pattern)?它是

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

    目录 1 单链表 1.1 单链表介绍 1.2 单链表的实现思路分析 1.3 实现代码 2 单链表的面试题 2.1 统计单链表中有效节点数量 2.2 新浪–倒数第k个节点 2.3 腾讯–单链表的反转 2.4 百度–逆序打印单链表 1 单链表 1.1 单链表介绍 由于顺序表的插入删除操作需要移动大量的元素,影响了运行效率,因此引入了线性表的链式存储——单链表.单链表通过一组任意的存储单元来存储线性表中的数据元素,不需要使用地址连续的存储单元,因此它 不要求在逻辑上相邻的两个元素在物理位置上也相邻.

  • Java数据结构之单链表详解

    一.图示 二.链表的概念及结构 链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的 . 实际中链表的结构非常多样,以下情况组合起来就有8种链表结构: 单向.双向 带头.不带头 循环.非循环 今天,我们实现的是一个 单向 无头 非循环的链表. 下面是此链表的结构组成. 三.单链表的实现 (1)定义一个节点类型 我们创建一个 ListNode 的类作为节点类型,那么我们如何定义成员属性呢? 通过上面的结构分析,我们需要定义两个成员变量 val --作为该节点的

  • java数据结构基础:单链表与双向链表

    目录 单链表: 实现思路: 代码实现: 双向链表: 实现思路: 代码实现: 总结 单链表: 每个数据是以节点的形式存在的 每个节点分为数据域和指针域 数据域中保存该节点的数据 指针域中保存指向下一个节点的指针 实现思路: 节点类SingleNode中保存数据和指向下一个节点的指针 单链表类SingleLinkedList中保存链表的头节点,实现相关链表方法 对于链表方法,涉及到位置查找,如在指定位置增加.删除节点,需要使用一个临时变量temp从头节点开始遍历,直至找到对应的位置. 对于节点的增加

  • java实现简单单链表

    本文实例为大家分享了java实现简单单链表的具体代码,供大家参考,具体内容如下 一.定义: 单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素.链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(相当于JAVA中的引用,指示后继元素存储位置,),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据. 二.结构: 如图所示,data就是当前节点的数据,next是指针,指针存放的是内存地址,是当前结点的下一结点内存地址,顺着这个地址就能找

  • Java数据结构之环形链表和约瑟夫问题详解

    目录 一.环形链表 1.创建结点 2.添加小结点 3.显示循环链表 二.约瑟夫问题 1.问题描述 2.首先确定圈大小及开始位置 3.出圈操作 4.出圈方法完整代码 总结 一.环形链表 1.创建结点 环形链表其实也很好理解,就是将单链表的头和尾连接起来,就形成了环形链表. public class Node { public int data; public Node next; public Node(int data) { this.data = data; } @Override publi

  • C#数据结构之单链表(LinkList)实例详解

    本文实例讲述了C#数据结构之单链表(LinkList)实现方法.分享给大家供大家参考,具体如下: 这里我们来看下"单链表(LinkList)".在上一篇<C#数据结构之顺序表(SeqList)实例详解>的最后,我们指出了:顺序表要求开辟一组连续的内存空间,而且插入/删除元素时,为了保证元素的顺序性,必须对后面的元素进行移动.如果你的应用中需要频繁对元素进行插入/删除,那么开销会很大. 而链表结构正好相反,先来看下结构: 每个元素至少具有二个属性:data和next.data

  • Python数据结构之单链表详解

    本文实例为大家分享了Python数据结构之单链表的具体代码,供大家参考,具体内容如下 # 节点类 class Node(): __slots__=['_item','_next'] # 限定Node实例的属性 def __init__(self,item): self._item = item self._next = None # Node的指针部分默认指向None def getItem(self): return self._item def getNext(self): return s

  • python算法与数据结构之单链表的实现代码

    =一.链表 链表是一种物理存储单元上非连续.非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的.链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成.每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域. 相比于线性表顺序结构,操作复杂.由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是

  • Java如何实现单链表的增删改查

    一.新建学生节点类 Stu_Node节点包含: 学号:int num; 姓名:String name; 性别:String gender; 下一个节点:Stu_Node next; 为了便于打印节点内容需要重写toString方法 class Stu_Node{ int num; String name; String gender; Stu_Node next; @Override public String toString() { return "Stu_Node{" + &qu

  • Java 数据结构之删除链表中重复的结点

    目录 解析一:(不提倡) 解析二:(正解) 核心考点:链表操作,临界条件检查,特殊情况处理 在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针. 解析一:(不提倡) 解决该问题较简单,且在写代码时不易出错的做法如下: 遍历一遍链表,记录重复结点的结点值. 再遍历一遍链表,逐个删除重复结点. 动图演示: 该方法需要遍历两遍链表,且需要开辟额外的内存空间存储重复结点的结点值,所以一般不提倡. /* struct ListNode { int val; st

随机推荐