Last active
August 14, 2022 19:43
-
-
Save sebinsua/b4504593fcf721fd40054e1fc261bc5d to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class SinglyLinkedListNode { | |
constructor(value) { | |
this.value = value; | |
this.tail = null; | |
} | |
valueOf() { | |
return this.value; | |
} | |
} | |
class SinglyLinkedList { | |
constructor(values = []) { | |
this.head = null; | |
this.length = 0; | |
for (const value of values) { | |
this.push(value); | |
} | |
} | |
unshift(value) { | |
const node = new SinglyLinkedListNode(value); | |
const currentHead = this.head; | |
node.tail = currentHead; | |
this.head = node; | |
this.length++; | |
} | |
shift() { | |
const currentHead = this.head; | |
const value = currentHead ? currentHead.value : null; | |
this.head = currentHead.tail; | |
this.length--; | |
return value; | |
} | |
push(value) { | |
const node = new SinglyLinkedListNode(value); | |
if (!this.head) { | |
this.head = node; | |
this.length++; | |
return; | |
} | |
let currentNode = this.head; | |
while (currentNode.tail) { | |
currentNode = currentNode.tail; | |
} | |
currentNode.tail = node; | |
this.length++; | |
} | |
pop() { | |
if (!this.head) { | |
return null; | |
} | |
let currentNode = this.head; | |
while (currentNode.tail) { | |
if (currentNode.tail && !currentNode.tail.tail) { | |
const value = currentNode.tail.value; | |
currentNode.tail = null; | |
this.length--; | |
return value; | |
} | |
currentNode = currentNode.tail; | |
} | |
} | |
*[Symbol.iterator]() { | |
let currentNode = this.head; | |
if (!currentNode) { | |
return; | |
} | |
while (currentNode) { | |
yield currentNode.value; | |
currentNode = currentNode.tail; | |
} | |
} | |
} | |
const list = new SinglyLinkedList([-2, -1, 0]); | |
list.push(1); | |
list.push(2); | |
list.push(3); | |
list.pop(); | |
list.push(3); | |
for (let v of list) { | |
console.log(v); | |
} | |
console.log(list); |
See reverse
: https://codesandbox.io/s/distracted-banach-t7ds8z?file=%2Fsrc%2Findex.js%3A0-2149
Note: this actually consumes the list
right now, which you might not want tbh.
function reverse(ll) {
let currentNode = ll.tail;
if (!currentNode) {
return;
}
let previousNode = null;
while (currentNode) {
[currentNode.tail, previousNode, currentNode] = [
previousNode,
currentNode,
currentNode.tail
];
}
const rll = new SinglyLinkedList();
rll.tail = previousNode;
return rll;
}
See also, my attempt to use less variables.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
See also:
DoublyLinkedList.js