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

1)链表是以节点的方式来存储，是链式存储
2)每个节点包含 data域，next域:指向下一个节点.
3)如图: 发现链表的各个节点不一定是连续存储.
4)链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

思路分析：
添加(创建)
1.先创建- -个head头节点，作用就是表示单链表的头
2.后面我们每添加一-个节点，就直接加入到链表的最后遍历:

代码实现：（按添加顺序排序）

package com.main.dataStructures;

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        HeroNode hero1 = new HeroNode(1,"wp","pp");
        HeroNode hero2 = new HeroNode(2,"lmx","dg");
        HeroNode hero3 = new HeroNode(3,"bb","ss");
        SingleLinkedList list = new SingleLinkedList();
        list.addNode(hero1);
        list.addNode(hero2);
        list.addNode(hero3);
        list.showNode();

    }
}


class SingleLinkedList{
    private HeroNode head = new HeroNode(0,"","");
    //添加
    public void addNode(HeroNode node){
        HeroNode temp = head;
        while (true){
            //判满
            if (temp.next == null){
                break;
            }
            //后移
            temp = temp.next;
        }
        //添加
        temp.next = node;
    }

    //显示
    public void showNode(){
        //判空
        if (head.next==null){
            System.out.println("链表为空");
        }
        //不能动头，定辅变量
        HeroNode temp = head.next;
        while (true){
            //判断是否到链表最后
            if (temp==null){
                break;
            }
            System.out.println(temp);
            //后移
            temp = temp.next;
        }
    }
}
class HeroNode{
    int no;
    String name;
    String nickName;
    HeroNode next;

    public HeroNode(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '}';
    }
}

思路分析：
1.首先找到新添加的节点的位置,是通过辅助变量(指针),通过遍历来搞定
2.新的节点.next=temp.next
3.将temp.next=新的节点

代码实现：（按编号排序）

package com.main.dataStructures;

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        HeroNode hero1 = new HeroNode(1,"wp1","pp");
        HeroNode hero2 = new HeroNode(2,"lmx2","dg");
        HeroNode hero3 = new HeroNode(3,"wp3","ss");
        HeroNode hero4 = new HeroNode(4,"wp4","qq");
        HeroNode hero5 = new HeroNode(5,"wp5","ww");
        HeroNode hero6 = new HeroNode(6,"wp6","aa");
        SingleLinkedList list = new SingleLinkedList();
        list.addNode2(hero5);
        list.addNode2(hero1);
        list.addNode2(hero6);
        list.addNode2(hero2);
        list.addNode2(hero4);
        list.addNode2(hero3);
        list.showNode();

    }
}


class SingleLinkedList{
    private HeroNode head = new HeroNode(0,"","");
    //按添加顺序添加
    public void addNode(HeroNode node){
        HeroNode temp = head;
        while (true){
            //判满
            if (temp.next == null){
                break;
            }
            //后移
            temp = temp.next;
        }
        //添加
        temp.next = node;
    }
    //按编号排序添加
    public void addNode2(HeroNode node){
        HeroNode temp = head;
        boolean flag = false;
        while (true){
            //判满:temp已经是链表最后一个元素了，无法添加

            if (temp.next == null){
                break;
            }
            if (temp.next.no>node.no){
                break;
            }else if (temp.next.no==node.no){
                flag = true;
                break;
            }
            //后移
            temp = temp.next;
        }
        //添加
        if (flag){
            System.out.println("编号已存在");
        }else {
            node.next = temp.next;
            temp.next = node;
        }
    }

    //显示
    public void showNode(){
        //判空：头节点的next等于null;说明该链表只有一个头节点，没有其他数据
        if (head.next==null){
            System.out.println("链表为空");
        }
        //不能动头，定辅变量
        HeroNode temp = head.next;
        while (true){
            //判断是否到链表最后
            if (temp==null){
                break;
            }
            System.out.println(temp);
            //后移
            temp = temp.next;
        }
    }
}
class HeroNode{
    int no;
    String name;
    String nickName;
    HeroNode next;

    public HeroNode(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '}';
    }
}

修改：
根据编号找到此人，然后将其除编号外其他对应信息修改即可

package com.main.dataStructures;

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        HeroNode hero1 = new HeroNode(1,"wp1","pp");
        HeroNode hero2 = new HeroNode(2,"lmx2","dg");
        HeroNode hero3 = new HeroNode(3,"wp3","ss");
        HeroNode hero4 = new HeroNode(4,"wp4","qq");
        HeroNode hero5 = new HeroNode(5,"wp5","ww");
        HeroNode hero6 = new HeroNode(6,"lmx6","asb");
        HeroNode hero7 = new HeroNode(6,"lmxcbb","a23");
        SingleLinkedList list = new SingleLinkedList();
        list.addNode2(hero5);
        list.addNode2(hero1);
        list.addNode2(hero6);
        list.addNode2(hero2);
        list.addNode2(hero4);
        list.addNode2(hero3);

        list.showNode();
        System.out.println("修改后的情况：~~");
        list.updateNode(hero7);
        list.showNode();

    }
}


