[数据结构与算法]java数据结构（一）单链表

java数据结构（一）
单链表
单链表是一种线性存储结构，其逻辑上相邻的存储单元物理上不一定相邻。
利用单链表模拟一个简易英雄人物管理系统。其中英雄人数包含的属性如下：
1）编号 2）姓名 3）昵称。
编号为主码。
实现数据的增删改查。并在增删时分别模拟了链头增，链尾增，链头删，链尾删的功能。其中的链尾增和链尾删结合可以模拟栈；链尾增和链头删可以模拟队列。
具体代码如下：

package com.yck.linkedlist;
import java.util.Scanner;

public class SingleLinkedList {
    public static void main(String[] args) {
        Scanner myScanner = new Scanner(System.in);
        HeroNode headNode = new HeroNode();
        LinkedList myHeroList = new LinkedList(headNode);     //英雄链表
        while(true){
            System.out.println();
            System.out.println("<===============主菜单==================>");
            System.out.println("a ---> 在队首(尾)添加英雄");
            System.out.println("b ---> 在任意位置添加一个新英雄");
            System.out.println("c ---> 更改英雄信息");
            System.out.println("d ---> 在队首(尾)删除英雄");
            System.out.println("f ---> 删除一个指定信息的新英雄");
            System.out.println("n ---> 输出当前表中英雄个数");
            System.out.println("p ---> 打印当前全部英雄信息");
            System.out.println("u ---> 查找同名的英雄信息");
            System.out.println("e ---> 退出");
            System.out.println("<=====================================>");
            System.out.printf("请输入您的操作:");
            char chars = myScanner.next().charAt(0);
            switch(chars){
                case 'a':
                    myHeroList.addOperator();
                    break;
                case 'b':
                    myHeroList.InsertNode();
                    break;
                case 'c':
                    System.out.printf("请输入需要更改信息的英雄编号:");
                    int index = myScanner.nextInt();
                    myHeroList.updateData(index);
                    break;
                case 'd':
                    myHeroList.delOperator();
                    break;
                case 'f':
                    myHeroList.delCertainNode();
                    break;
                case 'n':
                    int heroNum = myHeroList.getNodeNum();
                    System.out.println("共有"+heroNum+"位英雄");
                    break;
                case 'p':
                    myHeroList.showCurrentNode();
                    break;
                case 'u':
                    myHeroList.printSameName();
                    break;
                case 'e':
                    return;
            }
        }
    }
}

//定义一个HeroNode
class HeroNode{
    public int no;               //英雄编号
    public String name;          //英雄姓名
    public String nickname;      //英雄昵称
    public HeroNode next;        //链表项

    public HeroNode(){
    }

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

    public boolean equals(HeroNode heroNode){
        if((this.no == heroNode.no) && (this.name.equals(heroNode.name))
                &&(this.nickname.equals(heroNode.nickname))){
            return true;
        }else{
            return false;
        }
    }//判断两个英雄是否相等
}

class LinkedList{
    private HeroNode firstHeroNode;  //头节点
    private HeroNode rearHeroNode;   //尾节点
    private int nodeNum;             //结点个数

    public LinkedList(HeroNode firstHeroNode) {
        this.firstHeroNode = firstHeroNode;
        this.rearHeroNode = firstHeroNode;     //初始头节点等于尾结点。
    }

    public int getNodeNum(){       //获取链表的结点个数
        int countNodeNum = 0;
        HeroNode p = this.firstHeroNode;
        while(p.next != null){
            countNodeNum ++;   //继续遍历。
            p = p.next;
        }
        return countNodeNum;
    }



