/* Singley Linked List in JS with Closures
*
* The most important thing to enable understanding of a linked list is that all nodes created still exist in memory, even if they're not stored in a varaible / immediately accessible via a variable reference
*
*/
function SLinkedlist() {
let head = null
let tail = null
let length = 0
function Node(val = null) {
let next = null
let value = val
return {
set next(node) {
next = node
},
get next() {
return next
},
set value(val) {
value = val
},
get value() {
return value
}
}
}
// Add a node to TAIL
function _push(node) {
if ( length > 0 ) {
// tail already exists
// we can set it reference this new node
tail.next = node
} else {
// unitialised list, so we set this first element to be the node
head = node
}
// derefernce the old tail
tail = node // and make the tail our new node
length += 1 // and increase the size of the list!
return node // return the node we're inserting
}
// Remove a node from TAIL
function _pop() {
// start search from head
// we need the n node, and n-1 nodes
// n-1 will be the 'second to last'
let n = head, nMinus1 = head
// as long as our current node isn't the tail, keep going through the list
while ( n.next ) {
nMinus1 = n // the node before our search node
n = n.next // current search node
}
nMinus1.next = null // remove reference to the tail
tail = nMinus1 // set the tail to be our second to last
length -= 1 // reduce length
if (!length) {
tail = head = null // if the list is now empty, make the head and tail reference nothing
}
return n // return our 'popped' node
}
// Add an item to the HEAD of the list
function _unshift(node) {
if ( !length ) {
// everything is empty so this will also be new tail
tail = node
} else {
// this node should reference the head
node.next = head
}
// dereference the head
head = node // and set it to the new node!
length += 1 // and increase length
return node // and return our added node
}
// Remove an item from the HEAD of the list
function _shift() {
let n = head // get the node to remove
head = head.next // set the head to whatever was next
length -= 1 // reduce length
if ( !length ) tail = null // if now empty, also set tail to null
return n // get our shifted element
}
return {
push: function(val = null) {
if (val === null) throw new Error('no value provided to push')
console.log('Adding value to END of list!', { val })
return _push(new Node(val))
},
pop: function() {
if ( !length ) throw new Error('cannot pop an empty list')
console.log('Removing item from END of list!')
return _pop()
},
unshift: function(val = null) {
if(val === null) throw new Error('no value provided to unshift')
console.log('Adding value to START of list!', { val })
return _unshift(new Node(val))
},
shift: function() {
if ( !length ) throw new Error('cannot shift from an empty list')
console.log('Removing item from START of list!')
return _shift()
},
print: function() {
if ( !head || !tail ) {
console.error({ list: [], length })
return
}
const list = []
currentNode = head
do {
list.push(currentNode.value)
currentNode = currentNode.next
} while ( currentNode )
console.info({ list, length, head: head.value, tail: tail.value })
}
}
}
// output
const list = new SLinkedlist()
list.print()
list.push(1)
list.print()
list.push(2)
list.print()
list.push(3)
list.print()
list.unshift(0)
list.print()
list.shift()
list.print()
list.pop()
list.print()
list.pop()
list.print()
list.pop()
list.print()