The Doubly Linked List Data Structure in Javascript
/** | |
* linked-list.js | |
* A module that implements a Doubly Linked List data Structure | |
* @module LinkedList | |
*/ | |
module.exports = LinkedList; | |
/** | |
* Represents a Linked List Node. | |
* @param {Object} data | |
* @constructor | |
*/ | |
function LinkedListNode (data) { | |
this.successor = null; | |
this.predecessor = null; | |
this.data = data; | |
} | |
/** | |
* Represents a Linked List. | |
* @constructor | |
*/ | |
function LinkedList () { | |
this.size = 0; | |
this.first = null; | |
this.last = null; | |
} | |
LinkedList.prototype = { | |
/** | |
* Inserts an elment at the end of the list. | |
* @param {...Object} element | |
*/ | |
append: function (element) { | |
var linkedListNode; | |
var i; | |
for (i = 0; i < arguments.length; i += 1) { | |
linkedListNode = new LinkedListNode(arguments[i]); | |
if (this.size === 0) { | |
this.first = linkedListNode; | |
this.last = linkedListNode; | |
} else { | |
this._link(this.last, linkedListNode); | |
this.last = linkedListNode; | |
} | |
this.size += 1; | |
} | |
}, | |
/** | |
* Inserts an elment at the begining of the list. | |
* @param {...Object} element | |
*/ | |
prepend: function (element) { | |
var linkedListNode; | |
var i; | |
for (i = 0; i < arguments.length; i += 1) { | |
linkedListNode = new LinkedListNode(arguments[i]); | |
if (this.size === 0) { | |
this.first = linkedListNode; | |
this.last = linkedListNode; | |
} else { | |
this._link(linkedListNode, this.first); | |
this.first = linkedListNode; | |
} | |
this.size += 1; | |
} | |
}, | |
/** | |
* Removes a node from the linked list. | |
* @param {LinkedListNode} node | |
*/ | |
remove: function (node) { | |
if(!node.hasOwnProperty('data') || | |
!node.hasOwnProperty('predecessor') || | |
!node.hasOwnProperty('successor')) { | |
throw('Not a LinkedListNode'); | |
} | |
if (this.first === node) { | |
this.first = node.successor; | |
} | |
if (this.last === node) { | |
this.last = node.predecessor; | |
} | |
this._link(node.predecessor, node.successor); | |
this.size -= 1; | |
return node; | |
}, | |
/** | |
* Finds a node Object based on its 'data' key. | |
* @param {Object} data | |
* @return {LinkedListNode|Number} The first LinkedListNode containing the data value or -1 if not present. | |
*/ | |
search: function (data) { | |
var currentNode = this.first; | |
while (currentNode.data !== data && currentNode.successor) { | |
currentNode = currentNode.successor; | |
} | |
if (currentNode.data === data ) { | |
return currentNode; | |
} else { | |
return -1; | |
} | |
}, | |
/** | |
* Returns a string valued representation of the object. | |
* @return {String} | |
*/ | |
toString: function () { | |
var node = this.first; | |
var separator = ','; | |
var string = ''; | |
if (!node) { | |
return string; | |
} | |
while (node.successor) { | |
string += node.data.toString() + separator; | |
node = node.successor; | |
} | |
return string + node.data.toString(); | |
}, | |
isEmpty: function () { | |
return this.size === 0; | |
}, | |
/** | |
* Links two LinkedListNodes | |
* @access private | |
* @param {LinkedListNode} predecessor | |
* @param {LinkedListNode} successor | |
*/ | |
_link: function (predecessor, successor) { | |
if (predecessor) { | |
predecessor.successor = successor; | |
} | |
if (successor) { | |
successor.predecessor = predecessor; | |
} | |
} | |
}; |
var LinkedList = require('linked-list.js'); | |
var assert = require('assert'); | |
var myList; | |
beforeEach(function() { | |
myList = new LinkedList(); | |
}); | |
describe('Linked list', function () { | |
describe('Append', function () { | |
it('Should save a reference to the first and last elments of the list', function () { | |
myList.append('dad'); | |
assert.equal(myList.first.data, 'dad'); | |
assert.equal(myList.last.data, 'dad'); | |
}); | |
it('Should insert an item at the end of the list', function () { | |
myList.append('dad'); | |
myList.append('son'); | |
assert.equal(myList.first.data, 'dad'); | |
assert.equal(myList.last.data, 'son'); | |
}); | |
it('Should increase list size', function () { | |
assert.equal(myList.size, 0); | |
myList.append('dad','mom'); | |
assert.equal(myList.size, 2); | |
}); | |
it('Should link inserted items', function () { | |
myList.append('dad', 'mom'); | |
assert.equal(myList.first.successor.data, 'mom'); | |
assert.equal(myList.last.predecessor.data, 'dad'); | |
}); | |
}); | |
describe('Prepend', function () { | |
it('Should save a reference to the first and last elments of the list', function () { | |
myList.prepend('dad'); | |
assert.equal(myList.first.data, 'dad'); | |
assert.equal(myList.last.data, 'dad'); | |
}); | |
it('Should insert an item at the top of the list', function () { | |
myList.prepend('dad'); | |
myList.prepend('son'); | |
assert.equal(myList.first.data, 'son'); | |
assert.equal(myList.last.data, 'dad'); | |
}); | |
it('Should increase list size', function () { | |
assert.equal(myList.size, 0); | |
myList.prepend('dad','mom'); | |
assert.equal(myList.size, 2); | |
}); | |
it('Should link inserted items', function () { | |
myList.prepend('dad', 'mom'); | |
assert.equal(myList.first.successor.data, 'dad'); | |
assert.equal(myList.last.predecessor.data, 'mom'); | |
}); | |
}); | |
describe('Search', function() { | |
beforeEach(function () { | |
myList.append('dad','mom','son','daugther','dog','cat'); | |
}); | |
it('Should find return an element in the list', function () { | |
var element = myList.search('dad'); | |
assert.equal(element.data, 'dad'); | |
}); | |
it('Should return -1 when the element doesnt exist in the list', function () { | |
var element = myList.search('uncle'); | |
assert.equal(element, -1); | |
}); | |
}); | |
describe('Remove', function () { | |
beforeEach(function () { | |
myList.append('dad','mom','son','daugther','dog','cat'); | |
}); | |
it('Should attempt to remove LinkedListNodes only', function () { | |
var execption; | |
try { | |
myList.remove('not-a-node'); | |
} catch (error) { | |
exception = error; | |
} | |
assert.equal(exception, 'Not a LinkedListNode'); | |
}); | |
it('Should be able to remove an element from the list', function () { | |
var element = myList.search('dog'); | |
assert.equal(element.data, 'dog'); | |
myList.remove(element); | |
assert.equal(myList.search('dog'), -1); | |
}); | |
it('Should return the removed element', function () { | |
var element = myList.search('dog'); | |
assert.equal(element.data, 'dog'); | |
var removedElement = myList.remove(element); | |
assert.equal(element, removedElement); | |
assert.equal(removedElement.data, 'dog'); | |
}); | |
it('Should decrease list size', function () { | |
var size = myList.size; | |
var element = myList.search('dog'); | |
myList.remove(element); | |
assert.equal(myList.size, size - 1); | |
}); | |
it('Should update First element refernce', function () { | |
var element = myList.search('dad'); | |
myList.remove(element); | |
assert.equal(myList.first.data, 'mom'); | |
}); | |
it('Should update last element reference', function () { | |
var element = myList.search('cat'); | |
myList.remove(element); | |
assert.equal(myList.last.data, 'dog'); | |
}); | |
}); | |
describe('toString', function () { | |
beforeEach(function() { | |
myList.append('dad','mom','son','daugther','dog','cat'); | |
}); | |
it('Should return a string with all the elements in the list.', function () { | |
assert.equal(myList.toString(), 'dad,mom,son,daugther,dog,cat'); | |
}); | |
it('Should return an empty string when the list is empty', function () { | |
var emptyList = new LinkedList(); | |
assert.equal(emptyList.toString(), ''); | |
}); | |
}); | |
}); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment