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)	n represents the number of bits
`BitVector`	`get(bit)`	O(1)	O(n)	n represents the number of bits
`StringBuilder`	`append(str)`	O(1)	O(n)	n represents the number of strings
`StringBuilder`	`toString()`	O(n)	O(n)	n represents the number of strings
`Stack`	`push(obj)`	O(1)	O(n)	n represents the number of objects
	`pop()`	O(1)
	`peek()`	O(1)
`Queue`	`enqueue(obj)`	O(1)	O(n)	n represents the number of objects
`Queue`	`dequeue()`	O(1)	O(n)	n represents the number of objects
`SinglyLinkedList`	`insert(node, position)`	O(n)	O(n)	n represents the number of nodes
	`prepend(node)`	O(1)
	`remove(node)`	O(n)
	`count()`	O(n)
`DoublyLinkedList`	`insert(node, position)`	O(n)	O(n)	n represents the number of nodes
	`prepend(node)`	O(1)
	`append(node)`	O(1)
	`remove(node)`	O(n)
	`count()`	O(n)
`BinaryTree`	`traverseInOrder()`	O(n)	O(n)	n represents the number of nodes
	`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)	n represents the number of objects
`MinHeap`	`extractMin()`	O(log n)	O(n)	n represents the number of objects
`MaxHeap`	`insert(obj)`	O(log n)	O(n)	n represents the number of objects
`MaxHeap`	`extractMax()`	O(log n)	O(n)	n represents the number of objects
`Graph`	`traverseDepthFirst()`	O(n)	O(n)	n represents the number of nodes
`Graph`	`traverseBreadthFirst()`	O(n)	O(n)	n represents the number of nodes

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!

Package detail

efficient-data-structures

readme