数据结构（链表）

1.单链表

1.基本介绍

1.定义

2.逻辑结构

2.应用实例

1.需求分析

2.思路分析

3.完成添加和显示链表信息，直接添加到链表的尾部

package com.sun.linkedlist;

import java.util.Scanner;

/**
 * @author 孙显圣
 * @version 1.0
 */

class Test {
    public static void main(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        //添加几条记录
        Node node1 = new Node(1, "李白", "青莲剑歌");
        Node node2 = new Node(2, "杜甫", "青莲剑歌");
        Node node3 = new Node(3, "周瑜", "青莲剑歌");
        Node node4 = new Node(4, "诸葛亮", "青莲剑歌");
        singleLinkedList.add(node2);
        singleLinkedList.add(node1);
        singleLinkedList.add(node4);
        singleLinkedList.add(node3);
        boolean flag = true;
        while (flag) {
            System.out.println("1：显示，2：入队，3：出队，4：退出");
            Scanner scanner = new Scanner(System.in);
            int cmd = scanner.nextInt();
            switch (cmd) {
                case 1:
                    singleLinkedList.list();
                    break;
                case 2:
                    System.out.println("请输入要添加的数据：");
                    System.out.println("编号：");
                    int no = scanner.nextInt();
                    System.out.println("姓名：");
                    String name = scanner.next();
                    System.out.println("技能");
                    String skill = scanner.next();

                    Node node = new Node(no, name, skill);
                    singleLinkedList.add(node);
                    System.out.println("添加成功！");
                    break;
                case 3:

                    break;
                case 4:
                    flag = false;
                    System.out.println("退出系统");
            }
        }
    }
}



//用来管理节点
public class SingleLinkedList {
    //头结点，指向第一个元素
    private Node head = new Node();

    //添加节点
    public void add(Node node) {
        //遍历链表直到最后，然后添加节点
        //由于头结点不能动，所以需要一个辅助节点来遍历
        Node temp = head;
        while (true) {
            //只要临时节点的下一个节点不为空，就将临时节点向后移动
            if (temp.next != null) {
                //节点向后移动
                temp = temp.next;
                continue;
            }
            //当临时节点的下一个节点为空，则添加一个数据，然后退出循环
            temp.next = node;
            break;
        }
    }

    //遍历链表，显示信息
    public void list() {
        //临时节点指向头结点
        Node temp = head;
        while (temp.next != null) {
            //显示节点信息
            System.out.println(temp.next);
            temp = temp.next;
        }
    }

}

//编写一个节点类型，每一个对象即为一个节点
class Node {
    //数据域
    public int no;
    public String name;
    public String skill;

    //next域，指向下一个节点
    public Node next;

    public Node() {
    }

    public Node(int no, String name, String skill) {
        this.no = no;
        this.name = name;
        this.skill = skill;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", skill='" + skill + '\'' +
                '}';
    }
}

4.根据排名添加，如果排名重复则给出提示

    //按照顺序添加节点
    public void addBySequential(Node node) {

        //辅助节点
        Node temp = head;
        //遍历节点
        //只要下一个数不等于空并并且下一个数比当前数要小，则一定不是要插入的位置，所以向后移动
        while (temp.next != null && temp.next.no <= node.no) {
            temp = temp.next;
        }
        //只要出了循环就表示，下一个数是空或者下一个数大于当前的数，可以插入
        node.next = temp.next;
        temp.next = node;

    }

5.根据新节点的编号来修改信息

    //根据新节点的信息来修改链表
    public void update(Node newNode) {
        //根据id来查找到链表的那个节点

        //临时节点指向头结点
        Node temp = head;

        //只要下一个元素不为空就进入循环
        while (temp.next != null) {
            //如果符合条件，就修改这个节点的值
            if (temp.next.no == newNode.no) {
                //修改节点的值
                temp.next.name = newNode.name;
                temp.next.skill = newNode.skill;
                System.out.println("修改成功！修改后的节点信息为：" + temp.next);
                break;
            }
            //只要不符合条件就一直走
            temp = temp.next;
        }

    }

6.删除指定id的节点

    //删除指定id的节点
    public void del(int no) {
        //找到指定编号的节点的前一个位置
        Node temp = head;

        //只要没有找到指定no的节点就往后走
        while (temp.next != null) {
            if (temp.next.no == no) {
                //删除temp的下一个节点
                temp.next = temp.next.next;
                System.out.println("节点" + no + "删除成功！");
                break;
            }
            temp = temp.next;
        }

    }

3.单链表面试题

1.题目

2.面试题一

    // 1.根据头结点求单链表中有效节点的个数

    public int getLength(Node head) {
        // 根据头结点遍历即可
        // 临时节点
        Node temp = head;

        int length = 0; // 初始化长度为0
        // 只要临时节点的下一个节点不为空，则说明有一个有效节点，所以长度++
        while (temp.next != null) {
            length++;
            temp = temp.next;
        }
        return length;
    }

