An implementation of a double linked list

Question

Here is my implementation of double linked list. Is it possible to reduce the code and improve it?

Some methods here:

• head (returns head of the list) tail (returns tail of the list);
• append (param: new data; add new item to the end of the list);
• deleteAt (param: index; deletes item by index; error handling)
• at(returns item by index; error handling)
• insertAt (inserts item by index; new item should be placed at the specified index)
• reverse (rearranges the list's items back-to-front)
• each (param: function; applies specified function to each item of the list)
• indexOF(param: item; return index of the specified item (first entry))

function List() {
    this.length = 0;
    this._head = null;
    this._tail = null;
}

List.prototype = {

    head: function() {
      if (this.length > 0) {
          return this._head;
      } else {
          throw new Error("List has zero length.");
      }
    },

    tail: function() {
      if (this.length > 0) {
          return this._tail;
      } else {
           throw new Error("List has zero length.");
      }
    },

    append: function(value) {
        var node = {
            value: value,
            next: null,
            prev: null,
        }
        if (this.length == 0) {
            this._head = node;
            this._tail = node;
        } else {
            this._tail.next = node;
            node.prev = this._tail;
            this._tail = node;
        }
        this.length++;
        return this;
    },

    deleteAt: function(index) {
        if (index < this.length) {

            var node = this._head;
            var i = 0;
            while (i < index) {
                node = node.next;
                i++;
            }
            while (i != this.length - 1) {
                node.value = node.next.value;
                this._tail = node;
                node = node.next;
                i++;
            }
            node.value = null;
            node.next = null;
            this.length--;
            return this;
        } else {
            throw new Error("The index of the item that you have selected more than the length of the list.");
        }
    },

    at: function (index) {
      return this._at(index).value;
    },

    _at: function(index) {
        if (this.length < index) {
            throw new Error("The index of the item that you have selected more than the length of the list.");
        } else {
            var node = this._head;
            var i = 0;
            while (i != index) {
                node = node.next;
                i++;
            }
            return node;
        }
    },

    insertAt: function(index, value) {
        if (index < this.length) {
            var node = {
                value: value,
                next: null,
                prev: null,
            }

            var nodeCur = this._at(index);
            var nodePrev = nodeCur.prev;
            var nodeNext = nodeCur.next;

            node.prev = nodePrev;
            node.next = nodeNext;
            nodePrev.next = node;
            nodeNext.prev = node;

            this.length++;

            return this;
        } else {
            throw new Error("The index of the item that you have selected more than the length of the list.");
        }
    },

    reverse: function() {

        var node_buf = {
            value: null,
            next: null,
            prev: null,
        }

        var node_head = this._head;
        var node_tail = this._tail;

        var i = 0;

        while (i < Math.floor(this.length / 2)) { 
            node_buf.value = node_tail.value;
            node_tail.value = node_head.value;
            node_head.value = node_buf.value;
            node_head = node_head.next;
            node_tail = node_tail.prev;
            i++;
        }

        return this;
    },

    each: function(callback) {
        var node = this._head;
        var i = 0;
        while (i < this.length) {
            node.value = callback(node.value);
            i++;
            node = node.next;            
        }
        return this;
    },

    indexOF: function(value) {
        var node = this._head;
        var i = 0;
        while (i != this.length) {
            if (node.value == value) {
                return i;
            }
            node = node.next;
            i++;
        }
        throw new Error("Value " + value + " is not found.");
    }

};

Answer 1

Constructor and append()

You spend a lot of effort on special cases. Your code would be a lot simpler if the object that holds the head and tail pointers looks just like any other node.

function List() {
    this.length = 0;
    this._next = this._prev = this;
}

List.prototype.append = function(value) {
    this._prev = this._prev._next = {
        value: value,
        _next: this,
        _prev: this._prev
    };
    this.length--;
    return this;
};

head() and tail()

Why do you want to expose the list's nodes? I recommend removing these functions altogether.

_at()

Loops with this pattern…

var i = 0;
while (i < …) {
    …
    i++;
}

… would be better written as for loops.

It would be a good idea to note in a comment that indexes start at 1, not 0, as is idiomatic for JavaScript. You should also check that the index parameter is positive.

deleteAt()

The whole point of a linked list is that you can insert or delete an element in the middle of the list without having to copy every subsequent data entry. Yet, that is precisely what your second while loop is doing. In that case, you might as well use an array instead of a linked list.

If parameter validation fails, return early. That avoids having many lines of code separating the throw new Error(…) from the condition that triggered the exception. It also avoids an extra level of indentation.

But you have a nice _at(index) helper function defined already. Why not take advantage of it?

List.prototype.deleteAt = function(index) {
    var nodeToDelete = this._at(index);
    nodeToDelete._next._prev = nodeToDelete._prev;
    nodeToDelete._prev._next = nodeToDelete._next;
    this.length--;
};

reverse()

In a doubly-linked list, each node has two pointers. Reversing the list is simply a matter of swapping the _prev and _next pointers of every node.