Skip to content

Instantly share code, notes, and snippets.

@onteria
Created May 27, 2011 16:13
Show Gist options
  • Save onteria/995591 to your computer and use it in GitHub Desktop.
Save onteria/995591 to your computer and use it in GitHub Desktop.
A preliminary implementation of a basic LinkedList
/**
* @author onteria
* @description A library of functions to handle linked lists
* @name LinkedList
*/
// Expose our objects to APIs that use require()
exports.LinkedList = LinkedList;
exports.ListNode = ListNode;
/**
* @description Call a function on each of the list nodes
* @param {function} callback The function to call on each node in the form function(current_node) { }
*/
function EachNode(callback) {
var current_node = this.head;
for(var i = 0; i < this.length; i++) {
callback(current_node.value);
if(current_node.nextNode != undefined) {
current_node = current_node.nextNode;
}
}
}
/**
* @description Prepend a node to the head of a linked list
* @param {object} object the object to add to the start of the list
*/
function PrependNode(object) {
if (this.head == undefined) {
this.head = new ListNode(object);
}
else {
var tmp_node = new ListNode(object);
// Keep a placeholder of the current head value
var current_head = this.head;
// Point it's previous node to the new node
current_head.prevNode = tmp_node;
// and point the new node at the previous head node
tmp_node.nextNode = current_head;
// Finally make the new node the head node
this.head = tmp_node;
}
this.length++;
}
/**
* @description Append a node to the end of a linked list
* @param {object} object the object to add to the end of the list
*/
function AppendNode(object) {
var tmp_node = new ListNode(object);
if (this.head == undefined) {
this.head = tmp_node;
}
// Only the head node exists
else if (this.length == 1) {
tmp_node.prevNode = this.head;
this.head.nextNode = tmp_node;
}
else {
// We loop through the nodes until we get to the end
// The length property of our list lets us know when
// to stop.
var current_node = this.head;
for (var i = 1; i < this.length; i++) {
current_node = current_node.nextNode;
}
// Now, insert the temporary node at the end
tmp_node.prevNode = current_node;
current_node.nextNode = tmp_node;
}
this.length++;
}
/**
* @field
* @description Constructor to create a linked list
* @param {array} object_array An array of objects to populate the list
* @param {bool} prepend If true, prepend the objects, if false, append the objects (default: true)
* @return {object} The constructed LinkedList object
*/
function LinkedList(object_array, prepend) {
prepend = (prepend == undefined) ? true : prepend;
this.head = undefined;
this.length = 0;
this.PrependNode = PrependNode;
this.AppendNode = AppendNode;
this.EachNode = EachNode;
if (object_array.constructor == Array && object_array.length > 0) {
object_array.forEach(
function(object) {
if (prepend) {
this.PrependNode(object);
}
else {
this.AppendNode(object);
}
}, this
);
}
}
/**
* @field
* @description Constructor to create a linked list node
* @param {ListNode} previousNode An object to set as the previous node
* @param {ListNode} nextNode An object to set as the next node
* @return {object} The constructed LinkedList object
*/
function ListNode(value, previousNode, nextNode) {
this.value = value;
this.prevNode = previousNode;
this.nextNode = nextNode;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment