寻求链表节点删除的秘密 !!!

Question

你的clear并没有执行过任何清除remove的操作，仅仅是把数据展示了一边而已.
另外你的remove定义的参数的处理是否有待商榷，传入删除第3个,实际上看起来是删除第4个了。
/* 
 * @brief: remove all of the elements in the list 
 *  
 */ 
Twolink.prototype.clear = function()  // problem  
{ 
var tmp; 
var count = 0; 
//call remove function
while(this.lastNode!= null) 
{ 
//or call remove function
count ++; tmp = this.lastNode; console.log(" [1] count %d last node data %d ",count, this.lastNode.data); 
this.lastNode = tmp.prior; 
if( this.lastNode != null ) 
console.log(" [2] count %d  last node data %d ", count, this.lastNode.data); 
tmp = null; 
} 
} 

Answer 1

另外请在你的remove里将被移除的元素设置为null以真正的清除该元素,因为你此处的元素是一个对象,不能简单的把连接去掉就算完事.
/* 
 * remove the element 
 */ 
if( n == pos ) 
{ 
tmp.prior.next = tmp.next; 
tmp.next.prior = tmp.prior; 
tmp = null;
return true; 
} 
else 
return false; 
} 刚刚有看了一下代码,你的clear不是没有执行清除操作,而是你在log之后才做了清除,所以你的log记录有数据，但最终被清除的操作因为在log之后，所以没有被记录.

Answer 2

非常感谢 myvicy go through my code. Thanks very much.希望我正确的理解了您的建议. 呵呵 1. 同意您关于remove函数里的建议. 非常感谢.
  进行完remove 操作后, 遍历链表, 删除的节点已经消失, 正如测试函数的结果. 2. 进一步解释一下关于clear 函数 2.1 count变量只是为了log, 验证程序是否访问了链表中的每个节点, 包括头节点, 不是用来指示节点所在的位置.
 例如: [1] count 6 last node data 9  , 9其实就是头节点, 但是它的prior是空节点, 故只打印一次. 这个证明程序访问到了头节点.
 2.2 我的本意不是依赖remove来做链表清楚, 不过两个函数释放节点的方式是一样的: 在改变相继关系的同时, 逐个释放节点, 如code: 
while( this.lastNode != null)
{
//count ++;

  tmp = this.lastNode;

//console.log(" [1] count %d last node data %d ",count, this.lastNode.data);
  this.lastNode = tmp.prior;  //改变关系
if( this.lastNode != null )
console.log(" [2] count %d  last node data %d ", count, this.lastNode.data);
  tmp = null; // 释放节点
}  2.3 发现clear 不work 是通过测试程序的log, 如:9---> 75---> 98---> 50---> 45---> 5---> // 这是链表
execute clear //这里执行了clear 操作
9---> 75---> 98---> 50---> 45---> 5--->   // wrong result, 遍历链表, 每个节点依然存在  

Answer 3

<script>
function twolinkNode(data) 
{ 
this.data = data; 
this.next = this.prior = null; 
} /* 
 * @breif: doubly linked list 
 * @ 
 */ 
