Skip to content

Instantly share code, notes, and snippets.

@softwarespot
Last active April 21, 2017 19:11
Show Gist options
  • Save softwarespot/0022ba01b9331e69a419229983406860 to your computer and use it in GitHub Desktop.
Save softwarespot/0022ba01b9331e69a419229983406860 to your computer and use it in GitHub Desktop.
LinkedList implementation
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