# 1. 单向链表和双向链表
# 单向链表 LinkedList
- 只能从头遍历到尾或者从尾遍历到头(一般从头到尾)。
- 链表相连的过程是单向的,实现原理是上一个节点中有指向下一个节点的引用。
- 单向链表有一个比较明显的缺点:可以轻松到达下一个节点,但回到前一个节点很难,在实际开发中, 经常会遇到需要回到上一个节点的情况。
# 双向链表 DoublyLinkedList
- 既可以从头遍历到尾,也可以从尾遍历到头。
- 链表相连的过程是双向的。实现原理是一个节点既有向前连接的引用,也有一个向后连接的引用。
- 双向链表可以有效的解决单向链表存在的问题。
- 双向链表缺点:
- 每次在插入或删除某个节点时,都需要处理四个引用,而不是两个,实现起来会困难些。
- 相对于单向链表,所占内存空间更大一些。
- 但是,相对于双向链表的便利性而言,这些缺点微不足道。
# 2. 双向链表结构
- 双向链表不仅有 head 指针指向第一个节点,而且有 tail 指针指向最后一个节点 。
- 每一个节点由三部分组成:
item
储存数据、prev
指向前一个节点、next
指向后一个节点。 - 双向链表的第一个节点的
prev
指向null
。 - 双向链表的最后一个节点的
next
指向null
。
# 3. 双向链表常见的操作
append(element)
向链表尾部追加一个新元素。insert(position, element)
向链表的指定位置插入一个新元素。getElement(position)
获取指定位置的元素。indexOf(element)
返回元素在链表中的索引。如果链表中没有该元素就返回 -1。update(position, element)
修改指定位置上的元素。removeAt(position)
从链表中的删除指定位置的元素。remove(element)
从链表删除指定的元素。isEmpty()
如果链表中不包含任何元素,返回trun
,如果链表长度大于 0 则返回false
。size()
返回链表包含的元素个数,与数组的length
属性类似。toString()
由于链表项使用了 Node 类,就需要重写继承自 JavaScript 对象默认的toString
方法,让其只输出元素的值。forwardString()
返回正向遍历节点字符串形式。backwordString()
返回反向遍历的节点的字符串形式。
# 4. 双向链表的封装
# 双向链表类
- DoublyNode 类继承单向链表的 Node 类,新添加
this.prev
属性,该属性用于指向上一个节点。 - DoublyLinkedList 类继承 LinkedList 类,新添加
this.tail
属性,该属性指向末尾的节点。
//单向链表的节点类
class Node{
constructor(data) {
this.data = data
this.next = null
}
}
//单向链表
class LinkedList{
constructor() {
// 链表头节点,初始为 null
this.head = null
// 初始链表长度为 0
this.length = 0
}
}
// 双向链表的节点类(继承单向链表的节点类)
class DoublyNode extends Node {
constructor(element) {
super(element)
this.prev = null
}
}
// 双向链表类继承单向链表类
class DoublyLinkedList extends LinkedList {
constructor() {
super()
this.tail = 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
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
# append(element)
// append(element) 往双向链表尾部追加一个新的元素
// 重写 append()
append(data) {
// 1、创建新节点
const newNode = new DoublyNode(data)
// 2、追加新节点
if (this.length === 0) {
// 链表长度为 0 时,直接修改头尾指针即可
this.head = newNode
this.tail = newNode
} else {
// !!跟单向链表不同,不用通过循环找到最后一个节点,因为有尾指针
// 当添加一个节点时,涉及3个指针要修改
// 1、原来的尾节点的next指针要指向新节点
// 2、新节点的prev指针要指向原来的尾节点
// 3、尾指针要指向新节点
this.tail.next = newNode
newNode.prev = this.tail
this.tail = newNode
}
// 3、追加完新节点后,链表长度 + 1
this.length++
}
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
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
# insert(position, element)
// insert(position, data) 插入元素
// 重写 insert()
insert(position, data) {
// 1、对 position 进行越界判断,不能小于 0 或大于链表长度
if (position < 0 || position > this.length) return false
// 2、创建新的双向链表节点
const newNode = new DoublyNode(data)
// 3、插入节点,有3钟情况要考虑
// 3.1 在第 0 个位置插入
if (position === 0) {
if (this.length === 0) {
// 链表长度不为 0 时,直接修改头尾指针即可
this.head = newNode
this.tail = newNode
} else {
// 链表长度为 0 时,涉及3个指针要修改,要注意修改次序
// 1、新节点的next指针要指向原来的头节点
// 2、原来的头节点的prev指针要指向新节点
// 3、头指针要指向新节点
newNode.next = this.head
this.head.prev = newNode
this.head = newNode
}
} else if (position === this.length) {
// 3.2 在最后一个位置插入,涉及3个指针要修改,要注意修改次序
// 1、新节点的prev指针要指向原来的尾节点
// 2、原来的尾节点的next指针要指向新节点
// 3、尾指针要指向新节点
newNode.prev = this.tail
this.tail.next = newNode
this.tail = newNode
} else {
// 3.3 在中间位置插入,对应 0 < position < length 的情况
// 初始化一些状态变量
// 与单向链表不同的是,不需要previous变量保存上一个节点的指针了
let index = 0 // 遍历索引初始化为 0
let current = this.head // 遍历的当前节点初始化为 head
// 在 0 ~ position 之间遍历,不断地更新 current
// 直到找到要插入的位置
while (index++ < position) {
current = current.next
}
// 在当前节点之前插入新节点,涉及4个指针要修改,要注意修改次序
// 1、新节点的prev指针要指向当前节点的prev
// 2、新节点的next指针要指向当前节点
// 3、当前节点的prev的next指针要指向新节点
// 4、当前节点的prev指针要指向新节点
newNode.prev = current.prev
newNode.next = current
current.prev.next = newNode
current.prev = newNode
}
// 4、追加完新节点后,链表长度 + 1
this.length++
// 5、返回新添加的节点,方便其他操作
return newNode
}
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
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
# getData(position)
// getData(position) 获取指定位置的 data
// 重写 getData()
getData(position) {
// 1、position越界判断
if (position < 0 || position >= this.length) return null
// 2、判断要获取的节点离头尾节点哪个比较近
// 离头节点比较近
if (this.length / 2 >= position) {
// 获取指定 position 的节点
let index = 0
let current = this.head
while (index++ < position) {
current = current.next
}
// 3、返回相应节点的 data
return current.data
// 离尾节点比较近
} else {
let index = this.length - 1
let current = this.tail
while (index-- > position) {
current = current.prev
}
// 3、返回相应节点的 data
return current.data
}
}
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
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
# removeAt(position)
// removeAt(position) 删除指定位置的节点,并返回删除的那个节点
// 重写 removeAt()
removeAt(position) {
// 1、position越界判断
if (position < 0 || position >= this.length) return null
// 2、删除指定 position 节点
let current = this.head
// 删除第一个节点的情况
if (position === 0) {
// 链表内只有一个节点的情况
if (this.length === 1) {
this.head = null
this.tail = null
} else { // 链表内有多个节点的情况
this.head.next.prev = null
this.head = this.head.next
}
} else if (position === this.length - 1) { // 删除最后一个节点的情况
current = this.tail
this.tail.prev.next = null
this.tail = this.tail.prev
} else { // 删除 0 ~ this.length - 1 里面节点的情况
// 判断要删除的节点离头尾节点哪个比较近
// 离头节点比较近
if (this.length / 2 >= position) {
// 获取指定 position 的节点
let index = 0
while (index++ < position) {
current = current.next
}
// 删除相应节点
current.prev.next = current.next
current.next.prev = current.prev
} else { // 离尾节点比较近
// 获取指定 position 的节点
let index = this.length - 1
current = this.tail
while (index-- > position) {
current = current.prev
}
// 删除相应节点
current.prev.next = current.next
current.next.prev = current.prev
}
}
// 3、更新链表长度 -1
this.length--
// 4、返回被删除的节点,方便其他操作
return current
}
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
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
# forwardToString()
// forwardToString() 链表数据从前往后以字符串形式返回
forwardToString() {
let currentNode = this.head
let result = ''
// 遍历所有的节点,拼接为字符串,直到节点为 null
while (currentNode) {
result += currentNode.data + '--'
currentNode = currentNode.next
}
return result
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# backwardString()
// backwardString() 链表数据从后往前以字符串形式返回
backwardString() {
let currentNode = this.tail
let result = ''
// 遍历所有的节点,拼接为字符串,直到节点为 null
while (currentNode) {
result += currentNode.data + '--'
currentNode = currentNode.prev
}
return result
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# 其他方法的实现
双向链表的其他方法通过继承单向链表来实现。
# 完整实现
import { LinkedList, Node } from '../LinkedList/linkedList'
// 双向链表结构的封装
// 双向链表的节点类(继承单向链表的节点类)
class DoublyNode extends Node {
constructor(element) {
super(element)
this.prev = null
}
}
// 双向链表类(继承单向链表类)
export class DoublyLinkedList extends LinkedList {
constructor() {
super()
this.tail = null
}
// ------------ 链表的常见操作 ------------ //
// append(element) 往双向链表尾部追加一个新的元素
// 重写 append()
append(data) {
// 1、创建新节点
const newNode = new DoublyNode(data)
// 2、追加新节点
if (this.length === 0) {
// 链表长度为 0 时,直接修改头尾指针即可
this.head = newNode
this.tail = newNode
} else {
// !!跟单向链表不同,不用通过循环找到最后一个节点,因为有尾指针
// 当添加一个节点时,涉及3个指针要修改
// 1、原来的尾节点的next指针要指向新节点
// 2、新节点的prev指针要指向原来的尾节点
// 3、尾指针要指向新节点
this.tail.next = newNode
newNode.prev = this.tail
this.tail = newNode
}
// 3、追加完新节点后,链表长度 + 1
this.length++
}
// insert(position, data) 插入元素
// 重写 insert()
insert(position, data) {
// 1、对 position 进行越界判断,不能小于 0 或大于链表长度
if (position < 0 || position > this.length) return false
// 2、创建新的双向链表节点
const newNode = new DoublyNode(data)
// 3、插入节点,有3钟情况要考虑
// 3.1 在第 0 个位置插入
if (position === 0) {
if (this.length === 0) {
// 链表长度不为 0 时,直接修改头尾指针即可
this.head = newNode
this.tail = newNode
} else {
// 链表长度为 0 时,涉及3个指针要修改,要注意修改次序
// 1、新节点的next指针要指向原来的头节点
// 2、原来的头节点的prev指针要指向新节点
// 3、头指针要指向新节点
newNode.next = this.head
this.head.prev = newNode
this.head = newNode
}
} else if (position === this.length) {
// 3.2 在最后一个位置插入,涉及3个指针要修改,要注意修改次序
// 1、新节点的prev指针要指向原来的尾节点
// 2、原来的尾节点的next指针要指向新节点
// 3、尾指针要指向新节点
newNode.prev = this.tail
this.tail.next = newNode
this.tail = newNode
} else {
// 3.3 在中间位置插入,对应 0 < position < length 的情况
// 初始化一些状态变量
// 与单向链表不同的是,不需要previous变量保存上一个节点的指针了
let index = 0 // 遍历索引初始化为 0
let current = this.head // 遍历的当前节点初始化为 head
// 在 0 ~ position 之间遍历,不断地更新 current
// 直到找到要插入的位置
while (index++ < position) {
current = current.next
}
// 在当前节点之前插入新节点,涉及4个指针要修改,要注意修改次序
// 1、新节点的prev指针要指向当前节点的prev
// 2、新节点的next指针要指向当前节点
// 3、当前节点的prev的next指针要指向新节点
// 4、当前节点的prev指针要指向新节点
newNode.prev = current.prev
newNode.next = current
current.prev.next = newNode
current.prev = newNode
}
// 4、追加完新节点后,链表长度 + 1
this.length++
// 5、返回新添加的节点,方便其他操作
return newNode
}
// getData(position) 获取指定位置的 data
// 重写 getData()
getData(position) {
// 1、position越界判断
if (position < 0 || position >= this.length) return null
// 2、判断要获取的节点离头尾节点哪个比较近
// 离头节点比较近
if (this.length / 2 >= position) {
// 获取指定 position 的节点
let index = 0
let current = this.head
while (index++ < position) {
current = current.next
}
// 3、返回相应节点的 data
return current.data
// 离尾节点比较近
} else {
let index = this.length - 1
let current = this.tail
while (index-- > position) {
current = current.prev
}
// 3、返回相应节点的 data
return current.data
}
}
// removeAt(position) 删除指定位置的节点,并返回删除的那个节点
// 重写 removeAt()
removeAt(position) {
// 1、position越界判断
if (position < 0 || position >= this.length) return null
// 2、删除指定 position 节点
let current = this.head
// 删除第一个节点的情况
if (position === 0) {
// 链表内只有一个节点的情况
if (this.length === 1) {
this.head = null
this.tail = null
} else { // 链表内有多个节点的情况
this.head.next.prev = null
this.head = this.head.next
}
} else if (position === this.length - 1) { // 删除最后一个节点的情况
current = this.tail
this.tail.prev.next = null
this.tail = this.tail.prev
} else { // 删除 0 ~ this.length - 1 里面节点的情况
// 判断要删除的节点离头尾节点哪个比较近
// 离头节点比较近
if (this.length / 2 >= position) {
// 获取指定 position 的节点
let index = 0
while (index++ < position) {
current = current.next
}
// 删除相应节点
current.prev.next = current.next
current.next.prev = current.prev
} else { // 离尾节点比较近
// 获取指定 position 的节点
let index = this.length - 1
current = this.tail
while (index-- > position) {
current = current.prev
}
// 删除相应节点
current.prev.next = current.next
current.next.prev = current.prev
}
}
// 3、更新链表长度 -1
this.length--
// 4、返回被删除的节点,方便其他操作
return current
}
// forwardToString() 链表数据从前往后以字符串形式返回
forwardToString() {
let currentNode = this.head
let result = ''
// 遍历所有的节点,拼接为字符串,直到节点为 null
while (currentNode) {
result += currentNode.data + '--'
currentNode = currentNode.next
}
return result
}
// backwardString() 链表数据从后往前以字符串形式返回
backwardString() {
let currentNode = this.tail
let result = ''
// 遍历所有的节点,拼接为字符串,直到节点为 null
while (currentNode) {
result += currentNode.data + '--'
currentNode = currentNode.prev
}
return result
}
}
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
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
代码测试:
const doublyLinkedList = new DoublyLinkedList();
// append() 测试
console.log('append() 测试');
doublyLinkedList.append('ZZ');
doublyLinkedList.append('XX');
doublyLinkedList.append('CC');
console.log(doublyLinkedList.toString()); //--> ZZ XX CC
// insert() 测试
console.log('insert() 测试');
doublyLinkedList.insert(0, '00');
doublyLinkedList.insert(2, '22');
console.log(doublyLinkedList.toString()); //--> 00 ZZ 22 XX CC
// getData() 测试
console.log('getData() 测试');
console.log(doublyLinkedList.getData(1)); //--> ZZ
// indexOf() 测试
console.log('indexOf() 测试');
console.log(doublyLinkedList.indexOf('XX')); //--> 3
// removeAt() 测试
console.log('removeAt() 测试');
doublyLinkedList.removeAt(0);
doublyLinkedList.removeAt(1);
console.log(doublyLinkedList.toString()); //--> ZZ XX CC
// update() 测试
console.log('update() 测试');
doublyLinkedList.update(0, '111111');
console.log(doublyLinkedList.toString()); //--> 111111 XX CC
// remove() 测试
console.log('remove() 测试');
console.log(doublyLinkedList.remove('111111'));
// console.log(doublyLinkedList.remove('XX'));
console.log(doublyLinkedList.toString()); //--> XX CC
// forwardToString() 测试
console.log('forwardToString() 测试');
console.log(doublyLinkedList.forwardToString()); //--> XX--CC--
// backwardString() 测试
console.log('backwardString() 测试');
console.log(doublyLinkedList.backwardString()); //--> CC--XX--
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
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