Node.js环境下JavaScript实现单链表与双链表结构

单链表（LinkedList）的javascript实现

npmjs相关库：

complex-list、smart-list、singly-linked-list

编程思路：

• add方法用于将元素追加到链表尾部，借由insert方法来实现；
• 注意各个函数的边界条件处理。

自己的实现：

SingleNode.js

(function(){ "use strict"; function Node(element){  this.element = element;  this.next = null; } module.exports = Node;})();

LinkedList.js

(function(){ "use strict"; var Node = require("./lib/SingleNode"); function LinkedList(){  this._head = new Node("This is Head Node.");  this._size = 0; } LinkedList.prototype.isEmpty = function(){  return this._size === 0; }; LinkedList.prototype.size = function(){  return this._size; }; LinkedList.prototype.getHead = function(){  return this._head; }; LinkedList.prototype.display = function(){  var currNode = this.getHead().next;  while(currNode){   console.log(currNode.element);   currNode = currNode.next;  } }; LinkedList.prototype.remove = function(item){  if(item) {   var preNode = 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){  var newNode = new Node(newElement);  var finder = item ? this.find(item) : null;  if(!finder){   var last = this.findLast();   last.next = newNode;  }  else{   newNode.next = finder.next;   finder.next = newNode;  }  this._size++; }; /*********************** Utility Functions ********************************/ LinkedList.prototype.findLast = function(){  var currNode = this.getHead();  while(currNode.next){   currNode = currNode.next;  }  return currNode; }; LinkedList.prototype.findPre = function(item){  var currNode = this.getHead();  while(currNode.next !== null && currNode.next.element !== item){   currNode = currNode.next;  }  return currNode; }; LinkedList.prototype.find = function(item){  if(item == null)   return null;  var currNode = this.getHead();  while(currNode && currNode.element !== item){   currNode = currNode.next;  }  return currNode; }; module.exports = LinkedList;})();

双链表（DoubleLinkedList）的javascript实现

npmjs相关库：

complex-list、smart-list

编程思路：

• 双链表多了一个指向前趋的指针，故单链表中的辅助函数findPre就不需要了；
• 增加了反向输出方法；
• 注意边界条件的处理。

自己的实现

DoubleNode.js

(function(){ "use strict"; function Node(element){  this.element = element;  this.next = null;  this.previous = null; } module.exports = Node;})();

DoubleLinkedList.js

(function(){ "use strict"; var Node = require("./lib/DoubleNode"); function DoubleLinkedList(){  this._head = new Node("This is Head Node.");  this._size = 0; } DoubleLinkedList.prototype.getHead = function(){  return this._head; }; DoubleLinkedList.prototype.isEmpty = function(){  return this._size === 0; }; DoubleLinkedList.prototype.size = function(){  return this._size; }; DoubleLinkedList.prototype.findLast = function(){  var currNode = this.getHead();  while(currNode.next){   currNode = currNode.next;  }  return currNode; }; DoubleLinkedList.prototype.add = function(item){  if(item == null)   return null;  this.insert(item); }; DoubleLinkedList.prototype.remove = function(item){  if(item) {   var node = 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)   return null;  var currNode = this.getHead();  while(currNode && currNode.element !== item){   currNode = currNode.next;  }  return currNode; }; DoubleLinkedList.prototype.insert = function(newElement, item){  var newNode = new Node(newElement);  var finder = item ? this.find(item) : null;  if(!finder){   var last = 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(){  var currNode = this.findLast();  while(currNode != this.getHead()){   console.log(currNode.element);   currNode = currNode.previous;  } }; DoubleLinkedList.prototype.display = function(){  var currNode = this.getHead().next;  while(currNode){   console.log(currNode.element);   currNode = currNode.next;  } }; module.exports = DoubleLinkedList;})();