Last active
September 7, 2020 20:39
-
-
Save joannaylin/d3dfc926ba73833138e4571c8a0f9a15 to your computer and use it in GitHub Desktop.
singly linked list implementation in js
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.val = val; | |
this.next = null; | |
} | |
} | |
class SinglyLinkedList { | |
constructor() { | |
this.head = null; | |
this.tail = null; | |
this.length = 0; | |
} | |
// push: add node to end | |
push(val) { | |
var newNode = new Node(val) | |
if (!this.head) { | |
this.head = newNode | |
this.tail = newNode | |
} else { | |
this.tail.next = newNode | |
this.tail = newNode | |
} | |
this.length++; | |
return this; | |
} | |
// pop: remove node at end | |
pop() { | |
if (!this.head) return undefined; | |
var current = this.head | |
var 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: remove node from beginning | |
shift() { | |
if (!this.head) return undefined | |
var oldHead = this.head; | |
this.head = oldHead.next; | |
this.length-- | |
if (this.length===0) { | |
this.head = null; | |
this.tail = null; | |
} | |
return oldHead | |
} | |
// unshift: add node to beginning | |
unshift(val) { | |
var newNode = new Node(val) | |
if (!this.head) { | |
this.head = newNode; | |
this.tail = newNode; | |
} else { | |
newNode.next = this.head; | |
this.head = newNode; | |
} | |
this.length++ | |
return this | |
} | |
// get: retrieve a node by its position | |
get(idx) { | |
if (idx < 0 || idx >= this.length) return null | |
var counter = 0; | |
var current = this.head | |
while (counter !== idx) { | |
current = current.next; | |
counter++; | |
} | |
return current; | |
} | |
// set: change value of a node based on its position | |
set(idx, val) { | |
var foundNode = this.get(idx) | |
if (foundNode) { | |
foundNode.val = val | |
return true; | |
} | |
return false; | |
} | |
// insert: insert node based on position | |
insert(idx, val) { | |
if (idx < 0 || idx > this.length) return false; | |
if (idx === 0) { | |
this.unshift(val) | |
return true; | |
}; | |
if (idx === this.length) { | |
this.push(val); | |
return true; | |
}; | |
var newNode = new Node(val); | |
var beforeNode = this.get(idx-1); | |
var afterNode = beforeNode.next; | |
beforeNode.next = newNode; | |
newNode.next = afterNode; | |
this.length++; | |
return true; | |
} | |
// remove: remove node based on position | |
remove(idx) { | |
if (idx < 0 || idx > this.length) return undefined; | |
if (idx === this.length-1) { | |
this.pop() | |
} | |
if (idx === 0) { | |
this.shift() | |
} | |
var prevNode = this.get(idx-1) | |
var removeNode = prevNode.next | |
prevNode.next = removeNode.next | |
this.length--; | |
return removeNode; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment