【数据结构与算法】单向链表(添加节点、顺序添加节点、更新节点、删除节点、反转链表、获取链表长度、获取倒数第几个节点、打印链表、反转打印链表)

1. 单向链表的介绍

单向链表是有序的列表。以节点的方式来存储，是链式存储，每个节点包含data域和next域(指向下一个节点)，所以单向链表在内存中的储存是无序的

单向链表分带头节点的单向链表，和没有头节点的单向链表

2. 带head头的单向链表实现

实现对单向链表的增、删、改、查等操作

单向链表各节点说明：

• head节点：不储存数据，next指向下一个节点
• 最后一个节点：next为空，不指向任何节点

单向链表各方法说明：

• add：向单向链表添加一个节点
• addByOrder：按照Node的id升序，将Node添加到指定位置。如果id已存在，则添加失败并给出提示
• update：通过新节点的id，去更新单向链表中对应id的节点的数据
• deleteById：根据id删除单向链表中的节点
• reverseList：将单向链表的各个节点进行反转
• length：获取单向链表的节点个数
• getLastIndexNode：获取单向链表倒数第index个节点
• show：遍历显示链表所有节点的数据
• reversePrint：反向打印链表

单向链表的实现：

import java.util.Stack;

public class SingleLinkedListDemo {

    public static void main(String[] args) {

        // 先创建节点
        Node node1 = new Node(1, "node1");
        Node node2 = new Node(2, "node2");

        // 创建单向链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        // 先添加node2，再添加node1
        singleLinkedList.add(node2);
        singleLinkedList.addByOrder(node1);

        // 更新id = 2的节点
        Node newNode2 = new Node(2, "newNode2");
        singleLinkedList.update(newNode2);

        // 删除id = 1的节点
        singleLinkedList.deleteById(1);

        // 打印单向链表的长度
        System.out.println(singleLinkedList.length());

        // 获取倒数第一个节点，并打印
        System.out.println(singleLinkedList.getLastIndexNode(1));

        // 将单向链表进行反转
        singleLinkedList.reverseList();

        // 查看单向链表所有节点数据
        singleLinkedList.show();

        // 反向打印单向链表
        singleLinkedList.reversePrint();

    }
}

class SingleLinkedList {

    // 初始化一个head节点
    private Node headNode = new Node(0, "");

    // 先找到单向链表的最后一个节点(最后一个节点的next为null)，然后将next指向新节点
    public void add(Node node) {
        Node tmpNode = this.headNode;

        while (true) {
            // 如果找到最后一个节点，则添加新节点
            if (tmpNode.next == null) {
                tmpNode.next = node;
                break;
            } else {
                // 如果没有找到最后一个节点，则循环处理后面的节点
                tmpNode = tmpNode.next;
            }
        }
    }


    // 按照Node的id升序，将Node添加到指定位置。如果id已存在，则添加失败并给出提示
    public void addByOrder(Node node) {
        Node tmpNode = this.headNode;
        while (true) {
            // 如果没有下一个节点，则直接将新节点添加到单向链表的后面
            if (tmpNode.next == null) {
                tmpNode.next = node;
                break;
                // 如果下一个节点的id比新节点的id大，则将新节点添加到当前节点的后面
            } else if (tmpNode.next.id > node.id) {
                node.next = tmpNode.next;
                tmpNode.next = node;
                break;
                // 如果下一个节点的id和新节点的id相等，则不能添加
            } else if (tmpNode.next.id == node.id) {
                System.out.printf("准备添加的节点的id：%d已经在单向链表中存在，不能添加\n", node.id);
                break;
                // 否则，循环处理下一个节点
            } else {
                tmpNode = tmpNode.next;
            }
        }

    }


    // 通过新节点的id，去更新单向链表中对应id的节点的数据
    public void update(Node node) {

        Node tmpNode = this.headNode;
        while (true) {
            // 如果没有下一个节点，则表示未找到，不能更新
            if (tmpNode.next == null) {
                System.out.println("单向链表没有该节点的id，不能更新");
                break;
                // 如果找到了，则进行更新
            } else if (tmpNode.next.id == node.id) {
                tmpNode.next.name = node.name;
                break;
                // 否则，循环处理下一个节点
            } else {
                tmpNode = tmpNode.next;
            }
        }
    }

