Ninja Pumpkin Mutants

    efficient-data-structures
    TypeScript icon, indicating that this package has built-in type declarations

    0.1.310 • Public • Published

    Efficient data structures for Node

    build status coverage report npm npm

    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
    get(bit) O(1)
    StringBuilder append(str) O(1) O(n)
    n
    represents the number of strings
    toString() O(n)
    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
    dequeue() O(1)
    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
    extractMin() O(log n)
    MaxHeap insert(obj) O(log n) O(n)
    n
    represents the number of objects
    extractMax() O(log n)
    Graph traverseDepthFirst() O(n) O(n)
    n
    represents the number of nodes
    traverseBreadthFirst() O(n)

    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!

    Install

    npm i efficient-data-structures

    DownloadsWeekly Downloads

    34

    Version

    0.1.310

    License

    MIT

    Last publish

    Collaborators

    • borzabot
    • paulborza