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

Java
316
0
0
2023-06-05
基于MySql,Redis,Mq,ES的高可用方案解析
上一篇
java线程的五大状态，阻塞状态详解
下一篇
标签   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;
}
基于MySql,Redis,Mq,ES的高可用方案解析
上一篇
java线程的五大状态，阻塞状态详解
下一篇