Singly Linked List v1

node v10.21.0
version: 0.1.0
endpointsharetweet
/* 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()
Loading…

no comments

    sign in to comment