    // 根据id删除单向链表中的节点
    public void deleteById(int id) {
        Node tmpNode = this.headNode;
        while (true) {
            // 如果没有下一个节点，则表示为找到要删除的节点
            if (tmpNode.next == null) {
                System.out.println("未找到要删除的节点");
                break;
                // 如果找到要删除的节点，则进行删除
            } else if (tmpNode.next.id == id) {
                //被删除的节点没有被引用，会被自动垃圾回收
                tmpNode.next = tmpNode.next.next;
                break;
                // 否则，循环处理后面的节点
            } else {
                tmpNode = tmpNode.next;
            }
        }
    }

    // 将单向链表的各个节点进行反转
    public void reverseList() {
        // 当前处理节点
        Node currentNode = this.headNode.next;
        // 当前处理节点的下一个节点
        Node tmpNextNode;
        // 创建一个临时的反转单向链表的头
        Node tmpReverseHead = new Node(0, "");

        while (true) {
            // 如果当前节点为null，则表示反转结束
            if (currentNode == null) {
                // 反转结束，将临时的反转单向链表的头的next，赋值给单向链表的头的next
                this.headNode.next = tmpReverseHead.next;
                break;
                // 否则，从单向链表中依次取出节点，插入到临时的反转单向链表的头后面
            } else {
                // 将当前节点的下一个节点，赋值给临时的tmpNextNode
                tmpNextNode = currentNode.next;
                // 将反转单向链表的头的后面部分，放到当前节点的后面
                currentNode.next = tmpReverseHead.next;
                // 然后再将当前节点，放到反转单向链表的头的后面
                tmpReverseHead.next = currentNode;
                // 将临时的的tmpNextNode，赋值给当前节点，循环处理后面的节点
                currentNode = tmpNextNode;
            }
        }

    }


    // 获取单向链表的节点个数
    public int length() {
        Node tmpNode = this.headNode;
        int nodeCount = 0;
        while (true) {
            // 如果没有下一个节点了，则返回统计的节点个数
            if (tmpNode.next == null) {
                return nodeCount;
                // 否则，节点个数进行加1，然后循环处理后面的节点
            } else {
                nodeCount++;
                tmpNode = tmpNode.next;
            }
        }
    }


    // 获取单向链表倒数第index个节点
    public Node getLastIndexNode(int index) {
        Node tmpNode = this.headNode;

        int nodeCount = this.length();
        // 进行index的验证，如果不符合要求，则返回null
        if (index <= 0 || index > nodeCount) {
            System.out.println("传入的index小于等于0， 或超过的单向链表的最大长度");
            return null;
            // 如果index符合要求，则循环获取倒数第index个节点
        } else {
            for (int i = 0; i <= nodeCount - index; i++) {
                tmpNode = tmpNode.next;
            }
            return tmpNode;
        }

    }


    // 遍历显示链表的数据
    public void show() {
        if (this.headNode.next == null) {
            System.out.println("链表为空, 不能显示数据");
            return;
        }

        // 定义一个临时变量，指向当前要显示数据的节点
        Node tempNode = this.headNode.next;
        while (true) {
            // 如果为null，则跳出循环
            if (tempNode == null) {
                break;
            } else {
                // 输出当前节点的数据
                System.out.println(tempNode);
                // 然后循环处理后面的节点
                tempNode = tempNode.next;
            }
        }
    }

    // 反向打印链表
    public void reversePrint() {
        Node tmpNode = this.headNode;

        // 用栈来保存链表的数据，先进后出，实现反向打印
        Stack stack = new Stack();

        while (true) {
            // 如果没有下一个节点，表示遍历单向链表完成，开始打印栈中的数据
            if (tmpNode.next == null) {
                int stackSize = stack.size();
                for (int i = 0; i < stackSize; i++) {
                    System.out.println(stack.pop());
                }
                break;
                // 否则，将节点压入栈中，然后循环处理后面的节点
            } else {
                stack.push(tmpNode.next);
                tmpNode = tmpNode.next;
            }
        }
    }

}


// 每个Node对象就是一个节点
class Node {
    public int id;
    public String name;
    // 指向下一个节点
    public Node next;

    public Node(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Node [id = " + id + ", name = " + name + "]";
    }

}
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
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263

运行程序，结果如下：

1
Node [id = 2, name = newNode2]
Node [id = 2, name = newNode2]
Node [id = 2, name = newNode2]
1
2
3
4