线性结构-链表

发表于 | 更新于: | 分类于 |
字数统计: 3.5k | 阅读时长 ≈ 17

线性结构-链表

单链表的概念

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

image.png

小结:

  1. 链表是以节点的方式来存储,是链式存储
  2. 每个节点包含 data 域， next 域：指向下一个节点.(head节点不存放任何数据，作用是表示单链表头)
  3. 如图：发现链表的各个节点不一定是连续存储.
  4. 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

image.png

单链表的应用

待完成目标：

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

image.png

代码实现：

1.首先不考虑序号排序

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
//定义一个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.nickName = nickName;
        this.name = name;
    }

    @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
//定义一个单链表
class SingleLinkedList{
    //初始化一个头结点
    private HeroNode head = new HeroNode(0,"","");
    //添加节点到单链表,(当不考虑编号顺序是，直接添加到最后)
    public void addNode(HeroNode node){
        //找到最后的节点，lastNode.next == null,将这个最后的节点的next指向这个节点
        //使用辅助指针
        HeroNode temp = head;
        //遍历链表，找到最后
        while (true){
            if(temp.next==null){
                //说明到最后了
                break;
            }
            //如果没有找到最后，temp往后移
            temp = temp.next;
        }
        //当退出while，temp就指向了链表最后,将新的节点放到temp的next域
        temp.next = node;
    }

    //显示英雄链表
    public void showNode() {
        //判断链表是否为空
        if(head.next==null){
            System.out.println("链表为空");
            return;
        }
        //头结点不能动，需要一个辅助变量来遍历
        HeroNode temp = head.next;
        //判断是否到链表最后,这里的temp代表的是整个节点，为空说明不存在这个节点，就说明到最后了
        while (temp!=null){
            //输出这个节点的信息
            System.out.println(temp);
            //后移
            temp = temp.next;
        }

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//demo用例
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,"林冲","豹子头");
        HeroNode heroNode5 = new HeroNode(5,"张飞","黑旋风");
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addNode(heroNode1);
        singleLinkedList.addNode(heroNode2);
        singleLinkedList.addNode(heroNode3);
        singleLinkedList.addNode(heroNode4);
        singleLinkedList.addNode(heroNode5);
        singleLinkedList.showNode();
    }
}

打印结果：

1
2
3
4
5
HeroNode{no=1, name='宋江', nickName='及时雨'}
HeroNode{no=2, name='卢俊义', nickName='玉麒麟'}
HeroNode{no=3, name='吴用', nickName='智多星'}
HeroNode{no=4, name='林冲', nickName='豹子头'}
HeroNode{no=5, name='张飞', nickName='黑旋风'}

但是如果将1号和4号调换顺序之后就会出现问题（顺序会变成42315），毕竟没有排序

现在进行添加时自动排序部分代码的编写：

思路：

1.通过辅助变量找到新添加的位置

2.新的节点.next = 辅助变量.next

3.辅助变量.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
package top.ryan.linkedlist;

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,"林冲","豹子头");
        HeroNode heroNode5 = new HeroNode(5,"张飞","黑旋风");
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        SingleLinkedList singleLinkedList1 = new SingleLinkedList();
        singleLinkedList.addNode(heroNode1);
        singleLinkedList.addNode(heroNode3);
        singleLinkedList.addNode(heroNode2);
        singleLinkedList.addNode(heroNode5);
        singleLinkedList.addNode(heroNode4);
        singleLinkedList.showNode();
        System.out.println("===========================================");
        singleLinkedList1.addNodeInOrder(heroNode1);
        singleLinkedList1.addNodeInOrder(heroNode3);
        singleLinkedList1.addNodeInOrder(heroNode2);
        singleLinkedList1.addNodeInOrder(heroNode5);
        singleLinkedList1.addNodeInOrder(heroNode4);
        singleLinkedList1.showNode();
    }
}

//定义一个单链表
class SingleLinkedList{
    //初始化一个头结点
    private HeroNode head = new HeroNode(0,"","");
    //添加节点到单链表,(当不考虑编号顺序是，直接添加到最后)
    public void addNode(HeroNode node){
        //找到最后的节点，lastNode.next == null,将这个最后的节点的next指向这个节点
        //使用辅助指针
        HeroNode temp = head;
        //遍历链表，找到最后
        while (true){
            if(temp.next==null){
                //说明到最后了
                break;
            }
            //如果没有找到最后，temp往后移
            temp = temp.next;
        }
        //当退出while，temp就指向了链表最后,将新的节点放到temp的next域
        temp.next = node;
    }

    public void addNodeInOrder(HeroNode node){
        //找到最后的节点，lastNode.next == null,将这个最后的节点的next指向这个节点
        //使用辅助指针
        HeroNode temp = head;
        //遍历链表，找到最后
        while (true){
            if(temp.next==null){
                //说明到最后了
                break;
            }
            if (temp.next.no > node.no) {
                //找到位置了
                break;
            }
            //如果没有找到最后，temp往后移
            temp = temp.next;
        }
        //当退出while，temp找到了位置，将这个节点的next指向temp.next,然后temp.next 在指向node
        node.next = temp.next;
        temp.next = node;

    }

    //显示英雄链表
    public void showNode() {
        //判断链表是否为空
        if(head.next==null){
            System.out.println("链表为空");
            return;
        }
        //头结点不能动，需要一个辅助变量来遍历
        HeroNode temp = head.next;
        //判断是否到链表最后,这里的temp代表的是整个节点，为空说明不存在这个节点，就说明到最后了
        while (temp!=null){
            //输出这个节点的信息
            System.out.println(temp);
            //后移
            temp = temp.next;
        }

    }
}


//定义一个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.nickName = nickName;
        this.name = name;
    }

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

打印结果：

1
2
3
4
5
6
7
8
9
10
11
HeroNode{no=1, name='宋江', nickName='及时雨'}
HeroNode{no=3, name='吴用', nickName='智多星'}
HeroNode{no=2, name='卢俊义', nickName='玉麒麟'}
HeroNode{no=5, name='张飞', nickName='黑旋风'}
HeroNode{no=4, name='林冲', nickName='豹子头'}
===========================================
HeroNode{no=1, name='宋江', nickName='及时雨'}
HeroNode{no=2, name='卢俊义', nickName='玉麒麟'}
HeroNode{no=3, name='吴用', nickName='智多星'}
HeroNode{no=4, name='林冲', nickName='豹子头'}
HeroNode{no=5, name='张飞', nickName='黑旋风'}

问题又来了，在这里可以添加重复的数据，如何可以控制他不能添加重复数据，再有重复数据时给与友好提示呢，只需要更改一下addNodeInorder这个方法.

使用一个标识flag,来判断链表是否已经存在这个需要添加进链表的值就行了

代码：

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
public void addNodeInOrder(HeroNode node){
       //找到最后的节点，lastNode.next == null,将这个最后的节点的next指向这个节点
       //使用辅助指针
       HeroNode temp = head;
       boolean flag = false;
       //遍历链表，找到最后
       while (true){
           if(temp.next==null){
               //说明到最后了
               break;
           }
           if (temp.next.no > node.no) {
               //找到位置了
               break;
           }else if(temp.next.no == head.no){
               flag = true;
               break;
           }
           //如果没有找到最后，temp往后移
           temp = temp.next;
       }
       if(flag){
           throw new RuntimeException("数据已经添加过了，不能重复添加");
       }
       //当退出while，temp找到了位置，将这个节点的next指向temp.next,然后temp.next 在指向node
       node.next = temp.next;
       temp.next = node;

   }

总的代码：

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
package top.ryan.linkedlist;

