单链表的模拟实现

单链表的应用实现

顺序添加根据排名 若是排名号有了就显示添加失败
思路:1.head是头结点不能移动 所以要用一个临时节点 temp
2.找到要插入位置的前一个节点 用temp遍历
找到temp.next.no首次大于heroNode.no 的位置此时就在temp位置插入
让heroNode.next=temp.next ;temp=HeroNode
删除链表节点
思路: head不能动 temp 向后遍历找到那个要删除的排名号的下一个节点的位置

删除链表节点
思路: head不能动 temp 向后遍历找到那个要删除的排名号的下一个节点的位置

涉及的方法

1.默认添加节点数据 t
2.顺序添加节点数据
3.删除节点
4.修改节点数据
5.判断是否为空
6.获取节点
7.获取链表长度
8.显示链表所有数据
9.插入数据
10.根据位置返回
11.退出程序

代码

package 链表;


import java.util.Scanner;

/**
 * @author 一介草莽子
 * version 1.0
 */
@SuppressWarnings({"all"})
public class SingleLinkedListDemo {
    public static void main(String[] args) {

        SingleLinkedList singleLinkedList_ = new SingleLinkedList();
        //菜单
        boolean loop = true;
        Scanner scanner = new Scanner(System.in);
        int no = 0;//输入的排名号
        String name = null;//输入的名字
        String nickName = null;//输入的绰号
        //功能号
        int num = 0;

        while (loop) {
            System.out.println("============ 1.默认添加节点数据 ===========");
            System.out.println("============ 2.顺序添加节点数据 ===========");
            System.out.println("============ 3.删除节点        ============");
            System.out.println("============ 4.修改节点数据    ============");
            System.out.println("============ 5.判断是否为空    ============");
            System.out.println("============ 6.获取节点       ============");
            System.out.println("============ 7.获取链表长度    ============");
            System.out.println("============ 8.显示链表所有数据 ============");
            System.out.println("============ 9.插入数据 ============");
            System.out.println("============ 10.根据位置返回 ============");

            System.out.println("============ 11.退出程序        ============\n");

            System.out.print("请输入功能号:");
            num = scanner.nextInt();
            switch (num) {
                case 1://普通添加
                    System.out.println("【普通添加】 请输入 排名号,名字,绰号 ");
                    no = scanner.nextInt();
                    name = scanner.next();
                    nickName = scanner.next();
                    singleLinkedList_.add(new HeroNode(no, name, nickName));
                    break;
                case 2://顺序添加
                    System.out.println("【顺序添加】 请输入 排名号,名字,绰号 ");
                    no = scanner.nextInt();//输入的排名号
                    name = scanner.next();//输入的名字
                    nickName = scanner.next();//输入的绰号
                    singleLinkedList_.addIndex(new HeroNode(no, name, nickName));
                    break;
                case 3://删除
                    System.out.println("请输入要删的排名号~");
                    no = scanner.nextInt();
                    singleLinkedList_.remove(no);
                    break;
                case 4://修改
                    System.out.println("请输入修改的 排名号,名字,绰号 ");
                    no = scanner.nextInt();//输入的排名号
                    name = scanner.next();//输入的名字
                    nickName = scanner.next();//输入的绰号
                    singleLinkedList_.modify(new HeroNode(no, name, nickName));
                    break;
                case 5://判断是否为空 若是空会抛出异常
                    singleLinkedList_.IsEmpty(singleLinkedList_.head.next);
                    System.out.println("链表不为空...");
                    break;
                case 6://获取节点
                    System.out.print("请输入排名号");
                    no = scanner.nextInt();
                    HeroNode heroNode = singleLinkedList_.GetHeroNode(no);
                    System.out.println("获取到的节点是: " + heroNode.toString());
                    break;
                case 7://.获取链表长度
                    System.out.println("链表长度为: " + singleLinkedList_.GetListLength());
                    break;
                case 8://显示链表所有数据
                    singleLinkedList_.List();
                    break;
                case 9:
                    System.out.println("请输入插入的 排名号,名字,绰号 ");
                    no = scanner.nextInt();//输入的排名号
                    name = scanner.next();//输入的名字
                    nickName = scanner.next();//输入的绰号
                   singleLinkedList_.Insert(new HeroNode(no,name,nickName));
                    break;
                case 10:
                    System.out.print("请输入号：");
                    int n = scanner.nextInt();
                    HeroNode res = singleLinkedList_.GegElem(n);
                    System.out.println(res);

                    break;
                case 11:
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序结束...");
    }
}

class SingleLinkedList {
    //设置一个头结点 里面不存放值head 不能动
    HeroNode head = new HeroNode(0, "", "");

    //链表的长度
    private int length = 0;


    //插入--先找出要插入的位置的前一个位置
    public void Insert(HeroNode heroNode){

        HeroNode temp=head;//遍历去找合适的位置
        while(true){
            if(temp.next==null){
                break;
            }
            if(temp.next.no> heroNode.no){
                //找到了第一个大于heroNode.no的
                break;
            }
            temp=temp.next;
        }
        //heroNode.next指向后一个元素 前面的元素指向heroNode.next
        heroNode.next=temp.next;
        temp.next=heroNode;
        System.out.println("插入成功");
        length++;
    }
    //添加节点到单链表  -- 不考虑添加的顺序 直接添加到最后面
    public void add(HeroNode heroNode) {
        //head是不能动的 让临时变量 tmp来指向head
        HeroNode tmp = head;

        //循环遍历到最后找到指向null的那个那个对象
        while (true) {
            if (tmp.next == null) {
                break;//tmp.next指向null 说明找到最后了
            }
            tmp = tmp.next;
        }
        //把node节点添加到最后
        tmp.next = heroNode;
        length++;
        System.out.println("添加成功...");
    }


    /**
     * 顺序添加根据排名 若是排名号有了就显示添加失败
     * 思路:1.head是头结点不能移动 所以要用一个临时节点 temp
     * 2.找到要插入位置的前一个节点 用temp遍历
     * 找到temp.next.no首次大于heroNode.no 的位置此时就在temp位置插入
     * 让heroNode.next=temp.next ;temp=HeroNode
     */
    public void addIndex(HeroNode heroNode) {
        HeroNode temp = head;
        boolean flag = false;//标记要是排名号有相同的就true 不能添加
        while (true) {
            if (temp.next == null) {
                break;//空链表退出
            }
            //temp.no 是不对的 一开始 head是空节点
            if (temp.next.no == heroNode.no) {
                flag = true;//标记要是排名号有相同的就true 不能添加
                break;
            } else if (temp.next.no > heroNode.no) {
                //找到temp.next.no首次大于heroNode.no 的位置
                //此时就在temp位置插入 让heroNode.next=temp.next ;temp=HeroNode
                break;
            }
            //遍历
            temp = temp.next;
        }
        if (flag) {
            System.out.println("排名号已存在不能在添加...");

        } else {
            heroNode.next = temp.next;
            //temp = heroNode这样是不对的 temp.next 相当于头指针的next域指向下一个节点
            temp.next = heroNode;
            length++;
            System.out.println("添加成功...");
        }
    }

    /**
     * 删除链表节点
     * 思路: head不能动   temp 向后遍历找到那个要删除的排名号的下一个节点的位置
     */
    public void remove(int no) {
        //判断链表是否为空
        IsEmpty(head.next);
        HeroNode temp = head;
        //设置标记 找到了就flag=true;可删除
        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是head  temp.next就是代表第一个节点 所以就应该让temp.next 也就是head里的
            //next域指向第二个节点 temp.next.next  temp.next.next等价于 head.next.next
            temp.next = temp.next.next;
            length--;
            System.out.println("删除成功...");

        } else {
            System.out.println(no + "排名号不存在");
        }

    }


    /**
     * 修改链表元素内容
     * head是不能动的 让temp动 找到到要修改的节点 改变 name nickname  no不能改变
     */
    public void modify(HeroNode newHeroNode) {
        //判断列表是不是空
        IsEmpty(head.next);
        //临时节点
        HeroNode temp = head;
        //找的了就=true
        boolean flag = false;
        while (true) {
            if (temp.next == null) {
                break;//遍历到最后也没找到就退出
            }
            if (temp.next.no == newHeroNode.no) {
                flag = true;
                break;//找到到了编号 退出
            }

            //向后遍历
            temp = temp.next;
        }
        if (flag) {
            temp.next.name = newHeroNode.name;
            temp.next.nickname = newHeroNode.nickname;
            System.out.println("修改成功...");
        } else {
            System.out.println("没有找到" + newHeroNode.no + "号位置的元素");
        }

    }

    //返回链表的长度
    public int GetListLength() {
        return length;
    }

    //判断是否为空链表
    public void IsEmpty(HeroNode heroNode) {
        if (heroNode == null) {
            throw new RuntimeException("空链表....");
        }
    }


    /**
     * 获取元素 --查 根据排名号
     * head不能动 用temp来遍历查找
     */
    public HeroNode GetHeroNode(int no) {
        //判断是不是空表
        IsEmpty(head.next);
        HeroNode temp = head;
        while (true) {
            if (temp.next == null) {
                System.out.println("没找到。。。");
                return null;
            }//找到了返回节点
            if (temp.next.no == no) {
                return temp.next;
            }
            temp = temp.next;
        }
    }

    //按位置查找
    public HeroNode GegElem(int n){
        IsEmpty(head.next);
        HeroNode temp=head;
        boolean flag=true;
        for (int i = 0; i < n; i++) {
            if(temp.next==null){
                flag=false;
                break;
            }
            temp=temp.next;
        }
        if(flag){
            //返回找到的数据 不是temp.next 因为在循环的时候指向了下一个
            return temp;
        }
        else{
            return null;
        }
    }

    //显示链表
    public void List() {

        //判断是不是空的链表
        if (head.next == null) {
            System.out.println("不好意思这是一个空表...");
            return;
        }
        HeroNode tmp = head.next;
        while (true) {
            if (tmp == null) {
                break;
            }
            System.out.println(tmp.toString());

            tmp = tmp.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;
    }
    //设置该节点的toString方法


    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}