数据结构与算法 | 线性表 —— 链表

链表

定义

逻辑结构上一个挨一个的数据,在实际存储时,并没有像顺序表那样也相互紧挨着。恰恰相反,数据随机分布在内存中的各个位置,这种存储结构称为线性表的链式存储

由于分散存储,为了能够体现出数据元素之间的逻辑关系,每个数据元素在存储的同时,要配备一个指针,用于指向它的直接后继元素,即每一个数据元素都指向下一个数据元素(最后一个指向NULL(空))。这种结构成为 “单向链表“。

SingleLinkedList

在单向链表的基础上,给各个结点额外配备一个指针变量,用于指向每个结点的直接前趋元素。这样的链表被称为“双向链表”或者“双链表”。

DoublyLinkedList

当单向链表的尾部数据指向头部数据时,就构成了循环链表

CyclicLinkedList

单向链表

代码实现

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 one.wangwei.algorithms.datastructures.list.impl;

import one.wangwei.algorithms.datastructures.list.interfaces.IList;

/**
* 单向链表
*
* @param <T>
* @author wangwei
* @date 2018/05/03
*/
public class SingleLinkedList<T> implements IList<T> {

/**
* 集合大小
*/
private int size = 0;
/**
* 头部元素
*/
private Node<T> head = null;
/**
* 尾部元素
*/
private Node<T> tail = null;

/**
* 添加元素
*
* @param element
* @return
*/
@Override
public boolean add(T element) {
return addLast(element);
}

/**
* 添加元素
*
* @param index
* @param element
* @return
*/
@Override
public boolean add(int index, T element) {
checkElementIndex(index);
if (index == size) {
return add(element);
} else {
return addBefore(index, element);
}
}

/**
* 末端元素添加
*
* @param element
* @return
*/
private boolean addLast(T element) {
final Node<T> last = tail;
Node<T> newElement = new Node<>(element, null);
tail = newElement;
if (last == null) {
head = newElement;
} else {
last.next = newElement;
}
size++;
return true;
}

/**
* 插入元素
*
* @param element
* @param element
* @return
*/
private boolean addBefore(int index, T element) {
int prevIndex = index - 1;
Node<T> prev = prevIndex < 0 ? null : node(prevIndex);

Node<T> target = node(index);
Node<T> newElement = new Node<>(element, target);
if (prev == null) {
head = newElement;
} else {
prev.next = newElement;
}
size++;
return true;
}

/**
* 移除元素
*
* @param element
* @return
*/
@Override
public boolean remove(T element) {
if (element == null) {
for (Node<T> x = head; x != null; x = x.next) {
if (x.element == null) {
return unlink(x);
}
}
} else {
for (Node<T> x = head; x != null; x = x.next) {
if (element.equals(x.element)) {
return unlink(x);
}
}
}
return false;
}

/**
* 删除 index 位置上的元素
*
* @param index
* @return
*/
@Override
public T remove(int index) {
checkElementIndex(index);

int prevIndex = index - 1;
Node<T> prev = prevIndex < 0 ? null : node(prevIndex);
Node<T> node = node(index);
Node<T> next = node.next;

if (prev == null) {
head = next;
} else {
prev.next = next;
}

// 删除tail元素
if (next == null) {
tail = prev;
} else {
node.next = null;
}

T element = node.element;

node.element = null;
node = null;

size--;
return element;
}

/**
* 返回 index 位置上的元素
*
* @param index
* @return
*/
private Node<T> node(int index) {
checkElementIndex(index);
Node<T> x = head;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
}

/**
* 卸载元素
*
* @param node
*/
private boolean unlink(Node<T> node) {
// 找到前驱元素
Node<T> prev = null;
Node<T> x = head;

if (node.element == null) {
while (x != null && x.element != null) {
prev = x;
x = x.next;
}
} else {
while (x != null && !x.element.equals(node.element)) {
prev = x;
x = x.next;
}
}

if (x == null) {
return false;
}

final Node<T> next = node.next;

// 删除head元素
if (prev == null) {
head = next;
} else {
prev.next = next;
}

// 删除tail元素
if (next == null) {
tail = prev;
} else {
node.next = null;
}

node.element = null;
size--;
return true;
}

private void checkElementIndex(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
}

/**
* 设置index上的元素
*
* @param index
* @param element
* @return
*/
@Override
public T set(int index, T element) {
checkElementIndex(index);
Node<T> oldNode = node(index);
T oldElement = oldNode.element;
oldNode.element = element;
return oldElement;
}

/**
* 清空list集合
*/
@Override
public void clear() {
for (Node<T> x = head; x != null; ) {
Node<T> next = x.next;
x.element = null;
x.next = null;
x = next;
}
head = tail = null;
size = 0;
}

/**
* 判断是否包含某个元素
*
* @param element
*/
@Override
public boolean contains(T element) {
if (element == null) {
for (Node<T> x = head; x != null; x = x.next) {
if (x.element == null) {
return true;
}
}
} else {
for (Node<T> x = head; x != null; x = x.next) {
if (element.equals(x.element)) {
return true;
}
}
}
return false;
}

/**
* 集合大小
*
* @return
*/
@Override
public int size() {
return size;
}

/**
* 节点
*
* @param <T>
*/
private class Node<T> {

private T element = null;
private Node<T> next = null;

public Node(T element, Node<T> next) {
this.element = element;
this.next = next;
}
}

}

