Uni-directional singly linked list in JavaScript I've been studying data structures and have taken a stab at implementing a singly LL in JavaScript. Please review and advise on any additional improvements and optimizations:



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

function SinglyList(){
  this._length = 0;
  this.head = null;
};

//Add
SinglyList.prototype.add = function(val){
  var node = new Node(val),
      currentNode = this.head;

  //if list is empty
  if(!currentNode){
    this.head = node;
    this._length++;
    return;
  }

  //locate tail
  while(currentNode.next){
    currentNode = currentNode.next;
  }
  //Add to the tail
  currentNode.next = node;
  this._length++;

  return node;
}
//isEmpty
SinglyList.prototype.isEmpty = function(){
  return this._length === 0;
}

//Contains
SinglyList.prototype.contains = function(val){
  var currentNode = this.head;

  if(this.isEmpty()) return;

  while(currentNode){
    if(currentNode.data === val) return true;
    currentNode = currentNode.next;
  }

  return false;
}
//Reversed
SinglyList.prototype.reverse = function(){
  var currentNode = this.head,
      prev = null;

  while(currentNode){
    var temp = currentNode.next;
    currentNode.next = prev;
    prev = currentNode;
    currentNode = temp;
  }
  this.head = prev;
  return this;
}
//RemoveAt
SinglyList.prototype.removeAt = function(index){

  if(index&lt;0 || index &gt; this._length)
    return;

  var currentNode = this.head, i=0, prev;

  //if 1st in the list
  if(index === 0){
    this.head = currentNode.next;
    this._length--;
    return this;
  }
  //Subsequent items in the list
  while(i++ &lt; index-1){
    prev = currentNode;
    currentNode = currentNode.next;
  }
  prev.next = currentNode.next;
  this.head = prev;
  this._length--;

  return this;
}
//Remove by value
SinglyList.prototype.removeByVal = function(val){
  if(this.isEmpty()) return;
  if(!this.contains(val)) return;

  var currentNode = this.head;

  if(currentNode.data===val){
    this.head = currentNode.next;
    this._length--;
    return this;
  }

  while(currentNode.next){
    if(currentNode.next.data===val){
      prev = currentNode;
    }
    currentNode = currentNode.next;
  }

  prev.next = prev.next.next;
  this._length--;

  return this;

}
//Append
SinglyList.prototype.append = function(val){
  this.add(val);
  return this;
}
//Prepend
SinglyList.prototype.prepend = function(val){
  var node = new Node(val),
      temp = this.head;

  node.next = temp;
  this.head = node;
  return this;
}

var singlyList = new SinglyList();

singlyList.add(5);
singlyList.add(10);
singlyList.add(15);
singlyList.add(20);
singlyList.add(25);
singlyList.add(30);
singlyList.add(35);
singlyList.add(40);

console.log('Singly LL:\n'+JSON.stringify(singlyList));
console.log('isEmpty method:\n'+singlyList.isEmpty());
console.log('Contains:\n'+singlyList.contains(5));

console.log('Reversed:\n'+JSON.stringify(singlyList.reverse()));
console.log('Remove:\n'+JSON.stringify(singlyList.removeAt(2)));
console.log('Reversed:\n'+JSON.stringify(singlyList.reverse()));

console.log('Append:\n'+JSON.stringify(singlyList.append(45)));
console.log('Prepend:\n'+JSON.stringify(singlyList.prepend(50)));
console.log('Remove by value:\n'+JSON.stringify(singlyList.removeByVal(50)));
Just to be sure, this will always be slower than a plain Array() in JavaScript, no matter the optimizations we might find.

After perusing your code I came to:


I like your old school prototyping approach with prototype
You should have a function to retrieve the last element
I would call the root tail or root, as the last element tends to be the head
I would not declare null values in your constructors, it makes no difference:

function Node(val){
  this.data = val;
};

function SinglyList(){
  this._length = 0;
};

You almost never use (read) ._length, I would not keep track of it and just have a function that calculates the length, your code would be so much neater
I would let removeByVal() find the index that needs to be removed and then call removeAt()
I like reverse(), I had to scratch my head at first, it's quite clever for me
JS people would expect unshift instead of prepend
JS people would expect push instead of add
I like that you provided a chainable version of push