節點類
可以根據需要，對節點屬性進行修改。注意重寫toString()方法，以便后續的輸出操作。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
//節點類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
|
//鏈表類（管理節點）class LinkedList { //頭節點 Node head = new Node(0,null); //鏈表有效數據個數（鏈表長度）（頭節點不計） public int size(){ Node temp = head; int size = 0; while (true){ if (temp.next == null){ break; } size++; temp = temp.next; } return size; } //展示鏈表 public void list(){ if (head.next == null){ System.out.println("鏈表為空！"); return; } Node temp = head.next; while (true){ if (temp == null){ break; } System.out.println(temp); temp = temp.next; } } //增(根據id從小到大) public void add(Node newNode){ Node temp = head; while (true){ //用來找到鏈表尾 if (temp.next == null) { break; } if (temp.id == newNode.id){ System.out.println("要添加的節點的id已經存在，添加失??！"); return; } if (temp.next.id > newNode.id){ break; } temp = temp.next; } Node node = newNode; newNode.next = temp.next; temp.next = node; } //刪(根據id匹配刪除) public void remove(int id){ if (head.next == null){ System.out.println("鏈表為空!"); return; } Node temp = head; boolean flag = false; //用來標記是否找到對應id的節點 while (true){ if (temp.next == null){ break; } if (temp.next.id == id){ //找到要刪除節點的前一個節點 flag =true; break; } temp = temp.next; } if (flag){ temp.next = temp.next.next; }else { System.out.println("沒有找到要刪除的節點，刪除失敗!"); } } //改（根據id匹配要修改的節點） public void update(int id,String name){ if (head.next == null){ System.out.println("鏈表為空！"); return; } Node temp = head; boolean flag = false; //用來標記是否找到對應id的節點 while (true){ if (temp.next == null){ break; } if (temp.id == id){ flag = true; break; } temp = temp.next; } if (flag){ temp.name = name; }else { System.out.println("沒有找到要修改的節點，修改失??！"); } } //查（根據id匹配） public Node show(int id){ if (head.next == null){ System.out.println("鏈表為空！"); return null; } Node temp = head.next; boolean flag = false; while (true){ if (temp == null){ break; } if (temp.id == id){ flag = true; break; } temp = temp.next; } if (flag){ return temp; }else { System.out.println("沒有找到要查找的節點，查找失?。?quot;); return null; } } //查找倒數第n個節點 public Node lastShow(int n){ Node temp = head.next; int size = this.size(); if (size < n || n <= 0){ System.out.println("查找的節點不存在！"); return null; } for (int i = 0; i < size - n; i++) { temp = temp.next; } return temp; } //鏈表反轉 public void reverse(){ if (head.next == null || head.next.next == null){ return; } Node reverseHead = new Node(0,null); Node cur = head.next; //記錄當前遍歷到的節點 Node next = null; //記錄當前遍歷到的節點的下一個節點 while (true){ if (cur == null){ //確保遍歷到最后一個 break; } next = cur.next; //保存下一個節點，避免斷鏈 //使得反轉頭節點指向遍歷到的當前節點，而讓遍歷到的當前節點指向反轉頭節點的下一個節點 // 確保遍歷到的當前節點始終位于反轉頭節點的下一個 cur.next = reverseHead.next; reverseHead.next = cur; //遍歷 cur = next; } head.next = reverseHead.next; //最后讓原頭節點指向反轉頭節點的下一個節點，即可實現原鏈表的反轉 } //逆序打印 //方法一：先反轉 //方法二：使用棧結構 public void reversePrint(){ if (head.next == null){ System.out.println("鏈表為空！"); return; } Stack<Node> nodes = new Stack<>(); Node temp = head.next; while (true){ if (temp == null){ break; } nodes.push(temp); temp = temp.next; } while (nodes.size() > 0){ System.out.println(nodes.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
28
29
30
31
32
33
34
35
36
37
38
39
40
|
import java.util.Stack;/** * @Author: Yeman * @Date: 2021-10-14-12:55 * @Description: *///測試類public class SingleLinkedListTest { public static void main(String[] args) { LinkedList linkedList = new LinkedList(); Node node1 = new Node(1, "阿蘭"); Node node2 = new Node(2, "洛國富"); Node node3 = new Node(3, "艾克森"); //可以不按照id順序添加 linkedList.add(node1); linkedList.add(node3); linkedList.add(node2); linkedList.list(); System.out.println(linkedList.size()); //鏈表長度// System.out.println(linkedList.lastShow(2)); //倒數查找// linkedList.update(2,"張玉寧"); //改//// linkedList.remove(3); //刪//// System.out.println(linkedList.show(2)); //查// linkedList.reverse(); //鏈表反轉 linkedList.reversePrint(); //逆序打印 }} |
小結
單鏈表的節點由具體數據域和指針域兩部分組成，而帶有頭節點的單鏈表的頭節點不存儲具體數據，其指針域則指向鏈表的第一個有效節點，即非頭節點的第一個節點。
當對單鏈表進行增刪改查，逆序等操作時，要定義一個Node類型的輔助變量來遍歷鏈表，而頭節點注意要保持不動。
進行反轉操作時，最后需要使得頭節點指向反轉后的鏈表的第一個節點，這是唯一一處使得頭節點變動的地方。
到此這篇關于Java實現單鏈表SingleLinkedList增刪改查及反轉 逆序等的文章就介紹到這了,更多相關Java 單鏈表 內容請搜索服務器之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持服務器之家！
原文鏈接：https://blog.csdn.net/m0_46653805/article/details/120771961