查看源代码

循环链表

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
package one.wangwei.algorithms.datastructures.list.impl;

import one.wangwei.algorithms.datastructures.list.IList;

/**
* 单向循环链表
*
* @param <T>
* @author wangwei
* @date 2018/05/03
*/
public class SinglyCircularLinkedList<T> implements IList<T> {

/**
* 集合大小
*/
private int size = 0;
/**
* 头部元素
*/
private Node<T> head = null;
/**
* 尾部元素
*/
private Node<T> tail = null;

/**
* 添加元素
*
* @param element
* @return
*/
@Override
public boolean add(T element) {
return addLast(element);
}

/**
* 添加元素
*
* @param index
* @param element
* @return
*/
@Override
public boolean add(int index, T element) {
checkElementIndex(index);
if (index == size) {
return add(element);
} else {
return addBefore(index, element);
}
}

/**
* 末端元素添加
*
* @param element
* @return
*/
private boolean addLast(T element) {
final Node<T> last = tail;
Node<T> newElement = new Node<>(element, head);
tail = newElement;
if (last == null) {
head = newElement;
} else {
last.next = newElement;
}
size++;
return true;
}

/**
* 插入元素
*
* @param element
* @param element
* @return
*/
private boolean addBefore(int index, T element) {
int prevIndex = index - 1;
Node<T> prev = prevIndex < 0 ? tail : node(prevIndex);
Node<T> target = node(index);

Node<T> newElement = new Node<>(element, target);
if (index == 0) {
head = newElement;
}

prev.next = newElement;
size++;
return true;
}

/**
* 移除元素
*
* @param element
* @return
*/
@Override
public boolean remove(T element) {
if (head == null) {
return false;
}
Node<T> x = head;
for (int i = 0; i < size; i++) {
if (element == null && x.element == null) {
return unlink(x);
}
if (element != null && element.equals(x.element)) {
return unlink(x);
}
x = x.next;
}
return false;
}

/**
* 删除 index 位置上的元素
*
* @param index
* @return
*/
@Override
public T remove(int index) {
checkElementIndex(index);

int prevIndex = index - 1;
Node<T> prev = prevIndex < 0 ? tail : node(prevIndex);
Node<T> node = node(index);
Node<T> next = node.next;

if (index == 0) {
head = next;
} else if (index == size - 1) {
tail = prev;
} else {
node.element = null;
}

prev.next = next;

T element = node.element;
// for GC
node.element = null;
node = null;

size--;
return element;
}

/**
* 返回 index 位置上的元素
*
* @param index
* @return
*/
private Node<T> node(int index) {
checkElementIndex(index);
Node<T> x = head;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
}

/**
* 卸载元素
*
* @param node
*/
private boolean unlink(Node<T> node) {
// 找到前驱元素
Node<T> prev = null;
Node<T> x = head;

int prevIndex = 0;
for (int i = 0; i < size; i++) {
if (node.element == null && x.element == null) {
break;
}
if (node.element != null && x.element.equals(node.element)) {
break;
}
prev = x;
x = x.next;
prevIndex = i;
}

final Node<T> next = node.next;

// 删除head元素
if (prevIndex == 0) {
head = next;
prev = tail;
}
// 删除tail元素
if (prevIndex == size - 1) {
tail = prev;
}

prev.next = next;

// for GC
node.element = null;
node = null;

size--;
return true;
}

private void checkElementIndex(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
}

/**
* 设置index上的元素
*
* @param index
* @param element
* @return
*/
@Override
public T set(int index, T element) {
checkElementIndex(index);
Node<T> oldNode = node(index);
T oldElement = oldNode.element;
oldNode.element = element;
return oldElement;
}

/**
* 清空list集合
*/
@Override
public void clear() {
for (Node<T> x = head; x != null; ) {
Node<T> next = x.next;
x.element = null;
x.next = null;
x = next;
}
head = tail = null;
size = 0;
}

/**
* 判断是否包含某个元素
*
* @param element
*/
@Override
public boolean contains(T element) {
if (head == null) {
return false;
}
Node<T> x = head;
for (int i = 0; i < size; i++) {
if (element == null && x.element == null) {
return true;
}
if (element != null && element.equals(x.element)) {
return true;
}
x = x.next;
}
return false;
}

/**
* 集合大小
*
* @return
*/
@Override
public int size() {
return size;
}

/**
* 节点
*
* @param <T>
*/
private class Node<T> {

private T element;
private Node<T> next;

public Node(T element, Node<T> next) {
this.element = element;
this.next = next;
}
}
}