function Twolink() 
{ 
/* 
 * @breif: create one doubly linked list based on random number 
 */ 
Twolink.prototype.createTwolink = function(n) 
{ 
var rear; 
var q; if (n == 0)  
this.head = null; 
else if (n >  0)  
{ 
var k = parseInt(Math.random() * 100); 
this.head = new twolinkNode(k); 
rear = this.head; 
this.lastNode = this.head; for (var i = 1; i  < n; i++)  
{ 
k = parseInt(Math.random() * 100); 
q = new twolinkNode(k); 
rear.next = q; 
q.prior = rear; 
rear = q; } this.lastNode = rear; 
} 
} /* 
 * @brief: output the link 
 */ 
Twolink.prototype.outputTwoLink = function(curNode, direction) 
{ 
do
{ 
document.write(curNode.data + "---> "); 
if (direction == "head")  
curNode = curNode.next; 
else if (direction == "last")  
curNode = curNode.prior; 
}  while (curNode != null&&curNode!= this.head)
document.write("<br>")
} /* 
 * @brief: appends the specified element to the end of the list 
 * @return: true if successful, fals if failed 
 */ 
Twolink.prototype.add = function(dElement) 
{ 
var q = new twolinkNode(dElement); 
this.lastNode.next = q; 
q.prior = this.lastNode; 
//q.next = this.head;this.lastNode = q; 
return q;
} /* 
 * @brief: remove all of the elements in the list 
 *  
 */ 
Twolink.prototype.clear = function()  // problem  
{ 
var tmp; 
var count = 0; while( this.lastNode != null) 
{ 
count ++; 
if(this.lastNode.prior)
tmp = this.lastNode.prior; 
else
tmp = this.lastNode;
//console.log(" [1] count %d last node data %d ",count, this.lastNode.data); //if( this.lastNode != null ) 
//console.log(" [2] count %d  last node data %d ", count, this.lastNode.data); 
//document.write(count+":"+tmp.data+":"+tmp.next+":")
if(tmp.next){
tmp.next = null
this.lastNode = tmp; 
}else{
this.lastNode = null; 
this.head = null;
}
//this.outputTwoLink(t.head,"head"); 
} 
} /* 
 * @brief: removes the element in the specified position 
 * @para: position 
 * @return: the node in the specified position 
 */ 
Twolink.prototype.remove = function(pos) 
{ 
var tmp; 
var n; 
var q; tmp = this.head; 
q = tmp; 
n=0; while( n != pos ) 
{ 
q = tmp.next; 
tmp = q; 
n++; 
} /* 
 * remove the element 
 */ 
if( n == pos ) 
{ 
tmp.prior.next = tmp.next; 
tmp.next.prior = tmp.prior; 
tmp=null
return true; 
} 
else 
return false; 
} } 
//测试代码:  
t = new Twolink()
document.write("create the list with 6 random number  <br> "); 
t.createTwolink(6); 
t.outputTwoLink(t.head, "head"); 
document.write(" <br> remove the data in # 3  <br> "); 
t.remove(3); 
t.outputTwoLink(t.head, "head"); 
document.write("  <br>  insert 5 into the list"); 
document.write(" <br> "); 
t.add(5); 
t.outputTwoLink(t.head,"head"); document.write(" <br> "); 
document.write("execute clear"); 
t.clear(); 
document.write(" <br> "); 
document.write(" <br> "); 
</script>做了修改的代码，仍旧可能存在的问题就是在很多地方可能要对头尾进行判断处理，而你之前的代码并没有，我仅仅加了一些地方的判断，其他地方你自己看看那里还需要加入判断。

Answer 4

dear myvicy, your code does work ! Thanks.However, I want to figure out the root course since I encountered the same problem when implementing the ordered binary tree. 我把自己的代码重新走读了一遍
Twolink.prototype.clear = function()
{
var tmp;
var count = 0;
        
                while( this.lastNode != null)
{
count ++;
tmp = this.lastNode;

console.log(" [1] count %d last node data %d ",count, this.lastNode.data); this.lastNode = tmp.prior; if( this.lastNode != null )
console.log(" [2] count %d  last node data %d ", count, this.lastNode.data);
alert( "#" + count + (tmp==this.head) ); tmp = null;
}
在这个logic里, this.head并不是落网之鱼.
我用tmp==this.head去追踪对this.head的处理. 当count显示6, 显示结果为true, 并且执行了tmp=null的操作.
我就是不甘心对this.head来做一个特殊的操作. 
是不是有深层次的原因在里边呢? 郁闷的紧. 

Answer 5

this.lastnode最后指向的是tmp.prior 也就是this.head.prior, 那是一个null. 
很有可能, 造成了一个从this.lastNode 到this.head的引用. 不知道别的软件或者firebug里是否有查看某个对象的引用的功能?Thank you, myvicy.