Javascript verknüpfte Liste

Question

Ich versuche, eine verknüpfte Listenfunktion zu schreiben, die den Knoten nach Suchwert entfernen kann. Wenn der Wert übereinstimmt, entfernt er den Knoten und verknüpft den vorherigen Knoten mit dem nächsten Knoten. Ich habe den Pseudocode geschrieben, aber ich habe Probleme bei der Implementierung. Die Funktion heißt 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

Eine übliche Technik ist bidirektionale Verbindungen mit Zeigern zur vorherigen und nächsten Objekte in einer Liste erstellen Listeneintrag Entfernung und Patchen eines vorherigen Objekts nächsten Wert zu erleichtern.

Da diese Liste jedoch nur in eine Richtung verknüpft ist, sollte das Verfolgen des vorherigen Knotens in der Liste relativ zum Knoten beim Durchsuchen der Liste ermöglichen, dass ein Knoten mit übereinstimmendem Wert in einem einzigen Durchgang entfernt wird .

Dieses Beispiel zeigt, wie es gemacht werden könnte. (Das Testen gehört ganz Ihnen :-).

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

Answer 2

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

Erläuterung:

1. eine Variable deklarieren ‚zurück‘ besuchten Spur des Wertes der letzten Knotens zu halten, und eine Variable ‚aktuelle‘ den Wert des Stromes zu speichern, Knoten besucht.
2. Überprüfen Sie, ob der erste Knoten einen Wert hat, der dem Wert entspricht. Wenn die Werte gleich sind, dann ist der erste Knoten übersprungen und der nächste Knoten wird der erste Knoten
3. Während durch die verknüpfte Liste durchlaufen, wenn wir irgendein Knoten mit dem gesuchten Wert zu finden, verknüpfen wir die vorherigen Knotens neben die aktuelle Knoten des nächsten Elements, wodurch der aktuelle Knoten übersprungen wird.