Node.js环境下JavaScript实现单链表与双链表结构
单链表（LinkedList）的javascript实现
npmjs相关库：
complex-list、smart-list、singly-linked-list
编程思路：
- add方法用于将元素追加到链表尾部，借由insert方法来实现；
- 注意各个函数的边界条件处理。
自己的实现：
SingleNode.js
(function(){
"usestrict";
functionNode(element){
this.element=element;
this.next=null;
}
module.exports=Node;
})();
LinkedList.js
(function(){
"usestrict";
varNode=require("./lib/SingleNode");
functionLinkedList(){
this._head=newNode("ThisisHeadNode.");
this._size=0;
}
LinkedList.prototype.isEmpty=function(){
returnthis._size===0;
};
LinkedList.prototype.size=function(){
returnthis._size;
};
LinkedList.prototype.getHead=function(){
returnthis._head;
};
LinkedList.prototype.display=function(){
varcurrNode=this.getHead().next;
while(currNode){
console.log(currNode.element);
currNode=currNode.next;
}
};
LinkedList.prototype.remove=function(item){
if(item){
varpreNode=this.findPre(item);
if(preNode==null)
return;
if(preNode.next!==null){
preNode.next=preNode.next.next;
this._size--;
}
}
};
LinkedList.prototype.add=function(item){
this.insert(item);
};
LinkedList.prototype.insert=function(newElement,item){
varnewNode=newNode(newElement);
varfinder=item?this.find(item):null;
if(!finder){
varlast=this.findLast();
last.next=newNode;
}
else{
newNode.next=finder.next;
finder.next=newNode;
}
this._size++;
};
/***********************UtilityFunctions********************************/
LinkedList.prototype.findLast=function(){
varcurrNode=this.getHead();
while(currNode.next){
currNode=currNode.next;
}
returncurrNode;
};
LinkedList.prototype.findPre=function(item){
varcurrNode=this.getHead();
while(currNode.next!==null&&currNode.next.element!==item){
currNode=currNode.next;
}
returncurrNode;
};
LinkedList.prototype.find=function(item){
if(item==null)
returnnull;
varcurrNode=this.getHead();
while(currNode&&currNode.element!==item){
currNode=currNode.next;
}
returncurrNode;
};
module.exports=LinkedList;
})();
双链表（DoubleLinkedList）的javascript实现
npmjs相关库：
complex-list、smart-list
编程思路：
- 双链表多了一个指向前趋的指针，故单链表中的辅助函数findPre就不需要了；
- 增加了反向输出方法；
- 注意边界条件的处理。
自己的实现
DoubleNode.js
(function(){
"usestrict";
functionNode(element){
this.element=element;
this.next=null;
this.previous=null;
}
module.exports=Node;
})();
DoubleLinkedList.js
(function(){
"usestrict";
varNode=require("./lib/DoubleNode");
functionDoubleLinkedList(){
this._head=newNode("ThisisHeadNode.");
this._size=0;
}
DoubleLinkedList.prototype.getHead=function(){
returnthis._head;
};
DoubleLinkedList.prototype.isEmpty=function(){
returnthis._size===0;
};
DoubleLinkedList.prototype.size=function(){
returnthis._size;
};
DoubleLinkedList.prototype.findLast=function(){
varcurrNode=this.getHead();
while(currNode.next){
currNode=currNode.next;
}
returncurrNode;
};
DoubleLinkedList.prototype.add=function(item){
if(item==null)
returnnull;
this.insert(item);
};
DoubleLinkedList.prototype.remove=function(item){
if(item){
varnode=this.find(item);
if(node==null)
return;
if(node.next===null){
node.previous.next=null;
node.previous=null;
}else{
node.previous.next=node.next;
node.next.previous=node.previous;
node.next=null;
node.previous=null;
}
this._size--;
}
};
DoubleLinkedList.prototype.find=function(item){
if(item==null)
returnnull;
varcurrNode=this.getHead();
while(currNode&&currNode.element!==item){
currNode=currNode.next;
}
returncurrNode;
};
DoubleLinkedList.prototype.insert=function(newElement,item){
varnewNode=newNode(newElement);
varfinder=item?this.find(item):null;
if(!finder){
varlast=this.findLast();
newNode.previous=last;
last.next=newNode;
}
else{
newNode.next=finder.next;
newNode.previous=finder;
finder.next.previous=newNode;
finder.next=newNode;
}
this._size++;
};
DoubleLinkedList.prototype.dispReverse=function(){
varcurrNode=this.findLast();
while(currNode!=this.getHead()){
console.log(currNode.element);
currNode=currNode.previous;
}
};
DoubleLinkedList.prototype.display=function(){
varcurrNode=this.getHead().next;
while(currNode){
console.log(currNode.element);
currNode=currNode.next;
}
};
module.exports=DoubleLinkedList;
})();