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);
bst.add(10);
bst.add(5);
console.log(bst.isPresent(5));
console.log(bst.isPresent(10));
console.log(bst.isBalanced());
Your actual tree state:
10
/
5
bst.add(13);
Your actual tree state:
10
/ \
5 13
console.log(bst.isBalanced());
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());
console.log(bst.findMax());
console.log(bst.inOrder());
console.log(bst.preOrder());
console.log(bst.postOrder());
console.log(bst.layers());
console.log(bst.elementDepth(10));
console.log(bst.elementDepth(42));
console.log(bst.elementHeight(10));
console.log(bst.elementHeight(42));
console.log(bst.layers());
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);
linked.add(10);
linked.add(5);
linked.add(3);
console.log(linked.size);
linked.addAt(1, 7);
console.log(linked.dataAt(1));
console.log(linked.indexOf(7));
linked.remove(3);
console.log(linked.dataAt(2));
console.log(linked.indexOf(3));
linked.add(3);
linked.removeAt(1);
console.log(linked.dataAt(1));
console.log(linked.indexOf(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) |
Stack
import { Stack } from 'icollections';
let stack = new Stack();
console.log(stack.size);
stack.push(10);
stack.push(5);
stack.push(7);
console.log(stack.size);
console.log(stack.peek);
stack.pop();
console.log(stack.size);
console.log(stack.peek);
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);
queue.enqueue('a');
queue.enqueue('b');
queue.enqueue('c');
console.log(queue.isEmpty);
console.log(queue.size);
console.log(queue.front);
console.log(queue.dequeue());
console.log(queue.size);
console.log(queue.front);
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);
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);
queue.dequeue();
console.log(queue.front);
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)
set.add("a");
set.add("b");
console.log(set.size)
console.log(set.has("a")
console.log(set.has("b"))
console.log(set.values)
set.remove("a");
console.log(set.size).toBe(1);
console.log(set.has("a"))
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)
console.log(intersectSet.values)
var diffSet = setA.difference(setB);
console.log(diffSet.size)
console.log(diffSet.values)
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))
Map
import { Map } from 'icollections';
var map = new Map();
console.log(map.size);
map.set('arms', 2);
map.set('fingers', 10);
map.set('eyes', 2);
map.set('belley button', 1);
console.log(map.size);
let obj = { name: 'languange' };
map.set(obj, 'JavaScript');
console.log(map.has(obj));
console.log(map.has({ name: 'languange' }));
console.log(map.get(obj));
console.log(map.has('arms'));
console.log(map.get('arms'));
console.log(map.values);
map.delete('eyes');
console.log(map.has('eyes'));
map.clear();
console.log(map.size);
Hash Tables
import { HashTable } from 'icollections';
var hashTable = new HashTable(14);
console.log(hashTable.storageLimit);
hashTable.add('beau', 'person');
console.log(hashTable.lookup('beau'));
hashTable.remove('beau');
expect(hashTable.lookup('beau'));
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