学习笔记：链表的基本特性，双链表相较于单链表的优势，链表的代码实现。
1. 链表综述
与数组连续的存储空间相反，链表通过“指针”将一组零散的内存块串联起来使用。
三种最常见的链表结构：单链表、双向链表、循环链表。
2. 双向链表
2.1 双向链表特性
在实际的软件开发中，从链表中删除一个数据无外乎这两种情况：
- 删除结点中“值等于某个给定值”的结点；
- 删除给定指针指向的结点。
对于第一种情况，不管是单链表还是双向链表，为了查找到值等于给定值的结点，都需要从头结点开始一个一个依次遍历对比，直到找到值等于给定值的结点，然后再通过我前面讲的指针操作将其删除。
尽管单纯的删除操作时间复杂度是 O(1)，但遍历查找的时间是主要的耗时点，对应的时间复杂度为 O(n)。根据时间复杂度分析中的加法法则，删除值等于给定值的结点对应的链表操作的总时间复杂度为 O(n)。
对于第二种情况，我们已经找到了要删除的结点，但是删除某个结点 q 需要知道其前驱结点，而单链表并不支持直接获取前驱结点，所以，为了找到前驱结点，我们还是要从头结点开始遍历链表，直到 p->next=q，说明 p 是 q 的前驱结点。
但是对于双向链表来说，这种情况就比较有优势了。因为双向链表中的结点已经保存了前驱结点的指针，不需要像单链表那样遍历。所以，针对第二种情况，单链表删除操作需要 O(n) 的时间复杂度，而双向链表只需要在 O(1) 的时间复杂度内就可以完成。
同理，如果我们希望在链表的某个指定结点前面插入一个结点，双向链表比单链表有很大的优势。双向链表可以在 O(1) 时间复杂度搞定，而单向链表需要 O(n) 的时间复杂度。
由此可以看出，在某些情况，双向链表比单链表更加高效。这就是为什么在实际的软件开发中，双向链表尽管比较费内存，但还是比单链表的应用更加广泛的原因。Java语言中，LinkedHashMap这个容器的实现就用到了双向链表这种数据结构。
实际上，这里有一个更加重要的知识点，即用空间换时间的设计思想。当内存空间充足的时候，如果我们更加追求代码的执行速度，我们就可以选择空间复杂度相对较高、但时间复杂度相对很低的算法或者数据结构。相反，如果内存比较紧缺，比如代码跑在手机或者单片机上，这个时候，就要反过来用时间换空间的设计思路。
2.2 双向链表代码实现
MyDoublyLinkedList.java
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
| package linkedlist;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class MyDoublyLinkedList<E> implements Iterable<E> {
final private Node<E> head, tail;
private int size;
private static class Node<E> {
E val;
Node<E> next;
Node<E> prev;
Node(E val) {
this.val = val;
}
}
public MyDoublyLinkedList() {
this.head = new Node<>(null);
this.tail = new Node<>(null);
head.next = tail;
tail.prev = head;
this.size = 0;
}
public void addFirst(E val) {
Node<E> newNode = new Node<>(val);
Node<E> currNode = head.next;
newNode.next = currNode;
currNode.prev = newNode;
head.next = newNode;
newNode.prev = head;
size++;
}
public void addLast(E val) {
Node<E> newNode = new Node<>(val);
Node<E> currNode = tail.prev;
newNode.next = tail;
tail.prev = newNode;
currNode.next = newNode;
newNode.prev = currNode;
size++;
}
public void add(int index, E val) {
checkPositionIndex(index);
Node<E> currNode = getNode(index);
Node<E> prevNode = currNode.prev;
Node<E> newNode = new Node<>(val);
prevNode.next = newNode;
newNode.prev = prevNode;
newNode.next = currNode;
currNode.prev = newNode;
size++;
}
public E removeFirst() {
if (size < 1) {
throw new NoSuchElementException("Error Deleting! The LinkedList is Empty!");
}
Node<E> currNode = head.next;
Node<E> nextNode = currNode.next;
head.next = nextNode;
nextNode.prev = head;
currNode.next = null;
currNode.prev = null;
size--;
return currNode.val;
}
public E removeLast() {
if (size < 1) {
throw new NoSuchElementException("Error Deleting! The LinkedList is Empty!");
}
Node<E> currNode = tail.prev;
Node<E> prevNode = currNode.prev;
prevNode.next = tail;
tail.prev = prevNode;
currNode.next = null;
currNode.prev = null;
size--;
return currNode.val;
}
public E remove(int index) {
checkElementIndex(index);
Node<E> currNode = getNode(index);
Node<E> prevNode = currNode.prev;
Node<E> nextNode = currNode.next;
prevNode.next = nextNode;
nextNode.prev = prevNode;
currNode.next = currNode.prev = null;
size--;
return currNode.val;
}
public E get(int index) {
checkElementIndex(index);
Node<E> currNode = getNode(index);
return currNode.val;
}
public E getFirst() {
if (size < 1) {
throw new NoSuchElementException("Error Query! The LinkedList is Empty!");
}
return head.next.val;
}
public E getLast() {
if (size < 1) {
throw new NoSuchElementException("Error Query! The LinkedList is Empty!");
}
return tail.prev.val;
}
public E set(int index, E val) {
checkElementIndex(index);
Node<E> currNode = getNode(index);
E oldVal = currNode.val;
currNode.val = val;
return oldVal;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
private Node<E> getNode(int index) {
checkElementIndex(index);
if (index >= size / 2) {
Node<E> currNode = tail.prev;
for (int i = 0; i < size - index - 1; i++) {
currNode = currNode.prev;
}
return currNode;
}
Node<E> currNode = head.next;
for (int i = 0; i < index; i++) {
currNode = currNode.next;
}
return currNode;
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
private void display() {
System.out.println("size = " + size);
for (Node<E> p = head.next; p != tail; p = p.next) {
System.out.println(p.val + " -> ");
}
System.out.println("null");
System.out.println();
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
Node<E> p = head.next;
@Override
public boolean hasNext() {
return p != tail;
}
@Override
public E next() {
E val = p.val;
p = p.next;
return val;
}
};
}
}
|
3. 单链表
代码实现 ‘SinglyLinkedList.java’
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
| package linkedlist;
import java.util.NoSuchElementException;
public class MySinglyLinkedList<E> {
private static class Node<E> {
E val;
Node<E> next;
Node(E val) {
this.val = val;
}
}
private final Node<E> head, tail;
private int size;
public MySinglyLinkedList() {
this.head = new Node<>(null);
this.tail = new Node<>(null);
head.next = tail;
this.size = 0;
}
public void addFirst(E e) {
Node<E> newNode = new Node<>(e);
Node<E> currNode = head.next;
newNode.next = currNode;
head.next = newNode;
size++;
}
public void addLast(E e) {
Node<E> newNode = new Node<>(e);
Node<E> currNode;
if (size - 1 >= 0) {
currNode = getNode(size - 1);
} else {
currNode = head;
}
newNode.next = tail;
currNode.next = newNode;
size++;
}
public void add(int index, E e) {
checkPositionIndex(index);
if (index == size) {
addLast(e);
return;
} else {
Node<E> newNode = new Node<>(e);
Node<E> currNode = getNode(index);
Node<E> prevNode;
if (index - 1 >= 0) {
prevNode = getNode(index - 1);
} else {
prevNode = head;
}
newNode.next = currNode;
prevNode.next = newNode;
size++;
}
}
public E removeFirst() {
if(isEmpty()) {
throw new NoSuchElementException();
}
Node<E> currNode = head.next;
head.next = head.next.next;
currNode.next = null;
size--;
return currNode.val;
}
public E removeLast() {
if (isEmpty()) {
throw new NoSuchElementException();
}
Node<E> currNode = getNode(size - 1);
Node<E> prevNode;
if (size - 2 >=0) {
prevNode = getNode(size - 2);
} else {
prevNode = head;
}
prevNode.next = tail;
currNode.next = null;
size--;
return currNode.val;
}
public E remove(int index) {
checkElementIndex(index);
Node<E> currNode = getNode(index);
Node<E> prevNode;
if(index - 1 >= 0) {
prevNode = getNode(index - 1);
} else {
prevNode = head;
}
prevNode.next = prevNode.next.next;
currNode.next = null;
size--;
return currNode.val;
}
public E getFirst() {
if (isEmpty()) {
throw new NoSuchElementException();
}
return head.next.val;
}
public E getLast() {
if (isEmpty()) {
throw new NoSuchElementException();
}
return getNode(size - 1).val;
}
public E get(int index) {
checkElementIndex(index);
Node<E> currNode = getNode(index);
return currNode.val;
}
public E set(int index, E val) {
checkElementIndex(index);
Node<E> currNode = getNode(index);
E oldVal = currNode.val;
currNode.val = val;
return oldVal;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
private Node<E> getNode(int index) {
Node<E> p = head.next;
for (int i = 0; i < index; i++) {
p = p.next;
}
return p;
}
}
|