Last active
April 21, 2017 19:11
-
-
Save softwarespot/0022ba01b9331e69a419229983406860 to your computer and use it in GitHub Desktop.
LinkedList implementation
This file contains hidden or 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
function LinkedList() { | |
if (!(this instanceof LinkedList)) { | |
throw new TypeError('"LinkedList" cannot be called as a function. Use the "new" keyword to construct a new "LinkedList" object'); | |
} | |
this._head = undefined; | |
} | |
LinkedList.prototype = { | |
clear: function () { | |
var current = this._head; | |
while (current !== undefined) { | |
current.next = undefined; | |
current = current.next; | |
} | |
this._head = undefined; | |
return this; | |
}, | |
delete: function (index) { | |
var found = _findByIndex.call(this, index); | |
var previous = found.previous; | |
var removed = found.current; | |
// Store the removed node's next node reference | |
var next = removed.next; | |
// Remove the reference to the next node from the removed node | |
removed.next = undefined; | |
// Check if the head node was removed i.e. the previous wasn't changed from the initial value | |
// which is undefined | |
if (previous === undefined) { | |
this._head = next; | |
} else { | |
// Assign the previous node to point to the removed node's next reference node | |
previous.next = next; | |
} | |
// Return the removed node | |
return removed; | |
}, | |
get: function (index) { | |
return _findByIndex.call(this, index).current.data; | |
}, | |
forEach: function (fn, thisArg) { | |
var current = this._head; | |
var currIndex = 0; | |
while (current !== undefined) { | |
fn.call(thisArg, current.data, currIndex, current); | |
current = current.next; | |
currIndex += 1; | |
} | |
}, | |
push: function (data) { | |
var node = _createNode(data); | |
// If the "head" node is not defined, then define with the new node | |
if (this._head === undefined) { | |
this._head = node; | |
return node; | |
} | |
// Iterate through the list, checking if the "next" property contains the "next" node | |
var current = this._head; | |
while (current.next !== undefined) { | |
current = current.next; | |
} | |
current.next = node; | |
return this; | |
}, | |
reverse: function () { | |
var current = this._head; | |
var previous = undefined; | |
while (current !== undefined) { | |
var next = current.next; | |
current.next = previous; | |
previous = current; | |
current = next; | |
} | |
this._head = previous; | |
return this; | |
}, | |
toString: function () { | |
return JSON.stringify(this); | |
} | |
}; | |
// Define a read-only "size" property | |
Object.defineProperty(LinkedList.prototype, 'size', { | |
get: function () { | |
var size = 0; | |
var current = this._head; | |
while (current !== undefined) { | |
current = current.next; | |
size += 1; | |
} | |
return size; | |
} | |
}); | |
// LinkedList Example(s) | |
var list = new LinkedList(); | |
list.push('A'); | |
list.push('B'); | |
list.push('C'); | |
list.push('D'); | |
console.log('toString::', String(list)); | |
console.log('get::', list.get(1)); | |
console.log('delete::', list.delete(1)); | |
console.log('toString::', String(list)); | |
console.log('size::', list.size); | |
list.forEach(function (data, index, node) { | |
console.log('forEach::', data, index, node); | |
}); | |
list.reverse() | |
console.log('reverse::', String(list)); | |
list.clear(); | |
console.log('size::', list.size); | |
// Helper functions | |
// Wrapper to create a node | |
function _createNode(data) { | |
return { | |
data: data, | |
next: undefined | |
} | |
} | |
// Wrapper for finding the previous and current nodes by index. Throws an error when out of bounds. | |
// "this" is the current list | |
function _findByIndex(index) { | |
var current = this._head; | |
var previous = undefined; | |
var currIndex = 0; | |
while (currIndex !== index && current) { | |
previous = current; | |
current = current.next; | |
currIndex += 1; | |
} | |
// Check if the index provided, returned an empty node | |
if (current === undefined) { | |
throw new Error('Invalid argument, "index" was out of bounds'); | |
} | |
return { | |
previous: previous, | |
current: current | |
}; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment