hero sj：链表-双向链表

一、双向链表

1.单向链表的缺点分析：

1、单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找
2、单向链表不能自我删除，需要靠辅助结点，而双向链表则可以自我删除。

2、双向链表的遍历、增删改查操作

① 遍历：和单链表一样，只是可以向前，也可以向后
② 增加：（默认添加到双向链表的最后）
1）先找到双向链表的最后结点
2）temp.next=newHeroNode;
3) newHeroNode.pre=temp;
③ 修改：思路和单向链表一样
④ 删除：可以自我删除某个结点
1）先找到想要删除的这个结点
2）temp.pre.next=temp.next;
3) temp.next.pre=temp.pre;

3.结点类的创建，双向链表类的创建、功能实现：

① 结点类的创建，代码如下：

// 定义HeroNode2，每个HeroNode2的实例对象就是一个结点class HeroNode2{ public int no; public String name; public String nickname; public HeroNode2 next; // 指向下一个结点 public HeroNode2 pre; // 指向上一个结点 public HeroNode2(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 + '\'' + '}'; }}

② 双向链表类的创建、功能实现 代码如下：

// 创建一个双向链表的类class DoubleLinkedListt { // 先初始化一个头结点，头结点不要动，不存放具体数据 private HeroNode2 head = new HeroNode2(0, "", ""); // 返回头结点 public HeroNode2 getHead() { return head; } // 显示链表【遍历】 public void showlist() { // 判断链表是否为空 if (head.next == null) { System.out.println("链表为空"); return; } // 因为头结点，不能动，因此要一个辅助遍历temp来遍历 HeroNode2 temp = head.next; while (true) { // 判断是否到链表最后 if (temp == null) { break; } //输出结点信息 System.out.println(temp); // 将temp后移,一定要小心 temp = temp.next; } } // 添加操作 按结点编号顺序插入链表中 public void doubleAdd(HeroNode2 heroNode2){ boolean flag=false; HeroNode2 temp =head; while (true){ if (temp.next==null){ break; } if (temp.next.no>heroNode2.no){ break; } if (temp.next.no==heroNode2.no){ flag=true; break; } temp=temp.next; } if (flag){ System.out.printf("需要添加的结点编号%d：已存在",heroNode2.no); }else { if (temp.next!=null){ temp.next.pre=heroNode2; heroNode2.next=temp.next; heroNode2.pre=temp; temp.next=heroNode2; }else { temp.next=heroNode2; heroNode2.pre=temp; } } } // 修改一个结点的内容 与点链表一样 // 修改节点的信息，根据no编号来修改，即no编号不能改 // 说明：根据newHeroNode 的no来修改 public void updata(HeroNode2 newHeroNode2){ if(head.next==null){ System.out.println("链表为空"); return; } HeroNode2 temp=head.next; boolean flag=false; while (true){ if(temp==null) { break; // 到链表的最后 已经遍历完链表了 } if(temp.no==newHeroNode2.no){ flag=true; // 找到了 break; } temp=temp.next; } // 根据flag判断是否找到要修改的结点 if (flag){ temp.name= newHeroNode2.name; temp.nickname=newHeroNode2.nickname; }else { System.out.printf("没有找到编号%d的结点 ",newHeroNode2.no); } } //根据no值来判断删除 与单链表不同，双链表可以再定位到要删除结点的地方实现自我删除 public void del(int no){ if (head.next==null){ System.out.println("链表为空，无法删除"); return; } HeroNode2 temp=head.next; boolean flag=false; // 标识是否找到 while (true){ if (temp==null){ //到最后 break; } if (temp.no==no) { // 找到待删除结点的temp flag = true; break; } temp=temp.next; // temp后移，继续遍历 } if (flag){ temp.pre.next=temp.next; // 如果是最后一个结点，就不要执行下面这句话，否则出现空指针异常 if (temp.next!=null){ temp.next.pre=temp.pre; } }else { System.out.printf("要删除的编号%d的结点不存在\n",no); } }}

③主类测试，代码如下：

