Java数据结构 | 单链表的代码实现

public class SingleLinkedListTest {
    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, "林冲", "豹子头");
        HeroNode newHero = new HeroNode(2, "水", "浒");

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

        //1-增
//        添加英雄
//        singleLinkedList.addNode(hero1);
//        singleLinkedList.addNode(hero2);
//        singleLinkedList.addNode(hero3);
//        singleLinkedList.addNode(hero4);

        //按顺序添加节点
        singleLinkedList.addOrderNode(hero1);
        singleLinkedList.addOrderNode(hero4);
        singleLinkedList.addOrderNode(hero2);
        singleLinkedList.addOrderNode(hero3);

        //2-删
        singleLinkedList.del(1);

        //3-改
        //修改数据
        singleLinkedList.newNode(newHero);

        //4-查
        //显示链表
        singleLinkedList.list();
    }
}
class SingleLinkedList {
    //初始化一个头节点
    private HeroNode head = new HeroNode(0, "", "");

    /*
     * 添加新节点到单项链表
     * 思路:不考虑编号顺序时
     *  1.找到当前链表的最后一个节点
     *  2.找到最后节点的next指向新节点
     */
    public void addNode(HeroNode node) {
        //因为头节点不能移动,所以弄一个辅助变量temp
        HeroNode temp = head;

        //遍历链表找到最后
        while (true) {
            if (temp.next == null) {
                break;  //找到了
            }
            //如果没有找到,temp后移
            temp = temp.next;
        }

        //当while循环结束以后,temp指向了最后一个节点
        //将最后一个节点指向新的节点
        temp.next = node;
    }

    /*
     * 添加顺序新节点到单项链表
     * 思路:考虑编号顺序时
     *  1.找到当前链表的最后一个节点添加节点的前一个节点
     *  2.让顺序节点.next=temp.next
     *  3.再让temp.next=顺序节点
     */
    public void addOrderNode(HeroNode orderNode) {
        //因为头节点不能动,设置一个辅助变量节点来找添加的位置
        //因为是单链表,我们要找到添加节点的前一个节点
        HeroNode temp = head;
        boolean flag = false;   //添加的节点是否存在
        while (true) {
            //判断链表是否为空
            if (temp.next == null) {
                break;
            }
            //判断是否添加节点
            if (temp.next.no > orderNode.no) {
                break;
            } else if (temp.next.no == orderNode.no) {
                flag = true;
                break;
            }
            temp = temp.next;       //后移节点位置
        }
        if (flag) {
            System.out.printf("数据%d已经存在", orderNode.no);
        } else {
            //插入到单链表中temp节点的后面
            orderNode.next = temp.next;
            temp.next = orderNode;
        }
    }

    //修改节点的信息,根据新节点的no来修改,即no值不变
    public void newNode(HeroNode newNode) {
        //先判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //定义一个辅助变量
        HeroNode temp = head.next;
        boolean flag = false;   //是否找到要修改节点
        while (true) {
            if (temp == null) {
                break;  //已经遍历完列表了
            }
            if (newNode.no == temp.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.name = newNode.name;
            temp.nickName = newNode.nickName;
        } else {
            //没有找到
            System.out.printf("修改数据编号%d,没有找到,不能修改", newNode.no);
        }
    }

    /*
     *删除要删除节点
     *思路:
     *1-head不能动,因此要用辅助节点temp来找到删除节点的前一个
     *2-说明我们要比较的是temp.next.no和删除节点.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.printf("没有找到要删除编号 %d 的数据",no);
        }
    }

    //显示遍历链表
    public void list() {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
        }
        //因为头节点不能动,我们需要一个辅助变量来遍历
        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;
    }

    //显示
    @Override
    public String toString() {
        return "HeroNode [no=" + no + ", name = " + name + ", nickname=" + nickName + "]";
    }
}
上一篇:javascript – 在Node.js承诺的环境中监视挂起的异步操作


下一篇:数据结构笔记 —— 单链表和双向链表