Skip to content

Instantly share code, notes, and snippets.

@fabianuribe
Last active April 10, 2016 18:16
Show Gist options
  • Save fabianuribe/cf4f9af85e10521063ed to your computer and use it in GitHub Desktop.
Save fabianuribe/cf4f9af85e10521063ed to your computer and use it in GitHub Desktop.
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