第 4 章链表（三）-阿里云开发者社区

4.9、双向链表测试

4.9.1、测试代码

public static void main(String[] args) {
    // 测试
    System.out.println("双向链表的测试");
    // 先创建节点
    HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
    HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
    HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
    HeroNode hero4 = new HeroNode(5, "林冲", "豹子头");
    // 创建一个双向链表
    DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
    doubleLinkedList.add(hero1);
    doubleLinkedList.add(hero2);
    doubleLinkedList.add(hero3);
    doubleLinkedList.add(hero4);
    doubleLinkedList.list();
    // 测试按需插入
    doubleLinkedList.addByOrder(new HeroNode(4, "Heygo", "Heygogo"));
    doubleLinkedList.addByOrder(new HeroNode(6, "Oneby", "Onebyone"));
    System.out.println("按顺序插入后的情况");
    doubleLinkedList.list();
    // 修改
    HeroNode newHeroNode = new HeroNode(5, "公孙胜", "入云龙");
    doubleLinkedList.update(newHeroNode);
    System.out.println("修改后的链表情况");
    doubleLinkedList.list();
    // 删除
    doubleLinkedList.del(3);
    System.out.println("删除后的链表情况~~");
    doubleLinkedList.list();
}

4.9.2、程序运行结果

双向链表的测试
HeroNode [no=1, name=宋江, nickname=及时雨]
HeroNode [no=2, name=卢俊义, nickname=玉麒麟]
HeroNode [no=3, name=吴用, nickname=智多星]
HeroNode [no=5, name=林冲, nickname=豹子头]
按顺序插入后的情况
HeroNode [no=1, name=宋江, nickname=及时雨]
HeroNode [no=2, name=卢俊义, nickname=玉麒麟]
HeroNode [no=3, name=吴用, nickname=智多星]
HeroNode [no=4, name=Heygo, nickname=Heygogo]
HeroNode [no=5, name=林冲, nickname=豹子头]
HeroNode [no=6, name=Oneby, nickname=Onebyone]
修改后的链表情况
HeroNode [no=1, name=宋江, nickname=及时雨]
HeroNode [no=2, name=卢俊义, nickname=玉麒麟]
HeroNode [no=3, name=吴用, nickname=智多星]
HeroNode [no=4, name=Heygo, nickname=Heygogo]
HeroNode [no=5, name=公孙胜, nickname=入云龙]
HeroNode [no=6, name=Oneby, nickname=Onebyone]
删除后的链表情况~~
HeroNode [no=1, name=宋江, nickname=及时雨]
HeroNode [no=2, name=卢俊义, nickname=玉麒麟]
HeroNode [no=4, name=Heygo, nickname=Heygogo]
HeroNode [no=5, name=公孙胜, nickname=入云龙]
HeroNode [no=6, name=Oneby, nickname=Onebyone]

4.10、双向链表所有代码

