quark-dsa v1.14.0

quark-dsa

The Quark-dsa is a JavaScript utility library for data structures and operations on it. It is built using TypeScript and includes data structures Stack, Queue, Tree, Graph and many more.

All documentation for this library can be found here.

Install

npm install quark-dsa

Usage

There are several utility functions in quark-dsa, those you can use for performing data structures and operations.

• String: Check if string is palindrome and reverse the string are supported.

  Reverse the string

  import { reverseString } from "quark-dsa";
  
  let str = "quark";
  reverseString(str); // returns 'krauq'

  Check a string is palindrome

  import { isStringPalindrome } from "quark-dsa";
  
  let str = "racecar";
  isStringPalindrome(str); // returns true;

• Number: Check if number is palindrome, reverse the number and check if number is prime is supported.

  Reverse the number

  import { reverseNumber } from "quark-dsa";
  
  let num = 5698;
  reverseNumber(num); // returns 8965

  Check a number is prime number

  import { isPrime } from "quark-dsa";
  
  let num = 37019;
  isPrime(num); // returns true;

  Check a number is palindrome

  import { isNumberPalindrome } from "quark-dsa";
  
  let num = 1562651;
  isNumberPalindrome(num); // returns true;

• Array: Remove duplicates from an array and calculation of mean, median and mode are supported.

  Mean (Average Calculation) You can calculate the mean of a list. Supported mean types are arithmetic, geometric, harmonic and rms (root mean square). By default arithmetic is selected.

  import { mean } from "quark-dsa";
  
  let list = [2, 6, 4, 5, 8];
  mean(list); // returns 5
  mean(list, "geometric"); // returns 4.54
  mean(list, "harmonic"); // returns 4.03
  mean(list, "rms"); // returns 5.39

  Median You can calculate middle value of the list, which is median. If list has even number of items, it will return average of middle two values, otherwise it will return middle value. List will get sorted in ascending order before median calculation.

  import { median } from "quark-dsa";
  
  let list = [4, 12, 14, 17, 22, 23, 23, 24, 25, 29, 40, 67, 77, 82, 92];
  median(list); // returns 24
  let list2 = [142, 140, 130, 150, 160, 135, 158, 132];
  median(list2); // returns 141

  Mode You can also get the element having highest frequency in the list, which is mode. If the list has only one mode, then it will return as a number. If the list has more than one modes, then it will return all mode values in an array.

  import { mode } from "quark-dsa";
  
  let list = [3, 3, 6, 9, 16, 16, 16, 27, 27, 37, 48];
  mode(list); // returns 16
  let list2 = [3, 3, 3, 9, 16, 16, 16, 27, 37, 48];
  mode(list2); // returns [3, 16]

  Remove duplicates You can remove duplicates from a list and returns the same list. Here, in place operation is performed on the list. Only numbers and strings are supported in the list.

  import { removeDuplicates } from "quark-dsa";
  
  let list = [1, 2, 3, 3, 2, 1, 4, 5, 1, 5, 8, 3];
  removeDuplicates(list); // returns [1, 2, 3, 4, 5, 8];
  let list2 = [
    "John",
    "George",
    "Paul",
    "Ringo",
    "George",
    "Bob",
    "Elvis",
    "Freddie",
    "Paul",
  ];
  removeDuplicates(list2); // returns ["John", "George", "Paul", "Ringo", "Bob","Elvis", "Freddie"]

  Greatest Common Divisor (GCD) and Least Common Multiples (LCM) of an array You can calculate GCD and LCM of an array.

  import { gcd, lcm } from "quark-dsa";
  
  let list = [8, 12, 16];
  gcd(list); // returns 4
  let list2 = [12, 18, 24];
  lcm(list2); // returns 72

  Matrix Operations You can also perform matrix operations like addition, subtraction and multiplication on the n*n arrays.

  import {
    matrixAddition,
    matrixSubtraction,
    matrixMultiplication,
    matrixDeterminant,
  } from "quark-dsa";
  
  let list = [
    [2, 4, 3],
    [5, 7, 8],
    [9, 6, 7],
  ];
  let list2 = [
    [3, 5, 7],
    [8, 3, 4],
    [5, 7, 8],
  ];
  matrixAddition(list, list2); // returns [[5, 9, 10], [13, 10, 12], [14, 13, 15]]
  matrixSubtraction(list, list2); // returns [[-1, -1, -4], [-3, 4, 4], [4, -1, -1]]
  matrixMultiplication(list, list2); // returns [[53, 43, 54], [111, 102, 127], [110, 112, 143]]
  matrixDeterminant(list); // returns 51

