【数据结构】—— 单链表的增删改查-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数据结构】—— 单链表的增删改查。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

单链表的增删改查,数据结构,java,开发语言,数据结构

❤️一名热爱Java的大一学生，希望与各位大佬共同学习进步❤️

🧑个人主页：@周小末天天开心

各位大佬的点赞👍 收藏⭐ 关注✅，是本人学习的最大动力

感谢！

📕该篇文章收录专栏—数据结构

方法重写

重写条件

重写好处

重写演示

单链表

介绍

单链表的增删改查

创建HeroNode类，用来存放信息

创建SingleLinkedList类，用来存放方法

按顺序插入到链表最后

按照编号的顺序添加

编写显示该链表的方法

修改节点信息

删除节点

编写SingleLinkedListDemo类进行演示

获取单链表中的节点个数

将单链表反转

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

测试单链表的增删改查，查看输出结果

方法重写

在学习之前先要了解什么是方法重写，简单来说，方法重写就是子类可继承父类中的方法，而不需要重新编写相同的方法，但有时子类并不想原封不动地继承父类的方法，而是想作一定的修改，这就需要采用方法的重写。方法重写又称方法覆盖。

重写条件

（1）必须是继承关系

（2）子类中的方法要和父类一样

（3）重写是发生在两个类中

重写好处

子类扩展了父类中的方法，让父类中的功能变得更加强大。

注意：如果子类想调用父类方法，直接在重写方法中使用 super 关键字重写父类中的方法，且方法的修饰符必须是公共的，私有方法不可以重写。

重写演示

编写一个父类Animal

public class Animal { //创建一个父类 Animal
    public String name;//属性

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }
    public void eat() {
        System.out.println("喜欢……");
    }
}

再编写一个子类Dog，并继承父类

public class Dog extends Animal{//子类 Dog 继承父类 Animal

    @Override //方法重写的标记，看到此标记就代表方法重写现象
    public void eat() {
        //方法重写现象，在该类中eat方法和父类Animal中的eat方法的名称一样
        super.eat();//调用父类的 eat 方法
        System.out.println("吃骨头……");
    }
}

编写Demo类进行演示

public class Demo {
    public static void main(String[] args) {
        Dog dog = new Dog();
        dog.setName("哈士奇……");
        System.out.println(dog.getName());
        dog.eat();
    }
}

查看输出结果：

单链表的增删改查,数据结构,java,开发语言,数据结构

单链表

介绍

链表是一个有序的列表，但是它在内存中是存储如下的：

	头指针
head	150

地址	data域	next域
110	a2	180
120
130	a4	170
140	a6	NULL
150	a1	110
160
170	a5	140
180	a3	130

（1）链表是以节点的方式来存储的，是链式存储

（2）每个节点包含data域，next域：指向下一个节点

（3）如上图：发现链表的各个节点不一定是连续存储的

（4）链表分带头节点的链表和没有头节点的链表，根据实际需求来确定单链表（带头节点）

单链表的增删改查

创建HeroNode类，用来存放信息

//定义HeroNode，每个HeroNode 对象就是一个节点
class HeroNode {
    public int no;
    public String name;
    public String nickname;//昵称
    public HeroNode next;//指向下一个节点

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

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

创建SingleLinkedList类，用来存放方法

按顺序插入到链表最后

（1）先创建一个 head头节点，作用就是表示单链表的头

（2）后面每添加一个节点，就直接加入到链表最后，也可以理解为每有一个新节点，我们就把最后一个节点的 next域指向新节点

链表为空的条件：head.next == null（表示头节点的下一位为空）

链表最后的条件：temp.next == null （temp为辅助变量）

//先初始化一个头节点，头节点不要动，如果改动头节点那么就不好去找到链表最顶端的节点了
    private HeroNode head = new HeroNode(0 , "" , "");
    //头节点不存放具体的数据

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

    //思路：
    //1.找到当前链表的最后一个节点
    //2.将最后这个节点的next域指向新的节点
    public void add(HeroNode heroNode) {
        //因为head头节点不能动，所以需要一个辅助变量temp
        HeroNode temp = head;//将temp指向head
        //遍历链表，找到链表最后
        while(true) {
            //当temp的域等于空时，说明temp找到了链表最后了
            if(temp.next == null) {//找到最后了，结束程序
                break;
            }
            //如果没有找到最后，就将temp 后移指向下一个数据
            temp = temp.next;
        }
        //当退出了 while 循环时，那么 temp 就指向了链表的最后
        temp.next = heroNode; //将最后这个节点的next域指向新的节点
    }

按照编号的顺序添加

（1）首先找到新添加节点的位置，是通过辅助变量找到的

（2）添加方法：

1）新的节点.next = temp.next

2）temp.next = 新的节点

