尚硅谷图解Java数据结构和算法.pdf
图解.xlsx

1、单向链表

链表的介绍

链表在内存中的存储
二、链表 - 图1
特点

  • 链表是以节点的方式来存储,是链式存储
  • 每个节点包含 data 域 和 next 域。next域用来指向下一个节点
  • 链表的各个节点不一定是连续存储的
  • 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

带头结点的逻辑示意图
二、链表 - 图2

实现思路

创建（添加）

  • 先创建一个Head头节点，表示单链表的头

  • 后面我们每添加一个节点，就放在链表的最后

    遍历

  • 通过一个辅助变量，来遍历整个链表

image.png

有序插入

  • 先遍历链表，找到应该插入的位置
  • 要插入的节点的next指向插入位置的后一个节点
  • 插入位置的前一个节点的next指向要插入节点
    • 插入前要判断是否在队尾插入

image.png

根据某个属性节点修改值

  • 先遍历节点，找到修改的位置

    • 如果未找到修改节点，则不修改

      删除某个节点

  • 先遍历节点，找到要删除节点的前一个节点

  • 进行删除操作

image.png
代码

  1. package com.luyi.DataStructures.linkedlist;
  3. /**
  4.  * @author 卢意
  5.  * @create 2020-12-01 21:10
  6.  */
  7. public class SingleLinkedListDemo {
  9.     public static void main(String[] args) {
  10.         // 先创建节点
  11.         HeroNode heroNode1 = new HeroNode(1, "宋江", "及时雨");
  12.         HeroNode heroNode2 = new HeroNode(2, "卢俊义", "玉麒麟");
  13.         HeroNode heroNode3 = new HeroNode(3, "吴用", "智多星");
  14.         HeroNode heroNode4 = new HeroNode(4, "林冲", "豹子头");
  16.         // 创建一个链表
  17.         SingleLinkedList singleLinkedList = new SingleLinkedList();
  18.         // 加入
  19. //        singleLinkedList.add(heroNode1);
  20. //        singleLinkedList.add(heroNode2);
  21. //        singleLinkedList.add(heroNode3);
  22. //        singleLinkedList.add(heroNode4);
  23.         /**
  24.          * 结果:
  25.          * HeroNode{no=1, name='宋江', nickName='及时雨'}
  26.          * HeroNode{no=2, name='卢俊义', nickName='玉麒麟'}
  27.          * HeroNode{no=3, name='吴用', nickName='智多星'}
  28.          * HeroNode{no=4, name='林冲', nickName='豹子头'}
  29.          */
  30.         // 加入按照编号的顺序
  31.         singleLinkedList.addByOrder(heroNode1);
  32.         singleLinkedList.addByOrder(heroNode4);
  33.         singleLinkedList.addByOrder(heroNode2);
  34.         singleLinkedList.addByOrder(heroNode3);
  35.         singleLinkedList.addByOrder(heroNode3);
  36.         /**
  37.          * 结果
  38.          * 准备插入的英雄的编号[3]已存在,不能加入!
  39.          * HeroNode{no=1, name='宋江', nickName='及时雨'}
  40.          * HeroNode{no=2, name='卢俊义', nickName='玉麒麟'}
  41.          * HeroNode{no=3, name='吴用', nickName='智多星'}
  42.          * HeroNode{no=4, name='林冲', nickName='豹子头'}
  43.          */
  44.         // 显示
  45.         singleLinkedList.list();
  47.         // 测试 修改节点
  48.         HeroNode newHeroNode = new HeroNode(2, "小卢", "小麒麟");
  49.         HeroNode newHeroNode1 = new HeroNode(5, "小卢", "小麒麟");
  50.         singleLinkedList.update(newHeroNode );
  51.         singleLinkedList.update(newHeroNode1 );
  52.         /**
  53.          * 结果
  54.          * HeroNode{no=1, name='宋江', nickName='及时雨'}
  55.          * HeroNode{no=2, name='卢俊义', nickName='玉麒麟'}
  56.          * HeroNode{no=3, name='吴用', nickName='智多星'}
  57.          * HeroNode{no=4, name='林冲', nickName='豹子头'}
  58.          * 没有找到编号为[5]的节点
  59.          * 修改后的链表情况
  60.          *
  61.          * HeroNode{no=1, name='宋江', nickName='及时雨'}
  62.          * HeroNode{no=2, name='小卢', nickName='小麒麟'}
  63.          * HeroNode{no=3, name='吴用', nickName='智多星'}
  64.          * HeroNode{no=4, name='林冲', nickName='豹子头'}
  65.          */
  66.         // 修改后的显示
  67.         System.out.println("修改后的链表情况");
  68.         System.out.println();
  69.         singleLinkedList.list();
  71.         System.out.println("删除一个节点");
  72.         singleLinkedList.delete(1);
  73.         singleLinkedList.delete(2);
  74.         singleLinkedList.delete(3);
  75.         singleLinkedList.delete(4);
  76.         singleLinkedList.list();
  77.         /**
  78.          * 结果
  79.          * 删除一个节点
  80.          * 链表为空
  81.          */
  83.     }
  84. }
  85. // 定义一个单向链表 管理我们的英雄
  86. class SingleLinkedList {
  87.     // 初始化一下头结点  头结点不要动 不存放具体的数据
  88.     private HeroNode head =new HeroNode(0,null,null);
  90.     // 添加方法到单向链表
  91.     // 思路 当不考虑编号顺序时
  92.     // 1. 找到当前链表的最后节点
  93.     // 2. 将最后的这个节点的next 指向 新节点
  94.     public void add(HeroNode heroNode){
  95.         // 因为 head节点不能动 我们需要一个辅助节点 temp
  96.         HeroNode temp = head;
  97.         // 遍历链表找到最后
  98.         while (true){
  99.             // 找到链表的最后
  100.             if(temp.next == null){
  101.                 break;
  102.             }
  103.             // 如果没有找到 就将temp后移
  104.             temp = temp.next;
  105.         }
  106.         // 当退出white循环时, temp 就指向了链表的最后
  107.         temp.next = heroNode;
  108.     }
  110.     // 第二种添加英雄的方式, 根据排名将英雄插入到指定位置
  111.     // 如果有这个排名, 则添加失败 并给出提示
  112.     public void addByOrder(HeroNode heroNode){
  113.         // 因为头结点不能动 因此我们任然通过一个辅助指针(变量) 来帮助找到添加的位置
  114.         // 因为是单列表 temp是要找到添加节点的前一个节点, 否则插入不了
  115.         HeroNode temp = head;
  116.         boolean flag = false; // 标志添加的编号是否存在 默认为false
  117.         while(true) {
  118.             if(temp.next == null) { // 说明已经到了链表的最后了
  119.                 break;
  120.             }
  121.             if (temp.next.no > heroNode.no) { // 位置找到了 在temp和temp.next之间插入该节点
  122.                 break;
  123.             }else if (temp.next.no == heroNode.no) { // 说明希望添加的heroNode的编号已经存在 不能添加
  124.                 flag = true; // 说明编号存在
  125.                 break;
  126.             }
  127.             temp = temp.next;
  128.         }
  129.         // 判断 flag的值
  130.         if (flag){ // 不能添加 说明编号存在
  131.             System.out.println("准备插入的英雄的编号["+heroNode.no+"]已存在,不能加入!");
  132.         }else {
  133.             // 插入链表中 temp 中
  134.             heroNode.next = temp.next;
  135.             temp.next = heroNode;
  136.         }
  137.     }
  139.     // 显示链表 遍历
  140.     public void list(){
  141.         // 判断链表为空
  142.         if(head.next == null){
  143.             System.out.println("链表为空");
  144.             return;
  145.         }
  146.         // 因为头结点不能动我们需要一个复制节点 temp
  147.         HeroNode temp = head.next;
  148.         while(true){
  149.             // 输出这个节点的信息
  150.             System.out.println(temp);
  151.             if(temp.next == null){
  152.                 break;
  153.             }
  154.             // 将temp 后移 不然是一个死循环
  155.             temp = temp.next;
  156.         }
  158.     }
  159.     // 修改节点的信息 根据编号来修改 编号不能修改
  160.     public void update (HeroNode newHeroNode){
  161.         if(head.next == null){
  162.             System.out.println("链表为空");
  163.             return;
  164.         }
  165.         // 找到需要修改的节点 很具no查询
  166.         HeroNode temp = head.next;
  167.         boolean flag = false; // 表示是否找到该节点
  168.         while (true) {
  169.             if (temp == null) {
  170.                 break; // 表示链表已经遍历结束了 (不是最后一个节点 已经出到外面去了)
  171.             }
  172.             if (temp.no == newHeroNode.no){
  173.                 // 找到要修改的节点
  174.                 flag = true;
  175.                 break;
  176.             }
  177.             temp = temp.next;
  178.         }
  179.         // 根据flag判断是否找到要修改的节点
  180.         if(!flag){
  181.             System.out.println("没有找到编号为["+newHeroNode.no+ "]的节点");
  182.         }else {
  183.             temp.name = newHeroNode.name;
  184.             temp.nickName = newHeroNode.nickName;
  185.         }
  187.     }
  189.     // 删除节点
  190.     //思路 1.head节点不能动 因此我们需要一个temp辅助节点找到删除节点的前一个节点
  191.     //    2. 我们需要以temp节点的后一个节点的标号进行比较
  192.     public void delete(int no){
  193.         HeroNode temp = head;
  194.         boolean flag = false; // 标志是否找到待删除节点的
  195.         while (true) {
  196.             if (temp.next == null){ // temp已经到链表的最后
  197.                 break;
  198.             }
  199.             if (temp.next.no == no){
  200.                 // 找到了待删除节点的前一个节点
  201.                 flag = true;
  202.                 break;
  203.             }
  204.             temp = temp.next;
  205.         }
  206.         if (flag){
  207.             // 可以删除
  208.             HeroNode t = temp.next;
  209.             temp.next = t.next;
  210.             t.next = null;
  211.         }else {
  212.             System.out.println("没有找到该no=["+no+"]节点,无法删除");
  213.         }
  216.     }
  218. }
  220. // 定义一个HeroNode , 每个HeroNode 对象就是一个节点
  221. class HeroNode {
  222.     public int no;
  223.     public String name;
  224.     public String nickName;
  225.     public HeroNode next; // 指向下一个节点
  227.     // 构造器
  228.     public HeroNode(int hNo, String hName, String hNickName){
  229.         this.no = hNo;
  230.         this.name = hName;
  231.         this.nickName = hNickName;
  232.     }
  234.     // 为了显示方便 重写toString方法
  237.     @Override
  238.     public String toString() {
  239.         return "HeroNode{" +
  240.                 "no=" + no +
  241.                 ", name='" + name + '\'' +
  242.                 ", nickName='" + nickName + '\'' +
  243.                 '}';
  244.     }
  245. }

