JavaScript implements single chain and double chain table structure in Node.js environment

  • 2021-06-28 10:09:11
  • OfStack

javascript implementation of single-chain 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 list and is implemented by the insert method. Note the boundary condition treatment for 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 double-linked list (DoubleLinkedList)
npmjs Related Library:
complex-list, smart-list
Programming ideas:

The double-chain list has one more pointer to the future, so the auxiliary function findPre in the single-chain list is not needed. A reverse output method has been added. Note the handling 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;
})();


Related articles: