@TOC

✨博主介绍

🌊 作者主页：苏州程序大白

🌊 作者简介：🏆CSDN人工智能域优质创作者🥇，苏州市凯捷智能科技有限公司创始之一，目前合作公司富士康、歌尔等几家新能源公司

💬如果文章对你有帮助，欢迎关注、点赞、收藏

💅 有任何问题欢迎私信，看到会及时回复
💅关注苏州程序大白，分享粉丝福利

:bamboo:什么是数据结构

数据结构(data structure)是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。简而言之，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合。“结构”就是指数据元素之间存在的关系，分为逻辑结构和存储结构。

数据的逻辑结构和物理结构是数据结构的两个密切相关的方面，同一逻辑结构可以对应不同的存储结构。算法的设计取决于数据的逻辑结构，而算法的实现依赖于指定的存储结构。

数据结构的研究内容是构造复杂软件系统的基础，它的核心技术是分解与抽象。通过分解可以划分出数据的 3 个层次；再通过抽象，舍弃数据元素的具体内容，就得到逻辑结构。类似地，通过分解将处理要求划分成各种功能，再通过抽象舍弃实现细节，就得到运算的定义。上述两个方面的结合可以将问题变换为数据结构。这是一个从具体（即具体问题）到抽象（即数据结构）的过程。然后，通过增加对实现细节的考虑进一步得到存储结构和实现运算，从而完成设计任务。这是一个从抽象（即数据结构）到具体（即具体实现）的过程。

线性表和链表

链表与单链表介绍

链表（Linked LIst）是有序列表，但是它在内存中存储如下：

结合一个实际的工作案例，说明链表的实用价值。

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

单链表（带头结点）逻辑结构示意如下：

单链表的应用

单链表的应用实列

使用带head头的单向链表实现——水浒英雄排行榜管理：
1、完成对英雄人物的增删改查操作。
2、第一种方法在添加英雄的时候，直接添加到链表的尾部。
3、第二种方式在添加英雄的时候，根据排名讲英雄插入到指定位置（如果有这个排名，则添加失败，并给出提示）。

代码实现单链表的 创建、遍历、插入以及顺序插入 如下：

public class SingleLinkedListTest {
    public static void main(String[] args) {

        // 01-创建几个节点
        HeroNode heroNode1 = new HeroNode(1, "松江", "及时雨");
        HeroNode heroNode2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode heroNode3 = new HeroNode(3, "吴用", "智多星");
        HeroNode heroNode4 = new HeroNode(4, "林冲", "豹子头");

        // 02-创建一个链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
//        singleLinkedList.add(heroNode1);
//        singleLinkedList.add(heroNode4);
//        singleLinkedList.add(heroNode3);
//        singleLinkedList.add(heroNode2);

        // 按照顺序加入
        singleLinkedList.addByOrder(heroNode1);
        singleLinkedList.addByOrder(heroNode4);
        singleLinkedList.addByOrder(heroNode3);
        singleLinkedList.addByOrder(heroNode2);
        singleLinkedList.addByOrder(heroNode2);

        // 03-显示单链表
        singleLinkedList.showList();
    }
}

/**
 * 定义 SingleLinkedList 单链表管理我们的英雄
 */
class SingleLinkedList {
    // 01-初始化一个头节点，头节点不要动，不存放具体的数据
    private HeroNode head = new HeroNode(0, "", "");

    public HeroNode getHead() {
        return head;
    }

    // 02-添加节点到单向链表，直接添加到链表尾部

    /**
     * 思路分析：当不考虑编号顺序时
     * 1. 找到当前链表的最后节点
     * 2. 将最后这个节点的 next 指向新的节点
     */
    public void add(HeroNode heroNode) {
        // 因为头节点不能动，所以我们需要一个辅助变量 temp
        HeroNode temp = head;

        // 遍历链表
        while (true) {
            // 找到链表的最后
            if (temp.next == null) {
                break;
            }
            // 如果没有找到最后，将 temp 后移
            temp = temp.next;
        }
        // 当退出 while 循环时，temp 就指向了链表的最后
        temp.next = heroNode;
    }


