新星计划Day5【数据结构与算法】 链表

👩‍💻博客主页：京与旧铺的博客主页

✨欢迎关注🖱点赞🎀收藏⭐留言✒

🔮本文由京与旧铺原创，csdn首发！

😘系列专栏：java学习

💻首发时间：🎞2022年4月29日🎠

🎨你做三四月的事，八九月就会有答案，一起加油吧

🀄如果觉得博主的文章还不错的话，请三连支持一下博主哦

🎧最后的话，作者是一个新人，在很多方面还做的不好，欢迎大佬指正，一起学习哦，冲冲冲

图片

🛒导航小助手🎪

🥙014 数组模拟环形队列思路分析图

思路如下：

1.front变量的含义做一个调整：front就指向队列的第一个元素，也就是说arr[front]就是队列的第一个元素

front的初始值=0

2.rear变量的含义做一个调整：rear指向队列的最后一个元素的后一个位置，因为希望空出一个空间做为约定

rear的初始值=0

3.当队列满时，条件是(rear+1)%maxsize==front【满】

4.对队列为空的条件，rear=front空

5.当我们这样分析后， 队列中有效的数据的个数 (rear+maxsize-front)%maxSize //rear=1 front=0

6.我们就可以在原来的队列上修改，得到一个环形队列

🧆015 数组模拟环形队列实现

 public class ArrayQueueDemo{
     public static void main(String[] args){
         //测试一把
          System.out.println("测试数组模拟环形队列的案例");
         //创建一个环形队列
         CircleQueue queue=new ClrcleQueue(4);//说明设置4，其队列的最大有效数据是3
         char key=' ';//接收用户输入
         Scanner scanner=new Scanner(System.in);
         boolean loop=true;
         //输出一个菜单
         while(loop){
             System.out.println("s(show):显示队列");
             System.out.println("e(exit):退出程序");
             System.out.println("a(add):添加数据到队列");
             System.out.println("g(get):从队列取出数据");
             System.out.println("h(head):查看队列头的数据");
             key=scanner.next().charAt(0);//接收一个字符
             switch(key){
                 case 's':
                     queue.showQueue();
                     break;
                 case 'a':
                     System.out.println("输出一个数");
                     int value=scanner.nextInt();
                     queue.addQueue(value);
                     break;
                 case 'g'://取出数据
                     try{
                         int res=queue.getQueue();
                         System.out.println("取出的数据是%d\n",res);
                         
                     }catch(Exception e){
                         System.out.println(e.getMessage());
                     }
                     break;
                 case 'h'://查看队列头的数据
                     try{
                         int res=queue.headQueue();
                         System.out.println("队列头的数据是%d\n",res);
                     }catch(Exception e){
                         System.out.println(e.getMessage());
                     }
                     break;
                 case 'e'://退出
                     scanner.close();
                     loop=false;
                     break;
                 default:
                     break;
             }
         }
         System.out.println(程序退出);
     }
 }
 class ArrayQueue{
     private int maxsize;//表示数组的最大容量
     private int front;//队列头
     private int front;//队列尾
     private int[] arr;//该数组用于存放数据，模拟队列
     public CircleArray(int arrMaxSize){
         maxSize=arrMaxSize;
         arr=new int[maxSize];
     }
     //判断队列是否满
     public boolean isFull(){
         (rear+1)%maxsize==front;
     }
     //判断队列是否为空
     public boolean isEmpty(){
         return rear==front;
     }
     //添加数据到队列
     public void addQueue(int n){
         //判断队列是否满
         if(isFull()){
             System.out.println("队列满，不能加入数据");
             return;
         }
        //直接将数据加入
         arr[rear]=n;
         //将rear后移，这里必须考虑取模
         rear=(rear+1)%maxSize;
     }
     //获取队列的数据，出队列
     public int getQueue(){
         //判断队列是否空
         if(isEmpty()){
             //通过抛出异常
             throw new RuntimeException("队列空，不能取数据");
         }
         //这里需要分析出front是指向队列的第一个元素
         //1.先把front对应的值保留到一个临时变量
         //2.将front后移，考虑取模
         //3.将临时保存的变量返回
         int value=arr[front];
         front=(front+1)%maxSize;
         return value;
     }
     //显示队列的所有数据
     public void showQueue(){
         //遍历
         if(isEmpty()){
             System.out.println("队列孔，没有数据");
             return;
         }
         //思路：从front开始遍历，遍历多少个元素
         //动脑筋
         for(int i=0;i<front+size();i++){
             System.out.println("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]);
         }
     }
     //求出当前队列有效数据的个数
     public int size(){
         //rear=2
         //front=1
         //maxSize=3
         return(rear+maxSize-front)%maxSize;
     }
     //显示队列的头数据，注意不是取出数据
     public int headQueue(){
         //判断
         if(isEmpty()){
             throw new RuntimeException("队列空，不能取数据");
         }
         return arr[front];
     }
 }

🍨016 单链表介绍和内存布局

链表是有序的列表，但是它在内存中是存储如下

小结：

1.链表是以节点的方式来存储，是链式存储

2.每个节点包含data域，next域指向下一个节点

3.发现链表的各个节点不一定是连续存储

4.链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

🍭017 单链表创建和遍历的分析实现

使用带head头的单向链表实现 水浒英雄排行榜管理

完成对英雄人物的增删改查操作， 注: 删除和修改,查找 可以考虑学员独立完成，也可带学员完成 1) 第一种方法在添加英雄时，直接添加到链表的尾部

 public class SingleLinkedListDemo{
     public static void main(String[] args){
         //进行测试
         //先创建节点
         HeroNode hero1=new HeroNode(1,"宋江","及时雨");
         HeroNode hero1=new HeroNode(2,"卢俊义","玉麒麟");
         HeroNode hero1=new HeroNode(3,"吴用","智多星");
         HeroNode hero1=new HeroNode(4,"林冲","豹子头");
         
         //创建要给链表
         SingleLinkedList singleLinkedList=new SingleLinkedList();
          // 按照编号顺序加入节点
         singleLinkedList.addByOrder(her1);
         singleLinkedList.addByOrder(her4);
         singleLinkedList.addByOrder(her2);
         singleLinkedList.addByOrder(her3);
         singleLinkedList.addByOrder(her3); // 不能重复插入
         //显示一把
         singleLinkedList.list();
         //测试修改节点的代码
         HeroNode newHeroNode=new HeroNode(2,"小卢","玉麒麟");
         singleLinkedList.update(newHeroNode);
         System.out.println("修改后的链表情况");
         singleLinkedList.list();
         //删除一个节点
         singleLinkedList.del(1);
         singleLinkedList.del(4);
         singleLinkedList.del(2);
         singleLinkedList.del(3);
         System.out.println("删除后的链表情况");
         singleLinkedList.list();
     }
 }
 //定义SingleLinkedList管理我们的英雄
 class SingleLinkedList{
     //先初始化一个头节点，头节点不要动,不存放具体的数据
     private HreoNode head=new HeroNode(0,"","");
     //添加节点到单向链表
     //思路，当不考虑编号顺序时
     //1.找到当前链表的最后节点
     //2.将最后这个节点的next指向新的节点
     public void add(HeroNode heroNode){
         //因为head节点不能动，因此我们需要一个辅助遍历temp
         HeroNode temp=head;
         //遍历链表，找到最后
         while(true){
             if(temp.next==null){
                 break;
             }
             //如果没有找到最后，将temp后移
             temp=temp.next;
         }
         //当退出while循环时，temp就指向了链表的最后
         //将最后这个节点的next指向新的节点
         temp.next=heroNode;
     }
     //第二种方式在添加英雄时， 根据排名将英雄插入到指定位置(如果有这个排名，则添加失败，并给出提示)
     public void addByOrder(HeroNode heroNode){
         //因为头节点不能动，因此我们仍然通过一个辅助指针（变量）来帮助找到添加的位置
         //因为单链表，因为我们找的temp是位于添加位置的前一个节点，否则插入不了
         HeroNode temp=head;
         boolean flag=false;//标志添加的编号是否存在，默认为false
         while(true){
             if(temp.next=null){//说明temp已经在链表的最后
                 break;
             }
             if(temp.next.no>heroNode.no){//位置找到，就在temp的后面插入
                 break;
                 
             }else if(temp.next.no==heroNode.no){//说明希望添加的heroNode的编号已然存在
                 flag=true;//说明编号存在
                 break;
             }
             temp=temp.next;//后移，遍历当前链表
         }
         //判断flag的值
         if(flag){//不能添加，说明编号存在
             System.out.printf("准备插入的英雄的编号%d已经存在了，不能加入\n",heroNode.no);
         }else{
             //插入到链表中，temp的后面
             heroNode.next=temp.next;
             temp.next=heroNode;
         };
     }
     //修改节点的信息，根据no编号来修改，即no编号不能改
     //说明
     //1.根据newHeroNode的no来修改即可
     public void update(HeroNode newHeroNode){
         //判断是否为空
         if(head.next==null){
             System.out.println("链表为空");
             return;
         }
         //找到需要修改的节点，根据no编写
         //定义一个辅助变量
         HeroNode temp=head.next();
         boolean flag=false;//表示是否找到节点
         while(true){
             if(temp==null){//已经遍历完链表
                 break;
             }
             if(temp.no==newHeroNode.no){
                 //找到
                 flag=true;
                 break;
             }
             temp=temp.next;
         }
         //根据flag判断是否找到要修改的节点
         if(flag){
             temp.name=newHreoNode.name;
              temp.nickname=newHreoNode.nickname;
         }else{//没有找到
              System.out.printt("没有找到编号%d的节点，不能修改\n",newHeroNode.no);
         }
     }
     //删除节点
     //思路
     //1.head不能动，因此我们需要一个temp辅助节点，找到待删除节点的前一个节点
     //2.说明我们在比较时，是temp.next.no和需要删除的节点的no比较
     public void del(int no){
         HeroNode temp=head;
         boolean flag=false;//标志是否找到待删除节点的
         while(true){
             if(temp.next==null){//已经到链表的最后
                 break;
             }
             if(temp.next.no==no){
                 //找到了待删除节点的前一个节点temp
                 flag=true;
                 break;
             }
             temp=temp.next;//temp后移，遍历
         }
         //判断flag
         if(flag){//找到
             //可以删除
             temp.next=temp.next.next;
         }else{
             System.out.printf("要删除的%d节点不存在\n",no);
         }
     }
     //显示链表【遍历】
     public void list(){
         //判断链表是否为空
         if(head.next==null){
             System.out.println("链表为空");
             return;
         }
         //因为头节点，不能动，因此我们需要一个辅助变量来遍历
         HeroNode temp=head.next;
         while(true){
             //判断是否到链表最后
             if(temp==null){
                 break;
             }
             //输出节点的信息
             System.out.println(temp);
             //将temp后移，一定小心
             temp=temp.next;
         }
     }
 }
 //定义HeroNode,每个HeroNode对象就是一个节点
 class HeroNode{
     public int no;
     public String name;
     public String nickname;
     public HeroNode next;//执行下一个节点
     //构造器
     public HeroNode(int hNo,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+"]";
     }
     
 }

🍡018 单链表按顺序插入节点

2) 第二种方式在添加英雄时， 根据排名将英雄插入到指定位置(如果有这个排名，则添加失败，并给出提示）

🍠020 单链表节点的删除和小结

从单链表删除一个节点的思路

1.我们先找到需要删除的这个节点的前一个节点temp

2.temp.next=temp.next.next

3.被删除的节点将不会有其他引用指向，会被垃圾回收机制回收

🍒021 单链表新浪面试题

方法：获取到单链表的节点的个数（如果是带头节点的链表，需求不统计头节点）

head：链表的头节点，返回的就是有效节点的个数

 public static int getLength(HeroNode head){
     if(head.next==null){//空链表
         return 0;
     }
     int length=0;
     //定义一个辅助的变量，这里我们没有统计头节点
     HeroNode cur=head.next;
     while(cur!=null){
         length++;
         cur=cur.next;//遍历
     }
     return length;
 }

下期预告：力扣每日一练之数组上篇Day1

觉得文章写的不错的亲亲们，点赞评论走一波，爱你们哦！🥗