Created
September 14, 2024 22:54
-
-
Save notacouch/ce442cfd5f53494c70813aa423e2f906 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 Node { | |
| constructor(val) { | |
| this.value = val; | |
| } | |
| } | |
| class SLLNode extends Node { | |
| next = null; | |
| constructor(value) { | |
| super(value); | |
| } | |
| } | |
| class SinglyLinkedList { | |
| head = null; | |
| tail = null; | |
| length = 0; | |
| constructor() { | |
| } | |
| push(value) { | |
| const node = new SLLNode(value); | |
| if (!this.head) { | |
| this.head = this.tail = node; | |
| } else { | |
| this.tail.next = node; | |
| this.tail = node; | |
| } | |
| ++this.length; | |
| return this; | |
| } | |
| pop() { | |
| if (!this.head) return undefined; | |
| let poppedOff = this.tail; | |
| if (this.head === this.tail) { | |
| poppedOff = this.head; | |
| this.head = this.tail = null; | |
| this.length = 0; | |
| return poppedOff; | |
| } | |
| let nextNode = this.head; | |
| while(nextNode.next !== this.tail) { | |
| nextNode = nextNode.next; | |
| } | |
| nextNode.next = null; | |
| this.tail = nextNode; | |
| this.length--; | |
| return poppedOff; | |
| } | |
| shift() { | |
| if (!this.head) return undefined; | |
| let shiftedOff = this.head; | |
| this.head = this.head.next; | |
| shiftedOff.next = null; | |
| if (this.tail === shiftedOff) this.tail = null; | |
| this.length--; | |
| return shiftedOff; | |
| } | |
| unshift(value) { | |
| let node = new SLLNode(value); | |
| node.next = this.head; | |
| this.head = node; | |
| this.length++; | |
| if (!this.tail) this.tail = node; | |
| return this; | |
| } | |
| get(index) { | |
| if (index < 0 || index >= this.length) return null; | |
| let i = 0; | |
| let node = this.head; | |
| for (; i != index; ++i) { | |
| node = node.next; | |
| } | |
| return node; | |
| } | |
| set(index, value) { | |
| let node = this.get(index); | |
| if (!node) return false; | |
| node.value = value; | |
| return true; | |
| } | |
| insert(index, value) { | |
| if (index < 0 || index > this.length) return false; | |
| if (index === 0) return !!this.unshift(value); | |
| if (index === this.length) return !!this.push(value); | |
| let previousNode = this.get(index - 1); | |
| let node = new SLLNode(value); | |
| node.next = previousNode.next; | |
| previousNode.next = node; | |
| this.length++; | |
| return true; | |
| } | |
| remove(index) { | |
| if (index < 0 || index >= this.length) return undefined; | |
| if (index === 0) return this.shift(); | |
| if (index === this.length - 1) return this.pop(); | |
| let prevNode = this.get(index-1); | |
| let removed = prevNode.next; | |
| prevNode.next = removed.next; | |
| removed.next = null; | |
| this.length--; | |
| return removed; | |
| } | |
| removeNode(node) { | |
| if (!node || !node instanceof SLLNode) return undefined; | |
| if (node === this.head) return this.shift(); | |
| if (node === this.tail) return this.pop(); | |
| let previousNode = this.head; | |
| let currentNode = this.head; | |
| let i = 0; | |
| while(currentNode) { | |
| if (currentNode === node) { | |
| previousNode.next = currentNode.next; | |
| node.next = null; | |
| this.length--; | |
| return node; | |
| break; | |
| } | |
| i++; | |
| previousNode = currentNode; | |
| currentNode = currentNode.next; | |
| } | |
| return undefined; | |
| } | |
| reverse() { | |
| if (this.length <= 1) return this; | |
| let previousNode = this.head; | |
| let node = this.head.next; | |
| while(node) { | |
| let temp = node.next; | |
| node.next = previousNode; | |
| previousNode = node; | |
| node = temp; | |
| } | |
| let temp = this.tail; | |
| this.tail = this.head; | |
| this.head = temp; | |
| this.tail.next = null; | |
| return this; | |
| } | |
| [Symbol.iterator]() { | |
| let node; | |
| let previousNode; | |
| let iteration = 0; | |
| return { | |
| next: () => { | |
| if (iteration === 0) { | |
| node = this.head; | |
| } else { | |
| node = node.next; | |
| } | |
| iteration++; | |
| if (iteration-1 === this.length) { | |
| return { done: true } | |
| } | |
| return { done: false , value: node } | |
| } | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment