Still Questioning Still Questioning - 3 months ago 18
Javascript Question

Remove node from Singly Linked List

I'm implementing a remove function for LL in Javascript.

Here's my function:



//Define Node obj
function Node(data){
this.data = data;
this.next = null;
}

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

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

//If empty, build as first node
if(!currentNode){
this.head = node;
this._length++;
return;
}

//iterate over until end of list
while(currentNode.next){
currentNode = currentNode.next;
}

//add/append new node
currentNode.next = node;
this._length++;

return node;
};

SinglyList.prototype.remove = function(index){
var currentNode = this.head, count=0, previous;
//if list is empty, exit out
if(this._length===0) return;

//Check if first node
if(index===0){
this.head = currentNode.next;
this._length--;
}else{

while(count<index){
previous = currentNode;
currentNode = currentNode.next;
count++;
}//end while

previous.next = currentNode.next;

return previous;
}// end if

};

var singlyList = new SinglyList();

singlyList.add(1);
singlyList.add(2);
singlyList.add(3);
singlyList.add(4);
singlyList.add(5);
singlyList.add(6);
singlyList.add(7);
singlyList.add(8);
singlyList.add(9);
singlyList.add(10);

console.log(JSON.stringify(singlyList));
console.log('Remove:\n'+JSON.stringify(singlyList.remove(5)));





Problem: If i had 10 nodes in my list and called this function to remove 5th node, this function only returns 4th-10th nodes where 5th is removed. However, i'd expect it to return 1-10th where 5th is removed. What am i doing wrong and how can i retrieve a list where only the 5th node is removed?

Answer

Still You made small mistake in your code

1) while loop should run till < index-1 as you are starting count at 0

2) You are not doing this._length-- after deleting node other than first

3) JSON.stringify starting printing with head element, when you are deleting node you are returning the previous node so you are getting wrong node list

The corrected code is here

//Define Node obj
function Node(data){
  this.data = data;
  this.next = null;
}

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

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

      //If empty, build as first node
      if(!currentNode){
        this.head = node;
        this._length++;
        return;
      }

      //iterate over until end of list
      while(currentNode.next){
        currentNode = currentNode.next;
      }

      //add/append new node
      currentNode.next = node;
      this._length++;

      return node;
};

SinglyList.prototype.remove = function(index){
  var currentNode = this.head, count=0, previous;
  //if empty, exit out
  if(this._length===0) return;

  //Check against first node
  if(index===0){
      this.head = currentNode.next;
      this._length--;
  }else{

      while(count<index-1){
        previous = currentNode;
        currentNode = currentNode.next;
        count++;
      }//end while

      previous.next = currentNode.next;
      this._length--;

      return this.head;
  }// end if

};

var singlyList = new SinglyList();

singlyList.add(1);
singlyList.add(2);
singlyList.add(3);
singlyList.add(4);
singlyList.add(5);
singlyList.add(6);
singlyList.add(7);
singlyList.add(8);
singlyList.add(9);
singlyList.add(10);

document.write(JSON.stringify(singlyList));
singlyList.remove(5)
document.write('After removing 5 :\n'+JSON.stringify(singlyList));