• 数据结构与算法2-链表

    链表的作用和重要性不是很清楚，只是目前面了三个公司，两个公司都让现场实现一个链表的小功能……

    单链表

    链表是有序的列表，在内存中的存储如下： ![在这里插入图片描述](https://img-blog.csdnimg.cn/0e8e8a2a378c4e4caee50caddf834bab.png)

    小结：
    （1）链表是以节点的方式来存储，是链式存储
    （2）每个节点包含data域，next域：指向下一个节点
    （3）链表的各个节点不一定是链式存储
    （4）链表分带头节点的链表和没有头结点的链表，根据实际的需求来确定

    这里就以水浒英雄为例，用数组模拟一个链表，并实现其中基本的功能。
    1.添加（创建）
    （1）先创建一个head头节点，作用是单链表的头
    （2）后面每添加一个节点，就直接添加到链表的最后

    2.遍历：
    通过一个辅助变量遍历，帮助遍历整个链表

    3.修改：
    （1）通过遍历找到该节点
    （2）temp.name=***
    temp.nickname=***

    4.删除节点：
    （1）找到需要删除节点的前一个节点temp
    （2）temp.next=temp.next.next
    （3）被删除的节点，将不会有其他引用指向，会被垃圾回收机制回收

    扩展功能

    5.求有效节点数目（不统计带头节点）
    定义一个辅助变量，遍历的时候自增就行了

    6.查找单链表中倒数第k个节点
    （1）编写一个方法，接收head节点，同时接收一个index
    （2）index表示倒数第index个节点
    （3）先把链表从头到尾遍历，得到链表的总长度（或者直接调用之前的方法，获取有效节点的数目）
    （4）得到size后，从链表的第一个开始遍历（size-index）个，就得到了
    （5）如果找到了，就返回该节点，否则返回null
    注：如果起始节点temp=head，则为（size+1-index）；如果起始节点temp=head.next，则为（size-index）

    7.单链表的反转
    （1）先定义一个节点reverseHead=new HeroNode();
    （2）从头到尾遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead的最前端
    （3）原来的链表的head.next=reverseHead.next

    8.从尾到头打印单链表（只是打印，不用翻转）
    栈（Stack）：先进先出
    可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进先出特点，就实现了逆序打印的结果。
    注：将链表反转后打印也可以，只是这样会改变链表的结构，故不建议这样做。

    下面是核心代码：

    class LinkedList {
    Node head = new Node(0, "");

    //添加节点（添加到最后
    public void add(Node node) {
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = node;
    }

    //添加节点，按顺序添加
    public void add2(Node node) {
        Node temp = head;
        boolean flag = false;
        while (true) {
            if (temp.next == null) {//遍历完元素
                flag = true;
                break;
            }
            if (temp.next.no > node.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            node.next = temp.next;
            temp.next = node;
        }
    }

    //2.遍历节点
    public void show() {
        Node temp = head.next;
        while (temp != null) {
            System.out.println(temp);
            temp = temp.next;
        }
    }

    //3.修改节点-根据编号no修改姓名name
    public void update(Node node) {
        Node temp = head.next;
        while (temp != null) {
            if (temp.no == node.no) {
                temp.name = node.name;
                break;
            }
            temp = temp.next;
        }
    }

    //4.删除节点
    public void del(int no) {
        Node temp = head;
        while (temp.next != null) {
            if (temp.next.no == no) {
                temp.next = temp.next.next;
                break;
            }
            temp = temp.next;
        }
    }

    //5.获取有效节点的数目
    public int getNums() {
        Node temp = head;
        int sum = 0;
        while (temp.next != null) {
            sum++;
            temp = temp.next;
        }
        return sum;
    }

    //6.查找单链表中第k个节点
    public Node getLastNode(int index) {//index表示倒数第几个节点，范围是1-总节点数
        if (index < 1 || index > getNums()) {
            System.out.println("输入参数有误，请检查");
            return null;
        }
        Node temp = head.next;
        int sum = getNums();
        for (int i = 0; i < sum - index; i++) {
            temp = temp.next;
        }
        return temp;
    }

    //7.单链表的反转
    public void reverse() {
        if (head.next == null || head.next.next==null) {//链表为空或只有一个元素
//            System.out.println("链表为空");
            return;
        }
        Node cur = head.next;
        Node next;
        Node newNode=new Node(0,"");
        while (cur != null) {
            next = cur.next;
            cur.next=newNode.next;
            newNode.next=cur;
            cur=next;//将cur后移
        }
        head.next=newNode.next;
    }

    //8.反向打印单链表
    public void printReverse() {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        Node temp = head.next;
        Stack stack = new Stack();
        while (temp != null) {
            stack.push(temp);
            temp = temp.next;
        }
        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }

    //得到当前链表的第一个节点
    public Node getFirst() {
        if (head.next == null) {
            System.out.println("链表为空");
            return null;
        }
        return head.next;
    }
}

class Node {
    int no;
    String name;
    Node next;

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

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154

    双向链表

    单向列表的缺点：
    （1）查找的方向只能是一个方向，而双向链表可以向前或向后查找
    （2）单向链表不能自我删除，需要依靠辅助节点。双向链表可以自我删除
    单链表的删除，不能找被删除的节点，而应找它上一个节点。
    在这里插入图片描述
    双向链表的常用功能：
    1.遍历
    和单链表的思路一样，不过有向后、向前两种遍历方式。
    2.添加（默认添加到双向链表最后）
    （1）先找到双向链表最后这个节点
    （2）temp.next=newHeroNode
    （3）newHeroNode.pre=temp;
    3.修改
    和原来单向链表一样
    4.删除
    （1）因为是双向链表，因此可以自我删除某个节点
    （2）直接找到要删除的这个节点temp
    （3）temp.pre.next=temp.next
    （4）temp.next.pre=temp.pre

    class DoubleLinedList {
    DoubleNode head = new DoubleNode(0, "");

    //1.遍历节点
    //后向遍历
    public void show() {
        if (head.next == null) {
            System.out.println("链表为空，无法进行后向遍历");
            return;
        }
        DoubleNode temp = head.next;
        while (temp != null) {
            System.out.println(temp);
            temp = temp.next;
        }
    }

    //前向遍历
    public void preShow() {
        if (head.next == null) {
            System.out.println("链表为空，无法进行前向遍历");
            return;
        }
        DoubleNode temp = head;
        while (temp.next != null) {
            temp = temp.next;//前指向最后的位置
        }
        while (true) {
            System.out.println(temp);
            if (temp.pre == head) {
                break;
            }
            temp = temp.pre;
        }
    }

    //2.添加节点
    //直接添加到最后
    public void add(DoubleNode node) {
        DoubleNode temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = node;
        node.pre = temp;
    }

    //按编号大小的顺序添加
    public void add2(DoubleNode node) {
        DoubleNode temp = head;
        boolean flag = false;
        while (true) {
            if (temp.next == null) {//里面一个节点都没有
                flag = true;
                break;
            }
            if (temp.next.no > node.no) {
                flag = true;
                break;
            }else if(temp.next.no==node.no){
                System.out.println("编号"+node.no+"已存在，添加失败");
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            if (temp.next != null) {//链表不为空
                node.next = temp.next;
                temp.next.pre = node;
                temp.next = node;
                node.pre = temp;
            } else {//链表为空
                temp.next = node;
                node.pre = head;
            }
        }
    }

    //3.修改节点
    public void update(DoubleNode node) {
        DoubleNode temp = head.next;
        while (temp != null) {
            if (temp.no == node.no) {
                temp.name = node.name;
            }
            temp = temp.next;
        }
    }

    //4.删除节点
    public void delNode(int no) {
        DoubleNode temp = head.next;
        while (temp != null) {
            if (temp.no == no) {
                if (temp.next != null) {
                    temp.next.pre = temp.pre;
                }
                temp.pre.next = temp.next;

            }
            temp = temp.next;
        }
    }
}

class DoubleNode {
    int no;
    String name;
    DoubleNode pre;
    DoubleNode next;

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

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124

    单向环形链表

    Josephu（约瑟夫、约瑟夫环）问题
    Josephu问题为：设编号为1,2,3,……,n的n个人围坐一圈，约定编号为k(1<=k<=n)的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
    在这里插入图片描述
    n=5: 共有5个人
    k=1: 从第一个人开始报数
    m=2: 数2下

    创建环形链表的思路：
    构建一个单向的环形链表思路
    1.先创建第一个节点，让first指向该节点，并形成环形
    2.后面每创建一个新节点，就把该节点加入到已有的环形链表中

    遍历环形链表
    1.先让一个辅助指针（变量）curBoy指向first节点
    2.然后通过一个while循环遍历该环形链表即可，curBoy.next=first结束

    节点出圈的思路
    根据用户输入，生成一个小孩出圈的顺序
    n=5,有5个人
    k=1,从第一个人开始报数
    m=2,数2下
    1.需要创建一个辅助指针（变量）helper，事先应该指向环形链表最后的那个节点
    补充：小孩报数前，先让first和helper移动k-1次
    2.当小孩报数时，让first和helper指针同时移动m-1次
    3.这时就可以将first指向的节点出圈
    first=first.next
    helper.next=first
    原来first指向的节点就没有任何引用，就会被回收

    最终出圈的顺序2-4-1-5-3

    具体代码如下：

    class CircleSingleLinkedList {
    Boy first = null;

    //添加节点——输入数目n，直接添加n个节点
    public void add(int num) {
        Boy curBoy = null;
        if (num < 1) {
            System.out.println("添加参数有误");
            return;
        }
        for (int i = 1; i <= num; i++) {
            Boy boy = new Boy(i);
            if (first == null) {//链表中没有元素
                first = boy;
                first.next = first;
                curBoy = first;
            } else {
                curBoy.next = boy;
                boy.next = first;
                curBoy = boy;

            }
        }
    }

    //遍历节点
    public void show() {
        if (first == null) {
            System.out.println("链表为空");
            return;
        }
        Boy curBoy = first;
        while (true) {
            System.out.println(curBoy);
            if (curBoy.next == first) {
                break;
            }
            curBoy = curBoy.next;
        }
    }
    //根据用户的输入，计算出小孩出圈的顺序

    /**
     * @param startNo  表示从几开始数
     * @param countNum 表示数几下
     * @param nums     表示链中本有多少节点
     */
    public void countBoy(int startNo, int countNum, int nums) {
        if (startNo < 1 || startNo > nums || nums < 1) {
            System.out.println("输入参数有误");
            return;
        }
        //创建一个辅助指针，指向curBoy前的一个节点
        Boy helper = first;
        //这里不想变动first，故找中间变量curBoy
        Boy curBoy = first;
        //移动helper，使之指向curBoy前的一个节点
        while (true) {
            helper = helper.next;
            if (helper.next == first) {
                break;
            }
        }
        //先移动到起始位置
        for(int i=0;i<startNo-1;i++){
            curBoy=curBoy.next;
            helper=helper.next;
        }
        while (true){
            //停止的条件就是链表中只剩下一个节点
            if(helper.next==helper){
                System.out.println(helper);
                break;
            }
            for(int i=0;i<countNum-1;i++){
                curBoy=curBoy.next;
                helper=helper.next;
            }
            System.out.println(curBoy);
            curBoy=curBoy.next;
            helper.next=curBoy;

        }
    }
}

class Boy {
    int no;
    Boy next;

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

    @Override
    public String toString() {
        return "Boy{" +
                "no=" + no +
                '}';
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
  • 相关阅读:
    计算机网络的OSI七层模型
    水文科技新仪器——地埋式积水探测器
    React的Redux的状态管理
    A Survey on Trustworthy Recommender Systems 25 Jul 2022
    字符串思维题练习 DAY4（CF 1849 C , CF 518A , CF1321C , CF1527 C)
    python数据容器
    年过中年危机，如果我再年轻十岁我会每天花几小时这样学习Java
    lua 如何在嵌入式Linux中与c语言结合
    信奥要学哪些数学知识 学信奥要不要先学python
    YB4618 具有充电前端过电压和过温保护功能，低压差充电前端 OVP 保护开关IC
  • 原文地址：https://blog.csdn.net/qq_45142938/article/details/126020579