ICollections

“Bad programmers worry about the code. Good programmers worry about data structures and their relationships.” — Linus Torvalds

This project has javascript implementation for some common data structures like:

• Linked List
• Queue
• Priority Queue
• Stack
• Maps
• Hash Table
• Binary Search Tree
• Set

Install

$ npm i icollections

Usage

Binary Search Tree

import { BST } from 'icollections';
 
var bst = new BST();
console.log(hashTable.storageLimit); // 14
 
bst.add(10);
bst.add(5);
console.log(bst.isPresent(5)); // true
console.log(bst.isPresent(10)); // true
console.log(bst.isBalanced()); // false

Your actual tree state:

    10
   /
  5

bst.add(13);

Your actual tree state:

      10
     /  \
    5    13

console.log(bst.isBalanced()); // true
 
bst.add(2);
bst.add(133);
bst.add(42);
bst.add(12);

Your actual tree state:

      10
     /  \
    5    13
   /	/  \
  2    12    133
            /
           42

bst.invert())

Your actual tree state:

        10
       /  \
     13    5
    /  \    \
  133  12    2
    \
     42

console.log(bst.findMin()); // 2
console.log(bst.findMax()); // 133
console.log(bst.inOrder()); //[2,5,10,12,13,42,133]
console.log(bst.preOrder()); //[10,5,2,13,12,133,42]
console.log(bst.postOrder()); //[2,5,12,42,133,13,10]
console.log(bst.layers()); //[10, 5, 13, 2, 12, 133, 42]
console.log(bst.elementDepth(10)); // 0
console.log(bst.elementDepth(42)); // 3
console.log(bst.elementHeight(10)); // 3
console.log(bst.elementHeight(42)); // 0
console.log(bst.layers()); //[10, 5, 13, 2, 12, 133, 42]

Algorithm	Average	Worst Case
Space	O(n)	O(n)
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)

Linked Lists

import { LinkedList } from 'icollections';
 
var linked = new LinkedList();
console.log(linked.size); // 0
 
linked.add(10);
linked.add(5);
linked.add(3);
console.log(linked.size); // 3
 
linked.addAt(1, 7);
console.log(linked.dataAt(1)); // 7
console.log(linked.indexOf(7)); // 1
 
linked.remove(3);
 
console.log(linked.dataAt(2)); // -1
console.log(linked.indexOf(3)); // -1
 
linked.add(3);
linked.removeAt(1);
console.log(linked.dataAt(1)); // 3
console.log(linked.indexOf(5)); // -1

Algorithm	Average	Worst Case
Space	O(n)	O(n)
Search	O(n)	O(n)
Insert	O(1)	O(1)
Delete	O(1)	O(1)

Stack

import { Stack } from 'icollections';
 
let stack = new Stack();
console.log(stack.size); // 0
 
stack.push(10);
stack.push(5);
stack.push(7);
console.log(stack.size); // 3
console.log(stack.peek); // 7
 
stack.pop();
console.log(stack.size); // 2
console.log(stack.peek); // 5

Algorithm	Average	Worst Case
Space	O(n)	O(n)
Search	O(n)	O(n)
Insert	O(1)	O(1)
Delete	O(1)	O(1)

Queue

import { Queue } from 'icollections';
 
const queue = new Queue();
console.log(queue.size); // 0
 
queue.enqueue('a');
queue.enqueue('b');
queue.enqueue('c');
 
console.log(queue.isEmpty); // false
console.log(queue.size); // 3
console.log(queue.front); // 'a'
console.log(queue.dequeue()); // 'a'
console.log(queue.size); // 2
console.log(queue.front); // 'b'

Algorithm	Average	Worst Case
Space	O(n)	O(n)
Search	O(n)	O(n)
Insert	O(1)	O(1)
Delete	O(1)	O(1)

Priority Queue

import { PriorityQueue } from 'icollections';
 
const queue = new PriorityQueue();
console.log(queue.size); // 0
 
queue.enqueue(['I am last one', 4]);
queue.enqueue(['Just the third', 3]);
queue.enqueue(['Almost', 2]);
queue.enqueue(['FIRST ONE, WINNER', 1]);
 
console.log(queue.front); // ['FIRST ONE, WINNER', 1])
 
queue.dequeue();
 
console.log(queue.front); // ['Almost', 2]

Algorithm	Average	Worst Case
Space	O(n)	O(n)
Search	O(n)	O(n)
Insert	O(1)	O(1)
Delete	O(1)	O(1)

Set

    import { Set } from 'icollections';
 
    const set = new Set();
    console.log(set.size) // 0
 
    set.add("a");
    set.add("b");
 
    console.log(set.size) // 2
    console.log(set.has("a") // true
    console.log(set.has("b")) // true
    console.log(set.values) // ["a", "b"]
 
    set.remove("a");
    console.log(set.size).toBe(1);
    console.log(set.has("a")) // false
 
    var setA = new Set();
    var setB = new Set();
 
    setA.add("a");
    setA.add("b");
    setA.add("c");
    setB.add("a");
    setB.add("c");
    setB.add("z");
 
    var intersectSet = setA.intersection(setB);
 
    console.log(intersectSet.size) // 2
    console.log(intersectSet.values) // ["a", "c"]
 
    var diffSet = setA.difference(setB);
 
    console.log(diffSet.size) // 1
    console.log(diffSet.values) // ["b"]
 
 
    var setA = new Set();
    var setB = new Set();
 
    setA.add("a");
    setA.add("b");
    setA.add("c");
    setA.add("d");
 
    setB.add("a");
    setB.add("b");
 
    console.log(setB.subset(setA)) // true

Map

import { Map } from 'icollections';
 
var map = new Map();
console.log(map.size); // 0
 
map.set('arms', 2);
map.set('fingers', 10);
map.set('eyes', 2);
map.set('belley button', 1);
 
console.log(map.size); // 4
 
let obj = { name: 'languange' };
map.set(obj, 'JavaScript');
 
console.log(map.has(obj)); // true
console.log(map.has({ name: 'languange' })); // true
console.log(map.get(obj)); // 'JavaScript'
console.log(map.has('arms')); // true
console.log(map.get('arms')); // 2
 
console.log(map.values); // [2,10,2,1]
 
map.delete('eyes');
console.log(map.has('eyes')); // false
 
map.clear();
console.log(map.size); // 0

Hash Tables

import { HashTable } from 'icollections';
 
var hashTable = new HashTable(14);
console.log(hashTable.storageLimit); // 14
 
hashTable.add('beau', 'person');
 
console.log(hashTable.lookup('beau')); // 'person'
 
hashTable.remove('beau');
expect(hashTable.lookup('beau')); // undefined

Algorithm	Average	Worst Case
Space	O(n)	O(n)
Search	O(1)	O(n)
Insert	O(1)	O(n)
Delete	O(1)	O(n)

---

Contributing

$ git clone https://github.com/assuncaocharles/javascript_DataStructure

cd javascript_DataStructure

npm i

Running test

npm run test

---

To do

• Graph
• Binary Heap