    // 根据排名将英雄添加到指定位置，即按照顺序添加
    public void addByOrder(HeroNode heroNode){
        HeroNode temp = head;
        boolean flag = false;    // 标志添加的编号是否存在，默认为 false

        while (true){
            if (temp.next == null){    // 说明 temp 已经在链表最后
                break;
            }
            if(temp.next.no > heroNode.no){
                break;
            } else if(temp.next.no == heroNode.no){    // 编号已经存在
                flag = true;    // 说明编号存在
                break;
            }
            temp = temp.next;
        }

        if(flag){    // 不能添加，编号存在
            System.out.printf("待插入的英雄编号 %d 已经存在了，不能加入！", heroNode.no);
        } else {
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }


    // 显示链表[遍历]
    public void showList() {
        // 判断链表是否为空
        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;
        }
    }

}


/**
 * 单链表
 */
class HeroNode {
    public int no;
    public String name;
    public String nickname;
    public HeroNode next;   // 指向下一个节点

    // 构造器
    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 + '\'' +
                '}';
    }
}

单链表的节点信息的 修改操作 ，代码如下：

/* 以下三行代码加入到 main 方法里面 */

// 04-测试修改节点的代码
HeroNode heroNode = new HeroNode(2,"小卢","玉麒麟~~~");
singleLinkedList.update(heroNode);
singleLinkedList.showList();



/* 以下 update 方法加入到 SingleLinkedList 类里面 */

// 修改节点的信息，根据 no 编号来修改
public void update(HeroNode heroNode) {
    // 判断链表是否为空
    if (head.next == null) {
        System.out.println("链表为空！！！");
        return;
    }
    HeroNode temp = head.next;
    boolean flag = false;
    while (true) {
        if (temp.next == null) {
            break;    // 到达了链表的最后
        }
        if (temp.no == heroNode.no) {
            flag = true;
            break;
        }
        temp = temp.next;
    }

    if (flag) {
        temp.name = heroNode.name;
        temp.nickname = heroNode.nickname;
    } else {
        System.out.printf("没有找到编号为 %d 的节点，不能修改！！！", heroNode.no);
    }

}

单链表的节点信息的 删除操作 ，代码如下：

从单链表中删除一个节点的思路：

1、我们先要找到需要删除的这个节点的前一个节点temp。

2、temp.next=temp.next.next

3、被删除的节点，将不会有其它引用指向，会被垃圾回收机制回收。

/* 以下四行代码加入到 main 方法里面 */

// 05-删除一个节点
singleLinkedList.delete(1);
singleLinkedList.delete(5);
System.out.println("删除后链表的情况~~~~~");
singleLinkedList.showList();



/* 以下 delete 方法加入到 SingleLinkedList 类里面 */

// 根据 no 删除节点
public void delete(int no) {
    HeroNode temp = head;
    boolean flag = false;
    while (true) {
        if (temp.next == null) {
            break;
        }
        if (temp.next.no == no) {    // 找到待删除结点的前一个结点 temp
            flag = true;
            break;
        }
        temp = temp.next;
    }
    if (flag) {
        temp.next = temp.next.next;
    } else {
        System.out.printf("要删除的 %d 节点不存在\n", no);
    }
}

单链表面试题（新浪、百度、腾讯）

1、求单链表中有效节点的个数。

2、查找单链表中的倒数第N个节点。

3、单链表的反转。

4、从尾到头打印单链表。

解决 第一个 题目：求单链表中有效节点的个数 ，代码如下：

/* 以下三行代码加入到 main 方法里面 */

HeroNode head = singleLinkedList.getHead();
int length = SingleLinkedList.getLength(head);
System.out.println("有效节点个数为：" + length);



/* 以下 getLength 方法加入到 SingleLinkedList 类里面 */
// 获取单链表的节点个数（如果是带头节点的单链表，则不统计头节点）
public static int getLength(HeroNode heroNode) {
    if (heroNode.next == null) {
        return 0;
    }

    int length = 0;
    // 定义一个辅助遍历，这里就体现了没有统计头节点
    HeroNode cur = heroNode.next;
    while (cur != null) {
        length++;
        cur = cur.next;
    }

    return length;
}

解决 第二个 题目：查找单链表中的倒数第 k 个节点 ，代码如下：

/* 以下四行代码加入到 main 方法里面 */

HeroNode res1 = SingleLinkedList.findNode(singleLinkedList.getHead(), 2);
System.out.println("res = " + res1);
HeroNode res2 = SingleLinkedList.findNode(singleLinkedList.getHead(), 5);
System.out.println("res = " + res2);



// 查找单链表中的倒数第 n 个节点 

/**
 * 思路分析：
 * 1. 编写一个方法，接收 head 节点，同时接收一个 index
 * 2. index 表示是倒数第 index 个节点
 * 3. 先把链表从头到尾遍历，得到链表的总长度，使用 getLength 方法
 * 4. 得到 size 后，我们从链表的第一个车开始遍历 （size-index） 个，就可以得到
 * 5. 如果找到了，则返回该节点，否则返回 null
 */
public static HeroNode findNode(HeroNode head, int index) {
    if (head.next == null) {
        return null;
    }
    int length = getLength(head);
    if (index <= 0 || index > length) {
        return null;
    }
    HeroNode cur = head.next;
    for (int i = 0; i < (length - index); i++) {
        cur = cur.next;
    }
    return cur;
}

解决 第三个 题目：单链表的反转，代码如下：

单链表的反转解题思路：

1、先定义一个节点reverseHead = new HeroNode()；

2、从头到尾遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead的最前端。

3、原来的链表的head.next = reverseHead.next

/* 以下五行代码加入到 main 方法里面 */

// 单链表的反转测试
System.out.println("原来链表的情况~~~");
singleLinkedList.showList();
System.out.println("反转后链表的情况~~~");
SingleLinkedList.reverseList(head);
singleLinkedList.showList();



// 将单链表反转
public static void reverseList(HeroNode head) {
    // 如果当前链表为空，或者只有一个节点，无需反转，直接返回
    if (head.next == null || head.next.next == null) {
        return;
    }

    // 定义一个辅助变量，帮助遍历原先的链表
    HeroNode cur = head.next;
    HeroNode next = null;
    HeroNode reverseHead = new HeroNode(0, "", "");

    // 遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表 reverseHead 的最前端
    while (cur != null) {
        next = cur.next;
        cur.next = reverseHead.next;    // 将 cur 的下一个节点指向新的链表的最前端
        reverseHead.next = cur;    // 将 cur 连接到新的链表
        cur = next;    // 让 cur 后移
    }
    // 将 head.next 指向 reverseHead.next ，实现单链表的反转
    head.next = reverseHead.next;
}

解决 第四个 题目：从尾到头打印单链表，代码如下：

// 逆序打印，以下一行加入到 main方法中
SingleLinkedList.revesrePrint(head);



// 实现逆序打印
public static void revesrePrint(HeroNode head){
    if(head.next == null){
        return;
    }

    Stack<HeroNode> stack = new Stack<>();
    HeroNode cur = head.next;

    // 压栈
    while (cur != null){
        stack.push(cur);
        cur = cur.next;
    }

    // 出栈
    while (stack.size() > 0){
        System.out.println(stack.pop());
    }
}

双向链表

学完单链表发现，单链表只能从头结点开始访问链表中的数据元素，如果需要逆序访问单链表中的数据元素将极其低效。因而出现了 双链表结构 。双链表 是链表的一种，由节点组成，每个数据结点中都有两个指针，分别指向 直接后继 和 直接前驱 。双链表结构如下图：



使用 双链表 对上述单链表的功能进行再次实现，代码如下：

/**
 * @Author: 苏州程序大白
 * @Create: 2022/4/8 12:51
 * @Description: 双向链表案例
 */