单链表面试题


image.png

求单链表的有效节点的个数

  1.    /**
  2.      *
  3.      * @param head  链表的头节点
  4.      * @return 返回的是有效节点个数
  5.      */
  6.     public Integer getLength(HeroNode head){
  7.         if (head.next == null){
  8.             // 空链表
  9.             return 0;
  10.         }
  11.         int length = 0;
  12.         // 定义一个辅助变量
  13.         HeroNode cur =head.next;
  14.         while (cur != null) {
  15.             length++;
  16.             cur = cur.next;
  17.         }
  18.         return length;
  19.     }

求单链表的倒数第K个节点

  1.     // 求单链表的倒数第K个节点
  2.     // 思路 1 编写一个方法接收head节点 接收index(倒数第index节点)
  3.     //     2 先把链表变历 求出长度 length  去找到length-index的节点
  4.     public HeroNode findNodeStartLast(HeroNode head ,int index){
  5.         // 如果链表为空 返回null
  6.         if (head.next == null){
  7.             return null;
  8.         }
  9.         // 变历得到链表的长度
  10.         int length = this.getLength(head);
  11.         // 再一次遍历  返回 第length - index
  12.         // 先做一个index的校验
  13.         if(index <= 0 || index > length){
  14.             return null;
  15.         }
  16.         // 定义一个辅助节点
  17.         HeroNode temp = head.next;
  18.         for(int i = 0 ;i < length-index ;i++ ){
  19.             temp = temp.next;
  20.         }
  21.         return  temp;
  22.     }