Highlights

quark-dsa provides following data startuctures and common operations (more work is going on...):

• Stack: Basic push, pop, peek, length and serach operations are supported.
• Queue: Basic enqueue, dequeue, length and search operations are supported.
• Linked List: Construct, add node, update node, delete node, reverse, concat, get middle node, rotate operations are supported.
• Binary Tree: Construct, insert/update/delete node of the tree. Traversal paths of the tree (preorder, inorder, postorder, level order traversal), inverting the tree.

quark-dsa also provides commonly used algorithms as utility functions.

• Searching: Linear and Binary search algorithms are added to give position of key in the list.

quark-dsa provides sorting algorithms as utility functions.

• Sorting: Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort, Radix Sort.

Stack

Initialize the stack

You can create a stack with the given size. Size is optional argument with the default value 65535.

import { Stack } from "quark-dsa";

const stack = new Stack(200); // Creates stack with size 200.

Supported methods

Usage

import { Stack } from "quark-dsa";

const stack = new Stack(); // new stack is created.
stack.push(23); // pushes 23 to the top of the stack.
stack.push(36); // pushes 36 to the top of the stack.
stack.length(); // returns 2;
stack.search(36); // returns 1;
stack.search(98); // returns -1;
stack.pop(); // removes top element from the stack and returns it.
stack.peek(); // returns the top element of the stack, 23.
stack.length(); // returns 1;
stack.pop(); // removes top element from the stack and returns it.
stack.isEmpty(); // returns true as stack is empty now.

Queue

Initialize the queue

You can create a queue with the given size. Size is optional argument with the default value 65535.

import { Queue } from "quark-dsa";

const queue = new Queue(200); // Creates queue with size 200.

Supported methods

Usage

import { Queue } from "quark-dsa";

const queue = new Queue(); // new queue is created.
queue.enqueue(3); // inserts 3 to the rear of the queue.
queue.enqueue(8); // inserts 8 to the rear of the queue.
queue.length(); // returns 2;
queue.search(8); // returns 1;
queue.search(98); // returns -1;
queue.dequeue(); // removes the front item of the queue and then returns it.
queue.getFront(); // returns the front item of the queue, 8.
queue.enqueue(10); // inserts 10 to the rear of the queue.
queue.getRear(); // returns the rear item of the queue, 10.
queue.dequeue(); // removes the front item of the queue and then returns it.
queue.dequeue(); // removes the front item of the queue and then returns it.
queue.length(); // returns 0;
queue.isEmpty(); // returns true as queue is empty now.

Linked List

Initialize the linked list

You can create an empty linked list or you can pass an array which will convert an array to an linked list.

import { LinkedList } from "quark-dsa";

const list = new LinkedList(); // returns an empty linked list.

or;

const list = new LinkedList([17, 2, 96, 55, 40]); // returns a linked list with array elements inserted sequentially.

Supported methods

Usage

import { LinkedList } from "quark-dsa";

const list = new LinkedList([17, 2, 96, 55, 40]); // returns a linked list with array elements inserted sequentially.
list.print(); // returns the value in the console log "17 -> 2 -> 96 -> 55 -> 40".
list.add(3); // inserts 3 at last of the linked list.
list.update(45, 3); // updates node of index 3 with value 45.
list.remove(5); // removes node at index 5;
list.reverse(); // reverse the list.
list.getMiddleValue(); // returns the middle value of the list, 96.
list.rotateRight(4); // rotates the list to 4 positions towards right.
list.rotateLeft(5); // rotates the list to 5 positions towards left.

