Удалить узел из единственного связанного списка

Question

Я реализую функцию удаления для LL в Javascript.

Вот моя функция:

//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)));

Проблема: Если я имел 10 узлов в моем списке и назвал эту функцию, чтобы удалить 5-й узел, эта функция возвращает только четвёртый-10th узлы, где пятый удален. Тем не менее, я ожидаю, что он вернет 1-10, где 5-й будет удален. Что я делаю неправильно и как я могу получить список, в котором удаляется только 5-й узел?

Answer 1

Еще Вы сделали небольшую ошибку в коде

1) в то время как цикл должен работать до < индексов-1, как вы начинаете отсчет от 0

2) Вы не делаете this._length-- после удаления узла кроме первого

3) JSON.stringify начиная печать с головным элементом, при удалении узла вы возвращаете предыдущий узел, так что вы получаете список неправильного узла

Исправленный код здесь

//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));