-
Notifications
You must be signed in to change notification settings - Fork 4
/
Link.js
267 lines (233 loc) · 6.2 KB
/
Link.js
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
/**
* @Author: zhuxiankang
* @Date: 2018-10-10 08:48:55
* @Desc: 链表
*/
/*
数组长度固定,当数组数据填满时,需要加入新的元素会非常困难,在数组中添加和删除元素也非常麻烦。
JavaScript中的数组主要问题在于它被实现成了对象,与其他语言的数组相比效率很低。
如果发现在实际使用时数组很慢,可以考虑使用链表代替它。当然如果需要随机方案,数组仍然是更好的选择。
*/
/**
* @Author: zhuxiankang
* @Date: 2018-10-08 20:14:28
* @Desc: Node类
* @Parm:
*/
function Node(element) {
this.element = element
// next是指向下一个节点的链接, 尾巴节点指向null
this.next = null
}
/**
* @Author: zhuxiankang
* @Date: 2018-10-08 20:15:24
* @Desc: 链表操作类
* @Parm:
*/
function LinkList() {
// 头节点
this.head = new Node('head')
}
/**
* @Author: zhuxiankang
* @Date: 2018-10-08 20:18:28
* @Desc: 在链表中查找节点
* @Parm:
*/
LinkList.prototype.find = function(element) {
var currentNode = this.head
while(currentNode.element !== element) {
currentNode = currentNode.next
}
return currentNode
}
/**
* @Author: zhuxiankang
* @Date: 2018-10-08 20:19:56
* @Desc: 向链表插入节点
* @Parm:
*/
LinkList.prototype.insert = function(element, after) {
var newNode = new Node(element)
var currentNode = this.find(after)
// 新节点的下一个节点指向被插入节点的下一个节点
console.log('current: ', currentNode)
newNode.next = currentNode.next
// 被插入节点的下一个节点指向新节点(新节点插入在被插入节点的后面)
currentNode.next = newNode
}
/**
* @Author: zhuxiankang
* @Date: 2018-10-08 20:24:28
* @Desc: 显示链表所有节点
* @Parm:
*/
LinkList.prototype.display = function() {
var currentNode = this.head
while(!(currentNode.next === null)) {
console.log(currentNode.next)
currentNode = currentNode.next
}
}
/**
* @Author: zhuxiankang
* @Date: 2018-10-08 20:32:14
* @Desc: 查找当前节点的前一个节点
* @Parm:
*/
LinkList.prototype.findPrevious = function(element) {
var currentNode = this.head
while(!(currentNode.next === null) && (currentNode.next.element !== element)) {
currentNode = currentNode.next
}
return currentNode
}
/**
* @Author: zhuxiankang
* @Date: 2018-10-08 20:34:31
* @Desc: 删除当前节点
* @Parm:
*/
LinkList.prototype.remove = function(element) {
delete this.find(element)
var preNode = this.findPrevious(element)
console.log('preNode: ', preNode)
if(!(preNode.next === null)) {
// 将删除的前一个节点指向删除的后一个节点
preNode.next = preNode.next.next
}
}
// var link = new LinkList()
// link.insert('ziyi2', 'head')
// console.log(link.find('ziyi2'))
// link.insert('ziyi3', 'ziyi2')
// console.log(link.find('ziyi3'))
// link.insert('ziyi4', 'ziyi3')
// console.log(link.find('ziyi4'))
// link.display()
// link.remove('ziyi3')
// link.display()
/**
* @Author: zhuxiankang
* @Date: 2018-10-09 08:29:20
* @Desc: 可从后向前遍历的双向链表
* @Parm:
*/
function DoublyNode(element) {
this.element = element
// 后继节点
this.next = null
// 前驱节点
this.previous = null
}
/**
* @Author: zhuxiankang
* @Date: 2018-10-09 08:32:39
* @Desc: 双向操作链表(可以反序遍历节点)
* @Parm:
*/
function DoublyLinkList() {
this.head = new DoublyNode('head')
}
/**
* @Author: zhuxiankang
* @Date: 2018-10-09 08:34:09
* @Desc: 查找节点
* @Parm:
*/
DoublyLinkList.prototype.find = function(element) {
var currentNode = this.head
while(currentNode.element !== element) {
currentNode = currentNode.next
}
return currentNode
}
/**
* @Author: zhuxiankang
* @Date: 2018-10-09 08:33:17
* @Desc: 插入节点
* @Parm:
*/
DoublyLinkList.prototype.insert = function(element, after) {
var newNode = new DoublyNode(element)
var currentNode = this.find(after)
newNode.next = currentNode.next
newNode.previous = currentNode
// 注意currentNode的前置节点仍然没有变化
currentNode.next = newNode
}
/**
* @Author: zhuxiankang
* @Date: 2018-10-09 08:36:27
* @Desc: 删除节点
* @Parm:
*/
DoublyLinkList.prototype.remove = function(element) {
var currentNode = this.find(element)
delete this.find(element)
while(!(currentNode.next === null)) {
currentNode.previous.next = currentNode.next
currentNode.next.previous = currentNode.previous
currentNode.next = null
currentNode.previous = null
}
}
/**
* @Author: zhuxiankang
* @Date: 2018-10-09 08:40:07
* @Desc: 查找最后一个节点
* @Parm:
*/
DoublyLinkList.prototype.findLast = function() {
var currentNode = this.head
while(!(currentNode.next === null)) {
currentNode = currentNode.next
}
return currentNode
}
/**
* @Author: zhuxiankang
* @Date: 2018-10-09 08:41:42
* @Desc: 反序显示双向链表的元素
* @Parm:
*/
DoublyLinkList.prototype.displayReverse = function() {
var currentNode = this.findLast()
while(!(currentNode.previous === null)) {
console.log(currentNode)
currentNode = currentNode.previous
}
}
// var doublyLink = new DoublyLinkList()
// doublyLink.insert('ziyi0', 'head')
// doublyLink.insert('ziyi1', 'ziyi0')
// doublyLink.insert('ziyi2', 'ziyi1')
// doublyLink.remove('ziyi1')
// doublyLink.displayReverse()
/**
* @Author: zhuxiankang
* @Date: 2018-10-09 08:52:42
* @Desc: 循环链表(可以反序遍历链表,不用付出额外代价创建双向链表,也可以从任何节点开始遍历链表)
* @Parm:
*/
function LoopLinkList() {
this.head = new Node()
// 默认尾节点指向头节点
this.head.next = this.head
}
/**
* @Author: zhuxiankang
* @Date: 2018-10-09 08:57:19
* @Desc: 显示链表
* @Parm:
*/
LoopLinkList.prototype.display = function() {
var currentNode = this.head
// 当循环到头节点时退出循环
while(!(currentNode.next === null) &&
!(currentNode.next.element === 'head')) {
console.log(currentNode.next)
currentNode = currentNode.next
}
}