数据结构：单链表和双向链表_单双向链表

1、链表

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

小结：

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

2、单链表的应用

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

1. 第一种方法在添加英雄时，直接添加到链表的尾部

2. 第二种方式在添加英雄时，根据排名将英雄插入到指定位置(如果有这个排名，则添加失败，并给出提示）思路的分析示意图：

3. 修改节点功能

思路(1)先找到该节点，通过遍历，(2) temp.name= newheroNode name; temp. nickname= newheroNode.nickname

4. 删除节点

思路分析示意图：

3、代码实现

package com.jl.linkedlist;

/**
 * Create with IntelliJ IDAE
 *
 * @Author: JINLEI
 * @Description: 单链表应用—单链表实现水浒英雄排行榜
 *               1）完成对英雄人物的增删改查操作
 *               2）添加英雄时，直接添加到链表尾部
 *               3）添加英雄时，根据排名将英雄插入到指定的位置
 * @Date: 2022/3/10
 * @Time: 9:34
 **/
public class SingleLinkedListDemo {
    public static void main(String[] args) {

        //测试
        //创捷节点
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");

        //创建链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        //加入
//        singleLinkedList.add(hero1);
//        singleLinkedList.add(hero2);
//        singleLinkedList.add(hero3);
//        singleLinkedList.add(hero4);

        //加入按照编号的顺序
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero3);
        singleLinkedList.addByOrder(hero2);

        //显示
        singleLinkedList.list();

        //测试修改节点
        HeroNode newHeroBNode = new HeroNode(2, "小鹿", "玉麒麟！！！");
        singleLinkedList.update(newHeroBNode);
        System.out.println("修改后的情况~~");
        //显示
        singleLinkedList.list();

        //删除一个节点
        singleLinkedList.delete(1);
        singleLinkedList.delete(2);
        singleLinkedList.delete(4);
        singleLinkedList.delete(3);
        System.out.println("删除后的链表情况");
        //显示
        singleLinkedList.list();
    }
}

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

    //添加节点到单链表
    //1、找到当前链表的最后一个节点
    //2、将最后的一个节点的的next指向新的节点
    public void add(HeroNode heroNode){

        //因为head节点不能动， 因此我们需要一个辅助变量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){

        //头节点不能动，通过辅助变量帮助我们找到添加的位置
        //因为单链表我们找到的temp是位于添加位置的前一个节点，否则插入不了
        HeroNode temp = head;
        boolean flag = false;//标志添加的编号是否存在，默认为false
        while (true){
            if (temp.next == null){//temp在链表最后
                break;
            }
            if (temp.next.no > heroNode.no){//位置找到就在temp后面插入
                break;
            }else if (temp.next.no == heroNode.no){//说明希望添加的heroNode的编号存在
                flag = true;//说明编号存在
                break;
            }
            temp = temp.next;//后移
        }
        //判断flag的值
        if (flag){//不能添加，说明编号存在
            System.out.printf("准备插入的英雄的编号%d已经存在，不能加入\n",heroNode.no);
        }else {
            //插入到链表中，temp的后面
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    //修改节点的信息，根据no编号来修改，即no编号不能改
    public void update(HeroNode newHeroNode){
        //判断是否为空
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }
        //找到需要修改的节点，根据no编号
        //定义一个辅助变量
        HeroNode temp = head.next;
        boolean flag = false;//表示是否找到该节点
        while (true){
            if (temp == null){
                break;//已经遍历完链表
            }
            if (temp.no == newHeroNode.no){
                //找到
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //根据flag判断是否找到要修改的节点
        if (flag){
            temp.name = newHeroNode.name;
            temp.nickname = newHeroNode.nickname;
        }else {
            System.out.printf("没有找到编号%d的节点,不能修改\n",newHeroNode.no);
        }
    }
    //删除节点
    //head不动 需要一个辅助节点找到待删除节点的前一个节点
    //比较时，是temp.next.no和需要删除的节点的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;//temp后移，遍历
        }
        if (flag){
            //删除
            temp.next = temp.next.next;
        }else {
            System.out.printf("要删除的%d节点不存在",no);
        }
    }

    //显示链表（遍历）
    public void list(){
        //判断链表是否为空
        if (head.next == null){
            System.out.println("链表为空");
        }
        //因为头节点不能动，需要一个辅助变量来遍历
        HeroNode temp = head.next;
        while (true){
            //判断是否到链表最后
            if (temp == null){
                break;
            }
            //输出节点的信息
            System.out.println(temp);
            //将temp后移
            temp = temp.next;
        }
    }
}

//定义一个HeroNode  每个HeroNode对象就是一个节点
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 + '\'' +
                '}';
    }
}

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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215

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

• 获取单链表的节点个数
• 查找单链表的倒数第k个节点
• 单链表的反转
• 从尾到头打印单链表

package com.jl.linkedlist;

import java.util.Stack;

