新星计划Day5【数据结构与算法】 链表Part1
新星计划Day5【数据结构与算法】 链表Part1
👩💻博客主页：京与旧铺的博客主页
✨欢迎关注🖱点赞🎀收藏⭐留言✒
🔮本文由京与旧铺原创，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 单链表介绍和内存布局
链表是有序的列表，但是它在内存中是存储如下
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qN7tIbkm-1651288068686)(C:\Users\86191\AppData\Roaming\Typora\typora-user-images\image-20220429191109713.png)]
小结：
1.链表是以节点的方式来存储，是链式存储
2.每个节点包含data域，next域指向下一个节点
3.发现链表的各个节点不一定是连续存储
4.链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-22DPejfM-1651288068687)(C:\Users\86191\AppData\Roaming\Typora\typora-user-images\image-20220429191136569.png)]
🍭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 单链表按顺序插入节点
- 第二种方式在添加英雄时， 根据排名将英雄插入到指定位置(如果有这个排名，则添加失败，并给出提示）
🍠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
除的节点将不会有其他引用指向，会被垃圾回收机制回收
🍒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
觉得文章写的不错的亲亲们，点赞评论走一波，爱你们哦！🥗