单链表的创建和遍历的实现(Java)

之前站点上的文章，搬过来一下

（一点学习记录和问题思考）

创建单链表并实现数据的增删改查…

案例内容

将水浒英雄作为元素加进去，并且对他们进行排序输出，使用带head节点的单链表，实现一个水浒英雄排行榜管理，有两种方法:

添加英雄时，直接添加到链表尾部
根据排名将英雄插入到指定位置（如果有这个排名，则添加失败，给出提示）

方法一

思路

要先创造一个头节点，作为链表的头(力扣里把他叫做哨兵节点)，因为需要判断链表是否为空
之后每添加一个节点，就把他放在链表的尾部
关键是遍历，因为有了一个头节点，且这个头节点是不能移动的(注释有讲)，所以需要一个辅助变量来遍历整个链表

代码实现

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.list();
    }
}

//定义SingleLinkedList（创建链表）  管理英雄
class SingleLinkedList {
    //先初始化一个头节点，头节点不能动(因为动了头节点之后遍历顺序会乱)
    private HeroNode head = new HeroNode(0, "", "");  //private一个头节点，这样可以确保他不会移动

    public void add(HeroNode heroNode) {
        //头节点不能动，需要一个辅助变量temp遍历
        HeroNode temp = head;
        //遍历，找到链表的最后
        while (true){
            if (temp.next == null) {
                break;
            }
            //如果没找到最后，将temp后移
            temp = temp.next;
        }
        //将最后节点的next指向一个新的节点
        temp.next = heroNode;
    }
    //显示链表[遍历]
    public void list() {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        HeroNode temp = head.next;  //这是不为空的情况
        while (true) {
            if (temp == null) {
                break;
            }
            System.out.println(temp);
            //将temp后移，不然会陷入死循环
            temp = temp.next;
        }
    }
}

//定义一个类用于存放英雄的数据
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 + '\'' +
                '}';  //next不要写进去，不然每次输出会连带着下一个节点信息输出
    }
}

思考一：为什么要重写 toString 方法？

一般这个方法的作用，是将对象中各个属性值按照字符串的形式输出出来(即以文本的方式表示此对象的字符串)，但是不重写 toString（）的话,输出的就是一个内存地址(哈希码值)。

思考二：什么是重写？

指的是从父类继承之后，子类对于父类某方法的具体实现进行修改，你在System.out.println()一个对象时，是默认调用了 toString（）这个方法的，将对象转为字符串输出，toString（）方法继承于所有类的隐性基类，如果某类无重写 toString（）方法，这时调用 toString（）将得到（类名+地址名名）这样的字符串。改成别的方法名是不能称为“重写”的。重写 toString（）方法可以输出自己想要的文字信息。

小结

这个方法可以顺利输出英雄的顺序，但是如果在main函数中改变输入英雄的编号顺序，那么输出中英雄的编号顺序也会被打乱，那么就没法实现英雄排序这么一个功能了，所以就有了另外一个方法来插入英雄。

方法二

思路

大部分和方法一的差不多，主要关键点是找到插入的位置，判断编号是否存在，以及如何插入，与方法一一样，方法二任然需要辅助变量，来帮我们遍历链表。因为是单链表，不能找到前一个节点，所以在辅助变量移动到节点时，我们需要比较插入节点和辅助变量的下一个节点，然后根据情况是否符合将新节点插入到辅助变量后面。

代码实现

public void addByOrder(HeroNode heroNode) {
        HeroNode temp = head;
        boolean flag = false; //flag标志编号是否存在，默认为false
        while (true) {
            if (temp.next == null) {
                break;  //说明已经到链表的最后
            }
            if (temp.next.no > heroNode.no) {
                break;      //要让temp的下一个节点编号大于插入节点，才算找到位置
            } else if (temp.next.no == heroNode.no) {
                flag = true;
                break;     //编号存在，flag变为true，退出循环
            }
            temp = temp.next;  //后移，遍历链表
        }
        if (flag) {  //编号存在，不能添加
            System.out.printf("插入英雄的编号 %d 已经存在，不能加入\n", heroNode.no);
        } else {
            heroNode.next = temp.next;  //插入到链表中，temp后面
            temp.next = heroNode;
        }
    }

上面是一部分，将节点插入到单链表中，flag变量的存在，用来标识编号是否存在

重点：关键点是节点的插入

heroNode.next = temp.next;

temp.next = heroNode;

我们要将节点插入到 temp 和 temp.next 之间，所以将 heroNode.next 指向 temp.next (因为 temp.next 指向的下一个节点)，这样 heroNode.next 就可以指向下一个节点，而 temp.next 指向 heroNode ，就可以完成节点的连接了。

节点的修改

//修改链表
    public void update(HeroNode newHeroNode) {
        if (head.next == null) {   //判断链表是否为空
            System.out.println("链表为空");
            return;
        }
        HeroNode temp = head.next;
        boolean flag = false; //表示是否找到该结点
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.no == newHeroNode.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.name = newHeroNode.name;
            temp.nickname = newHeroNode.nickname;
        } else {
            System.out.printf("没有找到编号为 %d 的英雄\n", newHeroNode.no);
        }
    }

主要是要修改的节点，再针对要改的属性就行修改

设置一个newHeroNode变量存放修改的数据

HeroNode newHeroNode = new HeroNode(修改的数据);
SingleLinkedList.update(newHeroNode);

在主函数中加入这两句即完成对节点数据的修改

节点的删除

//删除节点
    public void del(int no) {
        HeroNode 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; //将要删除的节点的前一个节点指向他的下一个节点
        }
        else {
            System.out.printf("要删除的 %d 节点不存在\n", no);
        }
    }