@raikuxq/alg-ds

Common algorithms and data structures written in TypeScript, tested with Jest.

---

Documentation

Detailed documentation is available at:
raikuxq-algorithms.netlify.app/guide

---

Installing

Install by using any of these commands:
+ yarn add @raikuxq/alg-ds
+ npm install @raikuxq/alg-ds --save

Navigation

+ Algorithms
+ Utils
+ Math
+ Sorting algorithms
+ Linear data structures
+ Linked list
+ Stack
+ Queue
+ Non-linear data structures
+ 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

$3

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

$3

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

$3

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

SingleLinkedList
[ [ tests ] ](test/unit/data-structures/linked-list/linked-list.test.ts)
— Extends abstract linked list with implementation of one-way linking.

DoubleLinkedList
[ [ tests ] ](test/unit/data-structures/linked-list/linked-list.test.ts)
— Extends abstract linked list with implementation of two-way linking.

IterableSingleLinkedList
[ [ tests ] ](test/unit/data-structures/linked-list/linked-list-iterable.test.ts)
— Extends single linked list with iterator implementation.
Implements IIterable interface.

IterableDoubleLinkedList
[ [ tests ] ](test/unit/data-structures/linked-list/linked-list-iterable.test.ts)
— Extends double linked list with implementation of two-way linking.
Implements IBiDirectIterable interface.

Stack

$3

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

Queue

$3

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

Non linear data structures

Graph

$3

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.

$3

GraphEdge — Contains from/to links and edge weight.

AbstractGraph — Common logic for both directed and undirected graphs.


DirectedGraph [ [ tests ] ](test/unit/data-structures/graph/graph.test.ts)
— In case of directed graph A->B and B->A edges are not the same.

UndirectedGraph [ [ tests ] ](test/unit/data-structures/graph/graph.test.ts)
— In case of undirected graph A->B and B->A are equal.

$3

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.

$3

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).

$3

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.

$3

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

$3

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

Binary trees

IBinaryTree — Contains basic binary tree operations.

$3

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.