JavaScript implements single-linked list and double-linked list structure under Node.js environment

JavaScript implementation of single linked list (LinkedList)

npmjs related libraries:

complex-list, smart-list, singly-linked-list

Programming ideas:

• The add method is used to append elements to the end of the linked list, and is implemented by the insert method;
• Pay attention to the boundary condition processing of each function.

Your own implementation:

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

JavaScript implementation of DoubleLinkedList

npmjs related libraries:

complex-list, smart-list

Programming ideas:

• The double-linked list has an additional pointer to the forward trend, so the auxiliary function findPre in the single-linked list is no longer needed;
• Added reverse output method;
• Pay attention to the processing of boundary conditions.

Your own implementation

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