    public void addOperator(){     //添加英雄操作
        Scanner myScanner = new Scanner(System.in);
        System.out.println("<========添加操作菜单==========>");
        System.out.println("< a ----> 链首添加");
        System.out.println("< b ----> 链尾添加");
        System.out.println("<============================>");
        System.out.printf("请输入您的操作:");
        char userInput = myScanner.next().charAt(0);
        switch(userInput){
            case 'a':
                try{
                    this.addNodeToFront();      //在链头添加
                }catch(Exception e){
                    System.out.println(e.getMessage());
                }
                break;
            case 'b':
                try{
                    this.addNodeToRear();     //在链尾添加
                }catch(Exception e){
                    System.out.println(e.getMessage());
                }
                break;
            default:
                System.out.println("输入错误");
                break;
        }
    }

    public void addNodeToRear(){   //在链尾添加
        HeroNode newNode = inputFunc("添加");
        HeroNode rearNode = this.rearHeroNode;
        newNode.next = rearNode.next;
        rearNode.next = newNode;
        this.rearHeroNode = newNode;
        this.nodeNum ++;
    }

    private void addNodeToFront() {  //在链头添加
        HeroNode newNode = inputFunc("添加");
        HeroNode firstNode = this.firstHeroNode;
        newNode.next = firstNode.next;
        firstNode.next = newNode;
        if(getNodeNum() == 1){
            this.rearHeroNode = newNode;
        }
        this.nodeNum ++;
    }



    public void delOperator(){  //链表删除操作
        Scanner myScanner = new Scanner(System.in);
        System.out.println("<========删除操作菜单==========>");
        System.out.println("< a ----> 链首删除");
        System.out.println("< b ----> 链尾删除");
        System.out.println("<============================>");
        System.out.printf("请输入您的操作:");
        char userInput = myScanner.next().charAt(0);
        switch(userInput){
            case 'a':
                delNodeFromFront();
                break;
            case 'b':
                delNodeFromRear();
                break;
            default:
                System.out.println("输入错误");
                break;
        }
    }
    private void delNodeFromFront() {  //删除链头操作
        if(this.nodeNum == 0){
            System.out.println("当前没有英雄，无法删除。");
        }else{
            HeroNode tmpNode = this.firstHeroNode;
            this.firstHeroNode.next = this.firstHeroNode.next.next;
            this.nodeNum --;
        }
    }

    public void delNodeFromRear(){   //删除链尾元素。
        if(this.nodeNum == 0){
            System.out.println("当前没有英雄，无法删除。");
        }else{
            HeroNode tmpNode = this.firstHeroNode;
            while(tmpNode.next.next !=null){
                tmpNode = tmpNode.next;
            }
            tmpNode.next = null;
            this.rearHeroNode = tmpNode;
            this.nodeNum --;
        }
    }


    public HeroNode inputFunc(String operatorWord){   //用户输入函数
        Scanner myScanner = new Scanner(System.in);
        System.out.println("请输入要"+operatorWord+"的英雄的信息:");
        System.out.println("请输入该英雄编号:");
        int delno = myScanner.nextInt();
        if(operatorWord == "添加"){
            if(this.sameIndexJudge(delno)){
                throw new RuntimeException("该编号已被其他英雄占用!"); //编号重复，抛出异常
            }
        }

        System.out.println("请输入该英雄名字:");
        String delname = myScanner.next();

        System.out.println("请输入该英雄昵称:");
        String delnickname = myScanner.next();

        HeroNode delHeroNode = new HeroNode(delno,delname,delnickname);
        return delHeroNode;
    }

    public boolean sameIndexJudge(int newNo){   //判断新增加的英雄编号不会与原有英雄编号重复
        HeroNode tmpNode = this.firstHeroNode;
        boolean sameResult = false;
        int getHeroNum = 0;
        while(getHeroNum<this.getNodeNum()){
            tmpNode = tmpNode.next;
            if(tmpNode.no == newNo){
                sameResult = true;
                break;
            }
            getHeroNum++;
        }
        return sameResult;
    }