public class DoubleLinkedList { public static void main(String[] args) { // 进行测试 // 先创建结点 HeroNode2 sj = new HeroNode2(1, "宋江", "及时雨"); HeroNode2 ljy = new HeroNode2(2, "卢俊义", "玉麒麟"); HeroNode2 wy = new HeroNode2(3, "吴用", "智多星"); HeroNode2 lc = new HeroNode2(4, "林冲", "豹子头"); // 创建双向链表 DoubleLinkedListt doubleLinkedList = new DoubleLinkedListt(); // 结点编号方式添加 （根据no来排列添加） doubleLinkedList.doubleAdd(sj); doubleLinkedList.doubleAdd(lc); doubleLinkedList.doubleAdd(wy); doubleLinkedList.doubleAdd(ljy); // 显示 doubleLinkedList.showlist(); // 修改一个结点 HeroNode2 gss = new HeroNode2(2, "公孙胜", "入云龙"); doubleLinkedList.updata(gss); System.out.println("修改后的双向链表"); //修改后显示 doubleLinkedList.showlist(); //删除操作 doubleLinkedList.del(3); System.out.println("删除后的双向链表"); //删除后显示 doubleLinkedList.showlist(); }}

二、单向环形链表以及（约瑟夫问题）

1.构建一个单向环形链表思路

1、先创建第一个结点，让first指向该结点，并形成环形（first不能动，需要辅助变量temp来移动）
2、后面当每创建一个新的结点，就把该结点，加入到已有的环形链表中即可。

遍历单向环形链表
1、先让辅助指针temp（变量），以及指针first指向第一个结点
2、然后通过while循环遍历该环形链表 temp.next==first（表示遍历一圈结束）

2.环形链表的创建的过程

① 创建一个结点类（Person）

// 创建一个Person类表示一个结点class Person{ public int no; // 编号 public Person next; // 指向下一个结点，默认null public Person(int no) { this.no = no; } public int getNo() { return no; } public void setNo(int no) { this.no = no; } @Override public String toString() { return "Person{" + "no=" + no + '}'; }}

② 创建一个环形链表的类，其中先创建一个类似头结点的第一个结点first（作为指针），后续在添加结点的方法中给其指向第一个数据结点

// 创建一个环形链表的类class CircleSingLinkedList{ // 创建一个first结点，当前没有编号 // 类似头结点，不过后面要赋值 // private Person first =null; private Person first = new Person(-1); //添加结点的方法 public void CircleAdd(int nums){ // nums做一个数据校验 if (nums<1){ System.out.println("输入的nums的值不正确"); return; } Person temp=null; // 创建辅助变量 temp // 使用for来创建我们的环形链表 for (int i=1;i<=nums;i++){ // 根据编号，创建person结点 Person person = new Person(i); // 如果是第一个人 if (i==1){ first=person; // 第一个结点first指向新结点，编号1 first.next=first; // 形成一个元素的环形链表 temp=first; // 由于first不能动，让temp辅助变量也指向它来替代 }else { temp.next=person; // 第一个/添加上一个循环中的person结点指向这一循环中的person person.next=first; // 这轮循环中的person结点指向，第一个结点 temp=person; // temp后移到这轮循环person结点的位置 } } } // 遍历环形链表 public void ShowCircleList(){ if (first.no==-1){ //没有链表 System.out.println("没有任何人员"); return; } // 因为first不能动，因此我们使用一个辅助指针temp（变量）来完成 Person temp=first; while (true){ System.out.printf("人员的编号为%d：\n",temp.no); if (temp.next==first){ break; } temp=temp.next; } }}

③ 测试环形链表

public class Josephu { public static void main(String[] args) { // 测试创建一个环形链表和它的遍历 CircleSingLinkedList circleSingLinkedList = new CircleSingLinkedList(); // 加入9个Person成员结点进入链表 circleSingLinkedList.CircleAdd(9); // 遍历显示 circleSingLinkedList.ShowCircleList(); }}

3.约瑟夫问题

约瑟夫问题：设编号为1、2、…n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，以此类推，直到所有人出列为止，由此产生一个出对编号的序列。

例如：

生成9个成员的出圈小队。
n=9，即有9个成员
k=1，从第一个人开始报数
m=2，每次数2下

思路： 此方法由于first没有使用辅助指针，一直在变化，因此链表的结构受到改变
1、需求创建开始报数结点的例如（first）和指向从开始报数的结点的前一个结点位置的一个辅助指针helper
补充：报数前，先让first和helper移动k-1次
2、当成员报数时，让开始报数的结点和helper指针同时移动m-1次
3、这时就可以将temp指向的小孩结点出圈
first=first.next （first要后移一位）
helper.next=first （helper没有移动，只是它的指向）
原来的first指向的结点就没有任何引用，就会被自动回收

//

根据用户的输入，计算出成员出圈的顺序

/* * startNo 表示从第几个成员开始报数 * countNum 表示数几下 * nums 表示最初有多少个成员在圈中 * */

代码如下：

public void countPerson(int startNo,int countNum ,int nums){ // 先进行数据校验 if (first==null || startNo<1 || startNo>nums){ System.out.println("参数输入有误，请重新输入..."); return; } // 创建辅助指针，帮助出圈 因为直接移动first，helper的存在保证一直是个环形链表 Person helper = first; // 需求创建一个辅助指针(变量)helper，事先应该指向环形链表最后的结点 while (true){ if (helper.next==first){ break; } helper=helper.next; } // 成员报数前，先让first和helper移动k-1次 for (int j=0;j<startNo-1;j++){ first=first.next; helper=helper.next; } // 当成员报数时，让first和helper指针同时移动m-1次，然后出圈 // 这里是一个循环操作，直到圈中只有一个结点 while (true){ if (helper==first){ break; //圈中只有一个结点 } // 让first和helper指针同时移动到 countNum-1 for (int j=0;j<countNum-1;j++){ first=first.next; helper=helper.next; } // 这时first指向的结点，就是要出圈的成员结点 System.out.printf("成员%d出圈\n",first.no); // 这时将first指向的成员结点出圈 first=first.next; // first要后移一位 helper.next=first; // helper没有移动，只是它的指向 } System.out.printf("最后留在圈中的成员编号%d\n",first.no); }

测试如下：

// 测试成员出圈 circleSingLinkedList.countPerson(1,2,5);