1、双向链表的概念
链表是一种比较常见的数据结构,在频繁进行增、删操作时链表效率高于数组,但读取效率不高。链表分为:双向链表,单向链表和循环链表。
双向链表也叫双链表,不同于单链表只有一个指向下一结点的指针。双链表中拥有两个指针,分别指向当前结点的上一节点和下一节点。
2、示意图
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
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
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310/** * 链表类,元素是以结点的信息存储的 */ public class MylinkedList<T> { /** * 结点类,私有的。存放结点的值 * 以及上一个结点和下一个结点的地址 */ private class Node { T element; Node previous; // 指向该结点的上一个结点 Node next; // 指向该结点的下一个结点 Node() { } // 构造 Node(T element) { this.element = element; } } // 记录第一个结点 private Node first; // 记录最后一个结点 private Node last; // 记录链表中的结点个数 private int count; /** * 获取链表中的结点个数 * * @return 结点个数 */ public int size() { return count; } /** * 根据下标获取对应的结点并返回 * * @param index 需要获取结点的下标 * @return 下标对应的结点 */ private Node getNode(int index) { // 根据 index 获取元素值 if (index < 0 || index >= count) { // 如果下标越界,则抛异常 throw new IndexOutOfBoundsException("列表下标应在范围:[0 , " + count + ") 之间"); } // 从第一个结点开始遍历 Node node = this.first; for (int i = 0; i < index; i++) { // 遍历到下标对应的结点 node = node.next; } // 返回遍历到的结点 return node; } /** * 删除一个结点 * * @param node 需要删除的结点 */ private void removeNode(Node node) { if (count == 1) { // 如果这个链表中只有一个结点 // 那么清空链表即可 this.first = null; this.last = null; // 结点个数 -1 count--; return; } if (node == this.first) { // 如果需要删除的是 first 结点 // 则修改 node 的下一个结点为 first this.first = node.next; // 将 node 的下一个结点的上一个结点设置为 null node.next.previous = null; } else if (node == this.last) { // 如果需要删除的是 last 结点 // 则修改 node 的上一个结点为 last this.last = node.previous; // 将 node 的上一个结点的下一个结点设置为 null node.previous.next = null; } else { // 删除在中间的结点 // 将 node 的下一个结点的 previous 指向 node 的上一个结点 node.next.previous = node.previous; // 将 node 的上一个结点的 next 指向 node 下一个结点 node.previous.next = node.next; } // 移除 node 的全部指向 node.previous = null; node.next = null; // 元素个数 -1 count--; } /** * 在链表后面追加结点 * * @param element 新结点的元素值 */ public void add(T element) { // 实例化一个 Node 对象 Node node = new Node(element); if (count == 0) { // 如果链表中没有任何结点 // 则新增的元素为首位 this.first = node; } else { // 如果链表中已经存在其他结点 // 则依次往最后一个元素后追加 this.last.next = node; node.previous = this.last; } this.last = node; // 元素个数 +1 count++; } /** * 根据下标添加结点 * * @param index 需要添加结点的下标 * @param element 新结点的值 */ public void add(int index, T element) { // 实例化一个新的结点 Node newNode = new Node(element); if (index == 0) { // 添加 first 结点 // 将 newNode 的 next 指向原来的 first 结点 newNode.next = this.first; // 将原来的 first 的 previous 指向 newNode this.first.previous = newNode; // 修改 fist 结点为 newNode this.first = newNode; } else if (index == count) { // 添加 last 结点 // 将原来的 last 的 next 指向 newNode this.last.next = newNode; // 将 newNode 的 previous 指向原来的 last newNode.previous = this.last; // 修改 last 结点为 newNode this.last = newNode; } else { // 检查下标并获取下标对应的结点 Node node = getNode(index); // 中间结点的修改 // 新结点的上一个结点为原下标结点的上一个结点 newNode.previous = node.previous; // 新结点的下一个结点为原下标结点 newNode.next = node; // 修改原结点的上一个结点的 下一个结点为新结点 node.previous.next = newNode; // 修改原结点的上一个结点为新结点 node.previous = newNode; } // 元素个数 +1 count++; } /** * 根据下标删除结点 * * @param index 需要删除结点的下标 * @return 成功删除的值 */ public T remove(int index) { // 检查下标并获取结点 Node node = getNode(index); // 删除结点 removeNode(node); // 返回删除的结点值 return node.element; } /** * 将链表中指定下标为的元素,修改称为新的元素 * * @param index 需要修改的下标 * @param element 修改后的元素 * @return 旧的修改前的元素 */ public T set(int index, T element) { // 验证下标并获取下标对应结点 Node node = getNode(index); T oldElement = node.element; // 修改结点元素值 node.element = element; // 返回修改前的旧元素 return oldElement; } /** * 获取链表中指定下标位的元素 * * @param index 需要获取的下标 * @return 返回指定元素 */ public T get(int index) { // 验证下标并获取下标对应结点 Node node = getNode(index); // 获取下标对应的元素值 return node.element; } /** * 查询链表中某一个元素第一次出现的下标 * * @param element 待查询的元素 * @return 第一次出现的下标 */ public int indexOf(T element) { // 获取链表第一个结点 Node node = this.first; // 循环遍历链表结点并进行元素比较 for (int i = 0; i < size(); i++) { if (element.equals(node.element)) { // 返回第一次出现的下标 return i; } node = node.next; } // 没找到返回 -1 return -1; } /** * 判断链表中是否包含指定的元素 * * @param element 待判断的元素 * @return 判断结果 */ public boolean contains(T element) { return indexOf(element) != -1; } /** * 删除链表中指定的元素 * * @param element 需要删除的元素 * @return 是否成功删除 */ public boolean remove(T element) { // 获取链表第一个结点 Node node = this.first; // 记录删除的元素个数 int removeCnt = 0; // 循环遍历链表结点并进行元素比较 for (int i = 0; i < size(); i++) { if (element.equals(node.element)) { // 删除符合要求的元素 removeNode(node); // 计数器 +1 removeCnt++; } node = node.next; } return removeCnt != 0; } // 如果只删除第一个出现的 /* public boolean remove(T element) { int index = indexOf(element); if (index == -1) { return false; } remove(index); return true; } */ /** * 清空链表的所有数据 */ public void clear() { this.first = null; this.last = null; count = 0; } @Override public String toString() { // 实例化一个 StringBuilder 对象 if (count == 0) { // 如果链表为空,直接返回 [] return "[]"; } StringBuilder sb = new StringBuilder("[ "); // 从第一个结点开始循环 Node node = this.first; for (int i = 0; i < size(); i++) { // 追加到 StringBuilder 后面 sb.append(node.element).append(" , "); node = node.next; } sb.replace(sb.length() - 3, sb.length(), " ]"); return sb.toString(); } }
最后
以上就是听话黑裤最近收集整理的关于Java 实现双向链表以及对双链表的基本操作的全部内容,更多相关Java内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复