[数据结构与算法]单链表的增删查改

🏀 链表的介绍

??????链表是有序的列表，有如下特点：
（1）链表是以节点的方式存储，为链式存储；
（2）每个节点包含data域，next域：指向下一个节点；
（3）如下图所示：链表的各个节点不一定是连续存储的；
（4）链表分带头节点和没有头节点的，根据实际需求确定。

??????链表它在内存中是存储如下：链表的物理结构示意图👇👇👇

??????链表在我们想象概念中的样子是怎样的呢？如下是链表的逻辑结构示意图👇👇👇在我们编码时就把它想象成这样是最好的，不要把自己也给绕进去了~~~

🏀 单链表的添加

???单链表的添加有两种方法，如下所示：👇👇👇
???💥① 不考虑编码的顺序（方法一）也可以称之为尾插法
1.先创建一个head头节点，作用就是表示单链表的头；
2.后面我们每添加一个节点，就直接加入到链表的最后。
???方法一添加示意图如下所示👇👇👇

???💥② 需要按照编号的顺序添加（方法二）
???第二种方法就在内存中就实现了数据的添加操作，比在数据库中进行操作时要快很多，效率高！！！（推荐使用呀！）👍👍👍
1.首先找到新添加的节点的位置，是通过辅助变量(指针)temp，通过遍历实现；
2.新的节点.next = temp.next；
3.将temp.next = 新的节点。
???方法二添加示意图如下所示👇👇👇

🏀 单链表的遍历

????💥单链表的遍历过程相比较而言是最简单的一个过程，一个步骤就可以搞定
1.通过一个辅助变量（指针），帮助遍历整个单链表即可完成查询过程。

🏀 单链表的修改

????💥单链表的修改核心思想就是找到节点并替换除编号外的其他属性值
1.根据编号no来确认节点修改的位置，借助辅助变量(指针)temp，通过遍历实现
2. temp.name == 修改节点.name，temp.job ==修改节点.job
???单链表修改示意图如下所示👇👇👇

🏀 单链表的删除

????💥单链表的删除思想：找到被删除的节点后借助temp临时变量(指针)指向下下个节点
1.先找到需要删除的这个节点的前一个节点temp
2.temp.next = temp.next.next
3.被删除的节点将不会有其它引用指向，会被垃圾回收机制回收
???单链表删除示意图如下所示👇👇👇

🏀 具体代码实现

????💥以下是对上述增删查改思想的代码实现，功能都已完成，大家可以在对相关操作思考后再写代码的效率会高很多哦，不然也比较烧脑袋，有些地方我也花了不少时间去琢磨🙌🙌🙌

package com.java.linkedlist;

