-
Notifications
You must be signed in to change notification settings - Fork 1
/
dll.js
63 lines (57 loc) · 1.4 KB
/
dll.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
// A doubly-linked list class.
// Each item has prev, next, and value.
class DLL {
constructor(value, prev, next) {
this.value = value;
this.prev = prev || null;
this.next = next || null;
}
// Removes this node from a DLL
// The prev and next will still be valid after removal.
remove() {
let prev = this.prev;
let next = this.next;
if (prev) {
this.prev.next = next;
}
if (next) {
this.next.prev = prev;
}
}
// Call this on the first node in a list
toArray() {
let answer = [];
let node = this;
while (node) {
answer.push(node.value);
node = node.next;
}
return answer;
}
join(connector) {
return this.toArray().join(connector);
}
// Returns a new DLL with this value inserted at the beginning
// Can only be called on the head
// Returns the new head
prepend(value) {
if (this.prev) {
throw new Error('prepend should only be called on the head');
}
let newNode = new DLL(value, null, this);
this.prev = newNode;
return newNode;
}
// Returns a new DLL with this value appended at the end
// Can only be called on the tail
// Returns the new tail
append(value) {
if (this.next) {
throw new Error('append should only be called on the tail');
}
let newNode = new DLL(value, this, null);
this.next = newNode;
return newNode;
}
}
module.exports = DLL;