Javascript链表

Question

我正在尝试编写一个可以通过搜索值删除节点的链表函数。如果值匹配，它会删除该节点并将前一个节点链接到下一个节点。我写了伪代码，但我在执行时遇到了麻烦。该函数称为 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);

Answer 1

一种常见的技术是使用指向列表中上一个和下一个对象的指针创建双向链接，以便于删除列表条目和修补前一个对象的下一个值。

但是，鉴于此列表仅在一个方向上链接，在遍历列表时跟踪列表中相对于被检查节点的前一个节点应该允许在单次传递中删除具有匹配值的节点。

这个例子展示了它是如何完成的。 (测试都是你的:-)。

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.
};