    public void InsertNodeDetail(HeroNode addNode,int index){   //实现在指定位置插入英雄结点操作
        //将addNode添加到编号为index的英雄后
        HeroNode tmpNode = this.firstHeroNode;
        int getHeroNum = 0;
        while(getHeroNum < this.getNodeNum()){
            tmpNode = tmpNode.next;
            if(tmpNode.no == index) {
                break;
            }
            getHeroNum++;
        }
        addNode.next = tmpNode.next;
        tmpNode.next = addNode;
    }

    public void InsertNode(){   //在指定位置插入英雄
        Scanner  myScanner = new Scanner(System.in);
        System.out.printf("新英雄将会被插入到编号为?的英雄后，请输入?=:");
        int heroIndex = myScanner.nextInt();
        if(!sameIndexJudge(heroIndex)){
            System.out.println("未找到编号为"+heroIndex+"的英雄");
            return;
        }
        HeroNode newNode = inputFunc("添加");
        InsertNodeDetail(newNode,heroIndex);  //添加成功
        this.nodeNum ++;
    }

    public void delNode(HeroNode heroNode){  //删除指定英雄的结点
        HeroNode tmp = this.firstHeroNode;    //从头节点开始遍历。
        boolean findResult = false;
        while(true){
            if(tmp.next == null){  //证明当前结点为尾结点
                this.rearHeroNode = tmp;
                break;
            }else{
                if(tmp.next.equals(heroNode)){   //下一个结点是要找的结点
                    findResult = true;
                    tmp.next = tmp.next.next;
                    this.nodeNum --;
                }else{
                    tmp = tmp.next;
                }
            }
        }
        if(!findResult){
            System.out.println("未找到对应的英雄!");
        }
    }

    public void delNode(int no){  //删除指定编号的英雄
        HeroNode tmp = this.firstHeroNode;    //从头节点开始遍历。
        boolean findResult = false;
        while(true){
            if(tmp.next == null){  //证明当前结点为尾结点
                this.rearHeroNode = tmp;
                break;
            }else{
                if(tmp.next.no == no){   //下一个结点是要找的结点
                    findResult = true;
                    tmp.next = tmp.next.next;
                    this.nodeNum --;
                }else{
                    tmp = tmp.next;
                }
            }
        }
        if(!findResult){
            System.out.println("未找到对应编号的英雄!");
        }
    }

    public void delNodeAccName(String name){   //删除指定姓名的英雄
        HeroNode tmp = this.firstHeroNode;    //从头节点开始遍历。
        boolean findResult = false;
        while(true){
            if(tmp.next == null){  //证明当前结点为尾结点
                this.rearHeroNode = tmp;
                break;
            }else{
                if(tmp.next.name.equals(name)){   //下一个结点是要找的结点
                    findResult = true;
                    tmp.next = tmp.next.next;
                    this.nodeNum --;
                }else{
                    tmp = tmp.next;
                }
            }
        }
        if(!findResult){
            System.out.println("未找到对应姓名的英雄!");
        }
    }

    public void delNodeAccNickname(String nickname){ //删除指定昵称的英雄
        HeroNode tmp = this.firstHeroNode;    //从头节点开始遍历。
        boolean findResult = false;
        while(true){
            if(tmp.next == null){  //证明当前结点为尾结点
                this.rearHeroNode = tmp;
                break;
            }else{
                if(tmp.next.nickname.equals(nickname)){   //下一个结点是要找的结点
                    tmp.next = tmp.next.next;
                    this.nodeNum --;
                    findResult = true;
                }else{
                    tmp = tmp.next;
                }
            }
        }
        if(!findResult){
            System.out.println("未找到对应昵称的英雄!");
        }
    }