/**
 * Create with IntelliJ IDAE
 *
 * @Author: JINLEI
 * @Description: 常见的单链表的面试题
 * @Date: 2022/3/12
 * @Time: 16:10
 **/
public class LinkedList {

    //获取单链表的节点个数（如果是带头节点们需要不统计头节点）
    public static int getLength(HeroNode head){
        if (head.next == null){
            return 0;
        }
        int length = 0;
        HeroNode cur = head.next;
        while (cur != null){
            length++;
            cur = cur.next;
        }
        return length;
    }

    //查找单链表的倒数第k个节点
    public static HeroNode findLastIndexNode(HeroNode head,int index){
        //判断链表为空
        if (head.next == null){
            return null;
        }
        //第一个遍历得到链表的长度（节点的个数）
        int size = getLength(head);
        //第二次遍历size-index位置，就是我们倒数的第k个节点
        //先做一个index 的校验
        if (index < 0 || index > size){
            return null;
        }
        //定义一个辅助变量，for循环倒数的index
        HeroNode cur = head.next;
        for (int i = 0; i < size - index; i++) {
            cur = cur.next;
        }
        return cur;
    }

    //单链表的反转
    public static void reversetList(HeroNode head){
        //如果当前的链表为空或者只有一个节点无需反转直接返回
        if(head.next == null || head.next.next == null){
            return;
        }
        //定义一个辅助的变量 来遍历原来的链表
        HeroNode cur = head.next;
        HeroNode next = null;//指向当前节点cur的下一个节点
        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;
    }

    //从尾到头打印单链表
    //利用栈实现
    public static void reversePrint(HeroNode head){
        if (head.next == null){
            return;//空链表不打印
        }
        Stack<HeroNode> stack = new Stack<HeroNode>();
        HeroNode cur = head.next;
        //将链表中的节点压入栈
        while (cur != null){
            stack.push(cur);
            cur = cur.next;//cur后移压入下一个节点
        }
        //将栈中的节点打印  pop出栈
        System.out.println(stack.pop());
    }
}

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

5、约瑟夫问题

Joseph问题为:设编号为1,2,…n的n个人围坐一圏,约定编号为k(1<-ks=n)的人从1开始报数,数到m的那个人出列,它的下一位又从1开始报数,数到m的那个人又出列,依次类推,直到所有人出列为止,由此产生一个出队编号的序列

创建环形链表的思路图解：

小孩出圈的思路图解：

代码实现

package josephu;

/**
 * Create with IntelliJ IDAE
 *
 * @Author: JINLEI
 * @Description: 约瑟夫问题
 * @Date: 2022/3/16
 * @Time: 13:46
 **/
public class JosepHu {
    public static void main(String[] args) {

        //测试
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        //加入5个小孩
        circleSingleLinkedList.addBoy(5);
        circleSingleLinkedList.showBoy();

        //测试小孩出圈
        circleSingleLinkedList.countBoy(1,2,5);

    }
}

