什么是链表
链表是一种基础的数据结构，是一种线性表，在链表中，数据存储在内存中分散的位置，可以存储多个值链表的的每个元素由一个存储元素本身的节点和下一个元素的引用组成。由于数据存储在不同的位置，每个数据只能够通过其链表项提供的指针访问，数据的添加只需通过替换添加任一侧的指针即可。
现实中链表:火车、链条、寻宝游戏、许多人手牵着手
常见的链表结构
- 单向链表
- 双向链表
- 循环链表
- 有序链表
优势
- 相对于数组，添加或移除元素不需要移动其他元素，在进行添加或移除元素时的效率高。
- 内存利用率高，只有在需要的时候才会创建内存空间。
劣势
查找链表的元素效率低，必须从链表的首节点或尾节点开始向后遍历查找
单向链表
概念
单向链表的链接方向是单向的，对单向链表的访问要通过顺序读取从头部开始，即单向链表能从头节点正向遍历访问下一个节点，直到单向链表的尾节点，单向链表的尾节点的指向永远为null，单向链表也不能逆向遍历前面的单向链表节点。
劣势
- 查找链表的元素效率低，必须从链表的第一个节点开始向后遍历查找
代码实现
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
|
export class Node{
constructor(element) {
this.element = element;
this.next = null;
}
}
export class LinkedList{
constructor() {
this.head = null;
this.length = 0;
}
push(element) {
const node = new Node(element);
let current;
if (this.head === null) {
this.head = node;
} else {
current = this.head;
while (current.next) {
current = current.next;
}
current.next = node;
}
this.length++;
}
removeAt(index) {
if (index >= 0 && index < this.length) {
let current = this.head;
let index = 0;
if (index === 0) {
this.head = current.next;
} else {
const previous = this.getElementAt(index - 1);
current = previous.next;
previous.next = current.next;
}
this.length--;
return current.element;
} else {
return undefined;
}
}
getElementAt(index) {
if (index >= 0 && index <= this.length) {
let current = this.head;
for (let i = 0; i < index && current; i++) {
current = current.next;
}
return current;
}
return undefined;
}
insert(index, element) {
if (index >= 0 && index <= this.length) {
const node = new Node(element);
if (index === 0) {
const current = this.head;
node.next = current;
this.head = node;
} else {
const previous = this.getElementAt(index - 1);
const current = previous.next;
node.next = current;
previous.next = node;
}
this.length++;
return true;
} else {
return false;
}
}
toString() {
if (!this.head) {
return '';
}
let objString = `${this.head.element}`;
let current = this.head.next;
for (let i = 1; i < this.size() && current; i++) {
objString = `${objString},${current.element}`
current = current.next;
}
return objString;
}
toArray() {
let current = this.head;
let array = [];
while (current) {
array.push(current.element);
current = current.next;
}
return array;
}
indexOf(element) {
let current = this.head;
for (let i = 0; i < this.length && current; i++) {
if (element === current.element) {
return i;
}
current = current.next;
}
return -1;
}
remove(element) {
let index = this.indexOf(element);
return this.removeAt(index);
}
size() {
return this.length;
}
isEmpty() {
return this.size() === 0;
}
getHead() {
return this.head;
}
clear() {
this.head = undefined;
this.length = 0;
}
}
let list = new LinkedList();
list.push(15);
list.toString();
|
双向链表
概念
双向链表和普通单向链表的区别在于，在单向链表中，一个节点只有链向下一个节点的链接；而在双向链表中，链接是双向的：一个链向下一个元素，另一个链向前一个元素。
在单向链表中，如果迭代时错过了要找的元素，就需要回到起点，重新开始迭，而双向链表，可以从头到尾，或者从尾到头。我们也可以访问一个特定节点的下一个或前一个元素。
优势
- 双向链表中提供了两种迭代的方法：从头到尾，或者从尾到头。
- 可以访问一个特定节点 的下一个或前一个元素。
劣势
- 每次添加或删除节点操作更复杂，需要操作的引用较多(4个)
- 内存空间占用比单向链表大
代码实现
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
| import { LinkedList, Node } from '/LinkedList/app.js';
export class DoublyNode extends Node {
constructor(element, next, prev) {
super(element, next);
this.prev = prev;
}
}
export class DoublyLinkedList extends LinkedList {
constructor() {
this.tail = undefined;
}
push(element) {
const node = new DoublyNode(element);
let current;
if (this.head === null) {
this.head = node;
this.tail = node;
} else {
this.tail.next = node;
node.prev = this.tail;;
this.tail = node;
}
this.length++;
}
insert(index, element) {
if (index >= 0 && index <= this.length) {
const node = new DoublyNode(element);
let current = this.head;
if (index === 0) {
if (this.head === null) {
this.head = node;
this.tail = node;
} else {
node.next = this.head;
current.prev = node;
this.head = node;
}
} else if (index === this.length) {
current = this.tail;
current.next = node;
node.prev = current;
this.tail = node;
} else {
const previous = this.getElementAt(index - 1);
const current = previous.next;
node.next = current;
previous.next = node;
current.prev = node;
node.prev = previous;
}
this.length++;
return true;
} else {
return false;
}
}
removeAt(index) {
if (index >= 0 && index < this.length) {
let current = this.head;
let index = 0;
if (index === 0) {
this.head = current.next;
if (this.length === 1) {
this.tail = undefined;
} else {
this.head.prev = undefined;
}
} else if (index === this.length - 1) {
current = this.tail;
this.tail = current.prev;
this.tail.next = undefined;
} else {
current = this.getElementAt(index);
const previous = current.prev;
previous.next = current.next;
current.next.prev = previous;
}
this.length--;
return current.element;
} else {
return undefined;
}
}
getTail() {
super.clear();
this.tail = undefined;
}
inverseToString() {
if (!this.tail) {
return '';
}
let objString = `${this.tail.element}`;
let previous = this.tail.prev;
while (previous !== null) {
objString = `${objString},${previous.element}`;
previous = previous.prev;
}
return objString;
}
}
let list = new DoublyLinkedList();
list.push(13);
console.log(list);
|
循环链表
概念
循环链表可以像链表一样只有单向引用，也可以像双向链表一样有双向引用。循环链表和链表之间唯一的区别在于，最后一个元素指向下一个元素的指针，不是引用undefined，而是指向第一个元素。
优势
- 遍历的时候可以从任意的节点开始，增加了遍历的灵活性
代码实现
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
| import { LinkedList, Node } from '/LinkedList/app.js';
export class CircularLinkedList extends LinkedList {
constructor() {
}
push(element) {
const node = new Node(element);
let current;
if (this.head == null) {
this.head = node;
} else {
current = this.getElementAt(this.size() - 1);
current.next = node;
}
node.next = this.head;
this.length++;
}
insert(element, index) {
if (index >= 0 && index <= this.length) {
const node = new Node(element);
let current = this.head;
if (index === 0) {
if (this.head === null) {
this.head = node;
node.next = this.head;
} else {
node.next = current;
current = this.getElementAt(this.size());
this.head = node;
current.next = this.head;
}
} else {
const previous = this.getElementAt(index - 1);
node.next = previous.next;
previous.next = node;
}
this.length++;
return true;
}
return false;
}
removeAt(index) {
if (index >= 0 && index < this.length) {
let current = this.head;
if (index === 0) {
if (this.size() === 1) {
this.head = undefined;
} else {
const removed = this.head;
current = this.getElementAt(this.size() - 1);
this.head = this.head.next;
current.next = this.head;
current = removed;
}
} else {
const previous = this.getElementAt(index - 1);
current = previous.next;
previous.next = current.next;
}
this.length--;
return current.element;
}
return undefined;
}
}
let list = new CircularLinkedList();
list.push(13);
console.log(list);
|
有序链表
概念
有序链表是指保持元素有序的链表结构。除了使用排序算法之外，我们还可以将元素插入到正确的位置来保证链表的有序性。
在有序链表中，数据是按照关键值有序排列的。一般在大多数需要使用有序数组的场合也可以使用有序链表。有序链表优于有序数组的地方是插入的速度（因为元素不需要移动），另外链表可以扩展到全部有效的使用内存，而数组只能局限于一个固定的大小中。
(下面的代码例子为一个从头节点到尾节点有序递减的有序链表)
优势
- 相比数组，可以扩展到全部有效的使用内存，而数组在大多数编程语言中只能局限于一个固定的大小中(PS:JavaScript的数组不属于固定大小的数组)
- 有序链表优于有序数组的插入速度
代码实现
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
| import { LinkedList } from '/LinkedList/app.js';
export const Compare = {
LESS_THAN: -1,
BIGGER_THAN: 1,
EQUALS: 0
};
export function defaultCompare(a, b) {
if (a === b) {
return Compare.EQUALS;
}
return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}
export class SortedLinkedList extends LinkedList {
constructor() {
this.compareFn = compareFn;
}
push(element) {
if (this.isEmpty()) {
super.push(element);
} else {
const index = this.getIndexNextSortedElement(element);
super.insert(element, index);
}
}
insert(element, index = 0) {
if (this.isEmpty()) {
return super.insert(element, index === 0 ? index : 0);
}
const pos = this.getIndexNextSortedElement(element);
return super.insert(element, pos);
}
getIndexNextSortedElement(element) {
let current = this.head;
let i = 0;
for (; i < this.size() && current; i++) {
const comp = this.compareFn(element, current.element);
if (comp === Compare.LESS_THAN) {
return i;
}
current = current.next;
}
return i;
}
}
let list = new SortedLinkedList();
list.push(13);
console.log(list);
|