单链表的反转

image.png

  1.     // 单链表的反转
  2.     public HeroNode reverseNode(HeroNode head){
  3.         //如果当前链表为空，或者只有一个节点，无需反转，直接返回
  4.         if(head.next == null || head.next.next == null) {
  5.             return head.next;
  6.         }
  7.         //定义一个辅助的指针(变量)，帮助我们遍历原来的链表
  8.         HeroNode cur = head.next;
  9.         HeroNode next = null;// 指向当前节点[cur]的下一个节点
  10.         HeroNode reverseHead = new HeroNode(0, "", "");
  11.         //遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端
  12.         //动脑筋
  13.         while(cur != null) { 
  14.             next = cur.next;//先暂时保存当前节点的下一个节点，因为后面需要使用
  15.             cur.next = reverseHead.next;//将cur的下一个节点指向新的链表的最前端
  16.             reverseHead.next = cur; //将cur 连接到新的链表上
  17.             cur = next;//让cur后移
  18.         }
  19.         //将head.next 指向 reverseHead.next , 实现单链表的反转
  20.         head.next = reverseHead.next;
  21.         return reverseHead.next;
  22.     }

二、链表 - 图8

  • 创建一个新的头结点，作为新链表的头
  • 从头遍历旧链表，将遍历到的节点插入新链表的头结点之后
  • 注意需要用到两个暂存节点
    • 一个用来保存正在遍历的节点
    • 一个用来保存正在遍历节点的下一个节点

