Linkedlist, (and a Stack) Options

[CSM]

I created a "simple" linked list. Mainly because I wanted to, and also because I will have to do one in another language for a lab coming up. I wanted a good base with which to work.

Here is the generated documentation: JSDoc (sorry about the slow loading)

Sorry for the code boxes, but I tried to put it on the Unofficial Konfabulator Wiki and the wiki wouldn't put all the code inside one <code> tag. It only grabbed the first /** **/ section and refused to cooperate.
I then tried to host it to my decrepit website as a txt file, and they formatted it so weird it wasn't even funny. So, here it is:

CODE

/**
* Creates a default LinkedList if no parameters are passed. If an array is passed, the become the default elements.
*
* @class
* This is a simple implementation of a LinkedList. The idea is that there is no "array" of objects, but rather a
* bunch of objects that know (have a link to) the next element in the list. This list is simple in the regard that
* it is only a singly linked list (only has links in one direction) and as such, it may not be as efficient at some
* tasks.<p>
* The original idea behind a linked list in "lower-level" languages such as C/C++ was that unlike an array, a LinkedList
* didn't require a large block of continuous memory. Each element could point to the memory location of the next
* object, and so objects could be "stuffed in the cracks" where they fit. The downside to this is some operations such
* as getting an element at a specific index require more time than an array of similar size. However, everything in
* Computer Science is based around trade-offs.<p>
* I do not claim ownership of the idea of a LinkedList, just the code contained within this class.
*
* @since February 22nd, 2008
* @author A.McBain, 2008
* @constructor
* @param {Array} [initialValues] The initial values.
* @throws IllegalArgumentError If the passed object is not an Array.
*/
function LinkedList(initialValues) {

/**
* Creates a default Element if no parameters are passed. If an object is passed, it is set as the value of this
* Element. If previous references is passed, is stored as such.
*
* @class
* This is a simple Element which stores a "link" to the previous element and the value of the current Element.
*
* @private
* @since February 22nd, 2008
* @author A.McBain, 2008
* @constructor
* @param {Object} [value] The initial value.
* @param {Element} [previous] The previous Element.
*/
function Element(value, previous) {

/**
* Current value of this Element.
*
* @type Object
*/
this.value = (value !== undefined)? value : null;

/**
* Link to the previous Element.
*
* @type Element
*/
this.previous = (previous !== undefined)? previous : null;

// Make sure the previous link is always valid.
this.watch("previous", function(prop, oldValue, newValue) {

// Check for a valid Element object.
if(!(newValue instanceof Element)) {
throw (new Error("Element->previous 'Expected an Element, received: " + (typeof newValue) + "'"));
}

return (newValue);
});

/**
* Returns a string representation of this LinkedList.
*
* @returns A string representation of the object.
* @type string
*/
this.toString = function() {
return ("Element(<- value: '" + this.value + "')");
};
}



/**
* Returns the Element at the specified index.
*
* @private
* @param {number} index The index of the Element.
* @returns An Element.
* @type Element
* @throws an Error if an invalid index is passed.
* @throws an Error if the index is not within the bounds of the LinkedList.
*/
function getElementAt(index) {

// If it is not a number, throw an error.
if(isNaN(index = Number(index))) {
throw (new Error("LinkedList:getElementAt() 'Expected a valid index (number), received: " + (typeof index) + "'"));
}

// Check bounds.
if(index < 0 || index >= _size) {
throw (new Error("LinkedList:getElementAt() 'Array index out of bounds: 0 < " + index + " < " + _size + "'"));
}

// We are going backwards, so invert the index.
index = _size - index - 1;

// Store the Element we are currently at.
var item = tail;

// Traverse the linked list.
for(var i = 0; i < index; i++) {
item = item.previous;
}

return (item);
}

/**
* Tail (last item) of this LinkedList.
*
* @private
* @type Element
*/
var tail = null;

/**
* Current size (number of objects) of this LinkedList. Stored as a convenience. Technically,
* 99% of all operations on this LinkedList could be done without ever knowing its real size.
*
* @private
* @type number
*/
var _size = 0;



/**
* Adds an object to this LinkedList.
*
* @param {Object} object The object to be added.
*/
this.add = function(object) {

// Create a new Element which points to the current tail, then replace the tail.
tail = new Element(object, tail);

// Grow the size.
_size++;
};

/**
* Adds an array of objects to this LinkedList.
*
* @param {Array} array The array to be added.
* @throws an Error if the passed value is not a valid Array.
*/
this.addAll = function(array) {

// If it is not an array, throw an error.
if(!(array instanceof Array)) {
throw (new Error("LinkedList->addAll() 'Expected an Array, received: " + (typeof array) + "'"));
}

// Add all the items one at a time.
for(var i = 0; i < array.length; i++) {
this.add(array[i]);
}
};

/**
* Empties this LinkedList.
*/
this.clear = function() {

// Clean up.
delete tail;

// Reset the tail.
tail = null;

// Reset the size.
_size = 0;
};

/**
* Returns whether or not the specified object is contained in this LinkedList.
*
* @returns <code>true</code> if the object was found; <code>false</code> otherwise.
* @type boolean
* @throws an Error if an invalid index is passed.
* @throws an Error if the index is not within the bounds of the LinkedList.
*/
this.contains = function(object) {

// Pass it off to indexOf, and convert its response to a boolean.
return ((this.indexOf(object) < 0)? false : true);
};

/**
* Gets the value at the specified index.
*
* @param {number} index The position from which to get the value.
* @returns The value of the object at the specified index.
* @type Object
* @throws an Error if an invalid index is passed.
* @throws an Error if the index is not within the bounds of the LinkedList.
*/
this.get = function(index) {

// Get the Element at the specified index and return its value.
return (getElementAt(index).value);
};

/**
* Returns the index of the specified object in this LinkedList. Due to the order in
* which the items are stored, this will always return the last index of an object.
*
* @param {Object} object The object who's index is being located.
* @returns A positive index; -1 if the object is not found.
* @type number
*/
this.indexOf = function(object) {
var index = -1; // Default value.

// The Element we are currently processing.
var item = tail;

// Have we found the item?
var found = false;

// The currently processed index.
var currIndex = 0;

// Iterate over the Elements.
// If the next item is null, or we have found the item, exit.
while (item !== null && !found) {

// Strict equals evaluation.
if(item.value === object) {

// Store current index and set exit condition.
index = _size - currIndex - 1;
found = true;
}

// Next item.
item = item.previous;
currIndex++;
}

return (index);
};

/**
* Inserts the given object at the specified index. All elements past that index will be shifted down.
*
* @param {number} index The position at which to insert the given object.
* @param {Object} object The object to be inserted.
* @throws an Error if an invalid index is passed.
* @throws an Error if the index is not within the bounds of the LinkedList.
*/
this.insert = function(index, object) {

// Get the Element at the given index.
var item = getElementAt(index);

// Create an Element out of the passed object and have it link
// to the Element which the current Element at this index links to.
var temp = new Element(object, item.previous);

// Now make that Element link to the new Element, effectively shifting all the elements.
item.previous = temp;

// Increase the size
_size++;
};

/**
* Inserts the given Array at the specified index. All elements past that index will be shifted down.
*
* @param {number} index The position at which to insert the given object.
* @param {Array} array The Array to be inserted.
* @throws an Error if the passed value is not a valid Array.
* @throws an Error if an invalid index is passed.
* @throws an Error if the index is not within the bounds of the LinkedList.
*/
this.insertAll = function(index, array) {

// If it is not an array, throw an error.
if(!(array instanceof Array)) {
throw (new Error("LinkedList->addAll() 'Expected an Array, received: " + (typeof array) + "'"));
}

// Only if there is at least one item.
if(array.length > 0) {

// Get the Element which is going to refer to the new Elements.
// (could be done after the loop, but when inserting larger arrays we want to throw the error sooner)
var next = getElementAt(index);

// Get the Element the to which the first new Element is going to point.
var prev = (index > 0)? getElementAt(index - 1) : null;

// Start the mini linked list.
var first = new Element(array[0], prev);
var item = first;

// Iterate over the new array and convert it to Elements.
for(var i = 1; i < array.length; i++) {

// Create a new Element with the specified value and make it point to the previous value.
item = new Element(array[i], item);
}

// Make the Element previously at the insertion index point to the last inserted Element.
next.previous = item;

// Update the size to accommodate the new items.
_size += array.length;
}
};

/**
* Returns whether or not this LinkedList contains any elements.
*
* @returns <code>true</code> if this LinkedList is empty; <code>false</code> otherwise.
*/
this.isEmpty = function() {
return (_size === 0);
};

/**
* Removes and returns the object at the specified index.
*
* @param {number} index The position of the object to be removed.
* @returns The object at the given index.
* @type Object
* @throws an Error if an invalid index is passed.
* @throws an Error if the index is not within the bounds of the LinkedList.
*/
this.remove = function(index) {

// Get the Element we want to remove.
var item = getElementAt(index);

// Store its value.
var value = item.value;

// If this isn't the last element.
if((index = Number(index) + 1) < _size) {

// Get the next Element, so we can repair the links. We don't want to lose parts of the list.
var next = getElementAt(Number(index) + 1);

// Patch the links to skip over the newly remove Element.
next.previous = item.previous;
} else {

// Make the previous item is the new tail, as we just removed the current one.
tail = item.previous;
}

// Decrease size
_size--;

// Clean up
delete (item);

return (value);
};

/**
* Set the value at the specified index.
*
* @param {number} index The position at which to set the new value.
* @param {Object} object The value to be set.
* @throws an Error if an invalid index is passed.
* @throws an Error if the index is not within the bounds of the LinkedList.
*/
this.set = function(index, object) {

// Get the Element at the specified index and change its value.
getElementAt(index).value = object;
};

/**
* Returns the size of this LinkedList.
*
* @returns The size.
* @type number
*/
this.size = function() {
return (_size);
};

/**
* Returns the portion of this LinkedList as specified by the start index (inclusive) and the
* end index (exclusive). The returned LinkedList is structurally independent of this LinkedList.
*
* @param {number} start The index specifying the low end of the sublist.
* @param {number} end The index specifying the high end of the sublist.
* @returns A new LinkedList containing the specified sublist.
* @type LinkedList
* @throws an Error if the start index is not a valid number.
* @throws an Error if the end index is not a valid number.
* @throws an Error if the range specified by the start and end indicies is not a valid.
* @throws an Error if the index is not within the bounds of the LinkedList.
*/
this.subList = function(start, end) {

// If it is not a number, throw an error.
if(isNaN(start = Number(start)) || start < 0) {
throw (new Error("LinkedList:subList() 'Expected a valid low-end index (number), received: " + (typeof start) + "'"));
}

// If it is not a number, throw an error.
if(isNaN(end = Number(end)) || end > _size) {
throw (new Error("LinkedList:subList() 'Expected a valid high-end index (number), received: " + (typeof end) + "'"));
}

// If it is not a valid range, throw an error.
if((end - start) < 0) {
throw (new Error("LinkedList:subList() 'Expected a valid low-end index (number), received: " + (typeof start) + "'"));
}

// The new sublist.
var sublist = new LinkedList();

// Get the end index Element.
var item = getElementAt(end - 1);

// Iterate over the Elements. Exit when we find a null element or reach the end of our sublist.
for(var i = start; i < end; i++) {

// Add the new items to the sublist.
if(sublist.size() > 0) {
sublist.insert(0, item.value);
} else {
sublist.add(item.value);
}

// Next item.
item = item.previous;
}

// Return the new sublist.
return (sublist);
};

/**
* Returns an Array object representing this LinkedList.
*
* @returns An Array object.
*/
this.valueOf = function() {
var value = []; // Array of this LinkedList

// The Element we are currently processing.
var item = tail;

// Iterate over the Elements.
// If the next item is null, exit.
while (item !== null) {
value[value.length] = item.value;

// Next item.
item = item.previous;
}

// Reverse the Array and return it.
return (value.reverse());
};

/**
* Returns a string representation of this LinkedList.
*
* @returns A string representation of the object.
* @type string
*/
this.toString = function() {
return ("LinkedList(" + this.valueOf() + ")");
};


// Insert the initial values.
if(initialValues !== undefined && initialValues !== null) {
this.addAll(initialValues);
}
}

