1. 链表（Linked List）介绍

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

1）链表是以节点的方式来存储，是链式存储。

2）每个节点包含data域，next域：指向下一个节点。

3）链表的各个节点不一定是连续存储。

4）链表分带头节点的链表和不带头节点的链表，根据实际的需求来确定。

  • 单链表（带头节点）的逻辑结构示意图如下：

2. 单链表的增删改查

【注】下面的所有单链表操作均是使用带 head 头的单向链表实现 - 实现对水浒英雄排行榜管理，完成对英雄人物的增删改查。

2.1 链表添加操作

2.1.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
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
package com.self.linkedlist;

public class SingleLinkedListAdd {

    public static void main(String[] args) {
        //进行测试
        //创建节点
        HeroNodeAdd hero1 = new HeroNodeAdd(1, "宋江", "及时雨");
        HeroNodeAdd hero2 = new HeroNodeAdd(2, "卢俊义", "玉麒麟");
        HeroNodeAdd hero3 = new HeroNodeAdd(3, "吴用", "智多星");
        HeroNodeAdd hero4 = new HeroNodeAdd(4, "林冲", "豹子头");

        //创建链表
        SingleLinkedList_add singleLinkedList = new SingleLinkedList_add();
        //将节点加入
        singleLinkedList.add(hero1);
        singleLinkedList.add(hero2);
        singleLinkedList.add(hero3);
        singleLinkedList.add(hero4);

        //显示链表
        singleLinkedList.showLinkedList();

    }
}

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

    //初始化头结点，一般头结点不能更改，要不然之后的节点数据将找不到
    private HeroNodeAdd head = new HeroNodeAdd(0,"","");

    //添加节点到单向链表（找到链表的最后一个节点，让它指向新添加的节点，并将其next的null去掉）
    public void add(HeroNodeAdd heroNodeAdd){

        //因为head节点不能动，因此我们需要一个辅助遍历变量 temp
        HeroNodeAdd temp = head;
        //遍历链表，找到最后的节点
        while (true){
            //链表的最后一个节点
            if(temp.next == null){
                break;
            }
            //如果没有找到最后，就将temp后移
            temp = temp.next;
        }
        //当退出了while循环时，temp就已经指向了链表的最后一个节点
        //然后将最后这个的节点指向新添加的节点
        temp.next = heroNodeAdd;
    }

    //显示链表【遍历】
    public void showLinkedList(){
        //判断链表是否为空
        if(head.next == null){
            System.out.println("链表为空~");
            return ;
        }
        //因为head节点不能动，所以定义辅助变量进行遍历
        //这里的 temp 表示链表的最后一个节点.next
        HeroNodeAdd temp = head.next;
        while (true){
            //判断是否到链表最后
            if(temp == null){
                break;
            }
            //输出节点的信息
            System.out.println(temp);
            //将temp后移（输出一个节点信息后，temp后移才能输出下一个节点）
            temp = temp.next;
        }
    }
}

//定义一个HeroNode，每一个HeroNode对象就是一个节点
class HeroNodeAdd{

    public int no;
    public String name;
    public String nickname;
    public HeroNodeAdd next;

    //构造器
    public HeroNodeAdd(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

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

效果截图：

2.1.2 根据编号添加到指定位置

思路分析：

代码实现：

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
package com.self.linkedlist;

public class SingleLinkedListAddOrder {

    public static void main(String[] args) {

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

        //创建链表
        SingleLinkedList_addOrder singleLinkedList = new SingleLinkedList_addOrder();
        //将节点加入
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero3);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero2);


        //显示链表
        singleLinkedList.showLinkedList();


    }
}

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

    //初始化头结点，一般头结点不能更改，要不然之后的节点数据将找不到
    private HeroNodeAddOrder head = new HeroNodeAddOrder(0,"","");

    //第二种方式在添加英雄时，根据排名将英雄插入到指定位置
    // (如果有这个排名，则添加失败，并给出提示)
    public void addByOrder(HeroNodeAddOrder heroNodeAddOrder){
        //因为头结点不能动，因此我们仍然通过一个辅助变量来帮助找到添加的位置
        //注意：单链表要找的是添加位置的前一个节点，若是找到了后一个节点将无法添加
        HeroNodeAddOrder temp = head;
        boolean flag = false; //标识添加的编号是否存在，默认为false
        while (true){
            if (temp.next == null){ //说明temp已经到了链表的最后
                break;
            }
            if(temp.next.no > heroNodeAddOrder.no){ //找到位置，就在temp的后面插入（即：新添加的节点需要在temp和temp.next中插入）
                break;
            }else if (temp.next.no == heroNodeAddOrder.no){ //说明需要添加的节点编号已经存在
                flag = true; //编号存在
                break;
            }
            temp = temp.next;//若找不到，temp后移
        }
        //判断flag 的值
        if(flag){ //不能添加，编号已经存在
            System.out.printf("准备插入的英雄的编号 %d 已经存在,不能再次添加\n",heroNodeAddOrder.no);
        }else {
            //插入到链表中，temp的后面
            heroNodeAddOrder.next = temp.next;
            temp.next = heroNodeAddOrder;
        }
    }

    //显示链表【遍历】
    public void showLinkedList(){
        //判断链表是否为空
        if(head.next == null){
            System.out.println("链表为空~");
            return ;
        }
        //因为head节点不能动，所以定义辅助变量进行遍历
        //这里的 temp 表示链表的最后一个节点.next
        HeroNodeAddOrder temp = head.next;
        while (true){
            //判断是否到链表最后
            if(temp == null){
                break;
            }
            //输出节点的信息
            System.out.println(temp);
            //将temp后移（输出一个节点信息后，temp后移才能输出下一个节点）
            temp = temp.next;
        }
    }
}

//定义一个HeroNode，每一个HeroNode对象就是一个节点
class HeroNodeAddOrder{

    public int no;
    public String name;
    public String nickname;
    public HeroNodeAddOrder next;

    //构造器
    public HeroNodeAddOrder(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    //toString

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

效果截图：

2.2 链表修改操作

思路分析：

  1. 通过遍历找到需要修改的节点

  2. temp.name = heroNodeUpdate.name;temp.nickname = heroNodeUpdate.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

    代码实现：

    ```java
    package com.self.linkedlist;

    public class SingleLinkedListUpdate {

        public static void main(String[] args) {
            //进行测试
            //创建节点
            HeroNodeUpdate hero1 = new HeroNodeUpdate(1, "宋江", "及时雨");
            HeroNodeUpdate hero2 = new HeroNodeUpdate(2, "卢俊义", "玉麒麟");
            HeroNodeUpdate hero3 = new HeroNodeUpdate(3, "吴用", "智多星");
            HeroNodeUpdate hero4 = new HeroNodeUpdate(4, "林冲", "豹子头");

            //创建链表
            SingleLinkedList_update singleLinkedList = new SingleLinkedList_update();
            //将节点加入
            singleLinkedList.add(hero1);
            singleLinkedList.add(hero2);
            singleLinkedList.add(hero3);
            singleLinkedList.add(hero4);

            //测试修改节点信息
            System.out.println("修改前:");
            singleLinkedList.showLinkedList();

            HeroNodeUpdate newHeroNode = new HeroNodeUpdate(2, "小卢", "玉麒麟~~");
            singleLinkedList.update(newHeroNode);

            System.out.println("修改后:");
            singleLinkedList.showLinkedList();
        }
    }

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

        //初始化头结点，一般头结点不能更改，要不然之后的节点数据将找不到
        private HeroNodeUpdate head = new HeroNodeUpdate(0,"","");

        //添加节点到单向链表（找到链表的最后一个节点，让它指向新添加的节点，并将其next的null去掉）
        public void add(HeroNodeUpdate heroNodeUpdate){

            //因为head节点不能动，因此我们需要一个辅助遍历变量 temp
            HeroNodeUpdate temp = head;
            //遍历链表，找到最后的节点
            while (true){
                //链表的最后一个节点
                if(temp.next == null){
                    break;
                }
                //如果没有找到最后，就将temp后移
                temp = temp.next;
            }
            //当退出了while循环时，temp就已经指向了链表的最后一个节点
            //然后将最后这个的节点指向新添加的节点
            temp.next = heroNodeUpdate;
        }


        /**
         * 修改节点的信息，根据no编号进行修改，即no不能进行修改
         * 说明：
         *      1.heroNode的no来修改即可
         * @param heroNodeUpdate
         */
        public void update(HeroNodeUpdate heroNodeUpdate){
            if(head.next == null){
                System.out.println("链表为空~");
            }
            //找到需要修改的节点，根据no编号修改，
            //定义temp辅助变量，
            HeroNodeUpdate temp = head.next;
            boolean flag = false;//表示是否找到了该节点
            while (true) {
                if (temp == null) {//已经遍历完这个链表了
                    break;
                }
                if (temp.no == heroNodeUpdate.no) { //找到需要修改的节点
                    flag = true;
                    break;
                }
                //若没有找到，temp后移
                temp = temp.next;
            }
            //根据flag判断是否找到了要修改的节点
            if(flag){
                temp.name = heroNodeUpdate.name;
                temp.nickname = heroNodeUpdate.nickname;
            }else {//没有找到
                System.out.printf("没有找到编号为 %d 的节点编号，不能进行修改\n",heroNodeUpdate.no);
            }
        }

        //显示链表【遍历】
        public void showLinkedList(){
            //判断链表是否为空
            if(head.next == null){
                System.out.println("链表为空~");
                return ;
            }
            //因为head节点不能动，所以定义辅助变量进行遍历
            //这里的 temp 表示链表的最后一个节点.next
            HeroNodeUpdate temp = head.next;
            while (true){
                //判断是否到链表最后
                if(temp == null){
                    break;
                }
                //输出节点的信息
                System.out.println(temp);
                //将temp后移（输出一个节点信息后，temp后移才能输出下一个节点）
                temp = temp.next;
            }
        }

    }

    //定义一个HeroNode，每一个HeroNode对象就是一个节点
    class HeroNodeUpdate {

        public int no;
        public String name;
        public String nickname;
        public HeroNodeUpdate next;

        //构造器
        public HeroNodeUpdate(int no, String name, String nickname) {
            this.no = no;
            this.name = name;
            this.nickname = nickname;
        }

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

效果截图：

2.3 链表删除操作

思路分析：

代码实现：

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
package com.self.linkedlist;

public class SingleLinkedListDel {

    public static void main(String[] args) {
        //进行测试
        //创建节点
        HeroNodeDel hero1 = new HeroNodeDel(1, "宋江", "及时雨");
        HeroNodeDel hero2 = new HeroNodeDel(2, "卢俊义", "玉麒麟");
        HeroNodeDel hero3 = new HeroNodeDel(3, "吴用", "智多星");
        HeroNodeDel hero4 = new HeroNodeDel(4, "林冲", "豹子头");

        //创建链表
        SingleLinkedList_del singleLinkedList = new SingleLinkedList_del();
        //将节点加入
        singleLinkedList.add(hero1);
        singleLinkedList.add(hero2);
        singleLinkedList.add(hero3);
        singleLinkedList.add(hero4);

        //显示
        singleLinkedList.showLinkedList();

        //删除一个节点
        singleLinkedList.delete(1);
        System.out.println("删除后：");
        singleLinkedList.showLinkedList();
    }
}

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

    //初始化头结点，一般头结点不能更改，要不然之后的节点数据将找不到
    private HeroNodeDel head = new HeroNodeDel(0,"","");

    //添加节点到单向链表（找到链表的最后一个节点，让它指向新添加的节点，并将其next的null去掉）
    public void add(HeroNodeDel heroNodeDel){

        //因为head节点不能动，因此我们需要一个辅助遍历变量 temp
        HeroNodeDel temp = head;
        //遍历链表，找到最后的节点
        while (true){
            //链表的最后一个节点
            if(temp.next == null){
                break;
            }
            //如果没有找到最后，就将temp后移
            temp = temp.next;
        }
        //当退出了while循环时，temp就已经指向了链表的最后一个节点
        //然后将最后这个的节点指向新添加的节点
        temp.next = heroNodeDel;
    }

    /**
     * 删除节点：
     *      思路：
     *          1. head 不能动，因此需要一个temp辅助节点找到待删除节点的前一个节点(temp.next.no和待删除节点的no进行比较)
     *          2. temp.next = temp.next.next
     * @param no
     */
    public void delete(int no){
        HeroNodeDel temp = head;
        boolean flag = true; //是否找到待删除节点的前一个节点
        while (true){
            if(temp.next == null){//已经到链表最后
                break;
            }
            if(temp.next.no == no){ //找到了待删除节点的前一个节点temp
                flag = true;
                break;
            }
            temp = temp.next; //若没找到，继续讲temp后移
        }
        //判断flag
        if(flag){//找到
            //可以删除
            temp.next = temp.next.next;
        }else {
            System.out.printf("要删除的 %d 节点不存在，无法删除",no);
        }
    }


    //显示链表【遍历】
    public void showLinkedList(){
        //判断链表是否为空
        if(head.next == null){
            System.out.println("链表为空~");
            return ;
        }
        //因为head节点不能动，所以定义辅助变量进行遍历
        //这里的 temp 表示链表的最后一个节点.next
        HeroNodeDel temp = head.next;
        while (true){
            //判断是否到链表最后
            if(temp == null){
                break;
            }
            //输出节点的信息
            System.out.println(temp);
            //将temp后移（输出一个节点信息后，temp后移才能输出下一个节点）
            temp = temp.next;
        }
    }

}

//定义一个HeroNode，每一个HeroNode对象就是一个节点
class HeroNodeDel {

    public int no;
    public String name;
    public String nickname;
    public HeroNodeDel next;

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

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

效果截图：

以上就是单链表实现增删改查的全部过程！！！