The Doubly Linked List Data Structure in Javascript

linked-list.js

/**
 * 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;
        }
    }
};

linked-list_test.js

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(), '');
        });
    });
});