public class DoubleLinkedListTest {
    public static void main(String[] args) {

        System.out.println("双向链表测试~~~");

        // 01-创建几个节点
        HeroDoubleNode heroNode1 = new HeroDoubleNode(1, "松江", "及时雨");
        HeroDoubleNode heroNode2 = new HeroDoubleNode(2, "卢俊义", "玉麒麟");
        HeroDoubleNode heroNode3 = new HeroDoubleNode(3, "吴用", "智多星");
        HeroDoubleNode heroNode4 = new HeroDoubleNode(4, "林冲", "豹子头");

        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        doubleLinkedList.add(heroNode1);
        doubleLinkedList.add(heroNode2);
        doubleLinkedList.add(heroNode3);
        doubleLinkedList.add(heroNode4);

        doubleLinkedList.showList();

        // 修改测试
        HeroDoubleNode newNode = new HeroDoubleNode(4, "Jack", "Jacky");
        doubleLinkedList.update(newNode);
        System.out.println("修改后双向链表~~~");
        doubleLinkedList.showList();

        // 删除测试
        doubleLinkedList.delete(3);
        System.out.println("删除后双向链表~~~");
        doubleLinkedList.showList();

    }
}


class DoubleLinkedList {

    // 01-初始化一个头节点，头节点不要动，不存放具体的数据
    private HeroDoubleNode head = new HeroDoubleNode(0, "", "");

    // 02-返回头节点
    public HeroDoubleNode getHead() {
        return head;
    }

    // 03-显示链表[遍历]
    public void showList() {
        // 判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        HeroDoubleNode temp = head.next;
        while (true) {
            if (temp == null) {
                break;
            }
            System.out.println(temp);
            // 将 temp 后移，否则是死循环
            temp = temp.next;
        }
    }

    // 04-添加节点到双向链表最后

    /**
     * 思路分析：当不考虑编号顺序时
     * 1. 找到当前链表的最后节点
     * 2. 将最后这个节点的 next 指向新的节点
     */
    public void add(HeroDoubleNode heroNode) {
        // 因为头节点不能动，所以我们需要一个辅助变量 temp
        HeroDoubleNode temp = head;

        // 遍历链表
        while (true) {
            // 找到链表的最后
            if (temp.next == null) {
                break;
            }
            // 如果没有找到最后，将 temp 后移
            temp = temp.next;
        }
        // 当退出 while 循环时，temp 就指向了链表的最后
        temp.next = heroNode;
        heroNode.pre = temp;
    }

    // 05-修改节点的信息，根据 no 编号来修改
    public void update(HeroDoubleNode heroNode) {
        // 判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空！！！");
            return;
        }
        HeroDoubleNode temp = head.next;
        boolean flag = false;
        while (true) {
            if (temp == null) {
                break;    // 到达了链表的最后
            }
            if (temp.no == heroNode.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }

        if (flag) {
            temp.name = heroNode.name;
            temp.nickname = heroNode.nickname;
        } else {
            System.out.printf("没有找到编号为 %d 的节点，不能修改！！！", heroNode.no);
        }

    }

    /**
     * 06-删除节点思路分析：
     * 1. 对于双向链表，我们可以直接找到要删除的这个节点
     * 2. 找到后，自我删除节点即可
     */
    public void delete(int no) {
        if (head.next == null){
            System.out.println("链表为空，无法删除！！！");
            return;
        }

        HeroDoubleNode temp = head.next;
        boolean flag = false;

        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.no == no) {    // 找到待删除结点的前一个结点 temp
                flag = true;
                break;
            }
            temp = temp.next;
        }

        if (flag) {
            temp.pre.next = temp.next;
            if (temp.next != null){
                temp.next.pre = temp.pre;
            }

        } else {
            System.out.printf("要删除的 %d 节点不存在\n", no);
        }
    }
}


class HeroDoubleNode {
    public int no;
    public String name;
    public String nickname;
    public HeroDoubleNode next;   // 指向下一个节点
    public HeroDoubleNode pre;    // 指向前一个节点