//创建一个环形的单向链表
class CircleSingleLinkedList{
    //创建一个first节点
    private Boy first = null;
    //添加小孩节点，构建环形链表
    public void addBoy(int nums){
        //nums做数据校验
        if (nums < 1){
            System.out.println("nums的值不正确");
            return;
        }
        Boy curBoy = null;//辅助指针，帮助构建环形链表
        //for循环创建环形链表
        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 showBoy(){
        //判断链表是否为空
        if (first == null){
            System.out.println("链表为空");
            return;
        }
        //因为first不能动需要一个辅助指针完成遍历
        Boy curBoy = first;
        while (true){
            System.out.printf("小孩的编号%d \n",curBoy.getNo());
            if (curBoy.getNext() == first){//说明已经遍历完毕
                break;
            }
            curBoy = curBoy.getNext();//curBoy后移
        }
    }

    /**
     * 根据用户的输入，计算出小孩出圈的顺序
     * @param startNo 表示从第几个小孩开始数数
     * @param countNum 表示数几下
     * @param nums 表示最初有多少小孩在圈中
     */
    public void countBoy(int startNo,int countNum,int nums){
        //先对数据校验
        if (first == null || startNo < 1 || startNo > nums){
            System.out.println("参数输入有误，请重新输入");
            return;
        }
        //创建一个辅助指针，帮助小孩出圈
        Boy helper = first;
        //需要创建一个辅助变量helper指向环形链表的最后一个节点
        while (true){
            if (helper.getNext() == first){//说明helper指向了最后的小孩节点
                break;
            }
            helper = helper.getNext();
        }
        //小孩报数前，先让first和helper移动k-1次
        for (int i = 0; i < startNo - 1; i++) {
            first = first.getNext();
            helper = helper.getNext();
        }
        //当小孩报数时，让first和helper指针同时移动m-1次然后出圈
        //循环操作，直到圈中只有一个节点
        while (true){
            if (helper == first){
                 break;
            }
            //让first和helper指针同时移动countNum-1
            for (int i = 0; i < countNum - 1; i++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            //此时first指向的节点就是要出圈的节点
            System.out.printf("小孩%d出圈\n",first.getNo());
            //first出圈
            first = first.getNext();
            helper.setNext(first);
        }
        System.out.printf("最后留在圈中的小孩编号%d\n",first.getNo());
    }
}

//创建一个boy类，表示一个节点
class Boy{
    private int no;//编号
    private Boy next;//指向下一个节点默认为null

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

    public int getNo() {
        return no;
    }

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

    public Boy getNext() {
        return next;
    }

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

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

6、双向链表应用

双向链表的操作分析

使用带head头的双向链表实现-水浒英雄排行榜
管理单向链表的缺点分析：

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

代码实现

package com.jl.linkedlist;

/**
 * Create with IntelliJ IDAE
 *
 * @Author: JINLEI
 * @Description: 双向链表的应用
 * @Date: 2022/3/13
 * @Time: 20:04
 **/
public class DoubleLinkedListDemo {
    public static void main(String[] args) {
        System.out.println("双向链表的测试");

        HeroNode2 hero1 = new HeroNode2(1, "宋江", "及时雨");
        HeroNode2 hero2 = new HeroNode2(2, "卢俊义", "玉麒麟");
        HeroNode2 hero3 = new HeroNode2(3, "吴用", "智多星");
        HeroNode2 hero4 = new HeroNode2(4, "林冲", "豹子头");

        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        doubleLinkedList.add(hero1);
        doubleLinkedList.add(hero2);
        doubleLinkedList.add(hero3);
        doubleLinkedList.add(hero4);

        doubleLinkedList.list();

        HeroNode2 newHeroNode = new HeroNode2(4,"公孙胜","入云龙");
        doubleLinkedList.update(newHeroNode);
        System.out.println("修改后的链表情况");
        doubleLinkedList.list();

        //删除
        doubleLinkedList.delete(3);
        System.out.println("删除后的链表情况");
        doubleLinkedList.list();

    }
}
//创建一个双向链表的类
class DoubleLinkedList{
    //先初始化一个头节点，头节点不动，不存放具体的数据
    private HeroNode2 head = new HeroNode2(0,"","");

    //返回头节点
    public HeroNode2 getHead(){
        return head;
    }

    //遍历双向链表的方法
    //显示链表（遍历）
    public void list(){
        //判断链表是否为空
        if (head.next == null){
            System.out.println("链表为空");
        }
        //因为头节点不能动，需要一个辅助变量来遍历
        HeroNode2 temp = head.next;
        while (true){
            //判断是否到链表最后
            if (temp == null){
                break;
            }
            //输出节点的信息
            System.out.println(temp);
            //将temp后移
            temp = temp.next;
        }
    }

    //添加一个节点到双向链表的最后
    public void add(HeroNode2 heroNode){

        //因为head节点不能动， 因此我们需要一个辅助变量temp
        HeroNode2 temp = head;
        //遍历链表找到最后
        while (true){
            //找到链表的最后
            if (temp.next == null){
                break;
            }
            //如果没有找到,将temp后移
            temp = temp.next;
        }
        //退出while循环时temp指向了链表的最后
        //形成一个双向链表
        temp.next = heroNode;
        heroNode.pre = temp;
    }

    //修改双向链表的一个节点
    public void update(HeroNode2 newHeroNode){
        //判断是否为空
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }
        //找到需要修改的节点，根据no编号
        //定义一个辅助变量
        HeroNode2 temp = head.next;
        boolean flag = false;//表示是否找到该节点
        while (true){
            if (temp == null){
                break;//已经遍历完链表
            }
            if (temp.no == newHeroNode.no){
                //找到
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //根据flag判断是否找到要修改的节点
        if (flag){
            temp.name = newHeroNode.name;
            temp.nickname = newHeroNode.nickname;
        }else {
            System.out.printf("没有找到编号%d的节点,不能修改\n",newHeroNode.no);
        }
    }

    //删除双向链表的节点
    //直接找到要删除的节点，找到后自我删除
    public void delete(int no){
        if (head.next == null){
            System.out.println("链表为空无法删除");
        }
        HeroNode2 temp = head.next;
        boolean flag = false;//标志是否找到待删除的节点的位置
        while (true){
            if (temp == null){//找到链表的最后
                break;
            }
            if (temp.no == no){
                //找到待删除节点的前一个节点temp
                flag = true;
                break;
            }
            temp = temp.next;//temp后移，遍历
        }
        if (flag){//找到
            //删除
            temp.pre.next = temp.next;
            if (temp.next !=null){
                temp.next.pre = temp.pre;
            }
        }else {
            System.out.printf("要删除的%d节点不存在",no);
        }
    }
}
//定义一个HeroNode2  每个HeroNode对象就是一个节点
class HeroNode2{
    public int no;
    public String name;
    public String nickname;
    public HeroNode2 next;//指向下一个节点默认为null
    public HeroNode2 pre;//指向前一个节点默认为null

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

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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177