寻求链表节点删除的秘密 !!!
需求: 创建双向链表, 把双向链表清空
思路: 利用链表节点前后相继的特性, 逐个解除节点之间的关系, 释放节点.
问题: 如果只是利用前后指针改变彼此关系, 释放某个节点. 没有问题.
逐个改变关系, 做链表清空操作, 失败. 从log来看, 头节点访问到了, 并且也执行了释放的操作. 但是结果显示没有释放. 这个问题和在进行二叉树节点删除的情况相似, 不知道为啥. 郁闷就两个字.
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)
{
while (curNode != null)
{
document.write(curNode.data + "--->");
if (direction == "head")
curNode = curNode.next;
else if (direction == "last")
curNode = curNode.prior;
}
}
/*
* @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;
this.lastNode = 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 ++;
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;
}
}
/*
* @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;
return(tmp);
}
else
return false;
}
}
测试代码:
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>");
alert(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>");
t.outputTwoLink(t.head,"head");
执行结果:
create the list with 6 random number
9--->75--->98--->77--->50--->45--->
remove the data in # 3
9--->75--->98--->50--->45--->
insert 5 into the list
9--->75--->98--->50--->45--->5--->
execute clear
9--->75--->98--->50--->45--->5---> // wrong result
Log:
[1] count 1 last node data 5
[2] count 1 last node data 45
[1] count 2 last node data 45
[2] count 2 last node data 50
[1] count 3 last node data 50
[2] count 3 last node data 98
[1] count 4 last node data 98
[2] count 4 last node data 75
[1] count 5 last node data 75
[2] count 5 last node data 9
[1] count 6 last node data 9
[解决办法]
<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=nullreturn 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>