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