-
Notifications
You must be signed in to change notification settings - Fork 0
/
linked-list.js
113 lines (94 loc) · 2.35 KB
/
linked-list.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
function LinkedList() {
this.head = null;
}
LinkedList.prototype.isEmpty = function() {
return this.head === null;
}
LinkedList.prototype.size = function() {
let count = 0;
// create new pointer to NOT loose the beging of the head
let curr = this.head;
// Traverse of the list and increase count
while (curr !== null) {
count++;
curr = curr.next;
}
return count;
}
LinkedList.prototype.prepend = function(val) {
// 1. create new node wtih val
let newNode = {
data: val,
// 2. make the newnode's next point to current head
next: this.head
};
// 3. update this.head to point to new nodde
this.head = newNode;
}
LinkedList.prototype.append = function(val) {
// 1. create new node with next point to null
// since this going to be at the end of list
let newNode = {
data: val,
next: null
};
let curr = this.head;
// if empty attach it to head and return
if(this.isEmpty()) {
this.head = newNode;
return
}
// 2. Traverse to the end of the list
while (curr.next !== null) {
curr = curr.next;
}
// 3. Make last node's next value point to new node
curr.next = newNode;
}
LinkedList.prototype.contains = function (val) {
let curr = this.head;
while (curr !== null) {
if (curr.data === val) {
return true;
}
curr = curr.next;
};
return false;
};
LinkedList.prototype.remove = function(val) {
let prev = null;
let curr = this.head
if (!this.contains(val)) {
return;
}
// if the value is at the head
if (this.head.data === val) {
this.head = this.head.next;
return;
}
// otherwise is not 1st node
while (curr.data !== val) {
prev = curr;
curr = curr.next;
}
prev.next = curr.next
}
// Try out: node linked-list.js
let list = new LinkedList();
// append
list.append(20);
list.append(10);
list.append(7);
list.append(5);
console.log(list)
// add at the top the list
list.prepend(25);
// check methods
console.log('-- isEmpty: ',list.isEmpty());
console.log('-- size: ',list.size())
console.log('-- contains 5 : ',list.contains(5))
// rmeoves nodes top and anywhere in the list
list.remove(7)
list.remove(20)
console.log('-- contains 7: ',list.contains(7))
console.log(list)