2.面试题二

    // 2.查找单链表的倒数第几个节点
    public Node numberOfCollapses(Node head, int tail) {
        // 得到有效节点的数量
        int length = getLength(head);

        if (tail > length) {
            throw new RuntimeException("输入有误！");
        }

        // 计算是正数第几个节点
        int index = length - tail + 1;

        // 遍历得到正数第index个节点
        Node temp = head;
        int temp_index = 0; // 记录是第几个节点
        while (temp.next != null) {
            temp_index++;
            if (temp_index == index) {
                return temp.next;
            }
            temp = temp.next;
        }
        return null;
    }

3.面试题三

    // 3.单链表反转

    public void linkedListInversion(Node head) {
        // 排除零个节点和一个节点的情况
        if (head.next == null || head.next.next == null) {
            return;
        }
        // 临时指针一
        Node temp1 = head.next;
        // 临时指针二
        Node temp2 = new Node();
        // 反转链表的一个临时节点
        Node reverseHead = new Node();

        // 使用双指针遍历单链表
        while (temp1 != null) {
            // 让第二个指针指向第一个指针的后面
            if (temp1.next != null) {
                temp2 = temp1.next;
            } else {
                // 如果第一个指针的下一个位置为空，则让第二个指针指向null，这样移动完一个节点之后第一个指针就会指向第二个指针也就是空，可以退出循环
                temp2 = null;
            }
            // 将temp1指向的节点接入到reverseHead后面
            temp1.next = reverseHead.next;
            reverseHead.next = temp1;

            // 利用第二个指针移动temp1
            temp1 = temp2;

        }

        // 反转成功之后让head节点指向第一个节点
        head.next = reverseHead.next;
    }

4.面试题四

    // 4，从尾到头打印单链表

    public void reversePrint(Node head) {
        // 只要链表没有元素就直接return
        if (head.next == null) {
            return;
        }

        // 创建一个栈
        Stack<Node> stack = new Stack<>();

        // 将各个节点依次压入栈中
        Node temp = head.next;
        while (temp != null) {
            stack.push(temp);
            temp = temp.next;
        }

        // 取出栈中的元素
        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }

    }

2.双向链表

1.增删改查分析图解

2.代码实现

package com.sun.linkedlist;


/**
 * Description: 双向链表
 *
 * @Author sun
 * @Create 2024/3/28 20:53
 * @Version 1.0
 */
// 双向链表方法的测试
class DoubleLinkedListDemoTest {
    public static void main(String[] args) {
        // 创建一个双向链表
        DoubleLinkedListDemo doubleLinkedListDemo = new DoubleLinkedListDemo();

        // 创建几个节点
        Node2 node1 = new Node2(1, "李白", "青莲剑歌");
        Node2 node2 = new Node2(2, "杜甫", "青莲剑歌");
        Node2 node3 = new Node2(3, "周瑜", "青莲剑歌");
        Node2 node4 = new Node2(4, "诸葛亮", "青莲剑歌");

        // 添加节点
        doubleLinkedListDemo.add(node1);
        doubleLinkedListDemo.add(node2);
        doubleLinkedListDemo.add(node3);
        doubleLinkedListDemo.add(node4);

        // 遍历
        doubleLinkedListDemo.list();

        // 修改节点
        Node2 updateNode = new Node2(4, "4", "4");
        doubleLinkedListDemo.update(updateNode);

        // 删除节点
        doubleLinkedListDemo.del(4);

        // 遍历
        doubleLinkedListDemo.list();

        System.out.println("====================================");

        // 把编号打乱，测试按照编号添加的方法
        Node2 node5 = new Node2(5, "5", "5");
        Node2 node6 = new Node2(6, "6", "6");
        Node2 node7 = new Node2(7, "7", "7");
        Node2 node8 = new Node2(8, "8", "8");
        // 从node8逆序添加
        doubleLinkedListDemo.insertByOrder(node8);
        doubleLinkedListDemo.insertByOrder(node7);
        doubleLinkedListDemo.insertByOrder(node6);
        doubleLinkedListDemo.insertByOrder(node5);
        // 遍历
        doubleLinkedListDemo.list();


    }
}

public class DoubleLinkedListDemo {
    // 初始化双向链表
    // 头结点，指向第一个元素
    private Node2 head = new Node2(-1, "", "");

    public Node2 getHead() {
        return head;
    }

    // 遍历的方法与单向链表相同

    public void list() {
        // 判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        // 临时节点
        Node2 temp = head.next;

        // 只要临时节点不为空，就输出当前节点信息，然后向后移动
        while (temp != null) {
            System.out.println(temp);
            temp = temp.next;
        }
    }

    // 添加节点

    public void add(Node2 node2) {

        // 临时节点
        Node2 temp = head;

        // 首先遍历找到最后一个节点
        while (temp.next != null) {
            temp = temp.next;
        }

        // 目前temp 指向了最后一个节点
        temp.next = node2;
        node2.pre = temp;
    }

    // 修改节点，跟单向链表一致
    public void update(Node2 newNode) {
        // 根据id来查找到链表的那个节点

        // 临时节点指向头结点
        Node2 temp = head;

        // 只要下一个元素不为空就进入循环
        while (temp.next != null) {
            // 如果符合条件，就修改这个节点的值
            if (temp.next.no == newNode.no) {
                // 修改节点的值
                temp.next.name = newNode.name;
                temp.next.skill = newNode.skill;
                System.out.println("修改成功！修改后的节点信息为：" + temp.next);
                break;
            }
            // 只要不符合条件就一直走
            temp = temp.next;
        }
    }

