XMD

无语

算法基础03：单向链表

发表于 更新于 分类于 ，
本文字数： 14k 阅读时长 ≈ 13 分钟

链表介绍

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

分为带头节点的链表和 不带头节点的链表

根据实际需求确定

应用实例

代码实现

添加

第一种，顺序添加

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
/**
 * 单项链表
 *
 * @author：XMD
 * @date: 8.8.22
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //先创建节点
        HeroNode heroNode1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode heroNode2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode heroNode3 = new HeroNode(3, "吴用", "智多星");
        HeroNode heroNode4 = new HeroNode(4, "林冲", "豹子头");

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

        //显式
        singleLinkedList.list();

    }

}

/**
 * 定义SingleLinkedList管理我们的英雄
 */
class SingleLinkedList {

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

    /**
     * 思路，当不考虑编号顺序时
     * 1.找到当前链表的最后节点
     * 2.将最后这个节点的next指向新的节点
     * @param heroNode
     */
    public void add(HeroNode heroNode){
        //因为head节点不能动，因此我们需要一个辅助变量temp
        HeroNode temp = head;
        //遍历链表，找到最后
        while (true){
            //找到链表的最后
            if (temp.next == null){
                break;
            }
            //如果没有找到，将temp后移
            temp = temp.next;
        }
        //当退出while循环时，temp就指向了链表的最后
        //将最后的结点的next指向新的节点
        temp.next = heroNode;
    }

    /**
     * 显式链表（遍历）
     */
    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;
        }
    }


}

/**
 * 定义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;
    }
    @Override
    public String toString() {
        return "no=" + no + ", name=" + name + ", nickname=" + nickname;
    }
}

打印信息

1
2
3
4
5
6
7
8
no=1, name=宋江, nickname=及时雨

no=4, name=林冲, nickname=豹子头

no=2, name=卢俊义, nickname=玉麒麟

no=3, name=吴用, 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
/**
 * 单项链表
 * 直接添加到链表尾部
 * 是根据插入顺序而排序，不会根据序号排序
 *
 * @author：
 * @date: 8.8.22
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //先创建节点
        HeroNode heroNode1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode heroNode2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode heroNode3 = new HeroNode(3, "吴用", "智多星");
        HeroNode heroNode4 = new HeroNode(4, "林冲", "豹子头");

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

        singleLinkedList.addByOrder(heroNode1);
        singleLinkedList.addByOrder(heroNode4);
        singleLinkedList.addByOrder(heroNode2);
        singleLinkedList.addByOrder(heroNode3);


        //显式
        singleLinkedList.list();

    }

}

/**
 * 定义SingleLinkedList管理我们的英雄
 */
class SingleLinkedList {

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

    /**
     * 第一种添加方式
     * 思路，当不考虑编号顺序时
     * 1.找到当前链表的最后节点
     * 2.将最后这个节点的next指向新的节点
     * @param heroNode
     */
    public void add(HeroNode heroNode){
        //因为head节点不能动，因此我们需要一个辅助变量temp
        HeroNode temp = head;
        //遍历链表，找到最后
        while (true){
            //找到链表的最后
            if (temp.next == null){
                break;
            }
            //如果没有找到，将temp后移
            temp = temp.next;
        }
        //当退出while循环时，temp就指向了链表的最后
        //将最后的结点的next指向新的节点
        temp.next = heroNode;
    }

    /**
     * 第二种添加方式，根据排名将英雄插入指定位置
     * 如果有这个排名，则添加失败，并给出提示
     * @param heroNode
     */
    public void addByOrder(HeroNode heroNode){
        //因为head节点不能动，因此我们需要一个辅助变量temp
        //因为单链表，因为我们找的temp是位于添加位置的前一个节点，是否插入不了
        HeroNode temp = head;
        //标志添加的编号是否存在，默认为false
        boolean flag = false;
        while (true){
            //说明到链表的最后了
            if (temp.next == null){
                break;
            }
            //位置找到，就在temp的后面插入
            if (temp.next.no > heroNode.no){
                break;
            }else if (temp.next.no == heroNode.no){
                //添加的节点已经存在
                flag = true;
                break;
            }
            //后移动
            temp = temp.next;
        }
        if (flag){
            System.out.println("节点已经存在");
        }else {
            heroNode.next = temp.next;
            temp.next = heroNode;
        }

    }

    

    /**
     * 显式链表（遍历）
     */
    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;
        }
    }


}

