现有一任务,要求你用单链表对108个水浒英雄的编号、姓名、昵称进行存储。并且实现有序版的插入(尾插)与无序版的插入(按英雄的序号插入)。 ##节点结构 首先我们应该定义节点类,该类包括成员属性、包括一个用于初始化节点的构造方法、包括重写一个打印节点的toString()方法

// 英雄的结点类
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;
    }


    //重写toString,方便打印数据
    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}

##链表结构 上面我们定义了节点的结构,节点是链表的组成元素,接下来我们将创建一个链表类,在该类中先实现:插入,遍历节点的功能:

//创建一个管理节点的单链表
class HeroManager{
    //创建头结点,该头结点不可动
    private HeroNode head = new HeroNode(0,"","");

    //创建添加英雄的方法
    //1.找到当前结点的最后一个节点
    //2.将最后这个节点的next指向新创建的结点
    public void add(HeroNode heroNode){
        //由于head结点不能动,因此需要创建一个辅助结点进行遍历
        HeroNode temp = head;

        //通过遍历,找到尾结点
        while(true){
            if(temp.next == null){
                break;
            }

            //如果不为空,将temp指向最后
            temp = temp.next;
        }

        //将temp指向的这个最后的结点的next指向传入进来的新的节点
        temp.next = heroNode;
    }

    //遍历整个链表
    public void list(){
        //判断链表是否为空
        if(head.next == null){
            return;
        }

        //不为空,创建临时指针
        HeroNode temp = head.next;

        while (true){
            //如果temp的next为空,那么就结束循环
            if(temp == null){
                return;
            }

            //如果不为空,那么就打印节点
            System.out.println(temp.toString());

            //将temp后移
            temp = temp.next;
        }
    }
}

###顺序插入 好了,上面定义的链表中的插入方式是尾插,也就是不考虑节点的序号,下面我们实现一种可以按照节点的序号进行排序插入的方法:

// 按照顺序添加节点
public void addByOrder(HeroNode heroNode){
    //创建临时指针
    HeroNode temp = head;
    //创建一个flag,来标识新添加的序号是否存在
    boolean flag = false;

    //开启一个死循环,找到应该放入的位置,以及是否可以插入
    while(true){
        //如果到了末尾,循环就该结束,新节点应该插入到最后
        if(temp.next == null){
            break;
        }

        //如果temp的下一个节点的编号大于要插入的节点的编号,那么被插入的节点应该插入到temp的后面
        if(temp.next.no > heroNode.no){
            break;
        }else if(temp.next.no == heroNode.no){//如果下一个编号与要插入的节点的编号相等,那么该节点不允许插入
            flag = true;
            break;
        }

        //将temp下移
        temp = temp.next;
    }

    //根据flag判断是否将节点插入链表
    if(!flag){
        //flag为false,可以插入
        heroNode.next = temp.next;
        temp.next = heroNode;
    }else {
        System.out.printf("该节点的编号:%d 已在链表中存在,不允许插入重复数据!\n",heroNode.no);
        return;
    }
}

修改节点

实现了插入、遍历的功能是远远不够的,假如我们需要修改某一个节点的内容该怎样做呢?定义一个用于修改节点信息的方法就行了:

//修改节点的信息,不能修改编号,修改编号等于添加节点
//根据节点的no来修改
public void update(HeroNode heroNode){
    //判断链表是否为空
    if(head.next == null){
        System.out.println("链表为空");
        return;
    }

    //定义一个辅助变量
    HeroNode temp = head.next;
    boolean flag = false;   //标识是否找到该节点

    while (true){
        //判断是否到了节点末尾
        if(temp == null){
            break;
        }

        //如果匹配到了
        if(temp.no == heroNode.no){
            flag = true;
            break;
        }

        //将temp下移
        temp = temp.next;
    }

    //根据flag判断是否可以修改
    if(!flag){
        System.out.printf("对不起,没有找到您要修改的节点编号:%d",heroNode.no);
    }else {
        temp.name = heroNode.name;
        temp.nickname = heroNode.nickname;
    }

}

###删除节点 假如我们需要删除某一个节点该如何做呢?

//根据no删除某个节点
public void delete(int no){
    //判断节点是否为空
    if(head.next == null){
        System.out.println("链表为空,没有什么好删除的");
        return;
    }

    //创建临时指针
    HeroNode temp = head;
    //创建flag标识是否找到节点
    boolean flag = false;

    while (true){
        //节点到头,结束循环
        if(temp.next == null){
            break;
        }

        //匹配no,找节点
        if(temp.next.no == no ){
            flag = true;
            break;
        }

        temp = temp.next;
    }

    //根据flag判断是否能够删除节点
    if(!flag){
        System.out.printf("对不起,没有找到您要删除的节点的编号:%d",no);
    }else {
        temp.next = temp.next.next;
    }
}

###统计节点个数 假如我想知道此链表的有效节点的个数该如何实现呢?有效节点表示不包含头结点的节点。

//获取当前链表有效节点的个数,不统计头结点
public int getnumber(){
    int length = 0;
    HeroNode current = head.next;

    //链表为空,节点数量为0
    if(head.next == null){
        return length;
    }

    //不为空,遍历获取数量
    while(current !=null ){
        length++;
        current = current.next;
    }

    return length;
}

###获取倒数第K个节点 假如我想获取倒数第K个节点的信息该如何做呢?

//获取倒数第K个节点
public HeroNode getNodeByDescIndex(int index){

    //获取链表长度
    int length = this.getnumber();
    //计算正序位置
    int escIndex = length-index;
    //当前索引值的位置
    int currentIndex = 0;

    //设定临时指针变量
    HeroNode temp = head.next;
    if(head.next == null || index < 1 || index > length){
        return null;
    }

    //正序遍历链表获取此节点
    while(true){
        //到头了就结束
        if(temp == null){
            break;
        }

        //如果找到了此节点及结束
        if(currentIndex == escIndex){
            break;
        }

        temp = temp.next;
        currentIndex++;
    }
    return temp;
}

##链表测试 定义了节点和链表之后,我们就可以在主类中的主方法中进行测试了:

public class SingleLinkedList {
    public static void main(String[] args) {
        HeroManager hm = new HeroManager();
        HeroNode hn = new HeroNode(1, "宋江", "及时雨");
        HeroNode hn1 = new HeroNode(13, "卢俊义", "玉麒麟");
        HeroNode hn2 = new HeroNode(5, "吴用", "智多星");

        hm.addByOrder(hn);
        hm.addByOrder(hn1);
        hm.addByOrder(hn2);

        System.out.println("打印链表");
        list(hm.head.next);

    }
}

输出结果为:

打印链表
HeroNode{no=1, name='宋江', nickname='及时雨'}
HeroNode{no=5, name='吴用', nickname='智多星'}
HeroNode{no=13, name='卢俊义', nickname='玉麒麟'}