    // 从双向链表中删除节点，首先找到要删除的节点，然后自我删除即可

    // 删除指定id的节点
    public void del(int no) {
        // 首先判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空，不能删除");
            return;
        }

        // 临时节点指向第一个节点（这是因为第一个节点不为空才能这样）
        Node2 temp = head.next;

        // 只要没有找到指定no的节点就往后走
        while (temp != null) {

            // 判断是否是要找的节点
            if (temp.no == no) {
                // 执行自我删除
                temp.pre.next = temp.next;
                if (temp.next != null) {
                    // 这里如果temp指向了最后一个元素，则不执行，否则会报
                    temp.next.pre = temp.pre;
                }
                System.out.println("节点" + no + "删除成功！");
                break;
            }

            // 后移
            temp = temp.next;

        }
    }

    // 按照编号顺序来添加

    public void insertByOrder(Node2 newNode) {
        // 临时节点
        Node2 temp = head;
        // 只要临时节点的下一个节点不为空，并且no比新节点要小，就继续走
        while (temp.next != null && temp.next.no < newNode.no) {
            temp = temp.next;
        }
        // 目前停下来只有两种情况，一种是temp.next == null, 另一种是temp.next >= newNode.no
        // 如果下一个元素为空，则直接插入到temp的后面
        if (temp.next == null) {
            temp.next = newNode;
            newNode.pre = temp;
            return;
        }
        // 剩下的情况就是下一个元素不为空，则插入到temp跟下一个元素之间
        // 先插后面
        temp.next.pre = newNode;
        newNode.next = temp.next;

        // 再插前面
        temp.next = newNode;
        newNode.pre = temp;


    }

}

// 编写一个节点类型，每一个对象即为一个节点
class Node2 {
    // 数据域
    public int no;
    public String name;
    public String skill;

    // next域，指向下一个节点
    public Node2 next;
    public Node2 pre;

    public Node2() {
    }

    public Node2(int no, String name, String skill) {
        this.no = no;
        this.name = name;
        this.skill = skill;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", skill='" + skill + '\'' +
                '}';
    }
}

3.单向环形链表

1.题目

2.思路分析

3.首先构建一个环形链表

1.思路分析

2.代码

package com.sun.linkedlist;

/**
 * Description:
 *
 * @Author sun
 * @Create 2024/3/29 21:39
 * @Version 1.0
 */
public class Josephu {
    private Boy first = null;

    public static void main(String[] args) {
        Josephu josephu = new Josephu();
        josephu.addBoy(3);
        josephu.show();
    }
    /**
     * 根据数量添加小孩
     * @param nums
     */
    public void addBoy(int nums) {
        // 数据校验
        if (nums < 1) {
            System.out.println("输入数据有误！");
            return;
        }
        // 对第一个数据做出特殊处理
        Boy boy1 = new Boy(1);
        first = boy1;
        first.setNext(first);
        Boy curBoy = first;

        // 后续的数据循环处理
        for (int i = 2; i <= nums; i++) {
            Boy boy = new Boy(i);
            curBoy.setNext(boy);
            boy.setNext(first);
            curBoy = boy;
        }
    }
    // 遍历
    public void show() {
        Boy temp = first;

        while (true) {
            System.out.print(temp.getNo() + " ");
            if (temp.getNext() == first) {
                return;
            } else {
                temp = temp.getNext();
            }
        }
    }
}

// 创建节点对象
class Boy {
    private int no;
    private Boy next;

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

    public Boy getNext() {
        return next;
    }

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

    public int getNo() {
        return no;
    }
}

4.具体问题解决

1.思路分析

2.代码

    // 数小孩

    /**
     *
     * @param ranking 从第几个开始数
     * @param count 数几个
     * @param total 一共有几个小孩
     */
    public void countChild(int ranking, int count, int total) {
        // 进行简单校验
        if (ranking < 1 || ranking > total) {
            System.out.println("输入数据有误");
            return;
        }

        // 首先构建小孩
        addBoy(total);

        // 辅助指针helper指向最后一个元素
        Boy helper = first;
        while (true) {
            if (helper.getNext() == first) {
                break;
            }
            // 向后移动
            helper = helper.getNext();
        }

        // first 指向第ranking个小孩，helper也跟着移动 ranking - 1位
        for (int i = 0; i < ranking - 1; i++) {
            first = first.getNext();
            helper = helper.getNext();
        }

        // 循环出队
        while (true) {

            // 只剩一个小孩时直接出队，并退出循环
            if (helper == first) {
                System.out.println(helper.getNo() + "出队");
                break;
            }

            // first和helper移动count-1位
            for (int i = 0; i < count - 1; i++) {
                first = first.getNext();
                System.out.println(first.getNo() + "出队");
                helper = helper.getNext();
            }

            // 出队
            first = first.getNext();
            helper.setNext(first);
            System.out.println();
        }
    }