Created
May 27, 2011 16:13
-
-
Save onteria/995591 to your computer and use it in GitHub Desktop.
A preliminary implementation of a basic LinkedList
This file contains 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
/** | |
* @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