@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(n
log(n)) worst, O(nlog(n)) avg, O(n*log(n)) best. Memory: O(n) worst.
quick-sort [ tests ] — Time: O(n^2) worst, O(n
log(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.