-
Notifications
You must be signed in to change notification settings - Fork 0
/
linkedLists.js
255 lines (219 loc) · 6.54 KB
/
linkedLists.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
class Node {
constructor(value = null, nextNode = null) {
this.value = value;
this.nextNode = nextNode;
}
}
class LinkedList {
constructor() {
this.headNode = null;
}
// adds a new node containing value to the end of the list
append(value) {
const newNode = new Node(value);
// store the current head list
let currentNode = this.headNode;
// Edge: if the list is empty, add the new node to the head node
if (currentNode === null) {
this.headNode = newNode;
} else {
// this loop will deliver the pointer to the tail node
while (currentNode.nextNode !== null) {
currentNode = currentNode.nextNode;
}
// once the pointer reached to tail node, assign the new node
currentNode.nextNode = newNode;
}
}
// adds a new node containing value to the start of the list
prepend(value) {
const newNode = new Node(value);
const currentNode = this.headNode;
// assign new node as head node
this.headNode = newNode;
// add the original head node after the new node
this.headNode.nextNode = currentNode;
}
// returns the total number of nodes in the list
size() {
let currentNode = this.headNode;
let counter = 0;
// loop till the tail node
while (currentNode) {
counter++;
currentNode = currentNode.nextNode;
}
return counter;
}
// returns the first node in the list
head() {
return this.headNode;
}
// returns the last node in the list
tail() {
let currentNode = this.headNode;
// Edge: if the head node is empty, return null;
if (currentNode === null) {
return null;
}
while (currentNode.nextNode !== null) {
currentNode = currentNode.nextNode;
}
return currentNode;
}
// returns the node at the given index
at(index) {
// Edge: negative or non-integer
if (typeof index !== "number" || index < 0) {
console.error(
`Index must be an positive integer. Index passed: ${index}`
);
return;
}
let currentNode = this.headNode;
// create the counter to keep track of the list from head
let counter = 0;
// locate the pointer to the index
while (counter < index && currentNode !== null) {
currentNode = currentNode.nextNode;
counter++;
}
return currentNode;
}
// removes the last element from the list
pop() {
let currentNode = this.headNode;
// Edge: if the head node is empty
if (currentNode === null) {
return null;
}
// Edge: if there is one list
if (currentNode.nextNode === null) {
const poppedList = currentNode;
this.headNode = null;
return poppedList;
}
// track the one before the current node besides the current node
let precedingNode = null;
while (currentNode.nextNode !== null) {
precedingNode = currentNode;
currentNode = currentNode.nextNode;
}
// store the tail node
const poppedList = currentNode;
// clear the tail node
precedingNode.nextNode = null;
// return the popped tail node
return poppedList;
}
// returns true if the passed in value is in the list and otherwise returns false
contains(value) {
let currentNode = this.headNode;
while (currentNode !== null) {
// if there is a match return true and exit
if (currentNode.value === value) {
return true;
}
currentNode = currentNode.nextNode;
}
// otherwise return false
return false;
}
// returns the index of the node containing value, or null if not found.
find(value) {
if (this.headNode === null) {
return null;
}
let index = 0;
let currentNode = this.headNode;
while (currentNode !== null) {
// if there is a match return index and exit
if (currentNode.value === value) {
return index;
}
index++;
currentNode = currentNode.nextNode;
}
// otherwise, return null
return null;
}
// represents LinkedList objects as strings, so can print them out and preview them in the console. The format should be: ( value ) -> ( value ) -> ( value ) -> null
toString() {
let currentNode = this.headNode;
let strings = "";
while (currentNode !== null) {
strings += `( ${currentNode.value} ) -> `;
currentNode = currentNode.nextNode;
}
// add null at the end
strings += "null";
return strings;
}
// inserts a new node with the provided value at the given index
insertAt(value, index) {
if (typeof index !== "number" || index < 0) {
console.warn(`Index must be an positive integer. Index passed: ${index}`);
return;
}
const newNode = new Node(value);
if (index === 0) {
// add the original list at the index after the inserted list
newNode.nextNode = this.headNode;
this.headNode = newNode;
return;
}
// start the pointer from the head node
let targetNode = this.headNode;
// start another pointer from the node before the target index
let precedingNode = null;
let counter = 0;
// locate the pointer to the index
while (counter < index) {
// Edge: the index exceeded the list
if (targetNode === null) {
console.warn(`The index is out of bounds. Index passed: ${index}`);
return;
}
precedingNode = targetNode;
targetNode = targetNode.nextNode;
counter++;
}
newNode.nextNode = targetNode;
precedingNode.nextNode = newNode;
}
// removes the node at the given index (return boolean to indicate successful removal)
removeAt(index) {
if (typeof index !== "number" || index < 0) {
console.warn(`Index must be an positive integer. Index passed: ${index}`);
return;
}
// Edge: the head node is empty, or has only one list
if (index === 0) {
if (this.headNode === null) {
return true;
}
const followingNode = this.headNode.nextNode;
this.headNode = followingNode;
return true;
}
let targetNode = this.headNode;
let precedingNode = null;
let counter = 0;
while (counter < index) {
if (targetNode === null) {
console.warn("The index exceeds tail node index.");
return false;
}
precedingNode = targetNode;
targetNode = targetNode.nextNode;
counter++;
}
// set aside the nodes linked after the target node
const followingNodes = targetNode.nextNode;
if (precedingNode !== null) {
// overwrite the original target node with the following nodes
precedingNode.nextNode = followingNodes;
return true;
}
}
}