一、双向链表
使用带head头的双向链表实现-水浒英雄排行榜管理单向链表的缺点分析：
）单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。
2）单向链表不能自我删除，需要靠辅助节点，而双向链表，则可以自我删除，所以前面我们单链表删除节点时，总是找到temp,temp时待删除节点的前一个节点(认真体会)。
分析双向链表的遍历，添加，修改，删除的操作思路
.遍历和单链表一样只是可以向前，也可以向后查找
2.添加(默认添加到双向链表的最后)
）先找到双向链表的最后这个节点
2）temp.next=newHeroNode
）newHeroNode.p=temp
.修改思路和原理与单向链表一样
4.删除
）因为时双向链表，因此，我们可以实现自我删除某个节点
2）直接找到要删除的这个节点，比如temp
)temp.p.next=temp.next
4)temp.next.p=temp.p
publicclassDoubleLinkedListDemo{ publicstaticvoidmain(String[]args){ //测试 System.out.println("双向链表的测试"); //先创建节点 HeroNode2hero=newHeroNode2(,"宋江","及时雨"); HeroNode2hero2=newHeroNode2(2,"卢俊义","玉麒麟"); HeroNode2hero=newHeroNode2(,"吴用","智多星"); HeroNode2hero4=newHeroNode2(4,"林冲","豹子头"); //创建一个双向链表 DoubleLinkedListdoubleLinkedList=newDoubleLinkedList(); //加入 doubleLinkedList.add(hero); doubleLinkedList.add(hero2); doubleLinkedList.add(hero); doubleLinkedList.add(hero4); doubleLinkedList.list(); //修改 HeroNode2newHeroNode=newHeroNode2(4,"公孙胜","入云龙"); doubleLinkedList.update(newHeroNode); System.out.println("修改后的链表情况"); doubleLinkedList.list(); //删除 doubleLinkedList.del(); System.out.println("删除后的链表情况~~"); doubleLinkedList.list(); }}//创建一个双向链表的类classDoubleLinkedList{ //先初始化一个头节点，头节点不要动，不存放具体的数据 privateHeroNode2head=newHeroNode2(0,"",""); //返回头节点 publicHeroNode2getHead(){ turnhead; } //显示链表[遍历] publicvoidlist(){ //判断链表是否为空 if(head.next==null){ System.out.println("链表为空"); turn; } //因为头节点，不能动，因此我们需要一个辅助变量来遍历 HeroNode2temp=head.next; while(true){ //判断是否到链表最后 if(temp==null){ bak; } //输出节点的信息 System.out.println(temp); //将temp后移，一定小心 temp=temp.next; } } //添加一个节点到双向链表的最后 publicvoidadd(HeroNode2heroNode){ //因为head节点不能动，因此我们需要一个辅助变量temp HeroNode2temp=head; //遍历链表，找到最后 while(true){ //找到链表的最后 if(temp.next==null){ bak; } //如果没有找到最后，将temp后移 temp=temp.next; } //当退出while循环时，temp就指向了链表的最后 //形成一个双向链表 temp.next=heroNode; heroNode.p=temp; } //修改一个节点的内容，双向链表的节点内容修改和单向链表一样 //只是节点类型改成HeroNode2 publicvoidupdate(HeroNode2newHeroNode){ //判断是否空 if(head.next==null){ System.out.println("链表为空~~"); turn; } //找到需要修改的节点，根据no编号 //定义一个辅助变量 HeroNode2temp=head.next; booleanflag=false;//表示是否找到该节点 while(true){ if(temp==null){ bak;//已经遍历完链表 } if(temp.no==newHeroNode.no){ //找到 flag=true; bak; } temp=temp.next; } //根据flag判断是否找到要修改的节点 if(flag){ temp.name=newHeroNode.name; temp.nickname=newHeroNode.nickname; }else{//没有找到 System.out.printf("没有找到编号%d的节点，不能修改\n",newHeroNode.no); } } //从双向链表中删除一个节点 //说明 //.对于双向链表，我们可以直接找到要删除的这个节点 //2.找到后，自我删除即可 publicvoiddel(intno){ //判断当前链表是否为空 if(head.next==null){//空链表 System.out.println("链表为空，无法删除"); turn; } HeroNode2temp=head.next;//辅助变量(指针),指向第一个节点(与单向链表不同) booleanflag=false;//标志是否找到待删除节点 while(true){ if(temp.next==null){//已经到链表的最后节点的next bak; } if(temp.next.no==no){ //找到的待删除节点的前一个节点temp flag=true; bak; } temp=temp.next;//temp后移，遍历 } //判断flag if(flag){//找到 //可以删除 temp.p.next=temp.next; //如果是最后一个节点，就不需要执行下面的这句话，否则出现空指针 if(temp.next!=null){ temp.next.p=temp.p; } }else{ System.out.printf("要删除的%d节点不存在\n",no); } }}//定义HeroNode2,每个HeroNode对象就是一个节点classHeroNode2{ publicintno; publicStringname; publicStringnickname; publicHeroNode2next;//指向下一个节点,默认为null publicHeroNode2p;//指向前一个节点,默认为null //构造器 publicHeroNode2(intno,Stringname,Stringnickname){ this.no=no; this.name=name; this.nickname=nickname; } //为了显示方便，我们重写toString
Override publicStringtoString(){ turn"HeroNode2[no="+no+",name="+name+",nickname="+nickname+"]"; }}
二、环形链表及其应用：约瑟夫问题
环形链表图示
构建一个单向的环形链表思路
.先创建第一个节点，让first指向该节点，并形成环形
2.后面当我们每创建一个新的节点，就把该节点加入到已有的环形链表中即可。
遍历环形链表
.先让一个辅助指针(变量)curBoy,指向first节点
2.然后通过一个while循环遍历该环形链表即可cur.Boy.next==first结束
约瑟夫问题
.创建一个辅助指针(变量)helper,事先应该指向环形链表的最后这个节点。
2.小孩报数前，先让first和helper移动k-次（移动到报数的小孩）
.当小孩报数时，让first和helper指针同时的移动m-次
4.这时就可以将first指向的小孩节点出圈
first=first.next
helper.next=first
原来first指向的节点就没有任何引用，就会被回收
publicclassJosepfu{ publicstaticvoidmain(String[]args){ //测试看看构建环形链表，和遍历是否ok CircleSingleLinkedListcircleSingleLinkedList=newCircleSingleLinkedList(); circleSingleLinkedList.addBoy(5);//加入5个小孩节点 circleSingleLinkedList.showBoy(); //测试小孩出圈是否正确 circleSingleLinkedList.countBoy(,2,5);//2-4--5- }}//创建一个环形的单向链表classCircleSingleLinkedList{ //创建一个first节点，当前没有编号 privateBoyfirst=null; //添加小孩节点，构建一个环形的链表 publicvoidaddBoy(intnums){ //nums做一个数据校验 if(nums){ System.out.println("nums的值不正确"); turn; } BoycurBoy=null;//辅助指针，帮助构建环形链表 //使用for来创建环形链表 for(inti=;i=nums;i++){ //根据编号，创建小孩节点 Boyboy=newBoy(i); //如果是第一个小孩 if(i==){ first=boy; first.setNext(first);//构成环(暂时是一个节点的环) curBoy=first;//让curBoy指向第一个小孩 }else{//这块的操作看不懂，可以回去看一下当时老师视频里的流程图，特别好理解！！！！！！！！！！ curBoy.setNext(boy); boy.setNext(first); curBoy=boy; } } } //遍历当前的环形链表 publicvoidshowBoy(){ //判断链表是否为空 if(first==null){ System.out.println("没有任何小孩~~"); turn; } //因为first不能动，因此我们仍然使用一个辅助指针完成遍历 BoycurBoy=first; while(true){ System.out.printf("小孩的编号%d\n",curBoy.getNo()); if(curBoy.getNext()==first){//说明已经遍历完毕 bak; } curBoy=curBoy.getNext();//curBoy后移 } } //根据用户的输入，计算出小孩出圈的顺序 /** *
paramstartNo表示从第几个小孩开始数数 *paramcountNum表示数几下 *paramnums表示最初有多少小孩在圈中 */ publicvoidcountBoy(intstartNo,intcountNum,intnums){ //先对数据进行校验 if(first==null
startNo
startNonums){ System.out.println("参数输入有误，请重新输入"); turn; } //创建一个辅助指针，帮助完成小孩出圈 Boyhelper=first; //需要创建一个辅助指针(变量)helper,事先应该指向环形链表的最后这个节点 while(true){ if(helper.getNext()==first){//说明helper指向最后小孩节点 bak; } helper=helper.getNext(); } //小孩报数前，先让first和helper移动k-次 for(intj=0;jstartNo-;j++){ first=first.getNext(); helper=helper.getNext(); } //当小孩报数时，让first和helper指针同时的移动m-次，然后出圈 //这里是一个循环操作，直到圈中只有一个节点 while(true){ if(helper==first){//说明圈中只有一个节点 bak; } //让first和helper指针同时的移动countNum- for(intj=0;jcountNum-;j++){ first=first.getNext(); helper=helper.getNext(); } //这时first指向的节点，就是要出圈的小孩节点 System.out.printf("小孩%d出圈\n",first.getNo()); //这时将first指向的小孩节点出圈 first=first.getNext(); helper.setNext(first); } System.out.printf("最后留在圈中的小孩编号%d\n",first.getNo()); }}//创建一个Boy类，表示一个节点classBoy{ privateintno;//编号 privateBoynext;//指向下一个节点，默认null publicBoy(intno){ this.no=no; } publicintgetNo(){ turnno; } publicvoidsetNo(intno){ this.no=no; } publicBoygetNext(){ turnnext; } publicvoidsetNext(Boynext){ this.next=next; }}
,
