@raikuxq/alg-ds

Common algorithms and data structures.

Written in TypeScript, tested with Jest.

Documentation

Documentation app: raikuxq-algorithms.netlify.app/guide

Usage as package

Install by using any of these commands:

• yarn add @raikuxq/alg-ds
• npm install @raikuxq/alg-ds --save

Usage as repository

Clone this repository and install dependencies by using yarn command.

• yarn test - run all tests via jest
• yarn dev - run in dev mode via nodemon (src/index.ts is an entrypoint)
• yarn build - compile ts sources into js files
• yarn start - build and run in production mode
• yarn lint - lint check via eslint
• yarn lint:fix - fix source files via eslint

Navigation

• Algorithms
  • Utils
  • Math
  • Sorting algorithms
• Linear data structures
  • Linked list
  • Looped array
  • Stack
  • Queue
• Non-linear data structures
  • HASH table
  • Graph
  • Binary tree

Algorithms

Utils

memoize — Memoization util function.

Searching

binary-search [ tests ] — Binary searching algorithm. Time: O(log(n)).

Math

factorial [ tests ] — Recursive O(n!) and memoized O(n) factorial implementation.

fibonacci [ tests ] — Recursive O(n!) and memoized O(n) factorial implementation.

transpose-matrix [ tests ] — Transpose N*N matrix util function.

Sorting algorithms

bubble-sort [ tests ] — Time: O(n^2) worst, O(n^2) avg, O(n) best. Memory: O(1) worst.

selection-sort [ tests ] — Time: O(n^2) worst, O(n^2) avg, O(n^2) best. Memory: O(1) worst.

insertion-sort [ tests ] — Time: O(n^2) worst, O(n^2) avg, O(n) best. Memory: O(1) worst.

merge-sort [ tests ] — Time: O(nlog(n)) worst, O(nlog(n)) avg, O(n*log(n)) best. Memory: O(n) worst.

quick-sort [ tests ] — Time: O(n^2) worst, O(nlog(n)) avg, O(nlog(n)) best. Memory: O(1) worst.

Linear data structures

Interfaces

ILinearStorage — Contains common methods of linear data structures.

ILinearStorageRA — Allows random access (from end, from start, by index). Extends ILinearStorage interface.

IConvertableToArray — Contain methods for converting from/into array.

Linked List

Interfaces

ILinkedList — Contains basic linked lists operations. Extends ILinearStorageRA and IConvertableToArray interface.

Implementation

AbstractLinkedList — Common logic for both single and double linked lists. Implements ILinearStorageRA interface.

SingleLinkedList [ tests ] — Extends abstract linked list with implementation of one-way linking.

DoubleLinkedList [ tests ] — Extends abstract linked list with implementation of two-way linking.

IterableSingleLinkedList [ tests ] — Extends single linked list with iterator implementation. Implements IIterable interface.

IterableDoubleLinkedList [ tests ] — Extends double linked list with implementation of two-way linking. Implements IBiDirectIterable interface.

Looped Array

Interfaces

IArrayFacade — Contains basic array operations. Extends ILinearStorageRA interface. Extends IConvertableToArray interface.

Implementation

LoopedArray [ tests ] — Overwrites data on capacity overflow.

Stack

Implementation

Stack [ tests ] — LIFO data structure. Implements ILinearStorage interface.

Queue

Implementation

Queue [ tests ] — FIFO data structure. Implements ILinearStorage interface.

Non linear data structures

HASH Table

Interfaces

IKeyValueStorage — Contains basic key-value storages operations.

Implementation

HashTableNode — Contains key, data and isDeleted properties.

HashTable [ tests ] — Implementation of open addressing hash table using quadratic probing

Graph

Interfaces

IGraph — Contains basic graph operations.

IGraphIterator — Extends default iterator with init and getPath methods.

IGraphIterationStrategy — Iteration strategies which are used in shortest-path, has-path.

Implementation

GraphEdge — Contains from/to links and edge weight.

AbstractGraph — Common logic for both directed and undirected graphs.

DirectedGraph [ tests ] — In case of directed graph A->B and B->A edges are not the same.

UndirectedGraph [ tests ] — In case of undirected graph A->B and B->A are equal.

Graph Iterators

BreadthFirstSearchIterator — Traversal method for unweighted graphs, built on queue.

DepthFirstSearchIterator — Traversal method for unweighted graphs, built on stack.

DijkstraMethodIterator — Traversal method for weighted graphs, built on finding the minimal cost.

Graph Presenter

presenter-adjacency-lists [ tests ] — Representation of graph as an adjacency list (using Map).

presenter-adjacency-matrix [ tests ] — Representation of graph as an adjacency matrix (using Array N*N).

Graph Searching

has-path (BFS/DFS) [ tests ] — Search for the existence of a path between two vertices.

shortest-path (BFS/Dijkstra) [ tests ] — Search for one of several shortest paths between two vertices.

Graph Creators

create-graph-from-matrix [ tests ] — Convert a matrix N*N into a graph instance.

Graph Transposing

transpose-directed-graph [ tests ] — Transpose a directed graph (undirected graphs are symmetrical already).

Binary trees

IBinaryTree — Contains basic binary tree operations.

Implementation

AbstractBinaryNode — Contains left/right/parent links and node data.

AbstractBinaryTree — Common logic for all types of binary trees.

BinarySearchNode — Same as abstract binary node.

BinarySearchTree — Implementation of unbalanced binary search tree. Each node in left subtree is smaller and each node in right subtree is larger than the node data. Extends AbstractSearchTree.

RandBinarySearchNode — Have a rank attribute. Extends BinarySearchNode.

RandBinarySearchTree — Implementation of randomized binary search tree, which gives expected log(N) height. INSERTION have a 1/N+1 probability of inserting into root. Extends BinarySearchTree.