    public void addByOrder(HeroNode heroNode) {
        //因为头节点不能动，因此需要通过一个辅助指针(变量)来帮助找到添加的位置
        //因为是单链表，所以辅助变量temp应该是位于添加位置的前一个节点，否则无法插入
        HeroNode temp = head;
        boolean flag = false;//flag标志添加的编号是否存在，默认为false
        while(true) {
            if(temp.next == null) {//说明temp已经到了链表最后
                break;
            }
            if(temp.next.no > heroNode.no) {//位置找到，就在temp的后面插入
                //如果temp.next.no > heroNode.no 
                //说明 heroNode 就应该插入到 temp 和 temp.next 之间
                break;
            }
            if(temp.next.no == heroNode.no) {
                //说明希望添加的heroNode的编号以及存在
                flag = true;
                break;
            }
            temp = temp.next;//如果三个条件都不符合就将 temp 后移，继续遍历
        }
        //判断flag的值
        if(flag) {
            //如果 flag == true。说明编号已存在，所以无法插入
            System.out.printf("准备插入的编号%d已经存在，无法插入",heroNode.no);
        } else {
            //否则可以插入到链表中，temp 的后面
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
}

编写显示该链表的方法

//显示链表[遍历]
    public void list() {
        //先判断链表是否为空
        if(head.next == null) { //说明了链表为空
            System.out.println("链表为空");
            return;
        }
        //如果链表不为空，且头节点不能动，因此需要一个辅助变量来遍历
        HeroNode temp = head.next;
        //因为已经判断了链表不为空，说明链表至少有一个数据，所以是 head.next(头节点指向的下一个数据)
        while(true) {
            //判断是否已经到了链表最后
            if(temp == null) {
                //遍历是到了链表最后，所以退出循环
                break;
            }
            //如果不为空，则输出该节点的信息
            System.out.println(temp);//已经重写了 toString()
            //输出后需要将temp后移一位，因为输出该信息后需要让temp指向下一位，输出下一位的信息
            temp = temp.next;//不后移就是一个死循环
        }
    }

修改节点信息

//修改节点的信息，根据no编号来修改，即no编号不能改
    //根据newHeroNew 的 no 来进行修改即可
    public void update(HeroNode newHeroNew) {
        //判断是否为空
        if(head.next == null) {
            System.out.println("该链表为空");
            return;
        }
        //找到需要更改的节点，根据no编号
        //定义一个辅助变量
        HeroNode temp = head.next;//temp 赋的值为头节点的下一个节点
        boolean flag = false;//表示是否找到了该节点
        while(true) {
            if(temp == null) {
                //说明链表已经遍历完成，因为temp 指向的是下一个节点(需要注意，和上面不同)
                break;
            }
            if(temp.no > newHeroNew.no) {
                //因为temp 指向的是下一个节点。
                //所以就不需要 temp.next.no 了(需要注意，和上面不同)
                //位置找到，就在temp后面进行添加
                break;
            }
            if(temp.no == newHeroNew.no) {
                //因为temp 指向的是下一个节点。所以就不需要 temp.next.no 了(需要注意，和上面不同)
                //说明希望添加的编号已经存在
                flag = true;
                break;
            }
            temp = temp.next;//如果循环没有结束就一直进行遍历
        }
        //根据 flag 来进行判断是否找到了要修改的节点
        if(flag) {//如果flag 为 true 说明就找到了要修改的节点
            temp.name = newHeroNew.name;
            temp.nickname = newHeroNew.nickname;
            //注意：no 编号不可以修改
        } else { //说明没有找到要修改的节点
            System.out.printf("没有找到编号等于%d的节点\n",newHeroNew.no);
        }
    }

删除节点

（1）先找到需要删除的这个节点的前一个节点 temp

（2）temp.next = temp.next.next

（3）被删除的节点，将不会有其他引用指向，会被垃圾回收机制回收

    /*
    思路
    1.head 节点不能动，因此我们需要一个 temp 辅助接点找到待删除的前一个节点
    2.说明我们在比较时，是 temp.next.no 和需要删除的节点的 no 比较
     */
    public void delete(int no) {
        HeroNode temp = head;
        boolean flag = false;//标志是否找到了待删除的节点
        while(true) {
            if(temp.next == null) {//已经到链表的最后了
                break;
            }
            if(temp.next.no == no) {
                //找到了待删除节点的前一个节点temp
                flag = true;
                break;
            }
            temp = temp.next;//让 temp 后移，实现遍历
        }
        //判断 flag
        if(flag) {
            //如果flag位真，找到了要删除的节点，可以删除
            temp.next = temp.next.next;//将temp的下下个节点赋给下个节点(删除temp的下个节点)
        } else {
            System.out.printf("要删除的%d节点不存在\n",no);
        }
    }

编写SingleLinkedListDemo类进行演示

获取单链表中的节点个数

//获取单链表中节点的个数(如果是带头节点的链表。需要不统计头节点)

    /**
     * @param head 链表的头节点
     * @return 返回的就是有效节点的个数
     */
    public static int getlength(HeroNode head) {
        if (head.next == null) {
            //说明该链表为空链表
            return 0;
        }
        int length = 0;
        //定义一个辅助变量，没有统计头节点
        HeroNode cur = head.next;
        while (cur != null) {
            length++;
            cur = cur.next;//后移 cur 进行遍历
        }
        return length;
    }

将单链表反转

（1）先定义一个节点 reverseHead = new HeroNode();

（2）从头到尾遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表 reverseHead的最前端

（3）原来的链表的 head.next = reverseHead.next

//将单链表反转
    public static void reverseList(HeroNode head) {
        //如果当前链表为空，或者只有一个节点，则无需反转，直接返回
        if(head.next == null || head.next.next == null) {
            return ;
        }
        //定义一个辅助的指针(变量)，帮助我们遍历原来的链表
        HeroNode cur = head.next;
        HeroNode next = null;//指向当前节点[cur]的下一个节点
        HeroNode reverseHead = new HeroNode(0, " ", " ");
        //遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表 reverseHead 的最前端
        while(cur != null) {
            next = cur.next;//先暂时保存，当前节点的下一个节点，因为后面需要使用
            cur.next = reverseHead.next;//将 cur 的下一个节点指向新的链表的最前端
            reverseHead.next = cur;//将 cur 连接到新的链表上
            cur = next;//让 cur 后移
        }
        //将 head.next 指向 reverseHead.next ，实现单链表的反转
        head.next = reverseHead.next;
    }

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

//查找单链表中倒数第k个节点
    /*
    思路
    1.编写一个方法，接收 head 节点，同时接收一个 index
    2.index 表示是倒数第 index 个节点
    3.先将链表从头到尾进行遍历，得到的链表的总长度 getlength
    4.得到 size 后，从链表的第一个节点开始遍历(size - index)个，
    5.如果找到了，则返回该节点，否则返回 null
     */
    public static HeroNode findLastIndexNode(HeroNode head, int index) {
        //如果该链表为空，则返回 null
        if(head.next == null) {
            return null;//返回空
        }
        //第一个遍历得到链表的长度
        int size = getlength(head);
        //第二个遍历得到 size - index 的位置，就是我们倒数第k个节点
        //首先校验 index 的长度
        if(index <= 0 || index > size) {//不可以小于等于零以及不能大于 size
            return null;
        }
        //定义辅助变量然后进行赋值
        HeroNode cur = head.next;
        //for 循环定位到倒数的 index
        for(int i = 0; i < size - index; i++) {
            cur = cur.next;//后移一位遍历
        }
        return cur;
    }

测试单链表的增删改查，查看输出结果

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //进行测试
        //先创建节点
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");

        //创建要给链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();

        //直接加入在链表尾部
        singleLinkedList.add(hero1);
        singleLinkedList.add(hero2);
        singleLinkedList.add(hero3);
        singleLinkedList.add(hero4);

//        按顺序插入链表
//        singleLinkedList.addByOrder(hero1);
//        singleLinkedList.addByOrder(hero4);
//        singleLinkedList.addByOrder(hero3);
//        singleLinkedList.addByOrder(hero2);

        //显示
        singleLinkedList.list();

//        测试要修改节点的代码
//        System.out.println("=====修改后的链表为=====");
//        HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~~~");
//        singleLinkedList.update(newHeroNode);
//
//        //显示
//        singleLinkedList.list();

        //删除一个节点
//        System.out.println("=====删除后的链表为=====");
//        singleLinkedList.delete(1);
//        singleLinkedList.delete(4);
//
//        //显示
//        singleLinkedList.list();

//        //显示该链表中有效节点的个数
//        System.out.println("=====该链表中有效节点的个数是=====");
//        System.out.println(getlength(singleLinkedList.getHead()));
//
//        //测试一下看看是否得到了倒数第k个节点
//        HeroNode res = findLastIndexNode(singleLinkedList.getHead(), 2);
//            System.out.println("res= " + res);

//        //测试单链表的反转功能
//        System.out.println("=====原来链表的情况=====");
//        singleLinkedList.list();
//        System.out.println("=====反转后的链表情况=====");
//        reverseList(singleLinkedList.getHead());
//        singleLinkedList.list();
    }
}

单链表的增删改查,数据结构,java,开发语言,数据结构文章来源地址https://www.toymoban.com/news/detail-780839.html