• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

模拟单链表详解

开发技术 开发技术 5天前 5次浏览

模拟单链表详解

  • 单链表说明与分析
  1. 单链表是日常使用中常见的一种数据结构
  2. 单链表由一个个节点组成,每一个节点有数据域和指针域两部分,数据域存储具体要存储的数据,而指针域则存储节点指向的下一个节点,通过指针域将节点串起来
  3. 单链表在内存中的存储不是连续的,每一个节点和另一个节点可以存储在不同的地址空间,即地址可以不连续,通过指针相互连接
  4. 单链表的增删查改思路详见后源码
//创建节点类
//每一个节点类实例对象则为一个具体的节点

//则每一个Hero实例就是一个节点
class HeroNode{

    //编号
    public int no;
    //姓名
    public String name;
    //昵称
    public String nickedName;
    //指针域,存储的实则是一个地址,指向下一个节点
    public HeroNode next;

    public HeroNode() {
    }

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

    //显示节点信息
    @Override
    public String toString() {
        return "Hero{" +
                "no=" + no +
                ", name='" + name + ''' +
                ", nickedName='" + nickedName + '}';
    }
}
  • 单链表
//创建一个单链表类
class SingleLinkedList{

    //创建一个头节点,不存放任何数据
    public HeroNode head = new HeroNode();

    //编写方法删除链表中的节点(根据节点的编号)
    public void delete(int no){
        //因为头节点不能动,定义辅助遍历temp
        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 update(HeroNode newHero){
        //判断链表是否为空
        if (head.next == null){
            System.out.println("链表是空的~~");
            return;
        }
        //因为头节点不能动,因此创建一个辅助变量temp
        HeroNode temp = head.next;
        //创建一个标志位flag判断是否找到要修改的节点
        boolean flag = false;
        while (true){
            //如果已经遍历完链表,还没有找到,直接返回
            if (temp.next == null){
                break;
            }
            //如果找到需要修改的节点
            if (temp.no == newHero.no){
                flag = true;
                break;
            }
            //指针后移
            temp = temp.next;
        }
        //如果找到需要修改的节点
        if (flag){
            temp.name = newHero.name;
            temp.nickedName = newHero.nickedName;
        }else {
            //如果没有找到
            System.out.println("要修改的节点不存在~~");
        }
    }

    //编写向单链表中添加节点的方法,不考虑插入元素的位置,直接插入链表的最后
    public void add(HeroNode hero){
        //因为head头节点不能动,所以需要创建一个临时变量
        HeroNode temp = head;

        //先遍历链表找到链表的最后,然后将这个节点添加
        while (true){
            if (temp.next == null){
                break;
            }
            //如果不是最后一个节点,则temp指向的节点后移
            temp = temp.next;
        }
        //循环结束后找到链表的最后一个元素
        //将这个节点添加到链表
        temp.next = hero;
    }

    //向链表中添加元素2,按照英雄的编号大小添加
    //思路:
    //1.难点在于寻找新节点要插入的位置
    //2.考虑将新节点插入到temp 和 temp.next之间
    public void addByOrder(HeroNode hero){
        //因为头节点不能动,因此还是需要一个辅助变量temp指向head
        HeroNode temp = head;
        //定义一个表示位flag标识节点是否能添加成功,默认为false
        boolean flag = false;
        while (true){
            //如果已经遍历到最后一个节点,则将新节点添加到temp的后面
            if (temp.next == null){
                break;
            }
            //如果要添加的节点的标号大于temp,小于temp.next的编号,则找到temp
            if (temp.next.no > hero.no){
                break;
                //如果要添加的节点的编号已经存在,则不能添加
            }else if(temp.next.no == hero.no){
                flag = true;
                break;
            }
            //temp后移
            temp = temp.next;
        }
        if (flag){
            //如果flag为真,则表示要加入的节点编号已经存在
            System.out.println("该节点已经存在~~");
        }else {
            //循环结束后则已经找到新节点要插入的位置
            hero.next = temp.next;
            temp.next = hero;
        }
    }

    //显示链表
    public void list(){
        //先判断链表是否为空
        if (head.next == null){
            System.out.println("链表为空~~");
            return;
        }
        //因为头节点不能动,因此还是需要一个辅助遍历temp(类似一个指针,每次指向下一个节点)
        //temp指向第一个节点
        HeroNode temp = head.next;
        //如果链表不为空,则遍历链表
        while (true){
            //如果链表为空,则结束遍历
            if (temp == null){
                break;
            }
            //输出链表内容
            System.out.println(temp);
            //temp后移指向下一个节点
            temp = temp.next;
        }
    }

}

  • 测试
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(hero4);
        singleLinkedList.addByOrder(hero2);

        //显示链表
        singleLinkedList.list();

        //修改节点
        HeroNode newHero = new HeroNode(2, "小卢", "玉麒麟~~");
        singleLinkedList.update(newHero);

        System.out.println("修改后~~");
        //显示链表
        singleLinkedList.list();

        //删除节点
        singleLinkedList.delete(1);
        System.out.println("删除~~");
        //显示链表
        singleLinkedList.list();

    }
}

程序员灯塔
转载请注明原文链接:模拟单链表详解
喜欢 (0)