fast-data-structures

    0.0.5 • Public • Published

    Fast data structures

    Node.js module with most complete implementation of common data structures: Linked List and Binary Search Tree. (Heap in progress...)

    Motivation

    JavaScript arrays and objects are generally powerful structures. Arrays are used as collections of anything, and can easily emulate Stack or Queue. Object in JavaScript is basically a collection of key-value pairs, where each key (i.e. property name) is unique. So this structure is natural hash table. Although for client-side programming this is quite enough, on server-side we can deal with large amount of data and much more complex cases can be found. It’s always important to implement most efficient algorithm, according to requirements, and design application to be ready to scale without performance loss. Two basic more advanced data structures are Linked Lists and Binary Search Trees. There are a lot of implementations of these data structures out there, but I wanted to create one feature-rich implementation, with emphasis on features where these structures provide better performance than arrays or hash tables.

    Usage

    npm install fast-data-structures
    
        const LinkedList = require('fast-data-structures').LinkedList;
        const Bst = require('fast-data-structures').Bst;

    Linked List

    Linked lists are preferable over arrays if you:

    • have unpredictable number of elements which change over time
    • need to insert-delete elements at the beginning or middle of the list
    • perform large number of insert / delete operations
    • don't need random access to elements, but access is referenced to the beginning, end or one or more elements inside list
    • want to implement fast queue

    Create new empty list object

        const list = new LinkedList();

    ...or create new list from an array:

        const list = new LinkedList([1, 2, 3, 4, 5]);

    List contains doubly-linked Node objects, which have next properties:

    value
    next - reference to next node
    prev - reference to previous node
    

    LinkedList Properties & Methods:

    Property / Method Time complexity
    count O(1)
    first O(1)
    last O(1)
    getNewNode(val) O(1)
    addAfter(node, val) O(1)
    addBefore(node, val) O(1)
    addFirst(val) O(1)
    addLast(val) O(1)
    removeNode(node) O(1)
    removeFirst() O(1)
    removeLast() O(1)
    findByValue(val, getLast) O(N)
    iterate(callback) O(N)
    toArray() O(N)
    clear() O(1)
    equals(list, comparator) O(N)
    filter(callback) O(N)
    map(callback) O(N)
    reduce(callback, init) O(N)

    Binary Search Tree

    Binary search tree represents an important data structure when it comes to more complex work with sorted data, and fast search for specific elements in a collection. Fast and easy alternative to BST are Hash Sets ('Set' objects in ES6) or Hash Tables, which in JavaScript can be represented by Object or Map (ES6). Hash structures provide fast (O(1)) access to an element by its key. But any kind of additional logic over element keys (e.g. get minimum or maximum) leads to O(N) complexity. Also sorted array can be used instead of BST, but in case of frequent add/remove, preserving array to be sorted can be expensive. Therefore Balanced BST is competitive data structure if you want to:

    • Work with a dynamic sorted collection
    • Perform sorted traversal
    • Count number of elements less or greater than a value, or inside range
    • Traverse elements less or greater than a value, or inside range
    • Find next closest element
    • Find minimum or maximum

    This BST is realized implementing Red-Black algorithm to maintain tree balance for optimal access time.

    Object creation

    You can create new BST object in several different ways:

    1. Create new empty tree object
        const tree = new Bst();
    1. From simple array; key and value will be the same here:
        const tree = new Bst([1, 2, 3, 4, 5]);
    1. From array of objects with key/value properties:
        const tree = new Bst([{ key: 'a', value: 1 }, { key: 'b', value: 2 }, { key: 'c', value: 3} ]);
    1. From aray of objects with specified key predicate; whole object will be node value:
        let bstConstruct = {
            data: [
                { name: 'John', position: 'developer' }, 
                { name: 'Anna', position: 'manager' }
            ],
            keyPredicate: el => el.name
        };
        const tree = new Bst(bstConstruct);

    Additionally BST can be constructed with compareFunc attribute provided, which will be used as comparator function. This function should take two objects as arguments (a, b) and returns: -1 when a < b, 0 when a === b and 1 when a > b. It's used in case of complex keys which cannot be compared using built-in operators (<, ===, >). For performance reason, always consider generating keys which can be compared using regular operators.

        const tree = new Bst([], (el1, el2) => {
            if (el1.key.last > el2.key.last) {
                return 1;
            } else if (el1.key.last < el2.key.last) {
                return -1;
            } else {
                if (el1.key.first > el2.key.first) {
                    return 1;
                } else if (el1.key.first < el2.key.first) {
                    return -1
                } else {
                    return 0;
                }
            }
        });

    BST Node objects

    BST contains Node objects, which have next properties:

    key
    value
    left - reference to left child
    right - reference to right child
    count - number of elements in subtree (including itself)
    

    BST Properties & Methods:

    Property / Method Time complexity
    put(key, val) O(log(N))
    delete(key) O(log(N))
    getValue(key) O(log(N))
    min() O(log(N))
    max() O(log(N))
    floor(x) O(log(N))
    ceiling(x) O(log(N))
    iterate(callback, traversalType) O(N)
    iterateRange(from, to, callback, opt) O(N)
    countLess(x) O(log(N))
    countLessOrEqual(x) O(log(N))
    countGreater(x) O(log(N))
    countGreaterOrEqual(x) O(log(N))
    countRange(from, to, opt) O(log(N))
    toValueArray() O(N)
    toKeyArray() O(N)
    toArray() O(N)
    clear() O(1)
    filter(predicateFunc) O(N)
    map(callback) O(N)
    reduce(callback, init) O(N)

    Install

    npm i fast-data-structures

    DownloadsWeekly Downloads

    3

    Version

    0.0.5

    License

    MIT

    Last publish

    Collaborators

    • radiconi