Javascript linked list

Question

I am trying to write a linked list function that can remove the node by search value. If value matched it removes the node and link the previous node to the next node. I wrote the pseudo code, but I am having trouble implementing. The function is called removedSelected();

var LinkedList = function(){
  var list = {};
  //this should always point to the first node in the list 
  list.head = null;
  list.tail = null;


  list.addToTail = function(value){
    var newNode = Node(value);

    if(!list.head){
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
  };

   list.removeSelected = function(target){
//loop through the linked list 
    //if head value is not equal to target
    var node = this.head;
    while(node.value !== target){

    }
    //keep going through the list
        //if this.head === target
          //point the previous next to the next node            
  };

  list.indexCount = function(){
    return this.indexCount;
  }

  list.removeHead = function(){
    var deleted = this.head.value;
    this.head = this.head.next;
    if(this.head === null){
      this.tail = null;
    }
    return deleted;
  };

  list.contains = function(target){
    var node = this.head;
    while(node !== null){
      if(node.value === target){
       return true;
      }
      node = node.next;
    }
    return false; 
  };
  return list;
};

var Node = function(value){
  var node = {};

  node.value = value;
  node.next = null;

  return node;
};

var a = new LinkedList();
a.addToTail(1);
a.addToTail(5);
a.addToTail(55);
a.removeSelected(5);

First of all, THANK YOU for posting a complete, usable example. I don't have much time tonight, but I'll see what I can do. — Jeremy J Starcher
– Jeremy J Starcher, Commented Jun 3, 2016 at 2:51
@JeremyJStarcher Thank you for posting a comment thanking a post posting a complete example ;) — Derek 朕會功夫
– Derek 朕會功夫, Commented Jun 3, 2016 at 3:09

traktor · Accepted Answer · 2016-06-03 03:59:46Z

A common technique is to create bidirectional links with pointers to previous and next objects in a list to facilitate list entry removal and patching of a previous object's next value.

However, given that this list is linked in one direction only, keeping track of the previous node in the list relative to the node being examined while traversing the list should allow a node with matching value to be removed in a single pass.

This example shows how it might be done. (The testing is all yours :-).

list.removeSelected = function( target) {
    for( var previous = null, node = this.head;
            node;
                previous = node, node = next)
    {   var next = node.next;
        if( node.value == target)
        {   if( previous)
            {   previous.next = next;
            }
            else
            {   this.head = next;
            }
            if( !next)
                this.tail = previous;
            node.next = null;
            break;
        }
    }
    return node;  // the node removed or null if not found.
};

Jeyashri Natarajan · Accepted Answer · 2017-03-14 21:10:58Z

0

var removeSelected = function(head, val) {
                    var previous = null;
                    var current = head;
              while(current !== null){
                        if(current.val === val){
                            if(previous === null){
                                head = current.next;
                            }else{
                                previous.next = current.next;
                            }
                        }else{
                            previous = current;
                        }
                        current = current.next;  
                    }
                    return head;
                };

Explanation:

Declare a variable 'previous' to keep track of the value of the last node visited and a variable 'current' to store the value of the current node visited.
Check if the first node has a value equal to that of the value being searched. If the values are equal then the first node is skipped and the next node becomes the first node
While traversing through the linked list if we find any node containing the searched value ,we link the previous node's next to the current node's next element, thereby skipping the current node.

edited Mar 14, 2017 at 21:10

answered Mar 14, 2017 at 20:21

Jeyashri Natarajan

11 bronze badge

1 Comment

Nathan Tuggy Over a year ago

Could you please edit in an explanation of why this code answers the question? Code-only answers are discouraged, because they don't teach the solution.

Collectives™ on Stack Overflow

Javascript linked list

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related