const list2 = new LinkedList([89, 21, 63, 45]); // returns a linked list with array elements inserted sequentially.
list.concat(list2); // returns list with concatenated values of list2.

Binary Tree

Initialize the binary tree

You can create a tree with the root value. If the root value is not given, an empty node is created and set as a root of the tree.

import { BinaryTree } from "quark-dsa";

const tree = new BinaryTree(5); // The binary tree with root value as 5 is created.
const tree2 = new BinaryTree(); // The binary tree is created with root value set as null.

For performing operations on a node in the tree, we need to provide the path of the node. Path of the node should be in the format of L and R. For example, path LRRL means node of having path Left -> Right -> Right -> Left from the root node. Any characters other than L and R with throw an error.

Supported methods

Usage

import { BinaryTree } from "quark-dsa";

const tree = new BinaryTree(5); // Constructs a tree with 5 as a root node value.
tree.insertNode(3, "L"); // Inserts a node with value 3 on left of root.
tree.insertNode(9, "R"); // Inserts a node with value 9 on right of root.
tree.insertNode(5, "LR"); // Inserts a node with value 5 on right of 3.
tree.insertNode(7, "RL"); // Inserts a node with value 7 on left of 9.
tree.insertNode(6, "RLL"); // Inserts a node with value 6 on left on 7.
tree.insertNode(8, "RLR"); // Inserts a node with value 8 on right on 7.
tree.insertNode(12, "RR"); // Inserts a node with value 12 on right on 9.
tree.insertNode(20, "RRR"); // Inserts a node with value 20 on right on 12.
tree.inorder(); // Should return [3, 5, 5, 6, 7, 8, 9, 12, 20].
tree.preorder(); // Should return [5, 3, 5, 9, 7, 6, 8, 12, 20].
tree.postorder(); // Should return [5, 3, 6, 8, 7, 20, 12, 9, 5].
tree.levelOrder(); // Should return [5, 3, 9, 5, 7, 12, 6, 8, 20].
tree.height(); // Should return 4.
tree.updateNode(13, ""); // Should update root node with value 13.
tree.preorder(); // Should return [13, 3, 5, 9, 7, 6, 8, 12, 20].
tree.updateNode(31, "RLR"); // Updates the node with value 8 with 31.
tree.preorder(); // Should return [13, 3, 5, 9, 7, 6, 31, 12, 20].
tree.deleteNode("RR"); // Should delete the node 12.
tree.inorder(); // Should return [3, 5, 13, 6, 7, 31, 9].
tree.deleteNode("RLL"); // Should delete the node 6.
tree.inorder(); // Should return [3, 5, 13, 7, 31, 9].
tree.invert(); // Construct the invert (mirror) of the tree.
tree.inorder(); // Shoud return [9, 31, 7, 13, 5, 3].

Search

Quark-dsa supports Linear Search and Binary Search operations. You can pass the list and search key, it will return the position of the search key in the list.

Linear Search

Linear Search iterates over the list and returns the position of the search key in the list. If the search key is not present in the list, it will return -1.

import { LinearSearch } from "quark-dsa";

const list = [20, 12, 10, 15, 2];
LinearSearch(list, 15); // returns 3;
LinearSearch(list, 58); // returns -1;

Binary Search

Binary Search compares the search key with the middle value of the list and then partitions the list depending on the search key will be in the left or right partition. The important pre-requisite for the Binary Search is that the list should be in ascending order, otherwise it will throw an error. If the search key is not present in the list, it will return -1.

import { BinarySearch } from "quark-dsa";

const list = [2, 10, 12, 15, 20];
BinarySearch(list, 15); // returns 3;
BinarySearch(list, 58); // returns -1;