    public void delCertainNode(){   //删除某一英雄
        System.out.println();
        System.out.println("<==========指定删除信息===========>");
        System.out.println("a ----> 删除指定信息的英雄");
        System.out.println("b ----> 删除指定编号的英雄");
        System.out.println("c ----> 删除指定姓名的英雄");
        System.out.println("d ----> 删除指定昵称的英雄");
        System.out.println("<===============================>");
        System.out.printf("请输入您的操作:");
        Scanner  myScanner = new Scanner(System.in);
        char chars = myScanner.next().charAt(0);
        switch (chars){
            case 'a':
                HeroNode delHeroNode = inputFunc("删除");
                this.delNode(delHeroNode);
                break;
            case 'b':
                System.out.println("请输入要删除的英雄的信息");
                System.out.println("请输入该英雄编号:");
                int delno = myScanner.nextInt();
                this.delNode(delno);
                break;
            case 'c':
                System.out.println("请输入该英雄名字:");
                String delname = myScanner.next();
                this.delNodeAccName(delname);
                break;
            case 'd':
                System.out.println("请输入该英雄昵称:");
                String delnickname = myScanner.next();
                this.delNodeAccNickname(delnickname);
                break;
            default:
                System.out.println("输入有误!");
                break;
        }
    }
    public void updateData(int index){   //更新英雄数据
        Scanner myScanner = new Scanner(System.in);
        HeroNode tmpHero = this.firstHeroNode;
        if(sameIndexJudge(index)){
            while(tmpHero.next!=null){
                tmpHero = tmpHero.next;
                if(tmpHero.no == index){
                    System.out.println("已找到该英雄，详细信息如下:");
                    System.out.println("编号"+"\t"+"名字"+"\t"+"昵称");
                    System.out.println(tmpHero.no+"\t"+tmpHero.name+"\t"+tmpHero.nickname);
                    System.out.println("是否需要更改该英雄姓名? y/n");
                    System.out.printf("请输入您的选择:");
                    char input = myScanner.next().charAt(0);
                    switch(input){
                        case 'y':
                            System.out.println("请输入更改后英雄的名字");
                            String name = myScanner.next();
                            tmpHero.name = name;
                            break;
                        case 'n':
                            break;
                        default:
                            System.out.println("输入有误!");
                            break;
                    }

                    System.out.println("是否需要更改该英雄昵称? y/n");
                    System.out.printf("请输入您的选择:");
                    char input2 = myScanner.next().charAt(0);
                    switch(input2){
                        case 'y':
                            System.out.println("请输入更改后英雄的昵称");
                            String nickname = myScanner.next();
                            tmpHero.nickname = nickname;
                            break;
                        case 'n':
                            break;
                        default:
                            System.out.println("输入有误!");
                            break;
                    }
                    break;
                }
            }
        }else{
            System.out.println("无指定编号的英雄。");
        }
    }
    public void showCurrentNode(){    //打印所有英雄
        if(nodeNum !=0){
            HeroNode tmpNode = this.firstHeroNode;
            System.out.println("<=====================================>");
            System.out.println("编号"+"\t"+"名字"+"\t"+"昵称");
            while(tmpNode.next!=null){
                tmpNode = tmpNode.next;
                System.out.printf(tmpNode.no+"\t"+tmpNode.name+"\t"+tmpNode.nickname);
                System.out.println();
            }
        }else{
            System.out.println("无英雄");
        }
    }

    public void printSameName(){   //打印搜索到的英雄
        Scanner myScanner = new Scanner(System.in);
        System.out.printf("请输入想要查找的英雄姓名:");
        String name = myScanner.next();
        HeroNode tmpNode = this.firstHeroNode;
        int count = 0;
        System.out.println("<=====================================>");
        System.out.println("编号"+"\t"+"名字"+"\t"+"昵称");
        while(tmpNode.next != null){
            tmpNode = tmpNode.next;
            if(tmpNode.name.equals(name)){
                System.out.printf(tmpNode.no+"\t"+tmpNode.name+"\t"+tmpNode.nickname);
                System.out.println();
                count++;
            }
        }
        System.out.println("共找到"+count+"位相同的英雄。");
    }
}