数据结构 - 单链表_单链表插入结点

链表(Linked List) 介绍

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

• 链表是以节点的方式来存储,是链式存储。
• 每个节点包含 data域：存放数据， next 域：指向下一个节点。
• 如图：发现链表的各个节点不一定是连续存储。
• 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定。

单链表(带头结点)逻辑结构示意图如下

最后一个节点的 next 域 为 空。

单链表创建和遍历的分析与实现

单链表创建（添加示意图）

一、添加（创建）

1、先创建一个head 头节点， 作用就是表示单链表的头，不存放具体数据
2、添加：找到当前链表的最后一个节点也就是 next域 为 null，将最后这个节点的next 指向 新的节点

二、遍历

1、通过一个辅助变量（每个节点的 next域赋给这个辅助变量）打印，帮助遍历整个链表，为null 终止

单链表代码实现

/**
 * @ClassName SingleLinkedListDemo
 * @author: shouanzh
 * @Description 单链表
 * @date 2022/4/28 21:38
 */
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(hero4);
        singleLinkedList.add(hero2);
        singleLinkedList.add(hero3);

        // 遍历链表
        singleLinkedList.list();

    }

}

// 定义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 + "]";
    }
    
}


// 定义 SingleLinkedList 单链表
class SingleLinkedList{
    // 先初始化一个头节点,头节点不能动,不存放具体的数据
    private HeroNode head = new HeroNode(0, null, null);

	// 获取头节点
    public HeroNode getHead() {
        return head;
    }

    // 添加节点到单向链表
    // 思路，当不考虑编号顺序时
    // 1. 找到当前链表的最后节点
    // 2. 将最后这个节点的next 指向 新的节点
    public void add(HeroNode heroNode) {
        // 因为head节点不能动，因此我们需要一个辅助变量 temp
        HeroNode temp = head;
        // 遍历链表，找到最后一个节点 也就是 next域为 null
        while(true) {
            // next域为 null
            if(temp.next == null) {
                break;
            }
            // 如果next域为 不为null 则继续找下一个节点
            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) {
                return;
            }
            // 输出节点信息
            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
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

存在的问题
1、无法按照序号排序，只能按照插入顺序排序。
2、插入的序号可以重复。

HeroNode [no=1, name=宋江, nickname=及时雨]
HeroNode [no=4, name=林冲, nickname=豹子头]
HeroNode [no=2, name=卢俊义, nickname=玉麒麟]
HeroNode [no=3, name=吴用, nickname=智多星]

Process finished with exit code 0

1
2
3
4
5
6
7

单链表：按顺序插入、删除、修改、判重

按顺序插入思路

1、首先找到新添加的节点的位置, 通过辅助变量temp确定（temp是位于添加位置的前一个节点），通过遍历搞定。
2、新的节点 newNode：newNode.next = temp.next
3、将temp.next = newNode ，新的节点

修改的思路

遍历链表、找到no、然后修改。只能修改 姓名和昵称。

删除节点的思路

1、我们先找到 需要删除的这个节点的前一个节点 temp
2、temp.next = temp.next.next
3、被删除的节点，将不会有其它引用指向，会被垃圾回收机制回收

以上增、改、删的代码实现

/**
 * @ClassName SingleLinkedListDemo
 * @author: shouanzh
 * @Description 单链表
 * @date 2022/4/28 22:38
 */
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();

        // 节点加入链表,按编号顺序（且编号不可重复）
        System.out.println("#######原始数据##########");
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);
        singleLinkedList.addByOrder(hero3); // 测试重复添加

        // 遍历链表
        singleLinkedList.list();

        // 测试删除
        System.out.println("#######测试删除##########");
        singleLinkedList.delete(4);
        singleLinkedList.list();

    }

}

// 定义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 + "]";
    }
    
}


// 定义 SingleLinkedList 单链表
class SingleLinkedList{
    // 先初始化一个头节点,头节点不能动,不存放具体的数据
    private HeroNode head = new HeroNode(0, null, null);

	// 获取头节点
    public HeroNode getHead() {
        return head;
    }

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


    // 按编号顺序添加（如果编号存在，则添加失败，并给出提示）
    public void addByOrder(HeroNode heroNode) {
        // 因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置
        // 因为单链表，因为我们找的temp 是位于 添加位置的前一个节点，否则插入不了
        HeroNode temp = head;
        boolean flag = false;// flag标志添加的编号是否存在，默认为false

        while(true) {
            // 最后一个节点
            if(temp.next == null){
                break;
            }

            // temp 的下一个节点的 no 大于新加节点的 no
            // 因为 它满足了 按顺序 ，所以可以插入
            if(temp.next.no > heroNode.no){
                break;
            }

            // 编号以存在(不可重复)
            if(temp.next.no == heroNode.no) {
                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 heroNode) {
        // 判空
        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 == heroNode.no) {
                flag = true;
                break;
            }
            // 节点移动，继续找
            temp = temp.next;
        }

        // 根据 flag 判断
        if(flag) {
            // 找到，修改姓名和外号
            temp.name = heroNode.name;
            temp.nickname = heroNode.nickname;
        }else {
            System.out.printf("没有找到编号为【%d】,无法修改",heroNode.no);
        }
    }

    // 删除
    //1. head 不能动，因此我们需要一个temp辅助节点找到待删除节点的前一个节点
    //2. 说明：我们在比较时，是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) {
                flag = true;
                break;
            }

            // 移动继续找
            temp = temp.next;
        }

        // 通过 flag 进行判断
        if(flag) {
            // 已经找到，指向后一个引用
            temp.next = temp.next.next;
        }else {
            System.out.printf("删除的数据不存在【%d】",no);
        }

    }


    // 遍历链表
    public void list() {
        // 判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空~~~");
            return;
        }
        // 因为头节点，不能动，因此我们需要一个辅助变量来遍历
        HeroNode temp = head.next;

        while (true) {
            // 判断是否到链表的最后一个节点
            if (temp == null) {
                return;
            }
            // 输出节点信息
            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
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

测试

#######原始数据##########
编号 3 已经存在了, 不能加入
HeroNode [no=1, name=宋江, nickname=及时雨]
HeroNode [no=2, name=卢俊义, nickname=玉麒麟]
HeroNode [no=3, name=吴用, nickname=智多星]
HeroNode [no=4, name=林冲, nickname=豹子头]
#######测试删除##########
HeroNode [no=1, name=宋江, nickname=及时雨]
HeroNode [no=2, name=卢俊义, nickname=玉麒麟]
HeroNode [no=3, name=吴用, nickname=智多星]

Process finished with exit code 0
1
2
3
4
5
6
7
8
9
10
11
12

获取单链表中有效节点的个数

遍历即可

/**
 * 获取到单链表的节点的个数(如果是带头结点的链表，需求不统计头节点)
 * @param head 头节点
 * @return 返回有效节点长度
 */
public static int getLength(HeroNode head) {
    // 空链表
    if (head.next == null) {
        return 0;
    }

    int lenght = 0;
    // 定义一个辅助变量,这里没有统计头节点
    HeroNode cur = head.next;
    while (cur != null) {
        lenght++;
        cur = cur.next; // 遍历
    }
    return lenght;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

查找单链表中的倒数第k个结点

有效节点个数 - 倒数第几个节点 = 遍历多少个节点

比如7个节点 获取倒数第三个节点
那么 7-3 = 4，第四个节点.next 就是我们要的结果。

/**
 * 思路：
 * 1、先遍历得到 有效数据个数（总长度不包括头节点）
 * 2、index 倒数第几个节点
 * 3、我们从链表的第一个开始遍历(size-index)个，就可以得到
 * 4、找到则返回当前节点，找不到返回 null
 * @param head 头节点
 * @param index 倒数第几个节点
 * @return HeroNode
 */
public static HeroNode findLastIndexNode(HeroNode head, int index) {
    
    // 判空
    if (head.next == null) {
        return null;
    }

    // 第一个遍历得到链表的长度(节点个数)
    int size = getLength(head);

    // 先做一个index的校验
    if (index <= 0 || index > size) {
        // 查找的位置不能大过总长
        return null;
    }

	// 第二次遍历 size-index 位置，就是我们倒数的第K个节点
    // 定义给辅助变量， for 循环定位到倒数的index
    HeroNode cur = head.next;// 7-3=4, 7个有效节点 获取倒数第三个 遍历4次就可以了
    for (int i = 0; i < size - index; i++) {
        cur = cur.next;
    }
    return cur;
}
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

单链表的反转

思路
1、先定义一个节点 reverseHead = new HeroNode()
2、从头到尾遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端，并记录当前节点的下一个节点。
3、原来的链表的head.next = reverseHead.next

/**
 * 单链表的反转
 * @param head 头节点
 */
public static void reversalList(HeroNode head) {
    // 若链表为空，或者只有一个则不需要反转
    if (head.next == null || head.next.next == null) {
        return;
    }

    // 定义一个辅助变量，用于遍历原始未反转的那个链表
    HeroNode cur = head.next;
    // 用于动态指向 当前节点【cur】的 下一个节点
    HeroNode next;

    // 新链表(反转后的)的链表头
    HeroNode reverseHead = new HeroNode(0, "", "");

    // 思路： 遍历原始链表，每遍历一个节点将其取出，并放在新链表头(reverseHead)的最前端
    while (cur != null) {
        // 暂时先保存当前节点的下一个节点，用于后移
        next = cur.next;
        // 将遍历出来的新节点.next 指向reverseHead的.next (也就是拼接reverseHead的旧数据)
        cur.next = reverseHead.next;
        // 将 cur 连接到 reverseHead 表头最前端
        reverseHead.next = cur;
        // cur 后移
        cur = next;
    }

    // 将head.next 指向 reverseHead.next , 实现单链表的反转
    head.next = reverseHead.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

从尾到头打印单链表

方式1： 先将单链表进行反转操作，然后再遍历即可，这样的做的问题是会破坏原来的单链表的结构，不建议。

方式2：可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果。

/**
 * 从尾到头打印单链表 使用栈 先进后出 的特点
 * @param head 头节点
 */
public static void reversalPrint(HeroNode head) {
    
    // 判空
    if(head.next == null){
        return;
    }

    // 创建一个栈，将各个节点压入栈
    Stack<HeroNode> stack = new Stack();
    // 定义辅助变量，用于遍历原始链表
    HeroNode cur = head.next;
    
    // 将链表所有节点入栈
    while (cur != null) {
        stack.push(cur);// 节点入栈
        cur = cur.next;// 节点后移
    }
    // 所有节点依次出栈
    while(stack.size() > 0) {
        // stack的特点是先进后出
        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