| test name | time taken (ms) | sample mean (secs) | sample deviation |
|---|---|---|---|
| 100,000 add | 6.85 | 0.01 | 3.38e-4 |
| 100,000 add & poll | 35.35 | 0.04 | 8.44e-4 |
Gathering detailed insights and metrics for data-structure-typed
Javascript Data Structure & TypeScript Data Structure. Heap, Binary Tree, Red Black Tree, Linked List, Deque, Trie, HashMap, Directed Graph, Undirected Graph, Binary Search Tree, AVL Tree, Priority Queue, Graph, Queue, Tree Multiset, Singly Linked List, Doubly Linked List, Max Heap, Max Priority Queue, Min Heap, Min Priority Queue, Stack.
Installations
npm install data-structure-typedDeveloper Guide
BETA
Typescript
Yes
Module System
CommonJS, UMD
Node Version
22.10.0
NPM Version
10.9.0
Score
92.2
Supply Chain
100
Quality
89.2
Maintenance
100
Vulnerability
100
License
Releases
7
Contributors
5
Unable to fetch Contributors
Languages
5
TypeScript
JavaScript
HTML
Shell
Handlebars
TypeScript (95.37%)
JavaScript (3.15%)
HTML (0.85%)
Shell (0.56%)
Handlebars (0.07%)
Love this project? Help keep it running — sponsor us today! 🚀
Developer
Download Statistics
Total Downloads
494,201
Last Day
1,976
Last Week
9,254
Last Month
47,175
Last Year
345,836
GitHub Statistics
136 Stars
609 Commits
9 Forks
1 Watching
11 Branches
5 Contributors
Bundle Size
111.05 kB
Minified
25.50 kB
Minified + Gzipped
Maintainers
1
Package Meta Information
Latest Version
2.0.1
Package Id
data-structure-typed@2.0.1
Unpacked Size
8.56 MB
Size
1.37 MB
File Count
933
NPM Version
10.9.0
Node Version
22.10.0
Publised On
23 Jan 2025
Total Downloads
Cumulative downloads
Total Downloads
494,201
Last day
-29.6%
1,976
Compared to previous day
Last week
-26.4%
9,254
Compared to previous week
Last month
-10.4%
47,175
Compared to previous month
Last year
133.1%
345,836
Compared to previous year
Daily Downloads
Weekly Downloads
Monthly Downloads
Yearly Downloads
Dev Dependencies
34
@eslint/compat@eslint/eslintrc@eslint/js@swc/core@types/benchmark@types/jest@types/node@typescript-eslint/eslint-plugin@typescript-eslint/parserauto-changelogavl-tree-typedbenchmarkbinary-tree-typedbst-typeddata-structure-typeddependency-cruiserdoctoceslinteslint-config-prettiereslint-import-resolver-aliaseslint-import-resolver-typescripteslint-plugin-importfast-globheap-typedistanbul-badges-readmejestjs-sdslprettierts-jestts-loaderts-nodetsuptypedoctypescript
Versions
data-structure-typed
Our goal is to make every data structure as convenient and efficient as JavaScript's Array.
Installation and Usage
npm
1npm i data-structure-typed --save
yarn
1yarn add data-structure-typed
1import { 2 Heap, Graph, Queue, Deque, PriorityQueue, BST, Trie, DoublyLinkedList, 3 AVLTree, SinglyLinkedList, DirectedGraph, RedBlackTree, TreeMultiMap, 4 DirectedVertex, Stack, AVLTreeNode 5} from 'data-structure-typed';
If you only want to use a specific data structure independently, you can install it separately, for example, by running
1npm i heap-typed --save
Why
Do you envy C++ with STL (std::), Python with collections, and Java with java.util ? Well, no need to envy
anymore! JavaScript and TypeScript now have data-structure-typed.Benchmark compared with C++ STL.
API standards aligned with ES6 and Java. Usability is comparable to Python
Performance
Performance surpasses that of native JS/TS
| Method | Time Taken | Data Scale | Belongs To | big O |
|---|---|---|---|---|
| Queue.push & shift | 5.83 ms | 100K | Ours | O(1) |
| Array.push & shift | 2829.59 ms | 100K | Native JS | O(n) |
| Deque.unshift & shift | 2.44 ms | 100K | Ours | O(1) |
| Array.unshift & shift | 4750.37 ms | 100K | Native JS | O(n) |
| HashMap.set | 122.51 ms | 1M | Ours | O(1) |
| Map.set | 223.80 ms | 1M | Native JS | O(1) |
| Set.add | 185.06 ms | 1M | Native JS | O(1) |
Plain language explanations
| Data Structure | Plain Language Definition | Diagram |
|---|---|---|
| Linked List (Singly Linked List) | A line of bunnies, where each bunny holds the tail of the bunny in front of it (each bunny only knows the name of the bunny behind it). You want to find a bunny named Pablo, and you have to start searching from the first bunny. If it's not Pablo, you continue following that bunny's tail to the next one. So, you might need to search n times to find Pablo (O(n) time complexity). If you want to insert a bunny named Remi between Pablo and Vicky, it's very simple. You just need to let Vicky release Pablo's tail, let Remi hold Pablo's tail, and then let Vicky hold Remi's tail (O(1) time complexity). |  |
| Array | A line of numbered bunnies. If you want to find the bunny named Pablo, you can directly shout out Pablo's number 0680 (finding the element directly through array indexing, O(1) time complexity). However, if you don't know Pablo's number, you still need to search one by one (O(n) time complexity). Moreover, if you want to add a bunny named Vicky behind Pablo, you will need to renumber all the bunnies after Vicky (O(n) time complexity). |  |
| Queue | A line of numbered bunnies with a sticky note on the first bunny. For this line with a sticky note on the first bunny, whenever we want to remove a bunny from the front of the line, we only need to move the sticky note to the face of the next bunny without actually removing the bunny to avoid renumbering all the bunnies behind (removing from the front is also O(1) time complexity). For the tail of the line, we don't need to worry because each new bunny added to the tail is directly given a new number (O(1) time complexity) without needing to renumber all the previous bunnies. |  |
| Deque | A line of grouped, numbered bunnies with a sticky note on the first bunny. For this line, we manage it by groups. Each time we remove a bunny from the front of the line, we only move the sticky note to the next bunny. This way, we don't need to renumber all the bunnies behind the first bunny each time a bunny is removed. Only when all members of a group are removed do we reassign numbers and regroup. The tail is handled similarly. This is a strategy of delaying and batching operations to offset the drawbacks of the Array data structure that requires moving all elements behind when inserting or deleting elements in the middle. |  |
| Doubly Linked List | A line of bunnies where each bunny holds the tail of the bunny in front (each bunny knows the names of the two adjacent bunnies). This provides the Singly Linked List the ability to search forward, and that's all. For example, if you directly come to the bunny Remi in the line and ask her where Vicky is, she will say the one holding my tail behind me, and if you ask her where Pablo is, she will say right in front. |  |
| Stack | A line of bunnies in a dead-end tunnel, where bunnies can only be removed from the tunnel entrance (end), and new bunnies can only be added at the entrance (end) as well. |  |
| Binary Tree | As the name suggests, it's a tree where each node has at most two children. When you add consecutive data such as [4, 2, 6, 1, 3, 5, 7], it will be a complete binary tree. When you add data like [4, 2, 6, null, 1, 3, null, 5, null, 7], you can specify whether any left or right child node is null, and the shape of the tree is fully controllable. |  |
| Binary Search Tree (BST) | A tree-like rabbit colony composed of doubly linked lists where each rabbit has at most two tails. These rabbits are disciplined and obedient, arranged in their positions according to a certain order. The most important data structure in a binary tree (the core is that the time complexity for insertion, deletion, modification, and search is O(log n)). The data stored in a BST is structured and ordered, not in strict order like 1, 2, 3, 4, 5, but maintaining that all nodes in the left subtree are less than the node, and all nodes in the right subtree are greater than the node. This order provides O(log n) time complexity for insertion, deletion, modification, and search. Reducing O(n) to O(log n) is the most common algorithm complexity optimization in the computer field, an exponential improvement in efficiency. It's also the most efficient way to organize unordered data into ordered data (most sorting algorithms only maintain O(n log n)). Of course, the binary search trees we provide support organizing data in both ascending and descending order. Remember that basic BSTs do not have self-balancing capabilities, and if you sequentially add sorted data to this data structure, it will degrade into a list, thus losing the O(log n) capability. Of course, our addMany method is specially handled to prevent degradation. However, for practical applications, please use Red-black Tree or AVL Tree as much as possible, as they inherently have self-balancing functions. |  |
| Red-black Tree | A tree-like rabbit colony composed of doubly linked lists, where each rabbit has at most two tails. These rabbits are not only obedient but also intelligent, automatically arranging their positions in a certain order. A self-balancing binary search tree. Each node is marked with a red-black label. Ensuring that no path is more than twice as long as any other (maintaining a certain balance to improve the speed of search, addition, and deletion). |  |
| AVL Tree | A tree-like rabbit colony composed of doubly linked lists, where each rabbit has at most two tails. These rabbits are not only obedient but also intelligent, automatically arranging their positions in a certain order, and they follow very strict rules. A self-balancing binary search tree. Each node is marked with a balance factor, representing the height difference between its left and right subtrees. The absolute value of the balance factor does not exceed 1 (maintaining stricter balance, which makes search efficiency higher than Red-black Tree, but insertion and deletion operations will be more complex and relatively less efficient). |  |
| Heap | A special type of complete binary tree, often stored in an array, where the children nodes of the node at index i are at indices 2i+1 and 2i+2. Naturally, the parent node of any node is at ⌊(i−1)/2⌋. |  |
| Priority Queue | It's actually a Heap. | |
| Graph | The base class for Directed Graph and Undirected Graph, providing some common methods. |  |
| Directed Graph | A network-like bunny group where each bunny can have up to n tails (Singly Linked List). |  |
| Undirected Graph | A network-like bunny group where each bunny can have up to n tails (Doubly Linked List). |  |
Conciseness and uniformity
In java.utils, you need to memorize a table for all sequential data structures(Queue, Deque, LinkedList),
| Java ArrayList | Java Queue | Java ArrayDeque | Java LinkedList |
|---|---|---|---|
| add | offer | push | push |
| remove | poll | removeLast | removeLast |
| remove | poll | removeFirst | removeFirst |
| add(0, element) | offerFirst | unshift | unshift |
whereas in our data-structure-typed, you only need to remember four methods: push, pop, shift, and unshift for all sequential data structures(Queue, Deque, DoublyLinkedList, SinglyLinkedList and Array).
Data structures available
We provide data structures that are not available in JS/TS
| Data Structure | Unit Test | Perf Test | API Doc | NPM | Downloads |
|---|---|---|---|---|---|
| Binary Tree |  | | Docs | NPM |  |
| Binary Search Tree (BST) | | | Docs | NPM |  |
| AVL Tree | | | Docs | NPM |  |
| Red Black Tree | | | Docs | NPM |  |
| Tree Multimap | | | Docs | NPM |  |
| Heap | | | Docs | NPM |  |
| Priority Queue | | | Docs | NPM |  |
| Max Priority Queue | | | Docs | NPM |  |
| Min Priority Queue | | | Docs | NPM |  |
| Trie | | | Docs | NPM |  |
| Graph | | | Docs | NPM |  |
| Directed Graph | | | Docs | NPM |  |
| Undirected Graph | | | Docs | NPM |  |
| Queue | | | Docs | NPM |  |
| Deque | | | Docs | NPM |  |
| Hash Map | | | Docs | ||
| Linked List | | | Docs | NPM |  |
| Singly Linked List | | | Docs | NPM |  |
| Doubly Linked List | | | Docs | NPM |  |
| Stack | | | Docs | NPM |  |
| Segment Tree | | Docs | |||
| Binary Indexed Tree | | Docs |
Vivid Examples
AVL Tree
Try it out, or you can run your own code using our visual tool
Tree Multi Map
Directed Graph
Map Graph
Code Snippets
Red Black Tree snippet
TS
1import { RedBlackTree } from 'data-structure-typed'; 2 3const rbTree = new RedBlackTree<number>(); 4rbTree.addMany([11, 3, 15, 1, 8, 13, 16, 2, 6, 9, 12, 14, 4, 7, 10, 5]) 5rbTree.isAVLBalanced(); // true 6rbTree.delete(10); 7rbTree.isAVLBalanced(); // true 8rbTree.print() 9// ___6________ 10// / \ 11// ___4_ ___11________ 12// / \ / \ 13// _2_ 5 _8_ ____14__ 14// / \ / \ / \ 15// 1 3 7 9 12__ 15__ 16// \ \ 17// 13 16
JS
1import { RedBlackTree } from 'data-structure-typed'; 2 3const rbTree = new RedBlackTree(); 4rbTree.addMany([11, 3, 15, 1, 8, 13, 16, 2, 6, 9, 12, 14, 4, 7, 10, 5]) 5rbTree.isAVLBalanced(); // true 6rbTree.delete(10); 7rbTree.isAVLBalanced(); // true 8rbTree.print() 9// ___6________ 10// / \ 11// ___4_ ___11________ 12// / \ / \ 13// _2_ 5 _8_ ____14__ 14// / \ / \ / \ 15// 1 3 7 9 12__ 15__ 16// \ \ 17// 13 16
Free conversion between data structures.
1const orgArr = [6, 1, 2, 7, 5, 3, 4, 9, 8]; 2const orgStrArr = ["trie", "trial", "trick", "trip", "tree", "trend", "triangle", "track", "trace", "transmit"]; 3const entries = [[6, "6"], [1, "1"], [2, "2"], [7, "7"], [5, "5"], [3, "3"], [4, "4"], [9, "9"], [8, "8"]]; 4 5const queue = new Queue(orgArr); 6queue.print(); 7// [6, 1, 2, 7, 5, 3, 4, 9, 8] 8 9const deque = new Deque(orgArr); 10deque.print(); 11// [6, 1, 2, 7, 5, 3, 4, 9, 8] 12 13const sList = new SinglyLinkedList(orgArr); 14sList.print(); 15// [6, 1, 2, 7, 5, 3, 4, 9, 8] 16 17const dList = new DoublyLinkedList(orgArr); 18dList.print(); 19// [6, 1, 2, 7, 5, 3, 4, 9, 8] 20 21const stack = new Stack(orgArr); 22stack.print(); 23// [6, 1, 2, 7, 5, 3, 4, 9, 8] 24 25const minHeap = new MinHeap(orgArr); 26minHeap.print(); 27// [1, 5, 2, 7, 6, 3, 4, 9, 8] 28 29const maxPQ = new MaxPriorityQueue(orgArr); 30maxPQ.print(); 31// [9, 8, 4, 7, 5, 2, 3, 1, 6] 32 33const biTree = new BinaryTree(entries); 34biTree.print(); 35// ___6___ 36// / \ 37// ___1_ _2_ 38// / \ / \ 39// _7_ 5 3 4 40// / \ 41// 9 8 42 43const bst = new BST(entries); 44bst.print(); 45// _____5___ 46// / \ 47// _2_ _7_ 48// / \ / \ 49// 1 3_ 6 8_ 50// \ \ 51// 4 9 52 53 54const rbTree = new RedBlackTree(entries); 55rbTree.print(); 56// ___4___ 57// / \ 58// _2_ _6___ 59// / \ / \ 60// 1 3 5 _8_ 61// / \ 62// 7 9 63 64 65const avl = new AVLTree(entries); 66avl.print(); 67// ___4___ 68// / \ 69// _2_ _6___ 70// / \ / \ 71// 1 3 5 _8_ 72// / \ 73// 7 9 74 75const treeMulti = new TreeMultiMap(entries); 76treeMulti.print(); 77// ___4___ 78// / \ 79// _2_ _6___ 80// / \ / \ 81// 1 3 5 _8_ 82// / \ 83// 7 9 84 85const hm = new HashMap(entries); 86hm.print() 87// [[6, "6"], [1, "1"], [2, "2"], [7, "7"], [5, "5"], [3, "3"], [4, "4"], [9, "9"], [8, "8"]] 88 89const rbTreeH = new RedBlackTree(hm); 90rbTreeH.print(); 91// ___4___ 92// / \ 93// _2_ _6___ 94// / \ / \ 95// 1 3 5 _8_ 96// / \ 97// 7 9 98 99const pq = new MinPriorityQueue(orgArr); 100pq.print(); 101// [1, 5, 2, 7, 6, 3, 4, 9, 8] 102 103const bst1 = new BST(pq); 104bst1.print(); 105// _____5___ 106// / \ 107// _2_ _7_ 108// / \ / \ 109// 1 3_ 6 8_ 110// \ \ 111// 4 9 112 113const dq1 = new Deque(orgArr); 114dq1.print(); 115// [6, 1, 2, 7, 5, 3, 4, 9, 8] 116const rbTree1 = new RedBlackTree(dq1); 117rbTree1.print(); 118// _____5___ 119// / \ 120// _2___ _7___ 121// / \ / \ 122// 1 _4 6 _9 123// / / 124// 3 8 125 126 127const trie2 = new Trie(orgStrArr); 128trie2.print(); 129// ['trie', 'trial', 'triangle', 'trick', 'trip', 'tree', 'trend', 'track', 'trace', 'transmit'] 130const heap2 = new Heap(trie2, { comparator: (a, b) => Number(a) - Number(b) }); 131heap2.print(); 132// ['transmit', 'trace', 'tree', 'trend', 'track', 'trial', 'trip', 'trie', 'trick', 'triangle'] 133const dq2 = new Deque(heap2); 134dq2.print(); 135// ['transmit', 'trace', 'tree', 'trend', 'track', 'trial', 'trip', 'trie', 'trick', 'triangle'] 136const entries2 = dq2.map((el, i) => [i, el]); 137const avl2 = new AVLTree(entries2); 138avl2.print(); 139// ___3_______ 140// / \ 141// _1_ ___7_ 142// / \ / \ 143// 0 2 _5_ 8_ 144// / \ \ 145// 4 6 9
Binary Search Tree (BST) snippet
1import { BST, BSTNode } from 'data-structure-typed'; 2 3const bst = new BST<number>(); 4bst.add(11); 5bst.add(3); 6bst.addMany([15, 1, 8, 13, 16, 2, 6, 9, 12, 14, 4, 7, 10, 5]); 7bst.size === 16; // true 8bst.has(6); // true 9const node6 = bst.getNode(6); // BSTNode 10bst.getHeight(6) === 2; // true 11bst.getHeight() === 5; // true 12bst.getDepth(6) === 3; // true 13 14bst.getLeftMost()?.key === 1; // true 15 16bst.delete(6); 17bst.get(6); // undefined 18bst.isAVLBalanced(); // true 19bst.bfs()[0] === 11; // true 20bst.print() 21// ______________11_____ 22// / \ 23// ___3_______ _13_____ 24// / \ / \ 25// 1_ _____8____ 12 _15__ 26// \ / \ / \ 27// 2 4_ _10 14 16 28// \ / 29// 5_ 9 30// \ 31// 7 32 33const objBST = new BST<number, { height: number, age: number }>(); 34 35objBST.add(11, { "name": "Pablo", "size": 15 }); 36objBST.add(3, { "name": "Kirk", "size": 1 }); 37 38objBST.addMany([15, 1, 8, 13, 16, 2, 6, 9, 12, 14, 4, 7, 10, 5], [ 39 { "name": "Alice", "size": 15 }, 40 { "name": "Bob", "size": 1 }, 41 { "name": "Charlie", "size": 8 }, 42 { "name": "David", "size": 13 }, 43 { "name": "Emma", "size": 16 }, 44 { "name": "Frank", "size": 2 }, 45 { "name": "Grace", "size": 6 }, 46 { "name": "Hannah", "size": 9 }, 47 { "name": "Isaac", "size": 12 }, 48 { "name": "Jack", "size": 14 }, 49 { "name": "Katie", "size": 4 }, 50 { "name": "Liam", "size": 7 }, 51 { "name": "Mia", "size": 10 }, 52 { "name": "Noah", "size": 5 } 53 ] 54); 55 56objBST.delete(11);
AVLTree snippet
1import { AVLTree } from 'data-structure-typed'; 2 3const avlTree = new AVLTree<number>(); 4avlTree.addMany([11, 3, 15, 1, 8, 13, 16, 2, 6, 9, 12, 14, 4, 7, 10, 5]) 5avlTree.isAVLBalanced(); // true 6avlTree.delete(10); 7avlTree.isAVLBalanced(); // true
Directed Graph simple snippet
1import { DirectedGraph } from 'data-structure-typed'; 2 3const graph = new DirectedGraph<string>(); 4 5graph.addVertex('A'); 6graph.addVertex('B'); 7 8graph.hasVertex('A'); // true 9graph.hasVertex('B'); // true 10graph.hasVertex('C'); // false 11 12graph.addEdge('A', 'B'); 13graph.hasEdge('A', 'B'); // true 14graph.hasEdge('B', 'A'); // false 15 16graph.deleteEdgeSrcToDest('A', 'B'); 17graph.hasEdge('A', 'B'); // false 18 19graph.addVertex('C'); 20 21graph.addEdge('A', 'B'); 22graph.addEdge('B', 'C'); 23 24const topologicalOrderKeys = graph.topologicalSort(); // ['A', 'B', 'C']
Undirected Graph snippet
1import { UndirectedGraph } from 'data-structure-typed'; 2 3const graph = new UndirectedGraph<string>(); 4graph.addVertex('A'); 5graph.addVertex('B'); 6graph.addVertex('C'); 7graph.addVertex('D'); 8graph.deleteVertex('C'); 9graph.addEdge('A', 'B'); 10graph.addEdge('B', 'D'); 11 12const dijkstraResult = graph.dijkstra('A'); 13Array.from(dijkstraResult?.seen ?? []).map(vertex => vertex.key) // ['A', 'B', 'D'] 14 15
API docs & Examples
Benchmark
MacBook Pro (15-inch, 2018)
Processor 2.2 GHz 6-Core Intel Core i7
Memory 16 GB 2400 MHz DDR4
Graphics Radeon Pro 555X 4 GB
Intel UHD Graphics 630 1536 MB
macOS Big Sur
Version 11.7.9
Our performance testing is conducted directly on the TypeScript source code. The actual performance of the compiled JavaScript code is generally 3 times higher. We have compared it with C++, and it is only 30% slower than C++. Try it on gitpod
Just run
1pnpm perf:rbtree
11,000,000 add randomly: 1.367s 21,000,000 add: 374.859ms 31,000,000 get: 8.025ms 41,000,000 getNode: 1.293s
heap
avl-tree
| test name | time taken (ms) | sample mean (secs) | sample deviation |
|---|---|---|---|
| 100,000 add | 302.89 | 0.30 | 0.01 |
| 100,000 add randomly | 381.83 | 0.38 | 0.00 |
| 100,000 get | 0.60 | 5.95e-4 | 2.33e-4 |
| 100,000 getNode | 150.61 | 0.15 | 0.00 |
| 100,000 iterator | 28.23 | 0.03 | 0.00 |
| 100,000 add & delete orderly | 505.57 | 0.51 | 0.01 |
| 100,000 add & delete randomly | 677.36 | 0.68 | 0.00 |
rb-tree
| test name | time taken (ms) | sample mean (secs) | sample deviation |
|---|---|---|---|
| 100,000 add | 212.77 | 0.21 | 9.84e-4 |
| 100,000 add randomly | 163.70 | 0.16 | 0.00 |
| 100,000 get | 1.19 | 0.00 | 2.44e-4 |
| 100,000 getNode | 347.39 | 0.35 | 0.01 |
| 100,000 node mode add randomly | 162.26 | 0.16 | 0.00 |
| 100,000 node mode get | 344.90 | 0.34 | 0.00 |
| 100,000 iterator | 27.48 | 0.03 | 0.00 |
| 100,000 add & delete orderly | 386.33 | 0.39 | 0.00 |
| 100,000 add & delete randomly | 520.66 | 0.52 | 0.00 |
doubly-linked-list
| test name | time taken (ms) | sample mean (secs) | sample deviation |
|---|---|---|---|
| 1,000,000 push | 179.28 | 0.18 | 0.02 |
| 1,000,000 unshift | 197.22 | 0.20 | 0.05 |
| 1,000,000 unshift & shift | 153.16 | 0.15 | 0.00 |
| 1,000,000 addBefore | 247.30 | 0.25 | 0.03 |
directed-graph
| test name | time taken (ms) | sample mean (secs) | sample deviation |
|---|---|---|---|
| 1,000 addVertex | 0.10 | 9.92e-5 | 1.16e-6 |
| 1,000 addEdge | 6.44 | 0.01 | 0.00 |
| 1,000 getVertex | 0.10 | 9.82e-5 | 1.13e-6 |
| 1,000 getEdge | 22.60 | 0.02 | 0.00 |
| tarjan | 186.56 | 0.19 | 0.00 |
| topologicalSort | 145.42 | 0.15 | 0.01 |
queue
| test name | time taken (ms) | sample mean (secs) | sample deviation |
|---|---|---|---|
| 1,000,000 push | 47.74 | 0.05 | 0.02 |
| 100,000 push & shift | 5.39 | 0.01 | 1.25e-4 |
| Native JS Array 100,000 push & shift | 2225.50 | 2.23 | 0.10 |
deque
| test name | time taken (ms) | sample mean (secs) | sample deviation |
|---|---|---|---|
| 1,000,000 push | 22.88 | 0.02 | 0.01 |
| 1,000,000 push & pop | 27.95 | 0.03 | 0.01 |
| 1,000,000 push & shift | 29.83 | 0.03 | 0.01 |
| 100,000 push & shift | 2.71 | 0.00 | 9.03e-4 |
| Native JS Array 100,000 push & shift | 2182.03 | 2.18 | 0.04 |
| 100,000 unshift & shift | 2.61 | 0.00 | 8.71e-4 |
| Native JS Array 100,000 unshift & shift | 4185.90 | 4.19 | 0.04 |
hash-map
| test name | time taken (ms) | sample mean (secs) | sample deviation |
|---|---|---|---|
| 1,000,000 set | 253.45 | 0.25 | 0.07 |
| Native JS Map 1,000,000 set | 228.90 | 0.23 | 0.02 |
| Native JS Set 1,000,000 add | 179.65 | 0.18 | 0.01 |
| 1,000,000 set & get | 234.96 | 0.23 | 0.06 |
| Native JS Map 1,000,000 set & get | 284.90 | 0.28 | 0.01 |
| Native JS Set 1,000,000 add & has | 254.90 | 0.25 | 0.03 |
| 1,000,000 ObjKey set & get | 403.74 | 0.40 | 0.10 |
| Native JS Map 1,000,000 ObjKey set & get | 340.18 | 0.34 | 0.07 |
| Native JS Set 1,000,000 ObjKey add & has | 300.25 | 0.30 | 0.06 |
trie
| test name | time taken (ms) | sample mean (secs) | sample deviation |
|---|---|---|---|
| 100,000 push | 44.11 | 0.04 | 8.55e-4 |
| 100,000 getWords | 86.67 | 0.09 | 0.00 |
stack
| test name | time taken (ms) | sample mean (secs) | sample deviation |
|---|---|---|---|
| 1,000,000 push | 43.18 | 0.04 | 0.01 |
| 1,000,000 push & pop | 48.40 | 0.05 | 0.02 |
The corresponding relationships between data structures in different language standard libraries.
| Data Structure Typed | C++ STL | java.util | Python collections |
|---|---|---|---|
| Heap<E> | - | - | heapq |
| PriorityQueue<E> | priority_queue<T> | PriorityQueue<E> | - |
| Deque<E> | deque<T> | ArrayDeque<E> | deque |
| Queue<E> | queue<T> | Queue<E> | - |
| HashMap<K, V> | unordered_map<K, V> | HashMap<K, V> | defaultdict |
| DoublyLinkedList<E> | list<T> | LinkedList<E> | - |
| SinglyLinkedList<E> | - | - | - |
| BinaryTree<K, V> | - | - | - |
| BST<K, V> | - | - | - |
| RedBlackTree<E> | set<T> | TreeSet<E> | - |
| RedBlackTree<K, V> | map<K, V> | TreeMap<K, V> | - |
| TreeMultiMap<K, V> | multimap<K, V> | - | - |
| TreeMultiMap<E> | multiset<T> | - | - |
| Trie | - | - | - |
| DirectedGraph<V, E> | - | - | - |
| UndirectedGraph<V, E> | - | - | - |
| PriorityQueue<E> | priority_queue<T> | PriorityQueue<E> | - |
| Array<E> | vector<T> | ArrayList<E> | list |
| Stack<E> | stack<T> | Stack<E> | - |
| HashMap<E> | unordered_set<T> | HashSet<E> | set |
| - | unordered_multiset | - | Counter |
| ES6 Map<K, V> | - | LinkedHashMap<K, V> | OrderedDict |
| - | unordered_multimap<K, V> | - | - |
| - | bitset<N> | - | - |
Built-in classic algorithms
| Algorithm | Function Description | Iteration Type |
|---|---|---|
| Binary Tree DFS | Traverse a binary tree in a depth-first manner, starting from the root node, first visiting the left subtree, and then the right subtree, using recursion. | Recursion + Iteration |
| Binary Tree BFS | Traverse a binary tree in a breadth-first manner, starting from the root node, visiting nodes level by level from left to right. | Iteration |
| Graph DFS | Traverse a graph in a depth-first manner, starting from a given node, exploring along one path as deeply as possible, and backtracking to explore other paths. Used for finding connected components, paths, etc. | Recursion + Iteration |
| Binary Tree Morris | Morris traversal is an in-order traversal algorithm for binary trees with O(1) space complexity. It allows tree traversal without additional stack or recursion. | Iteration |
| Graph BFS | Traverse a graph in a breadth-first manner, starting from a given node, first visiting nodes directly connected to the starting node, and then expanding level by level. Used for finding shortest paths, etc. | Recursion + Iteration |
| Graph Tarjan's Algorithm | Find strongly connected components in a graph, typically implemented using depth-first search. | Recursion |
| Graph Bellman-Ford Algorithm | Finding the shortest paths from a single source, can handle negative weight edges | Iteration |
| Graph Dijkstra's Algorithm | Finding the shortest paths from a single source, cannot handle negative weight edges | Iteration |
| Graph Floyd-Warshall Algorithm | Finding the shortest paths between all pairs of nodes | Iteration |
| Graph getCycles | Find all cycles in a graph or detect the presence of cycles. | Recursion |
| Graph getCutVertices | Find cut vertices in a graph, which are nodes that, when removed, increase the number of connected components in the graph. | Recursion |
| Graph getSCCs | Find strongly connected components in a graph, which are subgraphs where any two nodes can reach each other. | Recursion |
| Graph getBridges | Find bridges in a graph, which are edges that, when removed, increase the number of connected components in the graph. | Recursion |
| Graph topologicalSort | Perform topological sorting on a directed acyclic graph (DAG) to find a linear order of nodes such that all directed edges go from earlier nodes to later nodes. | Recursion |
Software Engineering Design Standards
We strictly adhere to computer science theory and software development standards. Our LinkedList is designed in the traditional sense of the LinkedList data structure, and we refrain from substituting it with a Deque solely for the purpose of showcasing performance test data. However, we have also implemented a Deque based on a dynamic array concurrently.
| Principle | Description |
|---|---|
| Practicality | Follows ES6 and ESNext standards, offering unified and considerate optional parameters, and simplifies method names. |
| Extensibility | Adheres to OOP (Object-Oriented Programming) principles, allowing inheritance for all data structures. |
| Modularization | Includes data structure modularization and independent NPM packages. |
| Efficiency | All methods provide time and space complexity, comparable to native JS performance. |
| Maintainability | Follows open-source community development standards, complete documentation, continuous integration, and adheres to TDD (Test-Driven Development) patterns. |
| Testability | Automated and customized unit testing, performance testing, and integration testing. |
| Portability | Plans for porting to Java, Python, and C++, currently achieved to 80%. |
| Reusability | Fully decoupled, minimized side effects, and adheres to OOP. |
| Security | Carefully designed security for member variables and methods. Read-write separation. Data structure software does not need to consider other security aspects. |
| Scalability | Data structure software does not involve load issues. |
supported module system
Now you can use it in Node.js and browser environments
CommonJS:require export.modules =
ESModule: import export
Typescript: import export
UMD: var Deque = dataStructureTyped.Deque
CDN
Copy the line below into the head tag in an HTML document.
development
1 2<script src='https://cdn.jsdelivr.net/npm/data-structure-typed/dist/umd/data-structure-typed.js'></script>
production
1 2<script src='https://cdn.jsdelivr.net/npm/data-structure-typed/dist/umd/data-structure-typed.min.js'></script>
Copy the code below into the script tag of your HTML, and you're good to go with your development.
1const { Heap } = dataStructureTyped; 2const { 3 BinaryTree, Graph, Queue, Stack, PriorityQueue, BST, Trie, DoublyLinkedList, 4 AVLTree, MinHeap, SinglyLinkedList, DirectedGraph, TreeMultiMap, 5 DirectedVertex, AVLTreeNode 6} = dataStructureTyped;
No vulnerabilities found.
No security vulnerabilities found.