    // 构造器
    public HeroDoubleNode(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 + '\'' +
                '}';
    }
}

环形链表

环形链表 ，类似于单链表，也是一种链式存储结构，环形链表由单链表演化过来。单链表的最后一个结点的链域指向 NULL ，而环形链表则 首位相连 ，组成环状数据结构。如下图：

约瑟夫环问题

而在环形链表中，最为著名的即是 约瑟夫环问题 ，也称之为 丢手帕问题 。

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

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

根据用户的输入，生成一个小孩子出圈的顺序：

n=5,既有5个人
k=1,从第一个人开始报数
m=2，数2下

1、需求创建一个辅助变量（helper），事先应该指向环形链表的最后这个节点。
2、当小孩报数时，让first和helper移动k-1次。
3、可以将first指向的小孩节点出圈
first=first.next
helper.next=first

原来first指向的节点就没有任何引用，就会被收回

出圈顺序：
2->4->1->5->3

/**
 * @Author: 苏州程序大白
 * @Create: 2022/4/12 
 * @Description: 约瑟夫问题
 */
public class Josephu {
    public static void main(String[] args) {

        // 创建链表
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.addBoy(5);    // 加入 5 个节点
        circleSingleLinkedList.showNode();

        // 出圈操作
        circleSingleLinkedList.countBoyNode(1, 2, 5);
    }
}


/**
 * 创建一个环形单项链表
 */
class CircleSingleLinkedList {
    // 创建一个 first 节点
    private BoyNode first = null;

    // 添加节点，构建一个环形链表
    public void addBoy(int num) {
        if (num < 1) {
            System.out.println("参数小于 1 ，不正确！！！");
            return;
        }

        // 辅助节点，用于构建环形链表
        BoyNode curNode = null;

        // 使用 for 循环构建环形链表
        for (int i = 1; i <= num; i++) {
            // 根据编号创建节点
            BoyNode boyNode = new BoyNode(i);

            // 如果三第一个节点
            if (i == 1) {
                first = boyNode;
                first.setNext(first);
                curNode = first;    // 让 curNode 指向第一个节点

            } else {
                curNode.setNext(boyNode);
                boyNode.setNext(first);
                curNode = boyNode;
            }

        }
    }

    // 遍历当前的环形链表
    public void showNode() {
        if (first == null) {
            System.out.println("链表为空，没有节点~~~");
        }

        BoyNode temp = first;

        while (true) {
            System.out.printf("节点的编号 %d \n", temp.getNo());
            if (temp.getNext() == first) {
                break;
            }
            temp = temp.getNext();
        }
    }

    // 根据用户的输入，计算节点出圈顺序

    /**
     * @param startsNo 表示从第几个节点开始数数
     * @param countNum 表示数几下
     * @param nums 表示最初有多少个节点在圈中
     */
    public void countBoyNode(int startsNo, int countNum, int nums) {
        // 对参数进行校验
        if (first == null || startsNo < 1 || startsNo > nums) {
            System.out.println("参数输入有误，请重新输入！！！");
            return;
        }

        // 创建辅助变量
        BoyNode helper = first;
        while (true) {
            if (helper.getNext() == first) {
                break;
            }
            helper = helper.getNext();
        }

        // 节点报数前，先让 first 和 helper 移动 k-1 次
        for (int i = 0; i < (startsNo - 1); i++) {
            first = first.getNext();
            helper = helper.getNext();
        }

        // 出圈操作
        while (true) {
            // 说明圈中只有一个节点
            if (helper == first) {
                break;
            }

            for (int i = 0; i < (countNum - 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());
    }
}


/**
 * 创建一个 BoyNode 类，表示一个节点
 */
class BoyNode {

    private int no;          // 编号
    private BoyNode next;    // 指向下一个节点，默认为 null

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public BoyNode getNext() {
        return next;
    }

    public void setNext(BoyNode next) {
        this.next = next;
    }

    public BoyNode(int no) {
        this.no = no;
    }

}