单链表

链表有序的列表并是以节点的方式来存储的，每个节点包含data、next，next用来指向下一个节点的所在内存地址。链表区分带头节点和不带头节点如果链表中带head头节点，头节点只有next，没有data；尾节点的next指向NULL

插入节点

删除节点

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        // 测试
        // 1. 创建节点
        HeroNode hero1 = new HeroNode(1,"AA","aa");
        HeroNode hero2 = new HeroNode(2,"BB","bb");
        HeroNode hero3 = new HeroNode(3,"CC","cc");
        HeroNode hero4 = new HeroNode(4,"DD","dd");

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

        // 3. 链表加入节点
//        singleLinkedList.add(hero1);
//        singleLinkedList.add(hero2);
//        singleLinkedList.add(hero3);
//        singleLinkedList.add(hero4);

        // 3. 链表按照编号插入
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero3);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero4);

        // 4. 显示链表
        System.out.println("添加后的链表");
        singleLinkedList.list();

        // 5. 修改节点
        HeroNode newHeroNode = new HeroNode(2,"修改","修改");
        singleLinkedList.update(newHeroNode);
        System.out.println("修改后的链表");
        singleLinkedList.list();

        // 6. 删除节点
        singleLinkedList.del(4);
        System.out.println("删除后的链表");
        singleLinkedList.list();
    }
}

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

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

    /**
     * 打印节点时，以String的形式返回
     * @return
     */
    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}

/**
 * 定义链表SingleLinkedList
 */
class SingleLinkedList{
    private HeroNode head = new HeroNode(0,"",""); // 初始化一个不包含任何数据的头节点

    /**
     * 添加节点到单向链表：通过while循环找到最后一个节点，并将最后一个节点的next指向新的节点
     * 1. 找到当前链表的最后节点
     * 2. 将最后这个节点的next 指向新的节点
     * @param heroNode
     */
    public void add(HeroNode heroNode){
        HeroNode temp = head; // 因为head节点不能动，因此我们需要一个辅助遍历temp，通过temp开始从头节点遍历，直到next指向的是null，意味着当前节点是最后一个节点
        while(true){ // 遍历链表，找到最后
            if(temp.next == null){
                break;
            }
            temp = temp.next;
        }
        temp.next = heroNode; // 当退出while循环时，temp已经指向了链表的最后一个节点，此时将这个节点的next指向新heroNode。添加节点成功
    }

    /**
     * 遍历整个链表
     */
    public void list(){
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }

        HeroNode temp = head.next; // 因为head头节点不能动，所以需要一个辅助变量来遍历，因为头节点没有data所以直接指向头节点的下一个节点
        while (true){
            if(temp == null){ // 最后一个节点时，next为null，此时直接退出while循环
                break;
            }
            System.out.println(temp); // 打印出当前节点的内容
            temp = temp.next; // 指向下一个节点，注意：next指向的是下一个节点的内存地址，所以通过temp.next获得是下一个节点的内存地址，并赋值给temp，temp已经是下一个节点了
        }
    }

    /**
     * 按照HeroNode的no，插入到指定位置
     * @param heroNode
     */
    public void addByOrder(HeroNode heroNode){
        HeroNode temp = head;
        boolean flag = false;
        while (true){
            if(temp.next == null){ // 已经到最后一个节点
                break;
            }
            if(temp.next.no > heroNode.no){ // 找到要插入节点的位置
                break;
            }
            if(temp.next.no == heroNode.no){ // 要添加的heroNode编号已经存在
                flag = true;
                break;
            }
            temp = temp.next; // 后移，遍历当前链表
        }

        if (flag){
            System.out.println(" 要插入的no已经存在，不能插入" + heroNode.no);
        }else {
            heroNode.next = temp.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.println(" 没有找到对应的编号不能修改 " + newHeroNode.no);
        }
    }

    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.println("要删除的节点不存在");
        }
    }
}