/**
 * 定义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;
    }
    @Override
    public String toString() {
        return "no=" + no + ", name=" + name + ", nickname=" + nickname;
    }
}

打印

1
2
3
4
no=1, name=宋江, nickname=及时雨
no=2, name=卢俊义, nickname=玉麒麟
no=3, name=吴用, nickname=智多星
no=4, name=林冲, 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
package com.algorithm.linkedlist;


/**
 * 单项链表
 * 直接添加到链表尾部
 * 是根据插入顺序而排序，不会根据序号排序
 *
 * @author：
 * @date: 8.8.22
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //先创建节点
        HeroNode heroNode1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode heroNode2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode heroNode3 = new HeroNode(3, "吴用", "智多星");
        HeroNode heroNode4 = new HeroNode(4, "林冲", "豹子头");

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

        singleLinkedList.addByOrder(heroNode1);
        singleLinkedList.addByOrder(heroNode4);
        singleLinkedList.addByOrder(heroNode2);
        singleLinkedList.addByOrder(heroNode2);
        singleLinkedList.addByOrder(heroNode3);

        //显式
        singleLinkedList.list();

        HeroNode newHeroNode4 = new HeroNode(2, "小炉子", "玉观音");
        singleLinkedList.update(newHeroNode4);

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

        singleLinkedList.list();
    }

}

/**
 * 定义SingleLinkedList管理我们的英雄
 */
class SingleLinkedList {

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

    /**
     * 第一种添加方式
     * 思路，当不考虑编号顺序时
     * 1.找到当前链表的最后节点
     * 2.将最后这个节点的next指向新的节点
     * @param heroNode
     */
    public void add(HeroNode heroNode){
        //因为head节点不能动，因此我们需要一个辅助变量temp
        HeroNode temp = head;
        //遍历链表，找到最后
        while (true){
            //找到链表的最后
            if (temp.next == null){
                break;
            }
            //如果没有找到，将temp后移
            temp = temp.next;
        }
        //当退出while循环时，temp就指向了链表的最后
        //将最后的结点的next指向新的节点
        temp.next = heroNode;
    }

    /**
     * 第二种添加方式，根据排名将英雄插入指定位置
     * 如果有这个排名，则添加失败，并给出提示
     * @param heroNode
     */
    public void addByOrder(HeroNode heroNode){
        //因为head节点不能动，因此我们需要一个辅助变量temp
        //因为单链表，因为我们找的temp是位于添加位置的前一个节点，是否插入不了
        HeroNode temp = head;
        //标志添加的编号是否存在，默认为false
        boolean flag = false;
        while (true){
            //说明到链表的最后了
            if (temp.next == null){
                break;
            }
            //位置找到，就在temp的后面插入
            if (temp.next.no > heroNode.no){
                break;
            }else if (temp.next.no == heroNode.no){
                //添加的节点已经存在
                flag = true;
                break;
            }
            //后移动
            temp = temp.next;
        }
        if (flag){
            System.out.println("节点已经存在");
        }else {
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }


    /**
     * 修改结点信息，根据no编号修改，no不能修改
     * 说明
     * 1.根据newHeroNode的no来修改即可
     * @param newHeroNode
     */
    public void  update(HeroNode newHeroNode){
        //判断是否为空
        if (head.next == null){
            System.out.println("链表为空");
            return;
        }

        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.println("没有找到");
        }

    }

    

    /**
     * 显式链表（遍历）
     */
    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;
        }
    }


}

