1.单链表的介绍和内存布局
1.1链表是有序的列表,以节点的方式进行存储,每个节点包含data域,next域;
(1)data域:存储数据;next域:指向下一个节点
1.2 链表的各个节点不一定是连续存储的
1.3 链表分带头节点的链表和没有头节点的链表,根据实际的需求来确定
2.单链表的具体实现
2.1在添加英雄时,直接添加到链表的尾部
(1)分析
-先创建一个head头节点,作用就是表示单链表的头
-每添加一个节点,就直接加入到链表的最后
-遍历:通过辅助遍历遍历,帮助遍历整个链表
(2)源代码
package cn.atguigu.Linkedlist; public class SingleLinkedlistDemo { public static void main(String[] args) { // TODO Auto-generated method stub SingleLinkedlist singlelinkedlist=new SingleLinkedlist(); HeroNode hero1=new HeroNode(1, "宋江", "及时雨"); HeroNode hero2=new HeroNode(2, "卢俊义", "玉麒麟"); HeroNode hero3=new HeroNode(3, "吴用", "智多星"); HeroNode hero4=new HeroNode(4, "林冲", "豹子头"); singlelinkedlist.add(hero1); singlelinkedlist.add(hero2); singlelinkedlist.add(hero3); singlelinkedlist.add(hero4); singlelinkedlist.show(); } //创建SingleLinkedlist类 public static class SingleLinkedlist{ //创建头节点 private HeroNode head=new HeroNode(0, "", ""); //实现英雄人物的添加 public void add(HeroNode HeroNode) { //创建临时节点指向head HeroNode temp=head; //寻找最后一个节点 while(true) { if(temp.next==null) {//如果临时节点的下一个域为空,则其为最后一个节点 break; }else {//否则临时节点后移 temp=temp.next; } }//temp指向最后一个节点,将新节点添加到temp.next temp.next=HeroNode; } //实现显示链表 public void show() { //创建临时节点指向head HeroNode temp=head; //判断链表是否为空 if(temp.next==null) { System.out.println("链表为空"); return; } while(true) { if(temp.next==null) {//若临时变量的next为null,跳出循环 break; }else { temp=temp.next; System.out.println(temp); } } } } //创建HeroNode类 public static 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; } } }
2.2 在添加英雄时,根据排名将英雄插入到指定位置(如果有这个排名,则添加失败,给出提示)
(1)分析
-首先找到新添加的节点的位置,是通过辅助变量遍历解决
-新的节点.next=temp.next
-将temp.next=新的节点
(2)源代码-添加到SingleLinkedlist类
public void addByOrder(HeroNode HeroNode) { //创建临时节点 HeroNode temp=head; //创建布尔变量,判断链表中是否存在该排名的英雄,若有为true,其默认值为false boolean flag=false; while(true) { //判断链表是否为空 if (temp.next==null) { break; } if(temp.next.no>HeroNode.no) {//如果临时节点下一节点的排名大于新节点的排名,则该新节点应当添加在新节点后 break; }else if(temp.next.no==HeroNode.no){//说明该排名的英雄已存在,不需要添加 flag=true; } temp=temp.next;//temp后移 } //判断flag if(flag) { System.out.println(temp+"已存在,不需添加"); }else { HeroNode.next=temp.next; temp.next=HeroNode; } }
2.3 修改名字和昵称
//修改节点的信息,根据no编号来修改 public void update(HeroNode heroNode) { //判断节点是否为空 if(head.next==null) { System.out.println("链表为空,无法修改"); } //创建临时节点 HeroNode temp=head; //创建布尔值,默认为false,找到该排名时设置为true boolean flag=false; while(true) { if(temp.next==null) { break; } if(temp.no==heroNode.no) { flag=true; break; } temp=temp.next; } //判断flag if(flag) { temp.name=heroNode.name; temp.nickname=heroNode.nickname; }else { System.out.println("没有找到"+heroNode.no+"的节点"); } }
2.4 实现节点的删除
(1)分析
-先找到需要删除节点的前一个节点temp
-temp.next=temp.next.next
-被删除的节点,将不会有其他引用指向,会被垃圾回收机制回收
//实现节点的删除,根据no编号删除 public void delete(HeroNode heroNode) { //判断节点是否为空 if(head.next==null) { System.out.println("链表为空,无法删除"); } //创建临时节点 HeroNode temp=head; //创建布尔值,默认为false,找到该排名时设置为true boolean flag=false; while(true) { if(temp.next==null) { break; }else if(temp.next.no==heroNode.no) {//若临时节点下一节点的no编号与待删除的编号相同,设置flag变量,跳出循环 flag=true; break; } temp=temp.next; } //根据flag判断 if(flag) { temp.next=temp.next.next; }else { System.out.println("没有找到"+heroNode.no+"的节点"); } }
2.5 单链表面试题
//查找单链表中的倒数第k个节点【新浪面试题】 //思路 //1编写一个方法,接收head节点,同时接受一个index //2index表示是倒数第k个节点 //3先把链表从头到尾遍历,得到链表的总长度getLength //4得到size后,从链表的第一个开始遍历(size-index)个 public static HeroNode findLastIndexNode(HeroNode head,int index) { //判断链表是否为空 if(head.next==null) { return null;//没有找到 } int k=0; if(0<=index&&index<=getLength(head)) { k=getLength(head)-index; }else { return null; } HeroNode temp=head.next; for(;k>0;k--) { temp=temp.next; } return temp; } //方法:实现单链表的逆序打印[百度面试] //方式1:先将单链表进行反转操作,然后再遍历即可,存在问题是会破坏原来的单链表的结构,不建议 //方式2:利用栈的数据结构,将各个节点压入到栈中,利用栈先进后出的特点实现逆序打印,使用stack集合 public static void reversePrint(HeroNode head) { if(head.next==null) { return;//空链表,不能打印 } //创建一个栈 Stack<HeroNode> stack=new Stack<HeroNode>(); HeroNode temp=head.next; //入栈 while(temp!=null) { stack.push(temp); temp=temp.next; } while(stack.size()>0) { System.out.println(stack.pop()); } } //方法:实现单链表的反转【腾讯面试】 /* * 思路: * 1.先定义一个节点reverseHead=new HeroNode(); * 2.从头到尾遍历原来的链表,每遍历一个节点,就将其取出,并放在新的链表的最前端 * 3.原来的链表head.next=reverseHead.next */ public static void reverse(HeroNode head) { //创建新的头节点 HeroNode reverseHead =new HeroNode(0,"",""); //判断链表是否为空,或只有一个节点,无需反转 if(head.next==null||head.next.next==null) { return; } //遍历链表 //创建辅助指针,帮助遍历原来的链表 HeroNode temp=head.next; HeroNode next=null;//指向当前节点temp的下一个节点 while(temp!=null) { next=temp.next;//保存当前节点的下一个节点 temp.next=reverseHead.next;//将temp的下一个节点指向新的链表的最前端 reverseHead.next=temp; temp=next;//temp后移 } head.next=reverseHead.next; } //方法:获取到单链表的节点的个数(如果是带头结点的链表,要求不统计头节点) /** * @param head 链表的头节点 * @return 返回的是有效节点的个数 * @author motke * */ public static int getLength(HeroNode head) { HeroNode temp=head; int num=0; if(head.next==null) {//空链表 return 0; } while(temp.next!=null) { num++; temp=temp.next; } return num; }
2.6 单链表的缺点分析
(1)单向链表的查找的方向只能是一个方向,双向链表可以向前或向后查找。
(2)单向链表不能自我删除,需要依靠辅助节点,双向链表可以实现自我删除。
3.双链表的具体实现
package cn.atguigu.Linkedlist; public class DoubleLinkedlistDemo { public static void main(String[] args) { DoubleLinkedlist doubleLinkedlist=new DoubleLinkedlist(); HeroNode hero1=new HeroNode(1, "宋江", "及时雨"); HeroNode hero2=new HeroNode(2, "林冲", "豹子头"); HeroNode hero3=new HeroNode(3, "卢俊义", "玉麒麟"); HeroNode hero4=new HeroNode(4, "吴用", "智多星"); HeroNode hero5=new HeroNode(4, "史进", "九纹龙"); //实现双链表的添加 doubleLinkedlist.add(hero1); doubleLinkedlist.add(hero2); doubleLinkedlist.add(hero3); doubleLinkedlist.add(hero4); System.out.println("添加的效果~~"); doubleLinkedlist.show(); //实现双链表的修改 System.out.println("修改后的效果~~"); doubleLinkedlist.update(hero5); doubleLinkedlist.show(); //实现双链表的删除 System.out.println("删除后的效果~~"); doubleLinkedlist.delete(4); doubleLinkedlist.show(); } public static class HeroNode {//创建双向链表的节点 public int no; public String name; public String nickname; public HeroNode next; public HeroNode pre;//指向前一个节点 //构造器 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 + "]"; } } public static class DoubleLinkedlist{ //创建头节点 HeroNode head=new HeroNode(0, "", ""); //实现新节点的添加操作 public void add(HeroNode heroNode) { //创建临时节点 HeroNode temp=head; //temp.pre=head; //找到该链表的最后一个节点 while(temp.next!=null) { temp=temp.next; } //实现新节点的添加 temp.next=heroNode; heroNode.pre=temp; } public void delete(int no) { //判断节点是否为空 if(head.next==null) { System.out.println("链表为空,无法修改"); return; } //创建临时节点 HeroNode temp=head.next; //创建布尔值,默认为false,找到该排名时设置为true boolean flag=false; while(true) { if(temp==null) { break; }else if(temp.no==no) {//若临时节点下一节点的no编号与待删除的编号相同,设置flag变量,跳出循环 flag=true; break; } temp=temp.next; } //根据flag判断 if(flag) { temp.pre.next=temp.next; if(temp.next!=null) { temp.next.pre=temp.pre; } }else { System.out.println("没有找到"+no+"的节点"); } } //修改节点的信息,根据no编号来修改 public void update(HeroNode heroNode) { //判断节点是否为空 if(head.next==null) { System.out.println("链表为空,无法修改"); return; } //创建临时节点 HeroNode temp=head; //创建布尔值,默认为false,找到该排名时设置为true boolean flag=false; while(true) { if(temp==null) { break; } if(temp.no==heroNode.no) { flag=true; break; } temp=temp.next; } //判断flag if(flag) { temp.name=heroNode.name; temp.nickname=heroNode.nickname; }else { System.out.println("没有找到"+heroNode.no+"的节点"); } } //实现显示链表 public void show() { //创建临时节点指向head HeroNode temp=head; //判断链表是否为空 if(temp.next==null) { System.out.println("链表为空"); return; } while(true) { if(temp.next==null) {//若临时变量的next为null,跳出循环 break; }else { temp=temp.next; System.out.println(temp); } } } } }
4. 环形链表介绍和约瑟夫问题
4.1 环形链表的应用场景-约瑟夫问题(Josephu)
设编号为1,2,3...,n的n个人围坐一圈,约定编号为k(1<=k<=n)的人从1开始报数,数到m的那个人出列,它的下一位又开始从1开始报数,数到m的那个人再出列,以此类推,直到所有人出列为止,由此产生一个出队变好的序列。
利用不带头节点的循环单链表来解决该问题:先构成一个有n个节点的单向环链表,然后由k节点起从1开始计算,计到m时,对应节点从链表中删除,然后再从被删除节点的下一个节点又从1开始计数,直到最后一个节点从链表中删除,算法结束
4.2 源代码实现
package cn.atguigu.Linkedlist; public class CircleLinkedlistDemo { public static void main(String[] args) { // TODO Auto-generated method stub CircleLinkedlist cir=new CircleLinkedlist(); System.out.println("创建好的环形链表为~~"); cir.add(5); cir.list(); System.out.println("按照规定顺序出圈~~"); cir.countBoy(1, 3, 5); } //创建单向环形链表,实现节点添加操作 class CircleLinkedlist{ //创建一个节点,辅助作为一个头节点,first节点不可动,指向第一个节点 Boy first=null; //节点添加方法 public void add(int nums) { //对nums进行校验 if(nums<2) { System.out.println("输入数字不符合要求,请输入1以上的整数"); return; } //创建临时节点 Boy curBoy=null; for(int i=1;i<=nums;i++) { //创建节点 Boy boy=new Boy(i); if(i==1) {//第一个节点需要特殊处理 first=boy;//将第一个指针指向头节点 first.next=first;//自身形成一个环形 curBoy=first; }else { curBoy.next=boy; boy.next=first;//将新节点指向头节点 curBoy=boy;//curBoy后移一位 } } } //遍历当前链表 public void list() { //判断链表是否为空 if(first==null) { System.out.println("链表为空"); return; } //创建临时节点 Boy curBoy=first; do{ System.out.println(curBoy.no); curBoy=curBoy.next; }while(curBoy.next!=first); System.out.println(curBoy.no); } //根据用户输入,生成出圈的顺序 /** * * @param startNo 表示从第几个开始数数 * @param countNo 表示数几下 * @param nums 表示初始时刻的总数 */ public void countBoy(int startNo, int countNo, int nums) { if(first==null||startNo <1||startNo>nums) { System.out.println("参数输入有误,请重新输入"); return; } //创建辅助指针,帮助完成小孩出圈 Boy helper=first; //将该节点指向最后一个节点 while(true) { if(helper.next==first) { break; } helper=helper.next; } //将first和helper指针移动startNo-1次,找到指定的开始位置 for(int j=0;j<startNo-1;j++) { first=first.next; helper=helper.next; } while(true) { if(helper==first) { break;//说明圈中只有一个节点 } //当开始报数时,first和helper要移动countNo-1次 for(int j=0;j<countNo-1;j++) { first=first.next; helper=helper.next; } //这时fisrt指向的节点就是要出圈的数 System.out.print(first.no+",");//输出当前这个值 first=first.next;//将当前指针前移一位 helper.next=first;//删除前一个first指针 } System.out.print(first.no); } } //创建单向环形链表的节点 class Boy{ public int no; public Boy next;//指向下一个节点,默认null public Boy(int no) { this.no = no; } @Override public String toString() { return "Node [no=" + no + "]"; } }