二、链表 - 图9
二、链表 - 图10
二、链表 - 图11
二、链表 - 图12
二、链表 - 图13

逆序打印

  • 遍历链表，将遍历到的节点入栈
  • 遍历完后，进行出栈操作，同时打印出栈元素

image.png

  1.     //可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果
  2.     public static void reversePrint(HeroNode head) {
  3.         if(head.next == null) {
  4.             return;//空链表，不能打印
  5.         }
  6.         //创建要给一个栈，将各个节点压入栈
  7.         Stack<HeroNode> stack = new Stack<HeroNode>();
  8.         HeroNode cur = head.next;
  9.         //将链表的所有节点压入栈
  10.         while(cur != null) {
  11.             stack.push(cur);
  12.             cur = cur.next; //cur后移，这样就可以压入下一个节点
  13.         }
  14.         //将栈中的节点进行打印,pop 出栈
  15.         while (stack.size() > 0) {
  16.             System.out.println(stack.pop()); //stack的特点是先进后出
  17.         }
  18.     }

2、双向链表

单链表的问题

image.png

双向链表

二、链表 - 图16

实现思路

遍历

  • 和单向链表的遍历相同，需要一个辅助节点来保存当前正在遍历的节点

添加

  • 双向链表多出了一个frnot，所以在添加时，要让新增节点的front指向链表尾节点

修改

  • 和单向链表的修改相同

删除

  • 使用temp来保存要删除的节点
  • temp.pre.next指向temp.next
  • temp.next指向temp.pre

