Circular doubly linked list in JavaScript

Question

I've been studying data structures and have taken a stab at implementing a doubly LL in JavaScript. Please review and advise on any additional improvements and optimizations. I'm more interested in feedback particularly regarding the implementations of removeAt(), contains() and getItem() methods as they share similar, repetitive code:

//Blueprints
function Node(val){
  this.data = val;
  this.next = null;
  this.prev = null;
}

function DoublyList(){
  this._length = 0;
  this._isCircular = false;
  this.head = null;
  this.tail = null;
}

//Adds to the list
DoublyList.prototype.add = function(val){
  var node = new Node(val);

  if(this._length){
    this.tail.next = node;
    node.prev = this.tail;
    this.tail = node;
  }else{
    this.head = node;
    this.tail = node;
  }

  this._length++;
  return node;
}

//Check if list is empty
DoublyList.prototype.isEmpty = function(){
  return this._length===0;
}

//Contains method returns index if true
DoublyList.prototype.contains = function(val){
  if(this.isEmpty()){
    return 'List is Empty';
  }
  var currentNode = this.head, i=0;
  //if val is in 1st node
  if(currentNode.data === val){
    return 0;
  }
  //if val is in last node
  if(this.tail.data === val){
    return (this._length-1);
  }
  //if val is in middle
  while(i++ < (this._length-1)){
    if(currentNode.data === val){
      return (i-1);
    }
    currentNode = currentNode.next;
  }
  return false;
}

//Make circular
DoublyList.prototype.makeCircular = function(){
  if(!this.isEmpty()){
    this.head.prev = this.tail;
    this.tail.next = this.head;
    this._isCircular = true;
  }
}

//get data by node index
DoublyList.prototype.getItem = function(index){

  if(this.isEmpty()){
    return 'List is Empty';
  }

  if(index<0 || index > this._length){
    return 'Invalid Index!';
  }

  var currentNode = this.head, i=0;
  //if first item in list
  if(index===0){
    return currentNode.data;
  }
  //if last item in list
  if(index === (this._length-1)){
    return this.tail.data;
  }
  //if item is in middle of list
  while(i++ < index){
    currentNode = currentNode.next;
  }
  return currentNode.data;
}

DoublyList.prototype.removeAt = function(index){
  if(this.isEmpty()){
    return 'List is Empty';
  }

  if(index<0 || index > this._length){
    return 'Invalid Index!';
  }

  var currentNode = this.head, i=0;
  //if first item in list: O(1)
  if(index===0){
    this.head = currentNode.next;
    this.head.prev = this.tail;
    this.tail.next = this.head;
    this._length--;
    return this;
  }
  //if last item in list: O(1)
  if(index === (this._length-1)){
    this.tail = this.tail.prev;
    this.tail.next = this.head;
    this.head.prev = this.tail;
    this._length--;
    return this;
  }
  //if item is in middle of list: O(n)
  while(i++ < index){
    currentNode = currentNode.next;
  }
  var temp = currentNode;
  temp.prev.next = currentNode.next;
  this._length--;
  return this;
}

var doublyList = new DoublyList();

console.log('isEmpty:\n'+doublyList.isEmpty());
doublyList.add(5);
doublyList.add(10);
doublyList.add(15);
doublyList.add(20);
doublyList.add(25);
doublyList.add(30);
doublyList.add(35);
doublyList.add(40);

console.log('Added items...\n');
console.log('Original List:\n'+doublyList);
console.log('makeCircular:\n'+doublyList.makeCircular());
console.log('Circular List:\n'+doublyList);
console.log('Get 3rd item:\n'+doublyList.getItem(2));
console.log('Contains:\n'+doublyList.contains(15));
console.log('RemoveAt:\n'+doublyList.removeAt(2));

Answer 1

the main observation I have is that if you know the length, and you have the tail and head, then you should use that in getItem(index) (meaning that if you want the 8th element out of 10, you should start from the head and go down, 2 operations instead of 8)

Other than that:

• Contains can return a string, a number, or a boolean. That is bad design. In my mind it should return only a boolean. If you wanted to return the index, it should have been called indexOf
• The shortcuts you take in contains are probably not worth the code, by that I mean that unless you know that more often than not the target value is in the first or last node, I would not code exceptions for those cases.
• It is not intuitive that the caller must first add a node before turning the list into a circular one. Not to mention that makeCircular fails quietly when it does not make an empty list circular
• You should probably check _isCircular in removeAt(0), it seems as if you assume the list is circular now.

Personally, I would make the list always circular or never circular and optimize the code accordingly instead of checking this property and coding accordingly in 1 list.