With such an easy implementation to extend, it follows that anyone could create (for example) a Stack:

CODE

/**
* Creates a default Stack if no parameters are passed. If an array is passed, the become the default elements.
*
* @class
* This is a simple extension of LinkedList to provide Stack like functionality.<p>
* I do not claim ownership of the idea of a Stack, just the code contained within this class.
*
* @since February 22nd, 2008
* @author A.McBain, 2008
* @constructor
* @param {Array} [initialValues] The initial values.
* @throws IllegalArgumentError If the passed object is not an Array.
*/
function Stack(initialValues) {
LinkedList.call(this, initialValues);

/**
* Returns whether or not this Stack is empty.
*
* @returns <code>true</code> if this Stack contains no items; <code>false</code> otherwise.
*/
this.empty = function() {
return (this.isEmpty());
};

/**
* Looks at the object on the top of the Stack without removing it (from the stack).
*
* @returns The top of this Stack.
* @type Object
* @throws an Error if this Stack is empty.
*/
this.peek = function() {
return (this.get(this.size() - 1));
};

/**
* Removes and returns the object at the top of this Stack.
*
* @returns The top of this Stack.
* @type Object
* @throws an Error if this Stack is empty.
*/
this.pop = function() {
return (this.remove(this.size() - 1));
};

/**
* Pushes an object onto the top of this Stack.
*
* @see #add
* @param {Object} object The object to be added.
*/
this.push = function(object) {
this.add(object);
};

/**
* Returns the 1 based index of the location of the specified object on the Stack. This
* number indicates the distance from the top of the Stack. The top of the Stack is 1.
*
* @param {Object} object The object to be located.
* @returns A positive index; -1 if the object is not found.
* @type number
*/
this.search = function(object) {
var index = -1;
return (((index = this.indexOf(object)) < 0)? index : this.size() - index);
};

this.toString = function() {
return ("Stack(" + this.valueOf() + ")");
};
}

// Edit:
Yes you can thank me for totally blowing up the XML RSS Feed
// Dbl Edit:
Not even a "But why!?"? That's sad.

[CSM]

No data structure junkies?

[CSM]

No, I'm not spamming the XML feed again. This time I've converted my (originally written in) C++ BinarySearchTree class to JavaScript. The JSDoc API is available at my website, and the source to the implementation can be found via the JSDoc or directly here. Sorry if it loads slow, I don't have anywhere else to host it.

This class probably isn't of much interest to most, as with JS one could just implement a binary search function on a standard array. However, I put the code out there nonetheless. The code should cover all possible cases for removing elements. I do have code for an AVL tree, however, I did not fully implement it as the remove method does not rebalance the tree as needed. So rather than put out an incomplete implementation, I chose to not put it out at all. This class was created as a result of taking a data structures course in C++ where using such structures are common place and the implementation details and reasons for needing one are not lost on the programmers of the language.

Please do not infer that because I can (now) program in C++ that I actually like the language. I have a slight dislike of its syntax and conventions, despite the power it might offer. Plus, of all the languages I have used, it offers the 2nd worst error messages I have ever seen. SWI-Prolog takes the cake for worst.