[数据结构与算法]单链表实现Java版

单链表构造

每个节点可以存放到离散空间中，利用指针将每个节点串起来

节点由数据域与指针域组成，指针域只存在一个指针，指向下一个节点

存在一个头结点，无数据域，指针指向首节点，方便后续操作

Java中伪指针的表示——浅拷贝

类名 变量 = 对象名

这种不用new的实例化，让变量可以作为指针使用（内存地址相同），当变量（该变量可以看作一个对象）属性改变时，它指向的那个对象属性跟着改变

节点如何表示

//编写节点
class HeroNode {
    public int id;//英雄编号
    public String name;//英雄姓名
    public HeroNode next;//指向下一个节点

    //构造器
    public HeroNode(int hid, String hname) {
        this.id = hid;
        this.name = hname;
    }

    public String print() {
        return "HeroNode 英雄编号:" + id + "英雄姓名:" + name;
    }
}

链表的整体架构

package 数据结构.单链表;

/*
任务背景：使用有头结点的单链表实现——水浒英雄排行榜管理
具体功能要求：1.可以将英雄添加尾部
           2.可以将英雄插入指定位置
           3.可以删除英雄
           4.可以修改英雄
*/

//小知识：类名 变量 = 类；这种不用new的实例化，变量可以作为指针使用（内存地址相同），当变量对象属性改变时，它指向的那个对象属性跟着改变

//编写节点
class HeroNode {
    public int id;//英雄编号
    public String name;//英雄姓名
    public HeroNode next;//指向下一个节点

    //构造器
    public HeroNode(int hid, String hname) {
        this.id = hid;
        this.name = hname;
        this.next = null;//这句可以不用写，没有赋值时next本身就是null
    }

    //显示方法
    @Override
    public String toString() {
        return "HeroNode 英雄编号: " + id + " 英雄姓名: " + name;
    }
}

//创建单链表,管理英雄
class HeroLink {
    //先初始化一个头结点，头结点不能动,且不存放具体数据，因为只能存在一个，故设置其为私有对象
    private HeroNode head = new HeroNode(0, "");

    /*
    添加节点到单向链表中，添加至末尾；
    具体方法：先new一个新节点，上一个节点指针（next变量）指向该节点
    步骤  1.先遍历找到链表的最后节点
         2.new一个新节点（这里因为将新节点作为参数，故无需new）
         3.将上一个节点的next变量指向新节点
     */
    public void add(HeroNode heroNode) {

        //因为头结点不能动，所以需要一个辅助遍历变量temp
        HeroNode temp = head;

        //遍历链表，找到最后一个节点，该节点next变量为null

        //简洁版
//        while (temp.next != null) {
//            //让temp指向下一个节点，检测下一个个节点next是不是null
//            temp = temp.next;
//        }

        //上一个循环为简洁遍历，看不懂可以参考下面的遍历方法
        while (true) {
            //找到那个节点next变量为null则跳出循环，找不到则继续遍历，将temp指向下一个节点
            if (temp.next == null) {
                break;
            } else {
                temp = temp.next;
            }
        }

        //当退出循环时，temp就指向了最后一个节点
        //将该节点的next指向要添加的那个节点
        temp.next = heroNode;
    }

    //显示链表[遍历]
    public void list(){
        //先判断链表是否为空，为空直接不用遍历
        if(head.next==null){
            System.out.println("链表为空");
            return;
        }
        //头结点不能动，需要一个辅助变量遍历
        HeroNode temp = head;
        //简洁版
        while (temp.next != null) {
            //让temp指向下一个节点，检测下一个个节点next是不是null
            //这里主要要先改遍历节点在输出，否则会出现输出头结点，不输出尾节点的现象
            temp = temp.next;
            System.out.println(temp);
        }
    }

}


public class 单链表实现 {
    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,"武松");

        //创建英雄链表
        HeroLink heroLink = new HeroLink();
        heroLink.add(hero1);
        heroLink.list();
        heroLink.add(hero2);
        heroLink.add(hero3);
        heroLink.add(hero4);
        heroLink.list();

    }
}