節(jié)點(diǎn)類
可以根據(jù)需要，對(duì)節(jié)點(diǎn)屬性進(jìn)行修改。注意重寫(xiě)toString()方法，以便后續(xù)的輸出操作。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
//節(jié)點(diǎn)類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 + '\'' + '}'; }} |
鏈表類（主要）
所實(shí)現(xiàn)的增刪改查，反轉(zhuǎn)，逆序等功能基本能適用。實(shí)現(xiàn)思路在代碼中注釋。
|
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
|
//鏈表類（管理節(jié)點(diǎn)）class LinkedList { //頭節(jié)點(diǎn) Node head = new Node(0,null); //鏈表有效數(shù)據(jù)個(gè)數(shù)（鏈表長(zhǎng)度）（頭節(jié)點(diǎn)不計(jì)） 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; } } //增(根據(jù)id從小到大) public void add(Node newNode){ Node temp = head; while (true){ //用來(lái)找到鏈表尾 if (temp.next == null) { break; } if (temp.id == newNode.id){ System.out.println("要添加的節(jié)點(diǎn)的id已經(jīng)存在，添加失敗！"); return; } if (temp.next.id > newNode.id){ break; } temp = temp.next; } Node node = newNode; newNode.next = temp.next; temp.next = node; } //刪(根據(jù)id匹配刪除) public void remove(int id){ if (head.next == null){ System.out.println("鏈表為空!"); return; } Node temp = head; boolean flag = false; //用來(lái)標(biāo)記是否找到對(duì)應(yīng)id的節(jié)點(diǎn) while (true){ if (temp.next == null){ break; } if (temp.next.id == id){ //找到要?jiǎng)h除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn) flag =true; break; } temp = temp.next; } if (flag){ temp.next = temp.next.next; }else { System.out.println("沒(méi)有找到要?jiǎng)h除的節(jié)點(diǎn)，刪除失敗!"); } } //改（根據(jù)id匹配要修改的節(jié)點(diǎn)） public void update(int id,String name){ if (head.next == null){ System.out.println("鏈表為空！"); return; } Node temp = head; boolean flag = false; //用來(lái)標(biāo)記是否找到對(duì)應(yīng)id的節(jié)點(diǎn) 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("沒(méi)有找到要修改的節(jié)點(diǎn)，修改失??！"); } } //查（根據(jù)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("沒(méi)有找到要查找的節(jié)點(diǎn)，查找失敗！"); return null; } } //查找倒數(shù)第n個(gè)節(jié)點(diǎn) public Node lastShow(int n){ Node temp = head.next; int size = this.size(); if (size < n || n <= 0){ System.out.println("查找的節(jié)點(diǎn)不存在！"); return null; } for (int i = 0; i < size - n; i++) { temp = temp.next; } return temp; } //鏈表反轉(zhuǎn) public void reverse(){ if (head.next == null || head.next.next == null){ return; } Node reverseHead = new Node(0,null); Node cur = head.next; //記錄當(dāng)前遍歷到的節(jié)點(diǎn) Node next = null; //記錄當(dāng)前遍歷到的節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn) while (true){ if (cur == null){ //確保遍歷到最后一個(gè) break; } next = cur.next; //保存下一個(gè)節(jié)點(diǎn)，避免斷鏈 //使得反轉(zhuǎn)頭節(jié)點(diǎn)指向遍歷到的當(dāng)前節(jié)點(diǎn)，而讓遍歷到的當(dāng)前節(jié)點(diǎn)指向反轉(zhuǎn)頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn) // 確保遍歷到的當(dāng)前節(jié)點(diǎn)始終位于反轉(zhuǎn)頭節(jié)點(diǎn)的下一個(gè) cur.next = reverseHead.next; reverseHead.next = cur; //遍歷 cur = next; } head.next = reverseHead.next; //最后讓原頭節(jié)點(diǎn)指向反轉(zhuǎn)頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，即可實(shí)現(xiàn)原鏈表的反轉(zhuǎn) } //逆序打印 //方法一：先反轉(zhuǎn) //方法二：使用棧結(jié)構(gòu) 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()); } }} |
測(cè)試類
|
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: *///測(cè)試類public class SingleLinkedListTest { public static void main(String[] args) { LinkedList linkedList = new LinkedList(); Node node1 = new Node(1, "阿蘭"); Node node2 = new Node(2, "洛國(guó)富"); Node node3 = new Node(3, "艾克森"); //可以不按照id順序添加 linkedList.add(node1); linkedList.add(node3); linkedList.add(node2); linkedList.list(); System.out.println(linkedList.size()); //鏈表長(zhǎng)度// System.out.println(linkedList.lastShow(2)); //倒數(shù)查找// linkedList.update(2,"張玉寧"); //改//// linkedList.remove(3); //刪//// System.out.println(linkedList.show(2)); //查// linkedList.reverse(); //鏈表反轉(zhuǎn) linkedList.reversePrint(); //逆序打印 }} |
小結(jié)
單鏈表的節(jié)點(diǎn)由具體數(shù)據(jù)域和指針域兩部分組成，而帶有頭節(jié)點(diǎn)的單鏈表的頭節(jié)點(diǎn)不存儲(chǔ)具體數(shù)據(jù)，其指針域則指向鏈表的第一個(gè)有效節(jié)點(diǎn)，即非頭節(jié)點(diǎn)的第一個(gè)節(jié)點(diǎn)。
當(dāng)對(duì)單鏈表進(jìn)行增刪改查，逆序等操作時(shí)，要定義一個(gè)Node類型的輔助變量來(lái)遍歷鏈表，而頭節(jié)點(diǎn)注意要保持不動(dòng)。
進(jìn)行反轉(zhuǎn)操作時(shí)，最后需要使得頭節(jié)點(diǎn)指向反轉(zhuǎn)后的鏈表的第一個(gè)節(jié)點(diǎn)，這是唯一一處使得頭節(jié)點(diǎn)變動(dòng)的地方。
到此這篇關(guān)于Java實(shí)現(xiàn)單鏈表SingleLinkedList增刪改查及反轉(zhuǎn) 逆序等的文章就介紹到這了,更多相關(guān)Java 單鏈表 內(nèi)容請(qǐng)搜索服務(wù)器之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持服務(wù)器之家！
原文鏈接：https://blog.csdn.net/m0_46653805/article/details/120771961