image.png
代码

  1. package com.atguigu.linkedlist;
  3. public class DoubleLinkedListDemo {
  5.     public static void main(String[] args) {
  6.         // 测试
  7.         System.out.println("双向链表的测试");
  8.         // 先创建节点
  9.         HeroNode2 hero1 = new HeroNode2(1, "宋江", "及时雨");
  10.         HeroNode2 hero2 = new HeroNode2(2, "卢俊义", "玉麒麟");
  11.         HeroNode2 hero3 = new HeroNode2(3, "吴用", "智多星");
  12.         HeroNode2 hero4 = new HeroNode2(4, "林冲", "豹子头");
  13.         // 创建一个双向链表
  14.         DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
  15.         doubleLinkedList.add(hero1);
  16.         doubleLinkedList.add(hero2);
  17.         doubleLinkedList.add(hero3);
  18.         doubleLinkedList.add(hero4);
  20.         doubleLinkedList.list();
  22.         // 修改
  23.         HeroNode2 newHeroNode = new HeroNode2(4, "公孙胜", "入云龙");
  24.         doubleLinkedList.update(newHeroNode);
  25.         System.out.println("修改后的链表情况");
  26.         doubleLinkedList.list();
  28.         // 删除
  29.         doubleLinkedList.del(3);
  30.         System.out.println("删除后的链表情况~~");
  31.         doubleLinkedList.list();
  35.     }
  37. }
  39. // 创建一个双向链表的类
  40. class DoubleLinkedList {
  42.     // 先初始化一个头节点, 头节点不要动, 不存放具体的数据
  43.     private HeroNode2 head = new HeroNode2(0, "", "");
  45.     // 返回头节点
  46.     public HeroNode2 getHead() {
  47.         return head;
  48.     }
  50.     // 遍历双向链表的方法
  51.     // 显示链表[遍历]
  52.     public void list() {
  53.         // 判断链表是否为空
  54.         if (head.next == null) {
  55.             System.out.println("链表为空");
  56.             return;
  57.         }
  58.         // 因为头节点，不能动，因此我们需要一个辅助变量来遍历
  59.         HeroNode2 temp = head.next;
  60.         while (true) {
  61.             // 判断是否到链表最后
  62.             if (temp == null) {
  63.                 break;
  64.             }
  65.             // 输出节点的信息
  66.             System.out.println(temp);
  67.             // 将temp后移， 一定小心
  68.             temp = temp.next;
  69.         }
  70.     }
  72.     // 添加一个节点到双向链表的最后.
  73.     public void add(HeroNode2 heroNode) {
  75.         // 因为head节点不能动，因此我们需要一个辅助遍历 temp
  76.         HeroNode2 temp = head;
  77.         // 遍历链表，找到最后
  78.         while (true) {
  79.             // 找到链表的最后
  80.             if (temp.next == null) {//
  81.                 break;
  82.             }
  83.             // 如果没有找到最后, 将将temp后移
  84.             temp = temp.next;
  85.         }
  86.         // 当退出while循环时，temp就指向了链表的最后
  87.         // 形成一个双向链表
  88.         temp.next = heroNode;
  89.         heroNode.pre = temp;
  90.     }
  92.     //第二种方式在添加英雄时，根据排名将英雄插入到指定位置（按顺序添加）
  93.     //(如果有这个排名，则添加失败，并给出提示)
  94.     public void addByOrder(HeroNode2 heroNode){
  95.         //因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置
  96.         HeroNode2 temp = head;
  97.         boolean flag = false;
  98.         while (true){
  99.             if (temp.next == null){//说明temp已经在链表的最后
  100.                 break;
  101.             }
  102.             if (temp.next.no > heroNode.no){//位置找到，就在temp的后面插入
  103.                 break;
  104.             }else if (temp.next.no == heroNode.no){//说明希望添加的heroNode的编号已然存在
  105.                 flag = true; //说明编号存在
  106.                 break;
  107.             }
  108.             temp = temp.next; //后移，遍历当前链表
  109.         }
  110.         //判断flag 的值
  111.         if (flag){//不能添加，说明编号存在
  112.             System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\n", heroNode.no);
  113.         }else {
  114.             //插入到链表中, temp的后面
  115.             heroNode.next = temp.next;
  116.             temp.next = heroNode;
  117.             heroNode.pre = temp;
  118.         }
  119.     }
  121.     // 修改一个节点的内容, 可以看到双向链表的节点内容修改和单向链表一样
  122.     // 只是 节点类型改成 HeroNode2
  123.     public void update(HeroNode2 newHeroNode) {
  124.         // 判断是否空
  125.         if (head.next == null) {
  126.             System.out.println("链表为空~");
  127.             return;
  128.         }
  129.         // 找到需要修改的节点, 根据no编号
  130.         // 定义一个辅助变量
  131.         HeroNode2 temp = head.next;
  132.         boolean flag = false; // 表示是否找到该节点
  133.         while (true) {
  134.             if (temp == null) {
  135.                 break; // 已经遍历完链表
  136.             }
  137.             if (temp.no == newHeroNode.no) {
  138.                 // 找到
  139.                 flag = true;
  140.                 break;
  141.             }
  142.             temp = temp.next;
  143.         }
  144.         // 根据flag 判断是否找到要修改的节点
  145.         if (flag) {
  146.             temp.name = newHeroNode.name;
  147.             temp.nickname = newHeroNode.nickname;
  148.         } else { // 没有找到
  149.             System.out.printf("没有找到 编号 %d 的节点，不能修改\n", newHeroNode.no);
  150.         }
  151.     }
  153.     // 从双向链表中删除一个节点,
  154.     // 说明
  155.     // 1 对于双向链表，我们可以直接找到要删除的这个节点
  156.     // 2 找到后，自我删除即可
  157.     public void del(int no) {
  159.         // 判断当前链表是否为空
  160.         if (head.next == null) {// 空链表
  161.             System.out.println("链表为空，无法删除");
  162.             return;
  163.         }
  165.         HeroNode2 temp = head.next; // 辅助变量(指针)
  166.         boolean flag = false; // 标志是否找到待删除节点的
  167.         while (true) {
  168.             if (temp == null) { // 已经到链表的最后
  169.                 break;
  170.             }
  171.             if (temp.no == no) {
  172.                 // 找到的待删除节点的前一个节点temp
  173.                 flag = true;
  174.                 break;
  175.             }
  176.             temp = temp.next; // temp后移，遍历
  177.         }
  178.         // 判断flag
  179.         if (flag) { // 找到
  180.             // 可以删除
  181.             // temp.next = temp.next.next;[单向链表]
  182.             temp.pre.next = temp.next;
  183.             // 这里我们的代码有问题?
  184.             // 如果是最后一个节点，就不需要执行下面这句话，否则出现空指针
  185.             if (temp.next != null) {
  186.                 temp.next.pre = temp.pre;
  187.             }
  188.         } else {
  189.             System.out.printf("要删除的 %d 节点不存在\n", no);
  190.         }
  191.     }
  193. }
  195. // 定义HeroNode2 ， 每个HeroNode 对象就是一个节点
  196. class HeroNode2 {
  197.     public int no;
  198.     public String name;
  199.     public String nickname;
  200.     public HeroNode2 next; // 指向下一个节点, 默认为null
  201.     public HeroNode2 pre; // 指向前一个节点, 默认为null
  202.     // 构造器
  204.     public HeroNode2(int no, String name, String nickname) {
  205.         this.no = no;
  206.         this.name = name;
  207.         this.nickname = nickname;
  208.     }
  210.     // 为了显示方法，我们重新toString
  211.     @Override
  212.     public String toString() {
  213.         return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
  214.     }
  215. }