public class DoubleLinkedListDemo {
 public static void main(String[] args) {
  // 测试
  System.out.println("双向链表的测试");
  // 先创建节点
  HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
  HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
  HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
  HeroNode hero4 = new HeroNode(5, "林冲", "豹子头");
  // 创建一个双向链表
  DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
  doubleLinkedList.add(hero1);
  doubleLinkedList.add(hero2);
  doubleLinkedList.add(hero3);
  doubleLinkedList.add(hero4);
  doubleLinkedList.list();
  // 测试按需插入
  doubleLinkedList.addByOrder(new HeroNode(0, "Kobe", "BlackMamba"));
  doubleLinkedList.addByOrder(new HeroNode(4, "Heygo", "Heygogo"));
  doubleLinkedList.addByOrder(new HeroNode(6, "Oneby", "Onebyone"));
  System.out.println("按顺序插入后的情况");
  doubleLinkedList.list();
  // 修改
  HeroNode newHeroNode = new HeroNode(5, "公孙胜", "入云龙");
  doubleLinkedList.update(newHeroNode);
  System.out.println("修改后的链表情况");
  doubleLinkedList.list();
  // 删除
  doubleLinkedList.del(3);
  System.out.println("删除后的链表情况~~");
  doubleLinkedList.list();
 }
}
// 创建一个双向链表的类
class DoubleLinkedList {
 // 先初始化一个头节点, 头节点不要动, 不存放具体的数据
 private HeroNode head = new HeroNode(0, "", "");
 // 返回头节点
 public HeroNode getHead() {
  return head;
 }
 // 遍历双向链表的方法
 // 显示链表[遍历]
 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;
  }
 }
 // 添加一个节点到双向链表的最后.
 public void add(HeroNode heroNode) {
  // 因为head节点不能动，因此我们需要一个辅助遍历 temp
  HeroNode temp = head;
  // 遍历链表，找到最后
  while (true) {
   // 找到链表的最后
   if (temp.next == null) {//
    break;
   }
   // 如果没有找到最后, 将将temp后移
   temp = temp.next;
  }
  // 当退出while循环时，temp就指向了链表的最后
  // 形成一个双向链表
  temp.next = heroNode;
  heroNode.pre = temp;
 }
 // 第二种方式在添加英雄时，根据排名将英雄插入到指定位置
 // (如果有这个排名，则添加失败，并给出提示)
 public void addByOrder(HeroNode heroNode) {
  // 因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置
  // 目标：在 temp 的后面插入节点
  HeroNode temp = head;
  boolean flag = false; // flag标志添加的编号是否存在，默认为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 指向 temp 节点的下一个节点
    heroNode.next = temp.next;
    if(temp.next != null) {
     temp.next.pre = heroNode;
    }
    // temp 节点指向 heroNode 节点
    temp.next = heroNode;
    heroNode.pre = temp;
  }
 }
 // 修改一个节点的内容, 可以看到双向链表的节点内容修改和单向链表一样
 // 只是 节点类型改成 HeroNode2
 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 = newHeroNode.name;
   temp.nickname = newHeroNode.nickname;
  } else { // 没有找到
   System.out.printf("没有找到 编号 %d 的节点，不能修改\n", newHeroNode.no);
  }
 }
 // 从双向链表中删除一个节点,
 // 说明
 // 1 对于双向链表，我们可以直接找到要删除的这个节点
 // 2 找到后，自我删除即可
 public void del(int no) {
  // 判断当前链表是否为空
  if (head.next == null) {// 空链表
   System.out.println("链表为空，无法删除");
   return;
  }
  HeroNode temp = head.next; // 辅助变量(指针)
  boolean flag = false; // 标志是否找到待删除节点的
  while (true) {
   if (temp == null) { // 已经到链表的最后
    break;
   }
   if (temp.no == no) {
    // 找到的待删除节点的前一个节点temp
    flag = true;
    break;
   }
   temp = temp.next; // temp后移，遍历
  }
  // 判断flag
  if (flag) { // 找到
   // 可以删除
   // temp.next = temp.next.next;[单向链表]
   temp.pre.next = temp.next;
   // 这里我们的代码有问题?
   // 如果是最后一个节点，就不需要执行下面这句话，否则出现空指针
   if (temp.next != null) {
    temp.next.pre = temp.pre;
   }
  } else {
   System.out.printf("要删除的 %d 节点不存在\n", no);
  }
 }
}
// 定义HeroNode ， 每个HeroNode 对象就是一个节点
class HeroNode {
 public int no;
 public String name;
 public String nickname;
 public HeroNode next; // 指向下一个节点, 默认为null
 public HeroNode pre; // 指向前一个节点, 默认为null
 // 构造器
 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 + "]";
 }
}

4.11、总结

辅助变量 temp ，相当于一个指针，指向当前节点
如果定位至当前节点会丢失前一个节点的信息，那么我们只能定位至待操作节点的前一个节点：使用 temp.next 进行条件判断

5、单向环形链表

5.1、单向环形链表应用场景

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

5.2、单向环形链表图解

5.3、Josephu 问题

用一个不带头结点的循环链表来处理 Josephu 问题：先构成一个有 n 个结点的单循环链表，然后由 k 结点起从 1 开始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从 1 开始计数，直到最后一个结点从链表中删除算法结束。

5.4、环形链表的构建与遍历

5.4.1、Boy 节点的定义

Boy 节点就是个普普通通的单向链表节点

// 创建一个Boy类，表示一个节点
class Boy {
 private int no;// 编号
 private Boy next; // 指向下一个节点,默认null
 public Boy(int no) {
  this.no = no;
 }
 public int getNo() {
  return no;
 }
 public void setNo(int no) {
  this.no = no;
 }
 public Boy getNext() {
  return next;
 }
 public void setNext(Boy next) {
  this.next = next;
 }
}

5.4.2、单向循环链表的定义

first 节点为单向循环链表的首节点，是真实存放数据的节点，不是头结点

// 创建一个环形的单向链表
class CircleSingleLinkedList {
 // 创建一个first节点,当前没有编号
 private Boy first = null;
    // ...

5.4.3、构建单向循环链表

1、代码思路

长度为 1 的情况：

新创建的 boy 节点即是首节点：first = boy;
自封闭（自己构成环形链表）：first.setNext(first);
此时 first 节点既是首节点，也是尾节点，辅助指针也指向 first ：curBoy = first;

长度不为 1 的情况：

将 boy 节点添加至环形链表的最后：curBoy.setNext(boy); ，curBoy 节点永远是环形链表的尾节点
构成环形链表（最）：boy.setNext(first)；
辅助指针后移，指向环形链表的尾节点：curBoy = boy;

2、代码实现

// 添加小孩节点，构建成一个环形的链表
public void addBoy(int nums) {
    // nums 做一个数据校验
    if (nums < 1) {
        System.out.println("nums的值不正确");
        return;
    }
    Boy curBoy = null; // 辅助指针，帮助构建环形链表
    // 使用for来创建我们的环形链表
    for (int i = 1; i <= nums; i++) {
        // 根据编号，创建小孩节点
        Boy boy = new Boy(i);
        // 如果是第一个小孩
        if (i == 1) {
            first = boy; // 初始化 first 节点
            first.setNext(first); // 构成环
            curBoy = first; // 让curBoy指向第一个小孩
        } else {
            curBoy.setNext(boy); // 将 boy 节点加到链表尾部
            boy.setNext(first); // 构成环
            curBoy = boy; // curBoy 指针后移
        }
    }
}

5.4.4、遍历单向循环链表

1、代码思路

定义辅助变量 curBoy ，相当于一个指针，指向当前节点
何时退出 while 循环？当 curBoy 已经指向环形链表的尾节点：curBoy.getNext() == first

2、代码实现

// 遍历当前的环形链表
public void showBoy() {
    // 判断链表是否为空
    if (first == null) {
        System.out.println("没有任何小孩~~");
        return;
    }
    // 因为first不能动，因此我们仍然使用一个辅助指针完成遍历
    Boy curBoy = first;
    while (true) {
        System.out.printf("小孩的编号 %d \n", curBoy.getNo());
        if (curBoy.getNext() == first) {// 说明已经遍历完毕
            break;
        }
        curBoy = curBoy.getNext(); // curBoy后移
    }
}

5.5、解决 Josephu 问题

5.5.1、代码思路

辅助变量 helper ：helper 永都指向环形链表的尾节点，环形链表的尾节点永远都指向首节点，可得出：helper.getNext() == first
如何将 helper 定位至环形链表的尾节点？

初始化时，让 helper = first ，此时 helper 指向环形链表的首节点

while 循环终止条件？helper.getNext() == first ：此时 helper 已经移动至环形链表的尾节点

如何定位至第 startNo 个节点？如果想要定位至第 2 个节点，那么则需要让 first 和 helper 都移动 1 步，所以让 first 和 helper 都移动 (startNo - 1)步即可
如何数 nums 下？让 first 和 helper 都移动 (nums - 1)步即可
如何实现出圈？

我们需要将 first 指向的节点出圈，first 前一个节点的地址在 helper 中存着（环形链表）

先让 first 后移一步：first = first.getNext;

出圈：helper.setNext(first); ，原来的 first 节点由于没有任何引用，便会被垃圾回收机制回收

while 循环终止条件？圈中只剩一人：helper == first

5.5.2、代码实现

// 根据用户的输入，计算出小孩出圈的顺序
/**
 * 
 * @param startNo  表示从第几个小孩开始数数
 * @param countNum 表示数几下
 * @param nums     表示最初有多少小孩在圈中
 */
public void countBoy(int startNo, int countNum, int nums) {
 // 先对数据进行校验
 if (first == null || startNo < 1 || startNo > nums) {
  System.out.println("参数输入有误， 请重新输入");
  return;
 }
 // 创建要给辅助指针,帮助完成小孩出圈
 Boy helper = first;
 // 需求创建一个辅助指针(变量) helper , 事先应该指向环形链表的最后这个节点
 while (true) {
  if (helper.getNext() == first) { // 说明helper指向最后小孩节点
   break;
  }
  helper = helper.getNext();
 }
 // 小孩报数前，先让 first 和 helper 移动 k - 1次
 for (int j = 0; j < startNo - 1; j++) {
  first = first.getNext();
  helper = helper.getNext();
 }
 // 当小孩报数时，让first 和 helper 指针同时 的移动 m - 1 次, 然后出圈
 // 这里是一个循环操作，知道圈中只有一个节点
 while (true) {
  if (helper == first) { // 说明圈中只有一个节点
   break;
  }
  // 让 first 和 helper 指针同时 的移动 countNum - 1
  for (int j = 0; j < countNum - 1; 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());
}

5.6、Josephu 问题测试

5.6.1、测试代码

public static void main(String[] args) {
    // 测试一把看看构建环形链表，和遍历是否ok
    CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
    circleSingleLinkedList.addBoy(5);// 加入5个小孩节点
    circleSingleLinkedList.showBoy();
    // 测试一把小孩出圈是否正确
    circleSingleLinkedList.countBoy(1, 2, 3); // 2->4->1->5->3
}

5.6.2、程序运行结果

小孩的编号 1 
小孩的编号 2 
小孩的编号 3 
小孩的编号 4 
小孩的编号 5 
小孩2出圈
小孩4出圈
小孩1出圈
小孩5出圈
最后留在圈中的小孩编号3

5.7、Josephu 问题所有代码

public class Josepfu {
 public static void main(String[] args) {
  // 测试一把看看构建环形链表，和遍历是否ok
  CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
  circleSingleLinkedList.addBoy(5);// 加入5个小孩节点
  circleSingleLinkedList.showBoy();
  // 测试一把小孩出圈是否正确
  circleSingleLinkedList.countBoy(1, 2, 3); // 2->4->1->5->3
 }
}
// 创建一个环形的单向链表
class CircleSingleLinkedList {
 // 创建一个first节点,当前没有编号
 private Boy first = null;
 // 添加小孩节点，构建成一个环形的链表
 public void addBoy(int nums) {
  // nums 做一个数据校验
  if (nums < 1) {
   System.out.println("nums的值不正确");
   return;
  }
  Boy curBoy = null; // 辅助指针，帮助构建环形链表
  // 使用for来创建我们的环形链表
  for (int i = 1; i <= nums; i++) {
   // 根据编号，创建小孩节点
   Boy boy = new Boy(i);
   // 如果是第一个小孩
   if (i == 1) {
    first = boy; // 初始化 first 节点
    first.setNext(first); // 构成环
    curBoy = first; // 让curBoy指向第一个小孩
   } else {
    curBoy.setNext(boy); // 将 boy 节点加到链表尾部
    boy.setNext(first); // 构成环
    curBoy = boy; // curBoy 指针后移
   }
  }
 }
 // 遍历当前的环形链表
 public void showBoy() {
  // 判断链表是否为空
  if (first == null) {
   System.out.println("没有任何小孩~~");
   return;
  }
  // 因为first不能动，因此我们仍然使用一个辅助指针完成遍历
  Boy curBoy = first;
  while (true) {
   System.out.printf("小孩的编号 %d \n", curBoy.getNo());
   if (curBoy.getNext() == first) {// 说明已经遍历完毕
    break;
   }
   curBoy = curBoy.getNext(); // curBoy后移
  }
 }
 // 根据用户的输入，计算出小孩出圈的顺序
 /**
  * 
  * @param startNo  表示从第几个小孩开始数数
  * @param countNum 表示数几下
  * @param nums     表示最初有多少小孩在圈中
  */
 public void countBoy(int startNo, int countNum, int nums) {
  // 先对数据进行校验
  if (first == null || startNo < 1 || startNo > nums) {
   System.out.println("参数输入有误， 请重新输入");
   return;
  }
  // 创建要给辅助指针,帮助完成小孩出圈
  Boy helper = first;
  // 需求创建一个辅助指针(变量) helper , 事先应该指向环形链表的最后这个节点
  while (true) {
   if (helper.getNext() == first) { // 说明helper指向最后小孩节点
    break;
   }
   helper = helper.getNext();
  }
  // 小孩报数前，先让 first 和 helper 移动 k - 1次
  for (int j = 0; j < startNo - 1; j++) {
   first = first.getNext();
   helper = helper.getNext();
  }
  // 当小孩报数时，让first 和 helper 指针同时 的移动 m - 1 次, 然后出圈
  // 这里是一个循环操作，知道圈中只有一个节点
  while (true) {
   if (helper == first) { // 说明圈中只有一个节点
    break;
   }
   // 让 first 和 helper 指针同时 的移动 countNum - 1
   for (int j = 0; j < countNum - 1; 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类，表示一个节点
class Boy {
 private int no;// 编号
 private Boy next; // 指向下一个节点,默认null
 public Boy(int no) {
  this.no = no;
 }
 public int getNo() {
  return no;
 }
 public void setNo(int no) {
  this.no = no;
 }
 public Boy getNext() {
  return next;
 }
 public void setNext(Boy next) {
  this.next = next;
 }
}

5.8、总结

操作单向链表：对于插入、删除操作，只能定位至待操作节点的前一个节点，如果定位至当前节点，那么其上一个节点的信息便会丢失

第 4 章链表（三）

4.9、双向链表测试

4.9.1、测试代码

4.9.2、程序运行结果

4.10、双向链表所有代码

4.11、总结

5、单向环形链表

5.1、单向环形链表应用场景

5.2、单向环形链表图解

5.3、Josephu 问题

5.4、环形链表的构建与遍历

5.4.1、Boy 节点的定义

5.4.2、单向循环链表的定义

5.4.3、构建单向循环链表

1、代码思路

2、代码实现

5.4.4、遍历单向循环链表

1、代码思路

2、代码实现

5.5、解决 Josephu 问题

5.5.1、代码思路

5.5.2、代码实现

5.6、Josephu 问题测试

5.6.1、测试代码

5.6.2、程序运行结果

5.7、Josephu 问题所有代码

5.8、总结

热门文章

最新文章

相关电子书

第 4 章 链表（三）

4.9、双向链表测试

4.9.1、测试代码

4.9.2、程序运行结果

4.10、双向链表所有代码

4.11、总结

5、单向环形链表

5.1、单向环形链表应用场景

5.2、单向环形链表图解

5.3、Josephu 问题

5.4、环形链表的构建与遍历

5.4.1、Boy 节点的定义

5.4.2、单向循环链表的定义

5.4.3、构建单向循环链表

1、代码思路

2、代码实现

5.4.4、遍历单向循环链表

1、代码思路

2、代码实现

5.5、解决 Josephu 问题

5.5.1、代码思路

5.5.2、代码实现

5.6、Josephu 问题测试

5.6.1、测试代码

5.6.2、程序运行结果

5.7、Josephu 问题所有代码

5.8、总结

热门文章

最新文章

相关电子书

第 4 章链表（三）