Efficient data structures for Node
Installation
npm install --save efficient-data-structures
Efficient implementations
Data structure | Function | Runtime complexity | Space complexity | Complexity variables |
---|---|---|---|---|
BitVector |
set(bit, value) |
O(1) | O(n) |
|
get(bit) |
O(1) | |||
StringBuilder |
append(str) |
O(1) | O(n) |
|
toString() |
O(n) | |||
Stack |
push(obj) |
O(1) | O(n) |
|
pop() |
O(1) | |||
peek() |
O(1) | |||
Queue |
enqueue(obj) |
O(1) | O(n) |
|
dequeue() |
O(1) | |||
SinglyLinkedList |
insert(node, position) |
O(n) | O(n) |
|
prepend(node) |
O(1) | |||
remove(node) |
O(n) | |||
count() |
O(n) | |||
DoublyLinkedList |
insert(node, position) |
O(n) | O(n) |
|
prepend(node) |
O(1) | |||
append(node) |
O(1) | |||
remove(node) |
O(n) | |||
count() |
O(n) | |||
BinaryTree |
traverseInOrder() |
O(n) | O(n) |
|
traversePreOrder() |
O(n) | |||
traversePostOrder() |
O(n) | |||
isBinarySearchTree() |
O(n) | |||
isBalanced() |
O(n) | |||
isFull() |
O(n) | |||
isComplete() |
O(n) | |||
isPerfect() |
O(n) | |||
MinHeap |
insert(obj) |
O(log n) | O(n) |
|
extractMin() |
O(log n) | |||
MaxHeap |
insert(obj) |
O(log n) | O(n) |
|
extractMax() |
O(log n) | |||
Graph |
traverseDepthFirst() |
O(n) | O(n) |
|
traverseBreadthFirst() |
O(n) |
Usage
You need to first import the data structures that you're going to use.
;
BitVector
const bitVector = 10; bitVector;bitVector; console; // trueconsole; // false
StringBuilder
const stringBuilder = ; stringBuilder;stringBuilder; console; // 100 degrees Fahrenheit
Stack
const stack = ; stack;stack;stack; console; // 30console; // 30console; // 20
Queue
const queue = ; queue;queue;queue; console; // 10console; // 20
SinglyLinkedList
const singlyLinkedList = ;const tomNode = 'Tom';const jimNode = 'Jim'; singlyLinkedList;singlyLinkedList; singlyLinkedList; console; // 1
DoublyLinkedList
const doublyLinkedList = ; const tomNode = 'Tom';const jimNode = 'Jim'; doublyLinkedList;doublyLinkedList; doublyLinkedList; console; // 1
BinaryTree
// 8// / \// 4 10// / \ \// 2 6 20const root = 8; root; rootleft; rootleft; root; rootright;const tree = root; console; // [2, 4, 6, 8, 10, 20]console; // [8, 4, 2, 6, 10, 20]console; // [2, 6, 4, 20, 10, 8] console; // trueconsole; // trueconsole; // falseconsole; // falseconsole; // false
MinHeap
// 2// / \// 8 12// /// 10const minHeap = ; minHeap;minHeap;minHeap;minHeap; console; // 2console; // 8
MaxHeap
// 12// / \// 8 10// /// 2const maxHeap = ; maxHeap;maxHeap;maxHeap;maxHeap; console; // 12console; // 10
Graph
// 1---4// \ \// 2---3// \ /// 5const node1 = 1;const node2 = 2;const node3 = 3;const node4 = 4;const node5 = 5; node1children;node1children;node2children;node3children;node3children;node5children; const graph = node1; console; // [1, 2, 3, 4, 5]console; // [1, 2, 4, 3, 5]
Contributing
Got a new data structure you'd like to see implemented in this package? Please go ahead and create a work item for me; or better yet, send a pull request and I'll be sure to take a look at it within 24 hours. Thanks!