3、单向环形链表

约瑟夫问题

image.png

单向环形链表

单链表的尾节点指向首节点，即可构成单向环形链表
二、链表 - 图19

约瑟夫环

image.png
大致思路

  • 遍历链表找到指定位置的节点
  • 用一个front保存指定节点的前一个节点，方便删除
  • 当count==time时，删除此时正在遍历的节点，放入数组中，并将count的值初始化
  • 用一个变量loopTime记录已经出圈了几个人，当其等于length时则是最后一个节点，直接放入数组并返回数即可

image.png
代码

  1. package com.atguigu.linkedlist;
  3. public class Josepfu {
  5.     public static void main(String[] args) {
  6.         // 测试一把看看构建环形链表，和遍历是否ok
  7.         CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
  8.         circleSingleLinkedList.addBoy(125);// 加入5个小孩节点
  9.         circleSingleLinkedList.showBoy();
  11.         //测试一把小孩出圈是否正确
  12.         circleSingleLinkedList.countBoy(10, 20, 125); // 2->4->1->5->3
  13.         //String str = "7*2*2-5+1-5+3-3";
  14.     }
  16. }
  18. // 创建一个环形的单向链表
  19. class CircleSingleLinkedList {
  20.     // 创建一个first节点,当前没有编号
  21.     private Boy first = null;
  23.     // 添加小孩节点，构建成一个环形的链表
  24.     public void addBoy(int nums) {
  25.         // nums 做一个数据校验
  26.         if (nums < 1) {
  27.             System.out.println("nums的值不正确");
  28.             return;
  29.         }
  30.         Boy curBoy = null; // 辅助指针，帮助构建环形链表
  31.         // 使用for来创建我们的环形链表
  32.         for (int i = 1; i <= nums; i++) {
  33.             // 根据编号，创建小孩节点
  34.             Boy boy = new Boy(i);
  35.             // 如果是第一个小孩
  36.             if (i == 1) {
  37.                 first = boy;
  38.                 first.setNext(first); // 构成环
  39.                 curBoy = first; // 让curBoy指向第一个小孩
  40.             } else {
  41.                 curBoy.setNext(boy);//
  42.                 boy.setNext(first);//
  43.                 curBoy = boy;
  44.             }
  45.         }
  46.     }
  48.     // 遍历当前的环形链表
  49.     public void showBoy() {
  50.         // 判断链表是否为空
  51.         if (first == null) {
  52.             System.out.println("没有任何小孩~~");
  53.             return;
  54.         }
  55.         // 因为first不能动，因此我们仍然使用一个辅助指针完成遍历
  56.         Boy curBoy = first;
  57.         while (true) {
  58.             System.out.printf("小孩的编号 %d \n", curBoy.getNo());
  59.             if (curBoy.getNext() == first) {// 说明已经遍历完毕
  60.                 break;
  61.             }
  62.             curBoy = curBoy.getNext(); // curBoy后移
  63.         }
  64.     }
  66.     // 根据用户的输入，计算出小孩出圈的顺序
  67.     /**
  68.      * 
  69.      * @param startNo
  70.      *            表示从第几个小孩开始数数
  71.      * @param countNum
  72.      *            表示数几下
  73.      * @param nums
  74.      *            表示最初有多少小孩在圈中
  75.      */
  76.     public void countBoy(int startNo, int countNum, int nums) {
  77.         // 先对数据进行校验
  78.         if (first == null || startNo < 1 || startNo > nums) {
  79.             System.out.println("参数输入有误， 请重新输入");
  80.             return;
  81.         }
  82.         // 创建要给辅助指针,帮助完成小孩出圈
  83.         Boy helper = first;
  84.         // 需求创建一个辅助指针(变量) helper , 事先应该指向环形链表的最后这个节点
  85.         while (true) {
  86.             if (helper.getNext() == first) { // 说明helper指向最后小孩节点
  87.                 break;
  88.             }
  89.             helper = helper.getNext();
  90.         }
  91.         //小孩报数前，先让 first 和  helper 移动 k - 1次
  92.         for(int j = 0; j < startNo - 1; j++) {
  93.             first = first.getNext();
  94.             helper = helper.getNext();
  95.         }
  96.         //当小孩报数时，让first 和 helper 指针同时 的移动  m  - 1 次, 然后出圈
  97.         //这里是一个循环操作，知道圈中只有一个节点
  98.         while(true) {
  99.             if(helper == first) { //说明圈中只有一个节点
  100.                 break;
  101.             }
  102.             //让 first 和 helper 指针同时 的移动 countNum - 1
  103.             for(int j = 0; j < countNum - 1; j++) {
  104.                 first = first.getNext();
  105.                 helper = helper.getNext();
  106.             }
  107.             //这时first指向的节点，就是要出圈的小孩节点
  108.             System.out.printf("小孩%d出圈\n", first.getNo());
  109.             //这时将first指向的小孩节点出圈
  110.             first = first.getNext();
  111.             helper.setNext(first); //
  113.         }
  114.         System.out.printf("最后留在圈中的小孩编号%d \n", first.getNo());
  116.     }
  117. }
  119. // 创建一个Boy类，表示一个节点
  120. class Boy {
  121.     private int no;// 编号
  122.     private Boy next; // 指向下一个节点,默认null
  124.     public Boy(int no) {
  125.         this.no = no;
  126.     }
  128.     public int getNo() {
  129.         return no;
  130.     }
  132.     public void setNo(int no) {
  133.         this.no = no;
  134.     }
  136.     public Boy getNext() {
  137.         return next;
  138.     }
  140.     public void setNext(Boy next) {
  141.         this.next = next;
  142.     }
  143. }

4、跳跃表

1、什么是跳跃表

跳跃链表是一种随机化数据结构，基于并联的链表，其效率可比拟于二叉排序树(对于大多数操作需要O(log n)平均时间)，并且对并发算法友好。
基本上，跳跃列表是对有序的链表增加上附加的前进链接，增加是以随机化（抛硬币）的方式进行的，所以在列表中的查找可以快速的跳过部分列表(因此得名)。所有操作都以对数随机化的时间进行。

2、跳跃表原理

查询链表的时间复杂度

搜索链表中的元素时，无论链表中的元素是否有序，时间复杂度都为O(n)，如下图，搜索103需要查询9次才能找到该节点
二、链表 - 图22
但是能够提高搜索的其他数据结构，如：二叉排序树、红黑树、B树、B+树等等的实现又过于复杂。有没有一种相对简单，同时又能提搜索效率的数据结构呢，跳跃表就是这样一种数据结构。
Redis中使用跳跃表好像就是因为一是B+树的实现过于复杂，二是Redis只涉及内存读写，所以最后选择了跳跃表。

跳跃表实现——搜索

为了能够更快的查找元素，我们可以在该链表之上，再添加一个新链表，新链表中保存了部分旧链表中的节点，以加快搜索的速度。如下图所示
二、链表 - 图23
我们搜索元素时，从最上层的链表开始搜索。当找到某个节点大于目标值或其后继节点为空时，从该节点向下层链表搜寻，然后顺着该节点到下一层继续搜索。
比如我们要找103这个元素，则会经历：2->23->54->87->103
这样还是查找了5次，当我们再将链表的层数增高以后，查找的次数会明显降低，如下图所示。3次便找到了目标元素103
二、链表 - 图24
代码中实现的跳表结构如下图所示
一个节点拥有多个指针，指向不同的节点
二、链表 - 图25

跳跃表实现——插入

跳跃表的插入策略如下

  • 先找到合适的位置以便插入元素
  • 找到后，将该元素插入到最底层的链表中，并且抛掷硬币（1/2的概率）
    • 若硬币为正面，则将该元素晋升到上一层链表中，并再抛一次
    • 若硬币为反面，则插入过程结束
  • 为了避免以下情况，需要在每个链表的头部设置一个 负无穷 的元素

二、链表 - 图26
设置负无穷后，若要查找元素2，过程如下图所示
二、链表 - 图27
插入图解

  • 若我们要将45插入到跳跃表中二、链表 - 图28
  • 先找到插入位置，将45插入到合适的位置二、链表 - 图29
  • 抛掷硬币：为正，晋升二、链表 - 图30
  • 假设硬币一直为正，插入元素一路晋升，当晋升的次数超过跳跃表的层数时，需要再创建新的链表以放入晋升的插入元素。新创建的链表的头结点为负无穷二、链表 - 图31

以上便是跳跃表的插入过程