class SingleLinkedList{
    private HeroNode head = new HeroNode(0,"","");
    //按添加顺序添加
    public void addNode(HeroNode node){
        HeroNode temp = head;
        while (true){
            //判满
            if (temp.next == null){
                break;
            }
            //后移
            temp = temp.next;
        }
        //添加
        temp.next = node;
    }
    //按编号排序添加
    public void addNode2(HeroNode node){
        HeroNode temp = head;
        boolean flag = false;
        while (true){
            //判满:temp已经是链表最后一个元素了，无法添加
            if (temp.next == null){
                break;
            }
            if (temp.next.no>node.no){
                break;
            }else if (temp.next.no==node.no){
                flag = true;
                break;
            }
            //后移
            temp = temp.next;
        }
        //添加
        if (flag){
            System.out.println("编号已存在");
        }else {
            node.next = temp.next;
            temp.next = node;
        }
    }
    //修改
    //根据编号修改除编号外的其他数据
    public void updateNode(HeroNode newNode){
        HeroNode temp = head.next;
        boolean flag = false;
        while (true){
            if (temp == null){
                break;//已经遍历到最后了
            }
            if (temp.no == newNode.no){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            temp.name = newNode.name;
            temp.nickName = newNode.nickName;
        }else {
            System.out.println("没有该用户");
        }

    }

    //显示
    public void showNode(){
        //判空：头节点的next等于null;说明该链表只有一个头节点，没有其他数据
        if (head.next==null){
            System.out.println("链表为空");
        }
        //不能动头，定辅变量
        HeroNode temp = head.next;
        while (true){
            //判断是否到链表最后
            if (temp==null){
                break;
            }
            System.out.println(temp);
            //后移
            temp = temp.next;
        }
    }
}
class HeroNode{
    int no;
    String name;
    String nickName;
    HeroNode next;

    public HeroNode(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '}';
    }
}

删除操作：
从单链表中删除一一个节点的思路分析：
1.我们先找到需要删除的这个节点的前一-个节点temp
2. temp.next = temp.next.next
3.被删除的节点，将不会有其它引用指向，会被垃圾回收机制回收

package com.main.dataStructures;

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        HeroNode hero1 = new HeroNode(1,"wp1","pp");
        HeroNode hero2 = new HeroNode(2,"lmx2","dg");
        HeroNode hero3 = new HeroNode(3,"wp3","ss");
        HeroNode hero4 = new HeroNode(4,"wp4","qq");
        HeroNode hero5 = new HeroNode(5,"wp5","ww");
        HeroNode hero6 = new HeroNode(6,"lmx6","asb");
        HeroNode hero7 = new HeroNode(6,"lmxcbb","a23");
        SingleLinkedList list = new SingleLinkedList();
        list.addNode2(hero5);
        list.addNode2(hero1);
        list.addNode2(hero6);
        list.addNode2(hero2);
        list.addNode2(hero4);
        list.addNode2(hero3);
        list.showNode();
        System.out.println("修改后的情况：~~");
        list.updateNode(hero7);
        list.deleteNode(1);
        list.deleteNode(3);
        list.deleteNode(5);
        list.showNode();

    }
}


class SingleLinkedList{
    private HeroNode head = new HeroNode(0,"","");
    //按添加顺序添加
    public void addNode(HeroNode node){
        HeroNode temp = head;
        while (true){
            //判满
            if (temp.next == null){
                break;
            }
            //后移
            temp = temp.next;
        }
        //添加
        temp.next = node;
    }
    //按编号排序添加
    public void addNode2(HeroNode node){
        HeroNode temp = head;
        boolean flag = false;
        while (true){
            //判满:temp已经是链表最后一个元素了，无法添加
            if (temp.next == null){
                break;
            }
            if (temp.next.no>node.no){
                break;
            }else if (temp.next.no==node.no){
                flag = true;
                break;
            }
            //后移
            temp = temp.next;
        }
        //添加
        if (flag){
            System.out.println("编号已存在");
        }else {
            node.next = temp.next;
            temp.next = node;
        }
    }
    //修改
    //根据编号修改除编号外的其他数据
    public void updateNode(HeroNode newNode){
        HeroNode temp = head.next;
        boolean flag = false;
        while (true){
            if (temp == null){
                break;//已经遍历到最后了
            }
            if (temp.no == newNode.no){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            temp.name = newNode.name;
            temp.nickName = newNode.nickName;
        }else {
            System.out.println("没有该用户");
        }

    }
    //删除操作
    //思路
    //1. head不能动，因此我们需要-个temp辅助节点找到待删除节点的前一个节点
    //2.说明我们在比较时，是temp.next.no和需要删除的节点的no比较
    public void deleteNode(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("没有该用户");
        }

    }

    //显示
    public void showNode(){
        //判空：头节点的next等于null;说明该链表只有一个头节点，没有其他数据
        if (head.next==null){
            System.out.println("链表为空");
        }
        //不能动头，定辅变量
        HeroNode temp = head.next;
        while (true){
            //判断是否到链表最后
            if (temp==null){
                break;
            }
            System.out.println(temp);
            //后移
            temp = temp.next;
        }
    }
}
class HeroNode{
    int no;
    String name;
    String nickName;
    HeroNode next;

    public HeroNode(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '}';
    }
}