/**
 * 定义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;
    }
    @Override
    public String toString() {
        return "no=" + no + ", name=" + name + ", nickname=" + nickname;
    }
}

打印

1
2
3
4
5
6
7
8
9
no=1, name=宋江, nickname=及时雨
no=2, name=卢俊义, nickname=玉麒麟
no=3, name=吴用, nickname=智多星
no=4, name=林冲, nickname=豹子头
<<<<<<<
no=1, name=宋江, nickname=及时雨
no=2, name=小炉子, nickname=玉观音
no=3, name=吴用, nickname=智多星
no=4, name=林冲, 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
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
package com.algorithm.linkedlist;


/**
 * 单项链表
 * 直接添加到链表尾部
 * 是根据插入顺序而排序，不会根据序号排序
 *
 * @author：XMD
 * @date: 8.8.22
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //先创建节点
        HeroNode heroNode1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode heroNode2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode heroNode3 = new HeroNode(3, "吴用", "智多星");
        HeroNode heroNode4 = new HeroNode(4, "林冲", "豹子头");

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

        singleLinkedList.addByOrder(heroNode1);
        singleLinkedList.addByOrder(heroNode4);
        singleLinkedList.addByOrder(heroNode2);
        singleLinkedList.addByOrder(heroNode2);
        singleLinkedList.addByOrder(heroNode3);

        //显式
        singleLinkedList.list();

        HeroNode newHeroNode4 = new HeroNode(2, "小炉子", "玉观音");
        singleLinkedList.update(newHeroNode4);

        System.out.println("<<<<<<<<<<<<<<<-");

        singleLinkedList.list();
        System.out.println("<<<<<<<<<<<<<<<-");

        singleLinkedList.delete(1);
        singleLinkedList.delete(3);
        singleLinkedList.list();
    }

}

/**
 * 定义SingleLinkedList管理我们的英雄
 */
class SingleLinkedList {

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

    /**
     * 第一种添加方式
     * 思路，当不考虑编号顺序时
     * 1.找到当前链表的最后节点
     * 2.将最后这个节点的next指向新的节点
     *
     * @param heroNode
     */
    public void add(HeroNode heroNode) {
        //因为head节点不能动，因此我们需要一个辅助变量temp
        HeroNode temp = head;
        //遍历链表，找到最后
        while (true) {
            //找到链表的最后
            if (temp.next == null) {
                break;
            }
            //如果没有找到，将temp后移
            temp = temp.next;
        }
        //当退出while循环时，temp就指向了链表的最后
        //将最后的结点的next指向新的节点
        temp.next = heroNode;
    }

    /**
     * 第二种添加方式，根据排名将英雄插入指定位置
     * 如果有这个排名，则添加失败，并给出提示
     *
     * @param heroNode
     */
    public void addByOrder(HeroNode heroNode) {
        //因为head节点不能动，因此我们需要一个辅助变量temp
        //因为单链表，因为我们找的temp是位于添加位置的前一个节点，是否插入不了
        HeroNode temp = head;
        //标志添加的编号是否存在，默认为false
        boolean flag = false;
        while (true) {
            //说明到链表的最后了
            if (temp.next == null) {
                break;
            }
            //位置找到，就在temp的后面插入
            if (temp.next.no > heroNode.no) {
                break;
            } else if (temp.next.no == heroNode.no) {
                //添加的节点已经存在
                flag = true;
                break;
            }
            //后移动
            temp = temp.next;
        }
        if (flag) {
            System.out.println("节点已经存在");
        } else {
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }


    /**
     * 修改结点信息，根据no编号修改，no不能修改
     * 说明
     * 1.根据newHeroNode的no来修改即可
     *
     * @param newHeroNode
     */
    public void update(HeroNode newHeroNode) {
        //判断是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }

        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.println("没有找到");
        }

    }


    /**
     * 删除节点
     * 1。head不能动，因此我们需要一个temp辅助节点找到需要删除的前一个节点
     * 2.说用我们在比较时，是temp。next.no 和需要删除的节点的no比较
     */
    public void delete(int no) {
        HeroNode temp = head;
        boolean boo = false;
        while (true) {
            if (temp.next == null) {
                //已经到最后
                break;
            }

            if (temp.next.no == no) {
                //找到需要删除的前一个节点
                boo = true;
                break;
            }
            temp = temp.next;
        }

        if (boo) {
            temp.next = temp.next.next;
        } else {
            System.out.println("没有找到这个节点");
        }
    }


    /**
     * 显式链表（遍历）
     */
    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;
        }
    }


}

/**
 * 定义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;
    }

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

打印

1
2
3
4
5
6
7
8
9
10
11
12
13
14
节点已经存在
no=1, name=宋江, nickname=及时雨
no=2, name=卢俊义, nickname=玉麒麟
no=3, name=吴用, nickname=智多星
no=4, name=林冲, nickname=豹子头
<<<<<<<<<<<<<<<-
no=1, name=宋江, nickname=及时雨
no=2, name=小炉子, nickname=玉观音
no=3, name=吴用, nickname=智多星
no=4, name=林冲, nickname=豹子头
<<<<<<<<<<<<<<<-
no=2, name=小炉子, nickname=玉观音
no=4, name=林冲, nickname=豹子头

-------------本文结束感谢您的阅读-------------

相关文章