Java数据结构:单链表的实现与面试题汇总(上)

简介: 文章目录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 单链表的创建与遍历

单链表的创建:


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

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

遍历的思路:


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

当指针指向的节点的next域为null,说明当前节点为最后一个,遍历完成。

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

示意图如下:



首先需要通过遍历找到需要添加节点的位置,图中示意的为a1的位置;

新的节点的next指向a1.next;

将该位置,即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("要删除的节点不存在!");
        }
    }
}


相关文章
|
4月前
|
机器学习/深度学习 算法
24. 两两交换链表中的节点, 19.删除链表的倒数第N个节点 ,面试题 02.07. 链表相交
1. **两两交换链表中的节点**:通过引入虚拟头结点,使所有节点都能采用统一的交换逻辑,避免对头结点单独处理。 2. **删除链表的倒数第N个节点**:利用双指针技巧,让快慢指针保持N个节点的距离,当快指针到达末尾时,慢指针正好指向待删除节点的前一个节点。 3. **链表相交**:先计算两链表长度并调整起点,确保从相同距离末尾的位置开始遍历,从而高效找到相交节点或确定无交点。 以上方法均在时间复杂度和空间复杂度上进行了优化,适合用于理解和掌握链表的基本操作及常见算法设计思路。
|
4月前
|
存储 安全 Java
Java 集合面试题从数据结构到 HashMap 源码剖析详解及长尾考点梳理
本文深入解析Java集合框架,涵盖基础概念、常见集合类型及HashMap的底层数据结构与源码实现。从Collection、Map到Iterator接口,逐一剖析其特性与应用场景。重点解读HashMap在JDK1.7与1.8中的数据结构演变,包括数组+链表+红黑树优化,以及put方法和扩容机制的实现细节。结合订单管理与用户权限管理等实际案例,展示集合框架的应用价值,助你全面掌握相关知识,轻松应对面试与开发需求。
220 3
|
11月前
|
存储 算法 Perl
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法,并分析时间复杂度,理解链表特点。实验内容包括循环链表应用(约瑟夫回环问题)、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践,加深对链表数据结构的理解和应用能力。
191 4
|
8月前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
238 30
|
8月前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
384 25
|
9月前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】单链表的基本运算(头歌实践教学平台习题)【合集】
本内容介绍了单链表的基本运算任务,涵盖线性表的基本概念、初始化、销毁、判定是否为空表、求长度、输出、求元素值、按元素值查找、插入和删除数据元素等操作。通过C++代码示例详细解释了顺序表和链表的实现方法,并提供了测试说明、通 - **任务描述**:实现单链表的基本运算。 - **相关知识**:包括线性表的概念、初始化、销毁、判断空表、求长度、输出、求元素值、查找、插入和删除等操作。 - **测试说明**:平台会对你编写的代码进行测试,提供测试输入和预期输出。 - **通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了测试通过后的预期输出结果。 开始你的任务吧,祝你成功!
386 5
|
10月前
|
数据库
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
|
11月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
331 5
|
11月前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
1014 4
|
11月前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能,支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构,并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示,系统在处理小规模购物车时表现良好,但在大规模购物车操作下可能存在性能瓶颈。
263 0