| class Node { | |
| constructor(value) { | |
| this.value = value; | |
| this.next = null; | |
| } | |
| } | |
| class SinglyLinkedList { | |
| constructor() { | |
| this.head = null; | |
| this.tail = null; | |
| this.length = 0; | |
| } | |
| push(val) { | |
| let newNode = new Node(val); | |
| if(!this.head) { | |
| this.head = newNode; | |
| this.tail = this.head; | |
| } else { | |
| this.tail.next = newNode; | |
| this.tail = newNode; | |
| } | |
| this.length++; | |
| return this; | |
| } | |
| /** | |
| "How" >"are" > "you" | |
| nt | |
| c | |
| "How" >"are" > "you" | |
| nt | |
| c | |
| */ | |
| pop() { | |
| if(!this.head) return undefined; | |
| let current = this.head; | |
| let newTail = current; | |
| while(current.next) { | |
| newTail = current; | |
| current = current.next; | |
| } | |
| this.tail = newTail; | |
| this.tail.next = null; | |
| this.length--; | |
| if(this.length ===0) { | |
| this.head = null; | |
| this.tail = null; | |
| } | |
| return current; | |
| } | |
| shift() { | |
| if(!this.head) return undefined; | |
| let oldHead = this.head; | |
| this.head = this.head.next; | |
| this.length--; | |
| if(this.length ===0) { | |
| this.head = null; | |
| this.tail = null; | |
| } | |
| return oldHead; | |
| } | |
| unShift(val) { | |
| if(!this.head) return this.push(val); | |
| let newNode = new Node(val); | |
| newNode.next = this.head; | |
| this.head = newNode; | |
| this.length++; | |
| return this; | |
| } | |
| get(index) { | |
| if(index > this.length - 1 || index < 0) return null; | |
| let i = 0; | |
| let currentNode = this.head; | |
| while(i < index) { | |
| currentNode = currentNode.next; | |
| i++; | |
| } | |
| return currentNode; | |
| } | |
| set(index,value) { | |
| let node = this.get(index); | |
| if(node) { | |
| node.value = value; | |
| return true; | |
| } | |
| return false; | |
| } | |
| insert(index,value) { | |
| // ridiculous value | |
| if(index > this.length || index < 0) return false; | |
| // if insert at o, reuse unShift() | |
| if(index === 0) { | |
| return !!this.unShift(value); | |
| } | |
| // if insert at end, reuse push() | |
| if(index === this.length) { | |
| return !!this.push(value); | |
| } | |
| let newNode = new Node(value); | |
| let prevNode = this.get(index-1); | |
| newNode.next = prevNode.next; | |
| prevNode.next = newNode; | |
| this.length++; | |
| return true; | |
| } | |
| remove(index) { | |
| if(index > this.length -1 || index < 0 ) return undefined; | |
| // if remove at 0 , resuse shift() | |
| if(index === 0) return this.shift() | |
| // if remove at end, reuse pop() | |
| if(index === this.length - 1) return this.pop() | |
| let prevNode = this.get(index-1); | |
| let removedNode = prevNode.next; | |
| prevNode.next = removedNode.next; | |
| this.length--; | |
| return removedNode | |
| } | |
| reverse() { | |
| if(!this.head) return undefined; | |
| let currentNode = this.head; | |
| let prevNode; | |
| let nextNode = currentNode.next; | |
| this.head = this.tail; | |
| this.tail = currentNode; | |
| while(nextNode) { | |
| prevNode = currentNode; | |
| currentNode = nextNode; | |
| nextNode = currentNode.next; // keep to avoid losing ref | |
| currentNode.next = prevNode; | |
| } | |
| this.tail.next = null; | |
| return this; | |
| } | |
| reverse2() { | |
| if(!this.head) return undefined; | |
| let currentNode = this.head; | |
| let prevNode = null; | |
| let nextNode; | |
| this.head = this.tail; | |
| this.tail = currentNode; | |
| for(let i=0;i<this.length;i++){ | |
| nextNode = currentNode.next; | |
| currentNode.next = prevNode; | |
| prevNode = currentNode; | |
| currentNode = nextNode | |
| } | |
| return this; | |
| } | |
| print() { | |
| let arr= []; | |
| let currentNode = this.head; | |
| while(currentNode) { | |
| arr.push(currentNode.value) | |
| currentNode = currentNode.next | |
| } | |
| console.log(arr) | |
| } | |
| } | |
| let sl = new SinglyLinkedList(); | |
| sl.push("aaa") | |
| .push("bbb") | |
| .push("ccc") | |
| .push("ddd") | |
| .push("eee") | |