4
\$\begingroup\$

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<0 || index > 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++ < 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)));

\$\endgroup\$
2
  • \$\begingroup\$ there is an error with running the code snippet \$\endgroup\$
    – Tolani
    Sep 7, 2016 at 8:18
  • \$\begingroup\$ @TolaniJaiye-Tikolo fixed the snippet, of course know it is not beautiful any more ;0 \$\endgroup\$
    – konijn
    Sep 7, 2016 at 12:04

1 Answer 1

2
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ Thanks @konijn! great point on using removeByVal and removeAt together! \$\endgroup\$ Sep 7, 2016 at 23:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.