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