/**
 * Author:YuHao
 * Description: 辅助变量temp 其实就是表示指针的概念
 * Date:2022/7/15
 * Version:1.0
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {

        //1.先创建节点
        PersonNode personNode1 = new PersonNode(1, "鸣人", "七代火影");
        PersonNode personNode2 = new PersonNode(2, "卡卡西", "六代火影");
        PersonNode personNode3 = new PersonNode(3, "纲手", "五代火影");
        PersonNode personNode4 = new PersonNode(4, "水门", "四代火影");
        PersonNode personNode5 = new PersonNode(5, "佐助", "上忍");
        PersonNode personNode6 = new PersonNode(6, "宁次", "上忍");
        PersonNode personNode7 = new PersonNode(7, "小樱", "上忍");
        PersonNode personNode8 = new PersonNode(8, "雏田", "上忍");

        //2.创建一个链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();

        //3.将所创建的节点加入到单链表中(方法一)
        singleLinkedList.addNode(personNode1);
        singleLinkedList.addNode(personNode3);
        singleLinkedList.addNode(personNode2);
        singleLinkedList.addNode(personNode4);

        System.out.println("方法一的添加方式:");
        //4.查看链表信息
        singleLinkedList.showNode();

        //3.将所创建的节点加入到单链表中(方法二)
        singleLinkedList.addNodeByOrder(personNode5);
        singleLinkedList.addNodeByOrder(personNode6);
        singleLinkedList.addNodeByOrder(personNode8);
        singleLinkedList.addNodeByOrder(personNode7);

        System.out.println("方法二的添加方式:");
        //4.查看链表信息
        singleLinkedList.showNode();

        System.out.println("节点修改后的信息为:");
        //5.修改节点信息
        PersonNode newPersonNode = new PersonNode(8, "田妹", "鸣人老婆");
        singleLinkedList.editNode(newPersonNode);
        singleLinkedList.showNode();

        System.out.println("节点删除后的信息为:");
        singleLinkedList.deleteNode(7);
        singleLinkedList.showNode();
        singleLinkedList.deleteNode(7);

        System.out.println();
        System.out.print("有效节点数为:"+getNodeLength(singleLinkedList.getHead()));

    }
    //面试题：求单链表中有效节点的个数
    public static int getNodeLength(PersonNode personNode){
        if (personNode.next == null){
            System.out.println("链表为空，无有效节点");
            return 0;
        }
        int length = 0;
        PersonNode temp = personNode.next;
        while (temp != null){
            length++;
            temp = temp.next;
        }
        return length;
    }
}

//定义SingleLinkedList 管理人物节点
class SingleLinkedList {
    //先初始化头节点，因为头节点是不会变动的节点,不存放具体的数据
    private PersonNode head = new PersonNode(0,"","");

    //返回头节点
    public PersonNode getHead() {
        return head;
    }

    //1.添加节点到单链表中(方法一：不考虑编号的顺序，将节点直接添加到链表的尾部)
    //编码思路:(1)找到当前链表的最后节点; (2)将最后的这个节点的next指向新的节点
    public void addNode(PersonNode personNode){

        //由于head头节点不能动的原因，这里借助辅助变量temp
        PersonNode temp = head;

        //遍历链表，找到最后节点
        while (true) {

            //找到链表的最后条件
            if (temp.next == null){
                break;
            }

            //若没找到，则temp后移
            temp = temp.next;
        }

        //当退出while循环时，temp指向了单链表的最后。只要将最后节点的next指向新的节点即可完成添加的过程
        temp.next = personNode;
    }

    //1.添加节点到单链表中(方法二：考虑编号的顺序，根据排名顺序将人物插入到指定的位置上)
    //若该顺序位置上已有人物在，则添加失败，并给出相应的提示
    public void addNodeByOrder(PersonNode personNode){

        //因为头节点不能动的原因，这里仍通过辅助变量(指针)temp遍历来找到我们需要添加的位置
        //因为单链表的原因，我们找到的temp是位于添加位置的前一个节点，否则无法插入

        PersonNode temp = head;
        boolean tag = false; // 标识添加的编号是否存在，默认为false

        while (true) {

            //说明temp已经位于单链表的最后了
            if (temp.next == null){
                break;
            }

            if (temp.next.no > personNode.no){  //位置找到，在temp的后面插入即可
                break;
            }else if (temp.next.no == personNode.no){ //说明想要添加的personNode的编号已经存在，不能再次添加了
                tag = true; //说明编号已经存在
                break;
            }

            //后移，遍历当前单链表
            temp = temp.next;
        }

        //判断tag的值
        if (tag){
            System.out.println("准备插入的人物的编号:"+personNode.no+"已经存在，不能多次添加");
        }else {
            //将temp.next的值变成personNode.next,相当于把节点往后移动一个
            personNode.next = temp.next;
            //插入到单链表中，temp的后面
            temp.next = personNode;
        }
    }


    //2.查看链表，通过遍历实现，同样借助辅助变量
    public void showNode(){

        //先判断单链表是否为空
        if (head.next == null){
            System.out.println("链表为空");
            return;
        }

        //由于头节点不能动，因此我们需要借助辅助变量进行遍历temp
        //因为一旦上述的if条件不满足，证明单链表至少有一个数据，所以temp直接指向头指针的next即head.next
        PersonNode temp = head.next;

        while (true) {
            //判断是否到达单链表的最后
            if (temp == null){
                break;
            }
            //输出节点的信息
            System.out.println(temp);

            //将temp后移，否则死循环
            temp = temp.next;
        }
    }

    //3.修改节点的信息，根据no编号来修改，若no编号进行了修改等同于添加了,所以no编号是不能更改的
    //说明: 根据personNode的no编号来修改即可
    public void editNode(PersonNode personNode){
        //判断链表是否为空
        if (head.next == null){
            System.out.println("链表为空");
            return;
        }
        //找到需要修改的节点，根据no编号来确认位置
        //需要借助辅助变量temp
        PersonNode temp = head.next;
        boolean tag = false; //表示是否找到该节点

        while (true) {
            if (temp == null){
                break; //单链表遍历完成
            }
            if (temp.no == personNode.no){
                tag = true;
                break;
            }
            temp = temp.next;
        }

        //根据tag来判断是否找到要修改的节点
        if (tag) {
            temp.name = personNode.name;
            temp.job = personNode.job;
        }else {
            System.out.println("没有找到编号:"+personNode.no+"的节点，不能修改");
        }
    }

    //4.删除节点
    //思路:(1)head不能动，因此我们需要借助一个temp辅助变量节点找到待删除节点的前一个节点
    //(2)则我们在比较时，是temp.next.no 和 需要删除的节点.no 进行比较的过程
    public void deleteNode(int no){
        PersonNode temp = head;
        boolean tag = false; // 标识是否找到待删除的节点

        while (true) {
            if (temp.next == null){
                System.out.println("遍历结束，已经到单链表的最后了");
                break;
            }
            if (temp.next.no == no){ //找到待删除的节点的前一个节点
                tag = true;
                break;
            }
            temp = temp.next;
        }

        if (tag){   //找到待删除的节点
            // 可以删除
            temp.next = temp.next.next;
        }else {
            System.out.println("要删除编号为"+no+"的节点不存在");
        }
    }

}

//定义一个PersonNode,每一个PersonNode对象就是一个节点
class PersonNode {
    public int no;
    public String name;
    public String job;
    public PersonNode next;

    //创建构造器
    public PersonNode(int no, String name, String job){
        this.no = no;
        this.name = name;
        this.job = job;
    }

    //重写toString方法，为了显示方便
    @Override
    public String toString() {
        return "PersonNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", job='" + job + '\'' +
                '}';
    }
}

????以上便是对单链表基础的增删查改的全部分析和实现过程，单链表还有更多复杂的需求分析，还有更多优化的过程，值得大家去学习积累，毕竟学好链表打好基础对之后的底层代码理解帮助很大哦！！！💬💬💬下篇博文将更新双向链表等知识的梳理。
????路过的小伙伴，如果博文有帮助到你解决问题，可以点赞+收藏+关注一波呀~👊👊👊本人将会持续更新相关数据结构与算法Java实现版本学习的博文，感谢您的支持哦！！！芜湖起飞??????