Linked Lists in ES5

A Linked List is a sequence of nodes with references between predecessor and successor. Nodes on a singly linked list only have a reference to their successor, whereas on doubly linked lists, each node also holds a reference to their predecessor.

This Data Structure shines on insertion and deletion operations since it is achieved in constant time. However, searching is not fast since we can't leverage good searching algorithms such as Binary Search. It also requires extra space to store references to predecessors/successors.

Implementation

Our linked list will implement the following basic operations :

• Insert (Append or Prepend)
• Delete
• Search
• String representation

To make the basic operations simple, every instance of our Doubly Linked List will hold a reference to the first and last elements in the list; it will also keep track of the number of nodes it contains.

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

The complete source code for data structure's including the unit tests for this implementation are included here.