数据结构与算法

稀疏数组

二维数组创建方法

int arr[][] = new int[1][1];

第一个【】内存放有多少个一维数组

第二个【】存放一维数组的长度

arr[0][0] = 1
arr[0][1] =2
arr[0][2] =3
[输出]
[1,2,3]

二维数组的遍历

int arr[][] = new int[2][2];
for (int[] row : arr) {
    for (int data : row) {
      System.out.printf("%d\t", data);
    }
 System.out.println();
 }

棋盘案例

稀疏 sparsearray 数组，编写的五子棋程序中，有存盘退出和续上盘的功能。

分析问题:

因为该二维数组的很多值是默认值 0, 因此记录了很多没有意义的数据.->稀疏数组。

稀疏数组介绍

使用场景

当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。

我们创造的稀疏数组，

• 也是一个二维数组 他的【0】【n】会用来存放原来的二维数组的大小和长度
• 接下来的【n】【n】都会用放每一个值和他的二维数组坐标

应用实例

1. 使用稀疏数组，来保留类似前面的二维数组(棋盘、地图等等)
2. 把稀疏数组存盘，并且可以从新恢复原来的二维数组数
3. 整体思路分析

编写实例思路操作图

代码实现

/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.SarseArray
 * @className: sarseArray
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2021/12/15 16:14
 * @version: 1.0
 */
public class sarseArray {
    public static void main(String[] args) {
        /*创建原始的二维数组 11*11*/
        //0：表示没有棋子，1表示黑子，2表示白字
        int chessArr[][] = new int[11][11];
        chessArr[1][2] = 1;
        chessArr[2][3] = 2;
        chessArr[4][6] = 3;
        System.out.println("输出原始的二维数组");
        for (int[] row : chessArr) {
            for (int data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }
        //遍历二维数组所有非0 的数
        int sum = 0;
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                if (chessArr[i][j] != 0) {
                    sum++;
                }
            }
        }
        System.out.println("sum = " + sum);
        //将二维数组转化成 稀疏数组，创建对应的稀疏数组
        int sparseArr[][] = new int[sum + 1][3];
        sparseArr[0][0] = 11;
        sparseArr[0][1] = 11;
        sparseArr[0][2] = sum;
        //    完成了上述的步骤我们就拿到了 稀疏数组的第一行 就是我们存放数组大小和值的
        //接下来我们需要将二维数组的值放到 稀疏数组中
        /*
         * sparseArr[?][0] = i
         * sparseArr[?][1] = j
         * sparseArr[?][2] = chessArr[i][j];
         * 我们通过这种方式将 二维数组的坐标和值存到稀疏数组中
         * */
        // 我们用一个int 变量来记录是第几个
        int count = 0;
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                if (chessArr[i][j] != 0) {
                    count++;
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = chessArr[i][j];
                }
            }
        }
        //    输出稀疏数组
        System.out.println();
        System.out.println("得到的稀疏数组为");
        for (int i = 0; i < sparseArr.length; i++) {
            System.out.printf("%d\t%d\t%d\t\n", sparseArr[i][0], sparseArr[i][1], sparseArr[i][2]);
        }
        // 将稀疏数组回复成原始的二维数组
        /*
         * 1.先从稀疏数组的第一列 读取出 有关原始数组长度和有多少非0的值
         * 2.之后读取稀疏数组的后几行数据，并且赋值给原始的二维数组即可
         * */
        int[][] chessArr2 = new int[sparseArr[0][0]][sparseArr[0][1]];
        for (int i = 1; i < sparseArr.length; i++) {
            chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }
        System.out.println("输出恢复之后的二维数组");
        for (int[] row : chessArr2) {
            for (int data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }
    }
}

输出结果

队列

队列的一个使用场景

银行排队的案例:

队列介绍

1. 队列是一个有序列表，可以用数组或是链表来实现。
2. 遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出
3. 示意图：(使用数组模拟队列示意图)

数组模拟队列

数组模拟队列思路：思路图

• 队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 maxSize 是该队 列的最大容量。
• 因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front 及 rear 分别记录队列前后端的下标， front 会随着数据输出而改变，而 rear 则是随着数据输入而改变，如图所示

新增思路

当我们将数据存入队列时称为”addQueue”，addQueue 的处理需要有两个步骤：思路分析

1. 将尾指针往后移：rear+1 , 当 front == rear 【空】
2. 若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear 所指的数组元素中，否则无法存入数据。 rear == maxSize - 1[队列满]

根据队列思路实现数组模拟队列

/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.Queue
 * @className: ArrayQueueDemo
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2021/12/16 14:24
 * @version: 1.0
 */
public class ArrayQueueDemo {
    public static void main(String[] args) {
//创建一个队列
        ArrayQueue queue = new ArrayQueue(3);
        char key = ' '; //接收用户输入
        Scanner scanner = new Scanner(System.in);//
        boolean loop = true;
//输出一个菜单
        while (loop) {
            System.out.println("s(show): 显示队列");
            System.out.println("e(exit): 退出程序");
            System.out.println("a(add): 添加数据到队列");
            System.out.println("g(get): 从队列取出数据");
            System.out.println("h(head): 查看队列头的数据");
            key = scanner.next().charAt(0);//接收一个字符
            switch (key) {
                case 's':
                    queue.showQueue();
                    break;
                case 'a':
                    System.out.println("输出一个数");
                    int value = scanner.nextInt();
                    queue.addQueue(value);
                    break;
                case 'g': //取出数据
                    try {
                        int res = queue.getQueue();
                        System.out.printf("取出的数据是%d\n", res);
                    } catch (Exception e) {
// TODO: handle exception
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h': //查看队列头的数据
                    try {
                        int res = queue.headQueue();
                        System.out.printf("队列头的数据是%d\n", res);
                    } catch (Exception e) {
// TODO: handle exception
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e': //退出
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出~~");
    }
}
/* 根据 数组来实现的队列*/
class ArrayQueue {
    //队列最大上限
    private int MaxSize;
    //队列尾部
    private int rear;
    //队列头部
    private int front;
    //存放队列数据的数组
    private int[] ArrayQueue;
    /**
     * @author 冷环渊 Doomwatcher
     * @context: 初始化构造队列，初始化队列和头尾值向
     * @date: 2021/12/16 14:30
     * @param maxSize
     * @return:
     */
    public ArrayQueue(int maxSize) {
        // 获取最大值
        this.MaxSize = maxSize;
        //初始化 队列
        ArrayQueue = new int[MaxSize];
        //设置最大最小值
        rear = -1;
        front = -1;
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context: 判断是否队列是否达到存储上限
     * @date: 2021/12/16 14:30
     * @param
     * @return: boolean
     */
    public boolean isfull() {
        return rear == MaxSize - 1;
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context: 判断队列是否是空的
     * @date: 2021/12/16 14:32
     * @param
     * @return: boolean
     */
    public boolean isemity() {
        return rear == front;
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context: 向队列插入一条数据
     * @date: 2021/12/16 14:34
     * @param value
     * @return: void
     */
    public void addQueue(int value) {
        if (isfull()) {
            System.out.println("队列已满 不能加入更多的数据");
            return;
        }
        //++ 是后赋值，意思是执行完当前赋值，rear向后移动一位
        rear++;
        ArrayQueue[rear] = value;
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context:获取队列的值
     * @date: 2021/12/16 14:37
     * @param
     * @return: void
     */
    public int getQueue() {
        if (isemity()) {
            throw new RuntimeException("该队列是空的 无法获取到内容");
        }
        front++;
        return ArrayQueue[front];
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context:遍历队列输出 注意是遍历 不会更改队列的指向
     * @date: 2021/12/16 14:42
     * @param
     * @return: void
     */
    public void showQueue() {
        if (isemity()) {
            System.out.println("队列没有可以遍历的数值");
        }
        for (int i = 0; i < ArrayQueue.length; i++) {
            System.out.printf("arrQueue[%d]: %d\n", i, ArrayQueue[i]);
        }
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context:这里我们和上一个遍历方法一样 只是展示数据并不是去出数据
     * @date: 2021/12/16 14:45
     * @param
     * @return: void
     */
    public int headQueue() {
        if (isemity()) {
            throw new RuntimeException("没有头数据");
        }
        return ArrayQueue[front + 1];
    }
}

问题分析并优化

1. 目前数组使用一次就不能用， 没有达到复用的效果
2. 将这个数组使用算法，改进成一个环形的队列 取模：%

数组模拟环形队列

对前面的数组模拟队列的优化，充分利用数组. 因此将数组看做是一个环形的。(通过取模的方式来实现即可)

分析说明：

1. 尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定,这个在做判断队列满的 时候需要注意 (rear + 1) % maxSize == front 满]
2. rear == front [空]

根据思路实现数组模拟环形队列

/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.Queue
 * @className: CircleArrayQueueDemo
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2021/12/16 16:28
 * @version: 1.0
 */
public class CircleArrayQueueDemo {
    public static void main(String[] args) {
        System.out.println("测试环形队列");
//创建一个队列 这里空间为4 最大有效空间为3 留出一个空间作为约定
        CircleArrayQueue queue = new CircleArrayQueue(4);
        char key = ' '; //接收用户输入
        Scanner scanner = new Scanner(System.in);//
        boolean loop = true;
//输出一个菜单
        while (loop) {
            System.out.println("s(show): 显示队列");
            System.out.println("e(exit): 退出程序");
            System.out.println("a(add): 添加数据到队列");
            System.out.println("g(get): 从队列取出数据");
            System.out.println("h(head): 查看队列头的数据");
            key = scanner.next().charAt(0);//接收一个字符
            switch (key) {
                case 's':
                    queue.showQueue();
                    break;
                case 'a':
                    System.out.println("输出一个数");
                    int value = scanner.nextInt();
                    queue.addQueue(value);
                    break;
                case 'g': //取出数据
                    try {
                        int res = queue.getQueue();
                        System.out.printf("取出的数据是%d\n", res);
                    } catch (Exception e) {
// TODO: handle exception
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h': //查看队列头的数据
                    try {
                        int res = queue.headQueue();
                        System.out.printf("队列头的数据是%d\n", res);
                    } catch (Exception e) {
// TODO: handle exception
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e': //退出
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出~~");
    }
}
/** 环形队列
 * 思路变化：
 * 之前的队列有问什么问题所在
 * 问题分析并优化
 *1) 目前数组使用一次就不能用， 没有达到复用的效果
 *2) 将这个数组使用算法，改进成一个环形的队列 取模：%
 * 思路如下 ：
 * 1.front变量的含义做一个调整：front就指向队列的第一个元素，也就是说arr(front]就是队列的第一个元素
 * front的初始值
 * 2.rear变量的含义做一个调整：rear指向队列的最后一个元素的后一个位置.因为希望空出一个空间做为约定.
 * rear的初始值=0
 * 3.当队列满时，条件是（rear+1)%maxSize=front【满】
 * 4.对队列为空的条件，rear==front空
 * 5.当我们这样分析，队列中有效的数据的个数（rear+maxSize-front)%maxSize//rear=1front=0
 * 6.我们就可以在原来的队列上修改得到，一个环形队列
 *
 * */
class CircleArrayQueue {
    //队列最大上限
    private int MaxSize;
    //队列尾部 思路发生变化这次我们的队尾值变化为0指向队列最后一位的前一位
    private int rear;
    //队列头部 思路变化 指向队头的第一位 也就是下标 为 0   
    private int front;
    //存放队列数据的数组
    private int[] ArrayQueue;
    /**
     * @author 冷环渊 Doomwatcher
     * @context: 初始化构造队列，初始化队列和头尾值向
     * 这里为什么没有初始化队头队尾，因为默认 = 0
     * @date: 2021/12/16 14:30
     * @param maxSize
     * @return:
     */
    public CircleArrayQueue(int maxSize) {
        // 获取最大值
        this.MaxSize = maxSize;
        //初始化 队列
        ArrayQueue = new int[MaxSize];
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context:
     * 这里思路变化，因为我们要做环形队列这里我们有一个位置是动态变化的所以我们需要更新计算是否队列已满的方法
     * @date: 2021/12/16 14:30
     * @param
     * @return: boolean
     */
    public boolean isfull() {
        return (rear + 1) % MaxSize == front;
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context: 判断队列是否是空的
     * @date: 2021/12/16 14:32
     * @param
     * @return: boolean
     */
    public boolean isemity() {
        return rear == front;
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context:
     * 加入数据我们也要发生变化 这里我们用的是环形了
     * rear 的后移不再是最后一位，可能会出现越界的问题
     * （rear+1）%maxSize
     * @date: 2021/12/16 14:34
     * @param value
     * @return: void
     */
    public void addQueue(int value) {
        if (isfull()) {
            System.out.println("队列已满 不能加入更多的数据");
            return;
        }
        //赋值
        ArrayQueue[rear] = value;
        //考虑用取模来后移 rear
        rear = (rear + 1) % MaxSize;
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context:
     * 为什么不用 ++了呢 因为我们是环形 一定会出现越界，这里考虑取模动态的算出后移的位置
     * @date: 2021/12/16 14:37
     * @param
     * @return: void
     */
    public int getQueue() {
        if (isemity()) {
            throw new RuntimeException("该队列是空的 无法获取到内容");
        }
        /*
         * 1，我们这次的思路是front代表的是队列的第一个下标
         * 2. 用临时变量来拿出 当前的值
         * 3.后移front 返回值
         * */
        int value = ArrayQueue[front];
        front = (front + 1) % MaxSize;
        return value;
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context:
     * 遍历环形队列 输出 这里我们不再是遍历数组长度了
     * 我们需要求出有效的数量
     * @date: 2021/12/16 14:42
     * @param
     * @return: void
     */
    public void showQueue() {
        if (isemity()) {
            System.out.println("队列没有可以遍历的数值");
        }
        //这里我们因该是从 front 开始遍历
        for (int i = front; i < front + Size(); i++) {
            //这里下标我们选择取模 应为是环形的会出现越界的情况，所以我们使用取模运算
            System.out.printf("arrQueue[%d]: %d\n", i % MaxSize, ArrayQueue[i % MaxSize]);
        }
    }
    /*编写一个求出队列有效数据数量的放啊*/
    public int Size() {
        /* 取模思路套用
         * 1. rear = 1
         * 2. front = 0
         * 3. maxSize = 3
         * （1+3-0）%3 = 1 应为算出来是下标 所以我们这里有两个有效数据 0，1
         * */
        return (rear + MaxSize - front) % MaxSize;
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context:这里我们和上一个遍历方法一样 只是展示数据并不是去出数据
     * 这里不再是 front-1 应为 front此时默认就是0
     * @date: 2021/12/16 14:45
     * @param
     * @return: void
     */
    public int headQueue() {
        if (isemity()) {
            throw new RuntimeException("没有头数据");
        }
        return ArrayQueue[front];
    }
}

代码执行效果

链表

链表(Linked List)介绍 :

链表是有序的列表，但是它在内存中是存储如下

1. 链表是以节点的方式来存储,是链式存储
2. 每个节点包含 data 域， next 域：指向下一个节点.
3. 如图：发现链表的各个节点不一定是连续存储.
4. 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

单向链表

单向链表存储节点思路图

单链表的应用实例

使用带 head 头的单向链表实现 –水浒英雄排行榜管理完成对英雄人物的增删改查操作

我们都知道 水浒传里有108位英雄吧

我们这里随便举例四个，我们想用链表的方式把他们放入我们的英雄榜里（单向链表）

新增，修改，删除的思路

添加英雄:

根据排名将英雄插入到指定位置(如果有这个排名，则添加失败，并给出提示) 思路的分析示意图:

修改节点功能

古时候，有武功的人士逗喜欢为了排名去争斗，所以我们制作英雄榜需要有更换排名的功能

排名是固定的，他的下一名也是固定的 我们要修改的只有当前占有排名的人和昵称即可

• 先找到该节点，通过遍历，
• temp.name = newHeroNode.name ; temp.nickname= newHeroNode.nickname

删除节点

这个功能呢可以理解为，有英雄不想争夺排名了，退休回家种田耕地享受生活了，我们需要把不需要位置的英雄占有的位置腾出来。

单向链表的增删改查

/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.LinkedList
 * @className: LinkedlistDemo
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2021/12/17 16:24
 * @version: 1.0
 */
public class LinkedlistDemo {
    public static void main(String[] args) {
        // 设置一些英雄对象
        HeroNode heroNode = new HeroNode(1, "宋江", "及时雨");
        HeroNode heroNode1 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode heroNode2 = new HeroNode(3, "吴用", "智多星");
        HeroNode heroNode3 = new HeroNode(4, "林冲", "豹子头");
        // 声明单向链表
        SingleLinkedlist linkedlist = new SingleLinkedlist();
        //加入我们的英雄节点
        //linkedlist.add(heroNode);
        //linkedlist.add(heroNode1);
        //linkedlist.add(heroNode2);
        //linkedlist.add(heroNode3);
        //加入按照编号
        linkedlist.addByOrder(heroNode);
        linkedlist.addByOrder(heroNode3);
        linkedlist.addByOrder(heroNode2);
        linkedlist.addByOrder(heroNode1);
        //输出节点信息
        linkedlist.List();
        System.out.println("更新数据后");
        linkedlist.updateNode(new HeroNode(1, "冷环渊", "编码大师"));
        //输出节点信息
        linkedlist.List();
        System.out.println("删除数据后输出");
        linkedlist.DeleteNode(1);
        linkedlist.List();
    }
}
class SingleLinkedlist {
    //创建一个头结点
    HeroNode head = new HeroNode(0, "", "");
    //加入链表
    public void add(HeroNode node) {
        //头节点不能动 这里我们用一个临时指针来记录
        HeroNode temp = head;
        //遍历链表
        while (true) {
            //遍历为空就代表找了最后一个节点
            //不为空就后移一位继续找
            if (temp.next == null) {
                break;
            }
            //没有找到最后就后移 temp
            temp = temp.next;
        }
        //跳出while证明找到了最后的节点，将我们的新节点加入到最后的节点的next即可
        temp.next = node;
    }
    //添加节点 第二种方法
    public void addByOrder(HeroNode node) {
        /*
         * 因为头结点不能动，我们通过指针来记录头节点来帮助找到添加的位置
         *因为是单链表我们找的是 Temp是位于添加位置的前一个节点，否则插入不了
         * */
        //创建一个临时变量
        HeroNode temp = head;
        //用来标识 英雄是否存在 默认为不存在（false）
        boolean flag = false;
        while (true) {
            //找到最后为空的位置
            if (temp.next == null) {
                break;
            }
            //如果temp的下一个no 大于 我们加入的节点，就往temp加入
            if (temp.next.No > node.No) {
                break;
            }
            //如果下一个节点等于 加入节点的No 那么就代表已经存在了节点
            else if (temp.next.No == node.No) {
                //将flag 修改为 true 代表已经存在
                flag = true;
                break;
            }
            //如果上面的都没达成就代表当前节点位置不对，向后继续遍历
            temp = temp.next;
        }
        //    判断 flag的值
        if (flag) {
            //如果为 true 代表节点已经存在
            System.out.printf("当前节点%d已经存在了，不能加入\n", node.No);
        } else {
            //    如果为false 那代表符合插入条件并且不存在与当前链表
            node.next = temp.next;
            temp.next = node;
        }
    }
    //修改节点信息
    public void updateNode(HeroNode newHeroNode) {
        if (head.next == null) {
            System.out.println("链表是空的");
        }
        //这里是头节点不能修改，我用 temp 来指向头结点
        HeroNode temp = head.next;
        // 是否找到了no的标识
        boolean flag = false;
        while (true) {
            //找到最后一个
            if (temp == null) {
                break;
            }
            if (temp.No == newHeroNode.No) {
                //如果等于 那么代表可以修改
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            //  true 修改信息
            temp.NickName = newHeroNode.NickName;
            temp.Name = newHeroNode.Name;
        } else {
            System.out.printf("没有找到 %d 这个节点", newHeroNode.No);
        }
    }
    //删除节点信息
    public void DeleteNode(int no) {
        HeroNode temp = head;
        // 用来标注 是不是可以删除
        boolean flag = false;
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.No == no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //根据flag 删除Node
        if (flag) {
            //找到的话就删除，这里我们只需要指向空 GC会回收
            temp.next = temp.next.next;
        } else {
            System.out.printf("要删除的 %d 没有找到", no);
        }
    }
    //遍历链表
    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.next;
        }
    }
}
/**
 * 编写 水浒传英雄 节点
 *  用于存放每个英雄的属性
 * */
class HeroNode {
    //排名
    public int No;
    // 姓名
    public String Name;
    //昵称
    public String NickName;
    // 下一个是哪位好汉
    public HeroNode next;
    public HeroNode(int hNo, String hName, String hNickName) {
        this.No = hNo;
        this.Name = hName;
        this.NickName = hNickName;
    }
    //方便输出语句输出
    @Override
    public String toString() {
        return "HeroNode{" +
                "No=" + No +
                ", Name='" + Name + '\'' +
                ", NickName='" + NickName + '\'' +
                '}';
    }
}

链表使用效果

总结

我们这次制作了属于自己的英雄榜（单向链表）,我们收货了什么呢？

• 节点之间联系的思路
• 逐渐适应数据结构的一些思想
• 动手实操实现的习惯

单向链表各大厂面试题

新浪

    /**
     * @author 冷环渊 Doomwatcher
     * @context:
     * 新浪链表面试题 查找链表中的第k个节点
     * 思路：
     * 1.编写一个方法，接收head 节点，同时接收一个index
     * 2，index表示的是倒数第index 个节点
     * 3. 先把链表从头到尾遍历 得到链表的总长度 getlength
     * 4。得到Size之后 我们从链表的第一个开始遍历（Size-index）个，就可以得到
     * 5. 如果找到了 则返回该节点否则返回null
     * @date: 2021/12/18 15:12
     * @param head
     * @param index
     * @return: com.hyc.DataStructure.LinkedList.HeroNode
     */
    public static HeroNode getLastIndexNode(HeroNode head, int index) {
        // 如果除去头节点之后没有新的节点就代表链表是空的，返回空对象
        if (head.next == null) {
            return null;
        }
        // 获取到链表的长度
        int Size = SingleLinkedlist.getlength(head);
        //声明一个零时变量指向第一个有效的节点
        HeroNode cur = head.next;
        //假设 我们的例子是一共有三个有效节点 3 这里我们index 为 2 那么3-2 = 1 找到了倒数第二个的节点
        for (int i = 0; i < Size - index; i++) {
            cur = cur.next;
        }
        //找到节点之后我们直接返回即可
        return cur;
    }

腾讯

/**
     * @author 冷环渊 Doomwatcher
     * @context: 腾讯面试题 反转链表
     * 思路:
     * 1.先定义一个节点 reverseHead = new HeroNode();
     * 2.从头遍历原来的链表，每次遍历一个节点就将其取出并且放到信的链表的最前端，
     * 3.原来的链表head.next = reverseHead.Next
     * @date: 2021/12/18 15:38
     * @param head
     * @return: void
     */
    public static void reverseList(HeroNode head) {
        if (head.next == null || head.next.next == null) {
            return;
        }
        //需要新的一个空的头
        HeroNode reverseHead = new HeroNode(0, "", "");
        // 获得第一个有效的节点
        HeroNode cur = head.next;
        //指向[cur]的下一个的节点
        HeroNode next = null;
        while (cur != null) {
            //保存当前的节点的下一个位置 有用
            next = cur.next;
            // 将cur的下一个指向 新的链表的最前端
            cur.next = reverseHead.next;
            //将新链表的最前端为cur
            reverseHead.next = cur;
            //cur 继续向后遍历
            cur = next;
        }
        head.next = reverseHead.next;
    }

百度

/**
 * @author 冷环渊 Doomwatcher
 * @context: 百度面试题， 在不破坏链表结构的情况下 反向输出链表
 * 这里我们利用 一个 即将学到的 数据结构叫 栈
 * 栈结构的特点就是 先进后出
 * 将链表的节点按顺序遍历压入栈
 * 利用栈先进后出的特质，就可以保证性能的情况下输出不改变结构的倒序链表
 * @date: 2021/12/19 13:48
 * @param
 * @return: void
 */
public static void showreverseList(HeroNode node) {
    if (node.next == null) {
        return;
    }
    Stack<HeroNode> stack = new Stack<>();
    HeroNode cur = node.next;
    while (cur != null) {
        stack.push(cur);
        cur = cur.next;
    }
    while (stack.size() > 0) {
        System.out.println(stack.pop());
    }
}

课后练习

    /**
     * @author 冷环渊 Doomwatcher
     * @context: 合并两个链表 并且有序
     * @date: 2021/12/19 14:15
     * @param list1
     * @param list2
     * @return: com.hyc.DataStructure.LinkedList.SingleLinkedlist
     */
    public static HeroNode mergeList(HeroNode list1, HeroNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        HeroNode head = new HeroNode(0, "", "");
        HeroNode temp = head;
        while (list1 != null && list2 != null) {
            if (list1.No < list2.No) {
                temp.next = list1;
                list1 = list1.next;
            } else {
                temp.next = list2;
                list2 = list2.next;
            }
            temp = temp.next;
        }
        if (list1 == null) {
            temp.next = list2;
        }
        if (list2 == null) {
            temp.next = list1;
        }
        return head.next;
    }

双向链表

双向链表应用实例,双向链表的操作分析和实现

管理单向链表的缺点分析:

1. 单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。
2. 向链表不能自我删除，需要靠辅助节点 ，而双向链表，则可以自我删除，所以前面我们单链表删除 时节点，总是找到 temp,temp 是待删除节点的前一个节点(认真体会).
3. 分析了双向链表如何完成遍历，添加，修改和删除的思路

双向链表实现思路

分析 双向链表的遍历，添加，修改，删除的操作思路===》代码实现

1. 遍历 方和 单链表一样，只是可以向前，也可以向后查找

2. 添加 (默认添加到双向链表的最后)

   1. (1) 先找到双向链表的最后这个节点
   2. (2) temp.next = newHeroNode

3. newHeroNode.pre = temp;

4. 修改 思路和 原来的单向链表一样. 4) 删除
   (1) 因为是双向链表，因此，我们可以实现自我删除某个节点
   (2) 直接找到要删除的这个节点，比如 temp
   (3) temp.pre.next = temp.next
   (4) temp.next.pre = temp.pre;

实现链表节点

/**
 * 双向链表要用的节点
 * */
class ListNode {
    //排名
    public int No;
    // 姓名
    public String Name;
    //昵称
    public String NickName;
    // 下一个节点
    public ListNode next;
    //上一个节点
    public ListNode pre;
    public ListNode(int hNo, String hName, String hNickName) {
        this.No = hNo;
        this.Name = hName;
        this.NickName = hNickName;
    }
    //方便输出语句输出
    @Override
    public String toString() {
        return "HeroNode{" +
                "No=" + No +
                ", Name='" + Name + '\'' +
                ", NickName='" + NickName + '\'' +
                '}';
    }
}

双向链表实现

class DoubleLinkedList {
    //创建一个头结点
    ListNode head = new ListNode(0, "", "");
    public ListNode getHead() {
        return head;
    }
    public void setHead(ListNode head) {
        this.head = head;
    }
    //遍历链表
    public void List() {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //头节点不能动 这里我们用一个临时指针来记录
        ListNode temp = head.next;
        while (true) {
            //遍历为空就代表找了最后一个节点
            if (temp == null) {
                break;
            }
            //输出节点
            System.out.println(temp);
            //后移一位
            temp = temp.next;
        }
    }
    //加入双向链表
    public void add(ListNode node) {
        //头节点不能动 这里我们用一个临时指针来记录
        ListNode temp = head;
        //遍历链表
        while (true) {
            //遍历为空就代表找了最后一个节点
            //不为空就后移一位继续找
            if (temp.next == null) {
                break;
            }
            //没有找到最后就后移 temp
            temp = temp.next;
        }
        //指向下一个节点
        temp.next = node;
        //指向上一个节点
        node.pre = temp;
    }
    //修改双向链表，和单向链表基本一致不需要过多的修改
    //修改节点信息
    public void updateNode(ListNode newlistnode) {
        if (head.next == null) {
            System.out.println("链表是空的");
        }
        //这里是头节点不能修改，我用 temp 来指向头结点
        ListNode temp = head.next;
        // 是否找到了no的标识
        boolean flag = false;
        while (true) {
            //找到最后一个
            if (temp == null) {
                break;
            }
            if (temp.No == newlistnode.No) {
                //如果等于 那么代表可以修改
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            //  true 修改信息
            temp.NickName = newlistnode.NickName;
            temp.Name = newlistnode.Name;
        } else {
            System.out.printf("没有找到 %d 这个节点", newlistnode.No);
        }
    }
    /*
     * 双向链表删除
     * 对于双向链表来说就不需要找到上一个节点来删除了，
     * 可以找到自己删除
     * */
    public void DeleteNode(int no) {
        if (head.next == null) {
            System.out.println("链表为空 不需要删除");
            return;
        }
        ListNode temp = head.next;
        // 用来标注 是不是可以删除
        boolean flag = false;
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.next.No == no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //根据flag 删除Node
        if (flag) {
            //找到的话就删除，这里我们只需要指向空 GC会回收
            //temp.next = temp.next.next; 原先的单向链表删除现在在双向链表里就不好使了
            /*将当前节点的上一个节点的下一个指向 指向当前节点的下一个节点 相当于向前指向的next 直接跨过当前的节点指向下一个节点*/
            temp.pre.next = temp.next;
            /*将当前节点的下一个节点的上一个指向 指向当前节点的上一个节点，相当于向前的pre 直接快过当前的节点指向上一个
             * 如果当前节点是最后一节点，就不执行后面这个将下一个节点的指向更改，不然会出现空指针
             * */
            if (temp.next != null) {
                temp.next.pre = temp.pre;
            }
            /*这两步 坐完相当于 此时的当前节点已经没有了指向 会被回收*/
        } else {
            System.out.printf("要删除的 %d 没有找到", no);
        }
    }
}

总结

双向链表在之前的基础上：

1. 对比单向链表 双向链表可以自己删除，
2. 双线链表正反遍历更加的容易

环形链表

认识单向环形链表

这里我们以单向环形链表为例子

就是我们最后一个节点的next域指向头结点，形成闭环

引用场景以及问题

Josephu(约瑟夫、约瑟夫环) 问题

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

此产生一个出队编号的序列。

思路提示：

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

Josephu 问题解题思路

认识约瑟夫问题，以及我们想要实现的场景，

1. 编写实现 单向环形链表
2. 约瑟夫问题的要求 根据区间报数 报数的小孩出列
3. coding 出我们需要的需求

实现单向循环链表

思路

大体上和我们的单向链表有雷同的地方，区别在于：

1. 我们需要在创建链表的时候将尾结点的最后一个指向头结点，这也就意味着我们需要有至少两个指针来记录头尾节点。
2. 遍历的方式也要有些许的变化，结束循环的条件从head.next = null改变成CurBoy.next(指向尾部节点的指针) = first;最后为头节点的时候遍历为第二个

我们简单的先创建一个实现链表需要的节点对象

约瑟夫问题环形链表的节点

//环形链表 约瑟夫问题 节点
class Boy {
    private int No;
    private Boy Next;
    public Boy(int no) {
        this.No = no;
    }
    public int getNo() {
        return No;
    }
    public void setNo(int no) {
        No = no;
    }
    public Boy getNext() {
        return Next;
    }
    public void setNext(Boy next) {
        Next = next;
    }
}

创建环形链表对象实现生成链表和遍历链表，以及解决约瑟夫问题的方（具体的实现思路见代码注释）

// 环形单向链表
class CircleSingleLinkeList {
    Boy first = null;
    /**
     * @author 冷环渊 Doomwatcher
     * @context: 一个环形链表  参数是这个链表有多少节点
     * @date: 2021/12/21 15:47
     * @param nums
     * @return: void
     */
    public void CreateListNode(int nums) {
        if (nums < 1) {
            System.out.println("无法开始游戏，因为链表小于最小的游戏节点数量");
            return;
        }
        // 创建一个 辅助之间用于遍历和指向节点
        Boy curBoy = null;
        for (int i = 1; i <= nums; i++) {
            Boy boy = new Boy(i);
            //如果只有一个节点的话 也可以生成环形链表
            if (i == 1) {
                first = boy;
                first.setNext(first);
                curBoy = first;//将辅助指针指向链表的第一个节点 形成闭环
            } else {
                //    如果不是一个的话就生成多个节点
                curBoy.setNext(boy);
                boy.setNext(first);
                curBoy = boy;
            }
        }
    }
    public void showListBoy() {
        if (first == null) {
            System.out.println("链表为空，不能遍历");
            return;
        }
        //   frist 节点不能移动 我们创建一个指针
        Boy curboy = first;
        while (true) {
            System.out.printf("小孩的编号是： %d \n", curboy.getNo());
            // 说明已经遍历完毕
            if (curboy.getNext() == first) {
                break;
            }
            //后移 curboy
            curboy = curboy.getNext();
        }
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context: 这里我们以小孩做游戏来解决约瑟夫问题，
     * @date: 2021/12/22 21:16
     * @param nums 一共有多少个小孩
     * @param start 从那个小孩开始报数
     * @param index 每隔几个小孩报数一次
     * @return: void
     */
    public void JosephuFunc(int nums, int start, int index) {
        if (first == null || start < 1 || start > nums) {
            System.out.println("参数不对，请重新输入参数");
            return;
        }
        Boy helper = first;
        //将 helper遍历到最后一个节点
        while (true) {
            if (helper.getNext() == first) {
                break;
            }
            helper = helper.getNext();
        }
        // 小孩子 报数之前，要遍历指针到从start开始的小孩的节点
        for (int i = 0; i < start - 1; i++) {
            first = first.getNext();
            helper = helper.getNext();
        }
        //当小孩报数的时候 让 first和helper 同时移动m-1次 然后出圈
        //这里循环操作 知道圈中的一个节点
        while (true) {
            //说明列表只有一个节点
            if (helper == first) {
                break;
            }
            //循环之后将 指针后移
            for (int i = 0; i < index - 1; i++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            //    这个时候 first选中的节点就是要出圈的小孩
            System.out.printf("小孩 %d 出圈\n", first.getNo());
            //出圈操作
            first = first.getNext();
            helper.setNext(first);
        }
        System.out.printf("最后剩下的小孩 %d \n", first.getNo());
    }
}