Efficient data structures for Node
Installation
npm install --save efficient-data-structures
Efficient implementations
<thead>
<tr>
<th>Data structure</th>
<th>Function</th>
<th>Runtime complexity</th>
<th>Space complexity</th>
<th>Complexity variables</th>
</tr>
</thead>
<tbody>
<!-- BitVector -->
<tr>
<td rowspan="2"><code>BitVector</code></td>
<td><code>set(bit, value)</code></td>
<td>O(1)</td>
<td rowspan="2">O(n)</td>
<td rowspan="2">
<dl>
<dt>n</dt>
<dd>represents the number of bits</dd>
</dl>
</td>
</tr>
<tr>
<td><code>get(bit)</code></td>
<td>O(1)</td>
</tr>
<!-- StringBuilder -->
<tr>
<td rowspan="2"><code>StringBuilder</code></td>
<td><code>append(str)</code></td>
<td>O(1)</td>
<td rowspan="2">O(n)</td>
<td rowspan="2">
<dl>
<dt>n</dt>
<dd>represents the number of strings</dd>
</dl>
</td>
</tr>
<tr>
<td><code>toString()</code></td>
<td>O(n)</td>
</tr>
<!-- Stack -->
<tr>
<td rowspan="3"><code>Stack</code></td>
<td><code>push(obj)</code></td>
<td>O(1)</td>
<td rowspan="3">O(n)</td>
<td rowspan="3">
<dl>
<dt>n</dt>
<dd>represents the number of objects</dd>
</dl>
</td>
</tr>
<tr>
<td><code>pop()</code></td>
<td>O(1)</td>
</tr>
<tr>
<td><code>peek()</code></td>
<td>O(1)</td>
</tr>
<!-- Queue -->
<tr>
<td rowspan="2"><code>Queue</code></td>
<td><code>enqueue(obj)</code></td>
<td>O(1)</td>
<td rowspan="2">O(n)</td>
<td rowspan="2">
<dl>
<dt>n</dt>
<dd>represents the number of objects</dd>
</dl>
</td>
</tr>
<tr>
<td><code>dequeue()</code></td>
<td>O(1)</td>
</tr>
<!-- SinglyLinkedList -->
<tr>
<td rowspan="4"><code>SinglyLinkedList</code></td>
<td><code>insert(node, position)</code></td>
<td>O(n)</td>
<td rowspan="4">O(n)</td>
<td rowspan="4">
<dl>
<dt>n</dt>
<dd>represents the number of nodes</dd>
</dl>
</td>
</tr>
<tr>
<td><code>prepend(node)</code></td>
<td>O(1)</td>
</tr>
<tr>
<td><code>remove(node)</code></td>
<td>O(n)</td>
</tr>
<tr>
<td><code>count()</code></td>
<td>O(n)</td>
</tr>
<!-- DoublyLinkedList -->
<tr>
<td rowspan="5"><code>DoublyLinkedList</code></td>
<td><code>insert(node, position)</code></td>
<td>O(n)</td>
<td rowspan="5">O(n)</td>
<td rowspan="5">
<dl>
<dt>n</dt>
<dd>represents the number of nodes</dd>
</dl>
</td>
</tr>
<tr>
<td><code>prepend(node)</code></td>
<td>O(1)</td>
</tr>
<tr>
<td><code>append(node)</code></td>
<td>O(1)</td>
</tr>
<tr>
<td><code>remove(node)</code></td>
<td>O(n)</td>
</tr>
<tr>
<td><code>count()</code></td>
<td>O(n)</td>
</tr>
<!-- BinaryTree -->
<tr>
<td rowspan="8"><code>BinaryTree</code></td>
<td><code>traverseInOrder()</code></td>
<td>O(n)</td>
<td rowspan="8">O(n)</td>
<td rowspan="8">
<dl>
<dt>n</dt>
<dd>represents the number of nodes</dd>
</dl>
</td>
</tr>
<tr>
<td><code>traversePreOrder()</code></td>
<td>O(n)</td>
</tr>
<tr>
<td><code>traversePostOrder()</code></td>
<td>O(n)</td>
</tr>
<tr>
<td><code>isBinarySearchTree()</code></td>
<td>O(n)</td>
</tr>
<tr>
<td><code>isBalanced()</code></td>
<td>O(n)</td>
</tr>
<tr>
<td><code>isFull()</code></td>
<td>O(n)</td>
</tr>
<tr>
<td><code>isComplete()</code></td>
<td>O(n)</td>
</tr>
<tr>
<td><code>isPerfect()</code></td>
<td>O(n)</td>
</tr>
<!-- MinHeap -->
<tr>
<td rowspan="2"><code>MinHeap</code></td>
<td><code>insert(obj)</code></td>
<td>O(log n)</td>
<td rowspan="2">O(n)</td>
<td rowspan="2">
<dl>
<dt>n</dt>
<dd>represents the number of objects</dd>
</dl>
</td>
</tr>
<tr>
<td><code>extractMin()</code></td>
<td>O(log n)</td>
</tr>
<!-- MaxHeap -->
<tr>
<td rowspan="2"><code>MaxHeap</code></td>
<td><code>insert(obj)</code></td>
<td>O(log n)</td>
<td rowspan="2">O(n)</td>
<td rowspan="2">
<dl>
<dt>n</dt>
<dd>represents the number of objects</dd>
</dl>
</td>
</tr>
<tr>
<td><code>extractMax()</code></td>
<td>O(log n)</td>
</tr>
<!-- Graph -->
<tr>
<td rowspan="2"><code>Graph</code></td>
<td><code>traverseDepthFirst()</code></td>
<td>O(n)</td>
<td rowspan="2">O(n)</td>
<td rowspan="2">
<dl>
<dt>n</dt>
<dd>represents the number of nodes</dd>
</dl>
</td>
</tr>
<tr>
<td><code>traverseBreadthFirst()</code></td>
<td>O(n)</td>
</tr>
</tbody>
Usage
You need to first import the data structures that you're going to use.
import {
BitVector,
StringBuilder,
Stack,
Queue,
SinglyLinkedList,
SinglyLinkedListNode,
DoublyLinkedList,
DoublyLinkedListNode,
BinaryTree,
BinaryTreeNode,
MinHeap,
MaxHeap,
Graph,
GraphNode,
} from 'efficient-data-structures';
BitVector
const bitVector = new BitVector(10);
bitVector.set(0, true);
bitVector.set(1, false);
console.log(bitVector.get(0)); // true
console.log(bitVector.get(1)); // false
StringBuilder
const stringBuilder = new StringBuilder();
stringBuilder.append('100 degrees');
stringBuilder.append(' Fahrenheit');
console.log(stringBuilder.toString()); // 100 degrees Fahrenheit
Stack
const stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);
console.log(stack.peek()); // 30
console.log(stack.pop()); // 30
console.log(stack.peek()); // 20
Queue
const queue = new Queue();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
console.log(queue.dequeue()); // 10
console.log(queue.dequeue()); // 20
SinglyLinkedList
const singlyLinkedList = new SinglyLinkedList();
const tomNode = new SinglyLinkedListNode('Tom');
const jimNode = new SinglyLinkedListNode('Jim');
singlyLinkedList.insert(tomNode, 0);
singlyLinkedList.insert(jimNode, 0);
singlyLinkedList.remove(jimNode);
console.log(singlyLinkedList.count()); // 1
DoublyLinkedList
const doublyLinkedList = new DoublyLinkedList();
const tomNode = new DoublyLinkedListNode('Tom');
const jimNode = new DoublyLinkedListNode('Jim');
doublyLinkedList.insert(tomNode, 0);
doublyLinkedList.insert(jimNode, 0);
doublyLinkedList.remove(jimNode);
console.log(doublyLinkedList.count()); // 1
BinaryTree
// 8
// / \
// 4 10
// / \ \
// 2 6 20
const root = new BinaryTreeNode(8);
root.setLeft(new BinaryTreeNode(4));
root.left.setLeft(new BinaryTreeNode(2));
root.left.setRight(new BinaryTreeNode(6));
root.setRight(new BinaryTreeNode(10));
root.right.setRight(new BinaryTreeNode(20));
const tree = new BinaryTree(root);
console.log(tree.traverseInOrder()); // [2, 4, 6, 8, 10, 20]
console.log(tree.traversePreOrder()); // [8, 4, 2, 6, 10, 20]
console.log(tree.traversePostOrder()); // [2, 6, 4, 20, 10, 8]
console.log(tree.isBinarySearchTree()); // true
console.log(tree.isBalanced()); // true
console.log(tree.isFull()); // false
console.log(tree.isComplete()); // false
console.log(tree.isPerfect()); // false
MinHeap
// 2
// / \
// 8 12
// /
// 10
const minHeap = new MinHeap();
minHeap.insert(8);
minHeap.insert(10);
minHeap.insert(12);
minHeap.insert(2);
console.log(minHeap.extractMin()); // 2
console.log(minHeap.extractMin()); // 8
MaxHeap
// 12
// / \
// 8 10
// /
// 2
const maxHeap = new MaxHeap();
maxHeap.insert(8);
maxHeap.insert(10);
maxHeap.insert(12);
maxHeap.insert(2);
console.log(maxHeap.extractMax()); // 12
console.log(maxHeap.extractMax()); // 10
Graph
// 1---4
// \ \
// 2---3
// \ /
// 5
const node1 = new GraphNode(1);
const node2 = new GraphNode(2);
const node3 = new GraphNode(3);
const node4 = new GraphNode(4);
const node5 = new GraphNode(5);
node1.children.push(node2);
node1.children.push(node4);
node2.children.push(node3);
node3.children.push(node4);
node3.children.push(node5);
node5.children.push(node2);
const graph = new Graph(node1);
console.log(graph.traverseDepthFirst()); // [1, 2, 3, 4, 5]
console.log(graph.traverseBreadthFirst()); // [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!