import javax.xml.soap.Node;

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,"林冲","豹子头");
        HeroNode heroNode5 = new HeroNode(5,"张飞","黑旋风");
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        SingleLinkedList singleLinkedList1 = new SingleLinkedList();
        singleLinkedList.addNode(heroNode1);
        singleLinkedList.addNode(heroNode3);
        singleLinkedList.addNode(heroNode2);
        singleLinkedList.addNode(heroNode5);
        singleLinkedList.addNode(heroNode4);
        singleLinkedList.showNode();
        System.out.println("===========================================");
        singleLinkedList1.addNodeInOrder(heroNode1);
        singleLinkedList1.addNodeInOrder(heroNode3);
        singleLinkedList1.addNodeInOrder(heroNode2);
        singleLinkedList1.addNodeInOrder(heroNode5);
        singleLinkedList1.addNodeInOrder(heroNode4);
        singleLinkedList1.showNode();
        System.out.println("===========================================");
        HeroNode heroNode6 = new HeroNode(1,"宋江","及时雨1111");
        singleLinkedList1.updateNode(heroNode6);
        singleLinkedList1.showNode();
        System.out.println("===========================================");
        HeroNode node = new HeroNode(3,"","");
        singleLinkedList1.deleteNode(node);
        singleLinkedList1.showNode();
    }
}

//定义一个单链表
class SingleLinkedList{
    //初始化一个头结点
    private HeroNode head = new HeroNode(0,"","");
    //添加节点到单链表,(当不考虑编号顺序是，直接添加到最后)
    public void addNode(HeroNode node){
        //找到最后的节点，lastNode.next == null,将这个最后的节点的next指向这个节点
        //使用辅助指针
        HeroNode temp = head;
        //遍历链表，找到最后
        while (true){
            if(temp.next==null){
                //说明到最后了
                break;
            }
            //如果没有找到最后，temp往后移
            temp = temp.next;
        }
        //当退出while，temp就指向了链表最后,将新的节点放到temp的next域
        temp.next = node;
    }

    public void addNodeInOrder(HeroNode node){
        //找到最后的节点，lastNode.next == null,将这个最后的节点的next指向这个节点
        //使用辅助指针
        HeroNode temp = head;
        boolean flag = false;
        //遍历链表，找到最后
        while (true){
            if(temp.next==null){
                //说明到最后了
                break;
            }
            if (temp.next.no > node.no) {
                //找到位置了
                break;
            }else if(temp.next.no == head.no){
                flag = true;
                break;
            }
            //如果没有找到最后，temp往后移
            temp = temp.next;
        }
        if(flag){
            throw new RuntimeException("数据已经添加过了，不能重复添加");
        }
        //当退出while，temp找到了位置，将这个节点的next指向temp.next,然后temp.next 在指向node
        node.next = temp.next;
        temp.next = node;

    }

    //显示英雄链表
    public void showNode() {
        //判断链表是否为空
        if(head.next==null){
            System.out.println("链表为空");
            return;
        }
        //头结点不能动，需要一个辅助变量来遍历
        HeroNode temp = head.next;
        //判断是否到链表最后,这里的temp代表的是整个节点，为空说明不存在这个节点，就说明到最后了
        while (temp!=null){
            //输出这个节点的信息
            System.out.println(temp);
            //后移
            temp = temp.next;
        }

    }

    //修改英雄，根据no
    public void updateNode(HeroNode node){
        //判空
        if(head.next==null){
            System.out.println("链表为空");
        }
        //定义辅助变量
        HeroNode temp = head.next;
        //表示未找到该节点
        boolean flag = false;
        while (temp!=null){
            if(temp.no == node.no){
                //找到了
                flag = true;
                break;
            }

            //后移
            temp = temp.next;
        }
        if(!flag){
            System.out.printf("没找到%d的节点，不能修改\n",node.no);
        }
        temp.nickName = node.nickName;
        temp.name = node.name;
    }

    /**
     * 删除节点
     * @param node
     */
    public void deleteNode(HeroNode node){
        //判空
        if(head.next==null){
            System.out.println("链表为空");
            return;
        }
        //定义辅助变量
        HeroNode temp = head;
        boolean flag = false;
        while (temp.next!=null){
             if(temp.next.no == node.no){
                 flag = true;
                 break;
             }
            //后移
            temp = temp.next;
        }
        if(!flag){
            System.out.printf("没有编号为%d的该节点",node.no);
        }
        //删除节点
        temp.next = temp.next.next;
    }
}


//定义一个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.nickName = nickName;
        this.name = name;
    }

    @Override
    public String  toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}
-------------本文结束感谢您的阅读-------------