查看源代码

双向链表

代码实现

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
package one.wangwei.algorithms.datastructures.list.impl;

import one.wangwei.algorithms.datastructures.list.interfaces.IList;

/**
* 双向链表结构
*
* @param <T>
* @author wangwei
* @date 2018/04/28
*/
public class DoublyLinkedList<T> implements IList<T> {

/**
* 集合大小
*/
private int size = 0;
/**
* 头部元素
*/
private Node<T> head = null;
/**
* 尾部元素
*/
private Node<T> tail = null;

/**
* 添加元素
*
* @param element
* @return
*/
@Override
public boolean add(T element) {
return addLast(element);
}

/**
* 添加元素
*
* @param index
* @param element
* @return
*/
@Override
public boolean add(int index, T element) {
checkElementIndex(index);
if (index == size) {
return add(element);
} else {
return addBefore(element, node(index));
}
}

/**
* 末端元素添加
*
* @param element
* @return
*/
private boolean addLast(T element) {
final Node<T> last = tail;
Node<T> newElement = new Node<>(last, element, null);
tail = newElement;
if (last == null) {
head = newElement;
} else {
last.next = newElement;
}
size++;
return true;
}

/**
* 插入元素
*
* @param element
* @param target
* @return
*/
private boolean addBefore(T element, Node<T> target) {
Node<T> pred = target.prev;
Node<T> newElement = new Node<>(pred, element, target);
target.prev = newElement;
if (pred == null) {
head = newElement;
} else {
pred.next = newElement;
}
size++;
return true;
}

/**
* 移除元素
*
* @param element
* @return
*/
@Override
public boolean remove(T element) {
if (element == null) {
for (Node<T> x = head; x != null; x = x.next) {
if (x.element == null) {
unlink(x);
return true;
}
}
} else {
for (Node<T> x = head; x != null; x = x.next) {
if (element.equals(x.element)) {
unlink(x);
return true;
}
}
}
return false;
}

/**
* 删除 index 位置上的元素
*
* @param index
* @return
*/
@Override
public T remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}

/**
* 返回 index 位置上的元素
*
* @param index
* @return
*/
private Node<T> node(int index) {
// 二分查找
if (index < (size >> 1)) {
Node<T> x = head;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
} else {
Node<T> x = tail;
for (int i = size - 1; i > index; i--) {
x = x.prev;
}
return x;
}
}

/**
* 卸载元素
*
* @param node
*/
private T unlink(Node<T> node) {
final T element = node.element;
final Node<T> prev = node.prev;
final Node<T> next = node.next;

// 删除head元素
if (prev == null) {
head = next;
} else {
prev.next = next;
node.prev = null;
}

// 删除tail元素
if (next == null) {
tail = prev;
} else {
next.prev = prev;
node.next = null;
}

node.element = null;
size--;
return element;
}

private void checkElementIndex(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
}

/**
* 设置index上的元素
*
* @param index
* @param element
* @return
*/
@Override
public T set(int index, T element) {
checkElementIndex(index);
Node<T> oldNode = node(index);
T oldElement = oldNode.element;
oldNode.element = element;
return oldElement;
}

/**
* 清空list集合
*/
@Override
public void clear() {
for (Node<T> x = head; x != null; ) {
Node<T> next = x.next;
x.element = null;
x.next = null;
x.prev = null;
x = next;
}
head = tail = null;
size = 0;
}

/**
* 判断是否包含某个元素
*
* @param element
*/
@Override
public boolean contains(T element) {
if (element == null) {
for (Node<T> x = head; x != null; x = x.next) {
if (x.element == null) {
return true;
}
}
} else {
for (Node<T> x = head; x != null; x = x.next) {
if (element.equals(x.element)) {
return true;
}
}
}
return false;
}

/**
* 集合大小
*
* @return
*/
@Override
public int size() {
return size;
}

/**
* 节点
*
* @param <T>
*/
private class Node<T> {

private T element = null;
private Node<T> prev = null;
private Node<T> next = null;

public Node(Node<T> prev, T element, Node<T> next) {
this.element = element;
this.prev = prev;
this.next = next;
}
}

}

查看源代码

特点

线性表的链式存储相比于顺序存储,有两大优势:

  1. 链式存储的数据元素在物理结构没有限制,当内存空间中没有足够大的连续的内存空间供顺序表使用时,可能使用链表能解决问题。(链表每次申请的都是单个数据元素的存储空间,可以利用上一些内存碎片)
  2. 链表中结点之间采用指针进行链接,当对链表中的数据元素实行插入或者删除操作时,只需要改变指针的指向,无需像顺序表那样移动插入或删除位置的后续元素,简单快捷。

链表和顺序表相比,不足之处在于,当做遍历操作时,由于链表中结点的物理位置不相邻,使得计算机查找起来相比较顺序表,速度要慢。

参考资料

请我喝杯咖啡吧~