Product
Introducing License Enforcement in Socket
Ensure open-source compliance with Socket’s License Enforcement Beta. Set up your License Policy and secure your software!
data-structure-typed
Advanced tools
Data Structures of Javascript & TypeScript. Binary Tree, BST, Graph, Heap, Priority Queue, Linked List, Queue, Deque, Stack, AVL Tree, Tree Multiset, Trie, Directed Graph, Undirected Graph, Singly Linked List, Doubly Linked List, Max Heap, Max Priority Qu
Data Structures of Javascript & TypeScript.
DFS(Depth-First Search), DFSIterative, BFS(Breadth-First Search), morris, Bellman-Ford Algorithm, Dijkstra's Algorithm, Floyd-Warshall Algorithm, Tarjan's Algorithm.
npm install data-structure-typed --save
yarn add data-structure-typed
<script src="https://cdn.jsdelivr.net/npm/data-structure-typed/umd/bundle.min.js"></script>
const {AVLTree} = dataStructureTyped;
const {
Heap,
MinHeap,
SinglyLinkedList,
Stack,
AVLTreeNode,
BST,
Trie,
DirectedGraph,
DirectedVertex,
TreeMultiset
} = dataStructureTyped;
import {BST, BSTNode} from 'data-structure-typed';
const bst = new BST();
bst.add(11);
bst.add(3);
bst.addMany([15, 1, 8, 13, 16, 2, 6, 9, 12, 14, 4, 7, 10, 5]);
bst.size === 16; // true
bst.has(6); // true
const node6 = bst.get(6); // BSTNode
bst.getHeight(6) === 2; // true
bst.getHeight() === 5; // true
bst.getDepth(6) === 3; // true
bst.getLeftMost()?.id === 1; // true
bst.remove(6);
bst.get(6); // null
bst.isAVLBalanced(); // true
bst.BFS()[0] === 11; // true
const objBST = new BST<BSTNode<{ id: number, keyA: number }>>();
objBST.add(11, {id: 11, keyA: 11});
objBST.add(3, {id: 3, keyA: 3});
objBST.addMany([{id: 15, keyA: 15}, {id: 1, keyA: 1}, {id: 8, keyA: 8},
{id: 13, keyA: 13}, {id: 16, keyA: 16}, {id: 2, keyA: 2},
{id: 6, keyA: 6}, {id: 9, keyA: 9}, {id: 12, keyA: 12},
{id: 14, keyA: 14}, {id: 4, keyA: 4}, {id: 7, keyA: 7},
{id: 10, keyA: 10}, {id: 5, keyA: 5}]);
objBST.remove(11);
const {BST, BSTNode} = require('data-structure-typed');
const bst = new BST();
bst.add(11);
bst.add(3);
bst.addMany([15, 1, 8, 13, 16, 2, 6, 9, 12, 14, 4, 7, 10, 5]);
bst.size === 16; // true
bst.has(6); // true
const node6 = bst.get(6);
bst.getHeight(6) === 2; // true
bst.getHeight() === 5; // true
bst.getDepth(6) === 3; // true
const leftMost = bst.getLeftMost();
leftMost?.id === 1; // true
expect(leftMost?.id).toBe(1);
bst.remove(6);
bst.get(6); // null
bst.isAVLBalanced(); // true or false
const bfsIDs = bst.BFS();
bfsIDs[0] === 11; // true
expect(bfsIDs[0]).toBe(11);
const objBST = new BST();
objBST.add(11, {id: 11, keyA: 11});
objBST.add(3, {id: 3, keyA: 3});
objBST.addMany([{id: 15, keyA: 15}, {id: 1, keyA: 1}, {id: 8, keyA: 8},
{id: 13, keyA: 13}, {id: 16, keyA: 16}, {id: 2, keyA: 2},
{id: 6, keyA: 6}, {id: 9, keyA: 9}, {id: 12, keyA: 12},
{id: 14, keyA: 14}, {id: 4, keyA: 4}, {id: 7, keyA: 7},
{id: 10, keyA: 10}, {id: 5, keyA: 5}]);
objBST.remove(11);
const avlTree = new AVLTree();
avlTree.addMany([11, 3, 15, 1, 8, 13, 16, 2, 6, 9, 12, 14, 4, 7, 10, 5])
avlTree.isAVLBalanced(); // true
avlTree.remove(10);
avlTree.isAVLBalanced(); // true
import {AVLTree} from 'data-structure-typed';
const avlTree = new AVLTree();
avlTree.addMany([11, 3, 15, 1, 8, 13, 16, 2, 6, 9, 12, 14, 4, 7, 10, 5])
avlTree.isAVLBalanced(); // true
avlTree.remove(10);
avlTree.isAVLBalanced(); // true
const {AVLTree} = require('data-structure-typed');
const avlTree = new AVLTree();
avlTree.addMany([11, 3, 15, 1, 8, 13, 16, 2, 6, 9, 12, 14, 4, 7, 10, 5])
avlTree.isAVLBalanced(); // true
avlTree.remove(10);
avlTree.isAVLBalanced(); // true
import {DirectedGraph} from 'data-structure-typed';
const graph = new DirectedGraph();
graph.addVertex('A');
graph.addVertex('B');
graph.hasVertex('A'); // true
graph.hasVertex('B'); // true
graph.hasVertex('C'); // false
graph.addEdge('A', 'B');
graph.hasEdge('A', 'B'); // true
graph.hasEdge('B', 'A'); // false
graph.removeEdgeSrcToDest('A', 'B');
graph.hasEdge('A', 'B'); // false
graph.addVertex('C');
graph.addEdge('A', 'B');
graph.addEdge('B', 'C');
const topologicalOrderIds = graph.topologicalSort(); // ['A', 'B', 'C']
import {UndirectedGraph} from 'data-structure-typed';
const graph = new UndirectedGraph();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.removeVertex('C');
graph.addEdge('A', 'B');
graph.addEdge('B', 'D');
const dijkstraResult = graph.dijkstra('A');
Array.from(dijkstraResult?.seen ?? []).map(vertex => vertex.id) // ['A', 'B', 'D']
Data Structure | Unit Test | Performance Test | API Documentation | Implemented |
---|---|---|---|---|
Binary Tree | Binary Tree | |||
Binary Search Tree (BST) | BST | |||
AVL Tree | AVLTree | |||
Tree Multiset | TreeMultiset | |||
Segment Tree | SegmentTree | |||
Binary Indexed Tree | BinaryIndexedTree | |||
Graph | AbstractGraph | |||
Directed Graph | DirectedGraph | |||
Undirected Graph | UndirectedGraph | |||
Linked List | SinglyLinkedList | |||
Singly Linked List | SinglyLinkedList | |||
Doubly Linked List | DoublyLinkedList | |||
Queue | Queue | |||
Object Deque | ObjectDeque | |||
Array Deque | ArrayDeque | |||
Stack | Stack | |||
Coordinate Set | CoordinateSet | |||
Coordinate Map | CoordinateMap | |||
Heap | Heap | |||
Priority Queue | PriorityQueue | |||
Max Priority Queue | MaxPriorityQueue | |||
Min Priority Queue | MinPriorityQueue | |||
Trie | Trie |
By strictly adhering to object-oriented design (BinaryTree -> BST -> AVLTree -> TreeMultiset), you can seamlessly inherit the existing data structures to implement the customized ones you need. Object-oriented design stands as the optimal approach to data structure design.
Big O Notation | Type | Computations for 10 elements | Computations for 100 elements | Computations for 1000 elements |
---|---|---|---|---|
O(1) | Constant | 1 | 1 | 1 |
O(log N) | Logarithmic | 3 | 6 | 9 |
O(N) | Linear | 10 | 100 | 1000 |
O(N log N) | n log(n) | 30 | 600 | 9000 |
O(N^2) | Quadratic | 100 | 10000 | 1000000 |
O(2^N) | Exponential | 1024 | 1.26e+29 | 1.07e+301 |
O(N!) | Factorial | 3628800 | 9.3e+157 | 4.02e+2567 |
Data Structure | Access | Search | Insertion | Deletion | Comments |
---|---|---|---|---|---|
Array | 1 | n | n | n | |
Stack | n | n | 1 | 1 | |
Queue | n | n | 1 | 1 | |
Linked List | n | n | 1 | n | |
Hash Table | - | n | n | n | In case of perfect hash function costs would be O(1) |
Binary Search Tree | n | n | n | n | In case of balanced tree costs would be O(log(n)) |
B-Tree | log(n) | log(n) | log(n) | log(n) | |
Red-Black Tree | log(n) | log(n) | log(n) | log(n) | |
AVL Tree | log(n) | log(n) | log(n) | log(n) | |
Bloom Filter | - | 1 | 1 | - | False positives are possible while searching |
Name | Best | Average | Worst | Memory | Stable | Comments |
---|---|---|---|---|---|---|
Bubble sort | n | n2 | n2 | 1 | Yes | |
Insertion sort | n | n2 | n2 | 1 | Yes | |
Selection sort | n2 | n2 | n2 | 1 | No | |
Heap sort | n log(n) | n log(n) | n log(n) | 1 | No | |
Merge sort | n log(n) | n log(n) | n log(n) | n | Yes | |
Quick sort | n log(n) | n log(n) | n2 | log(n) | No | Quicksort is usually done in-place with O(log(n)) stack space |
Shell sort | n log(n) | depends on gap sequence | n (log(n))2 | 1 | No | |
Counting sort | n + r | n + r | n + r | n + r | Yes | r - biggest number in array |
Radix sort | n * k | n * k | n * k | n + k | Yes | k - length of longest key |
Data Structure | C++ STL | java.util | Python collections |
---|---|---|---|
Dynamic Array (ArrayList) | std::vector<T> | ArrayList<E> | list |
Linked List | std::list<T> | LinkedList<E> | deque |
Set | std::set<T> | HashSet<E> | set |
Map | std::map<K, V> | HashMap<K, V> | dict |
Stack | std::stack<T> | Stack<E> | N/A |
Queue | std::queue<T> | LinkedList<E> | N/A |
Priority Queue | std::priority_queue<T> | PriorityQueue<E> | N/A |
Hash Table | N/A | N/A | defaultdict, Counter, etc. |
Deque | std::deque<T> | N/A | N/A |
Multiset | std::multiset<T> | N/A | N/A |
Multimap | std::multimap<K, V> | N/A | N/A |
Unordered Set | std::unordered_set<T> | HashSet<E> | N/A |
Unordered Map | std::unordered_map<K, V> | HashMap<K, V> | N/A |
Bitset | std::bitset<N> | N/A | N/A |
Ordered Dictionary (OrderedDict) | N/A | N/A | OrderedDict |
User-Defined Dictionary | N/A | N/A | UserDict |
User-Defined List | N/A | N/A | UserList |
User-Defined Set | N/A | N/A | UserSet |
Double-Ended Queue (Deque) | std::deque<T> | N/A | N/A |
Skip List | N/A | N/A | N/A |
Circular Queue | N/A | N/A | N/A |
Bit Array | N/A | N/A | N/A |
Bloom Filter | N/A | N/A | N/A |
Linked Hash Set | N/A | LinkedHashSet<E> | N/A |
Linked Hash Map | N/A | LinkedHashMap<K, V> | N/A |
Sorted Set | N/A | TreeSet<E> | N/A |
Sorted Map | N/A | TreeMap<K, V> | N/A |
Tree Set | N/A | N/A | N/A |
Tree Map | N/A | N/A | N/A |
Persistent Collections | N/A | N/A | N/A |
std::unordered_multiset | std::unordered_multiset<T> | N/A | N/A |
std::unordered_multimap | std::unordered_multimap<K, V> | N/A | N/A |
N/A | TreeSet<E> | TreeSet<E> | N/A |
N/A | TreeMap<K, V> | TreeMap<K, V> | N/A |
N/A | LinkedBlockingQueue<E> | N/A | N/A |
N/A | ConcurrentHashMap<K, V> | N/A | N/A |
N/A | N/A | namedtuple | N/A |
N/A | N/A | ChainMap | N/A |
N/A | N/A | defaultdict | N/A |
N/A | N/A | Counter | N/A |
FAQs
Javascript Data Structure. Heap, Binary Tree, Red Black Tree, Linked List, Deque, Trie, HashMap, Directed Graph, Undirected Graph, Binary Search Tree(BST), AVL Tree, Priority Queue, Graph, Queue, Tree Multiset, Singly Linked List, Doubly Linked List, Max
We found that data-structure-typed demonstrated a healthy version release cadence and project activity because the last version was released less than a year ago. It has 1 open source maintainer collaborating on the project.
Did you know?
Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.
Product
Ensure open-source compliance with Socket’s License Enforcement Beta. Set up your License Policy and secure your software!
Product
We're launching a new set of license analysis and compliance features for analyzing, managing, and complying with licenses across a range of supported languages and ecosystems.
Product
We're excited to introduce Socket Optimize, a powerful CLI command to secure open source dependencies with tested, optimized package overrides.