Javascript implementation of the main data structures. Each data structure object is constructed using a factory function that holds the data structure name.

Install

npm install datastructures-js

Usage

let ds = require('datastructures-js');

Data Structures

• Stack
• Queue
• Priority Queue
• Set
• Linked List
• Doubly Linked List
• Binary Search Tree
• AVL Tree
• Min Heap Tree
• Max Heap Tree
• Trie
• Graph
• Directed Graph

Contribution & License

• Contribution
• License

Stack

elements data type: any type.

construction

let stack = ds.stack();

.push(element)

push an element to the top of the stack.

stack.push('test');

.peek()

returns the top element in the stack.

console.log(stack.peek()); // test

.pop()

pops the top element of the stack.

console.log(stack.pop()); // test
console.log(stack.peek()); // null

.isEmpty()

checks if the stack is empty.

console.log(stack.isEmpty()); // true

.length()

returns the length length of the stack.

console.log(stack.length()); // 0

Queue

elements data type: any type.

construction

let queue = ds.queue();

// OR

let queue = ds.q();

.enqueue(element)

adds an element to the back of the queue.

queue.enqueue(10);
queue.enqueue(20);

.front()

returns the front element in queue.

console.log(queue.front()); // 10

.back()

returns the back element in the queue.

console.log(queue.back()); // 20

.dequeue()

dequeues an element from the queue.

console.log(queue.dequeue()); // 10
console.log(queue.front()); // 20

.isEmpty()

checks if the queue is empty.

console.log(queue.isEmpty()); // false

.length()

returns the length of the queue

console.log(queue.length()); // 1

.toArray()

converts the queue to an array with front starting at 0

queue.enqueue(1);
queue.enqueue(4);
queue.enqueue(2);
console.log(queue.toArray()); // [1, 4, 2]

.clear()

clears the queue

queue.clear();
queue.length(); // 0

PriorityQueue

elements data type: any type.

construction

let pQueue = ds.priorityQueue();

// OR

let pQueue = ds.pq();

.enqueue(element, priority)

adds an element with priority (number) to the back of the queue.

pQueue.enqueue('patient 1', 2); // lower priority
pQueue.enqueue('patient 2', 1); // higher priority

.front()

returns the front element in queue.

console.log(pQueue.front()); // patient 1

.back()

returns the back element in the queue.

console.log(pQueue.back()); // patient 3

.dequeue()

dequeues the highest priority element from the queue.

console.log(pQueue.dequeue()); // patient 2
console.log(pQueue.front()); // patient 1

.isEmpty()

checks if the queue is empty.

console.log(queue.isEmpty()); // false

.length()

returns the length of the queue.

console.log(queue.length()); // 1

converts the queue to an array in the order elements were queued

queue.enqueue('test 1', 2);
queue.enqueue('test 2', 3);
queue.enqueue('test 3', 1);
console.log(queue.toArray()); // ['test 1', 'test 2', 'test 3']

.clear()

clears the queue

queue.clear();
console.log(queue.length()); // 0

Set

elements data type: number, string, boolean, null, undefined.

construction

let set = ds.set();

.add(element)

adds an element to the set.

set.add('A');
set.add('B');
set.add('C');
set.add('D');

.isEmpty()

checks if the set is empty.

console.log(set.isEmpty()); // false

.contains(element)

checks if the set contains an element

console.log(set.contains('C')); // true

.remove(element)

removes an element from the set.

set.remove('C');
console.log(set.contains('C')); // false

.size()

returns the number of elements in the set.

console.log(set.size()); // 3

.union(set)

unions the set with another set and returns the resulting set.

let set2 = ds.set();
set2.add('A');
set2.add('E');
set2.add('F');
let unionSet = set.union(set2); // unionSet contains A, B, D, E, F

.intersect(set)

intersects the set with another set and returns the resulting set.

let set2 = ds.set();
set2.add('A');
set2.add('E');
set2.add('F');
// set contains A, B, D
let intersectSet = set.intersect(set2); // intersectSet contains A

.diff(set)

returns the diff set between the set and another set.

let set2 = ds.set();
set2.add('A');
set2.add('E');
set2.add('F');
// set contains A, B, D
let diffSet = set.diff(set2); // diffSet contains B, D

.isSubset(set)

checks if the set is a subset of another set

let s1 = ds.set();
s1.add('B');
s1.add('G');
s1.add('D');

let s2 = ds.set();
s2.add('A');
s2.add('G');
s2.add('B');
s2.add('G');
s2.add('D');

console.log(s2.isSubset(s1)); // false
console.log(s1.isSubset(s2)); // true

.toArray()

converts the set into an array.

console.log(set.toArray()); // ['A', 'B', 'D']

.clear()

clears the set

set.clear(); // set is empty
console.log(set.size()); // 0  

LinkedList

node value data type: number, string, boolean, null, undefined.

construction

let linkedList = ds.linkedList();

// OR

let linkedList = ds.ll();

.addFirst(value)

add a node with the specified value to the beginning of the list.

linkedList.addFirst('n1');

.addLast(value)

add a node with the specified value to the end of the list.

linkedList.addLast('n4');

.addAfter(value, newValue)

add a node with newValue after an existing value's node, throws exception if value doesnt exist.

try {
    linkedList.addAfter('n1', 'n2');
    linkedList.addAfter('n33', 'n3');
}
catch (e) {
    console.log(e.message); // node n33 not found
}

.addBefore(value, newValue)

add a node with newValue before an existing value's node, throws exception if value doesnt exist.

try {
  linkedList.addBefore('n4', 'n3');
  linkedList.addBefore('n33', 'n3');
}
catch (e) {
  console.log(e.message); // node n33 not found
}

.find(value)

returns a linkedListNode object that contains two functions:

• .getNext() returns the next linkedListNode object.
• .getValue() returns the node value.

let n3 = linkedList.find('n3');
console.log(n3.getValue()); // n3
console.log(n3.getNext().getValue()); // n4

.head()

returns the first linkedListNode object in the list.

let head = linkedList.head();
console.log(head.getValue()); // n1

.traverse(cb)

traverse the linked list and calls cb for each node

linkedList.traverse((value) => { console.log(value); });
// n1
// n2   
// n3
// n4

.remove(value)

remove the value's node from the list or throw an exception if value not found.

linkedList.remove('n3');

.removeFirst()

removes the first node in the list.

linkedList.removeFirst(); // n1 removed

.removeLast()

removes the last node in the list.

linkedList.removeLast(); // n4 removed

.length()

returns the number of nodes in the list.

console.log(linkedList.count()); // 1

.clear()

removes all the nodes from the list.

linkedList.clear();
console.log(linkedList.length()); // 0	

DoublyLinkedList

node value data type: number, string, boolean, null, undefined.

construction

let dList = ds.doublyLinkedList();

// OR

let dList = ds.dll();

.addFirst(value)

add a node with the specified value to the beginning of the list.

dList.addFirst('n1');

.addLast(value)

add a node with the specified value to the end of the list.

dList.addLast('n4');

.addAfter(value, newValue)

add a node with newValue after an existing value's node, throws exception if value doesnt exist.

try {
  dList.addAfter('n1', 'n2');
  dList.addAfter('n33', 'n2');
}
catch (e) {
  console.log(e.message); // node n33 not found
}

.addBefore(value, newValue)

add a node with newValue before an existing value's node, throws exception if value doesnt exist.

try {
  dList.addBefore('n4', 'n3');
  dList.addBefore('n33', 'n2');
}
catch (e) {
  console.log(e.message); // node n33 not found
}

.find(value)

returns a doublyLinkedListNode object that contains three functions:

• .getNext() returns the next doublyLinkedListNode object.
• .getPrev() returns the previous doublyLinkedListNode object.
• .getValue() returns the node's value.

let n3 = dList.find('n3');
console.log(n3.getValue()); // n3
console.log(n3.getNext().getValue()); // n4
console.log(n3.getPrev().getValue()); // n2

.head()

returns the first doublyLinkedListNode object in the list.

let head = dList.head();
console.log(head.getValue()); // n1

.tail()

returns the last doublyLinkedListNode object in the list.

let tail = dList.tail();
console.log(tail.getValue()); // n4

.removeFirst()

removes the first node from the list.

dList.removeFirst();

.removeLast()

removes the last node from the list.

dList.removeLast();

.remove(value)

remove the value's node from the list.

dList.remove('n2');

.length()

returns the number of nodes in the list.

let length = dList.length();

.clear()

clears all the nodes from the list.

dList.clear();
console.log(dList.length()); // 0  

BinarySearchTree

node value data type: string, number

construction

let bst = ds.binarySearchTree();

// OR

let bst = ds.bst();

.insert(value)

inserts a node with the specified value into the tree.

bst.insert(50);
bst.insert(80);
bst.insert(30);
bst.insert(90);
bst.insert(60);
bst.insert(40);
bst.insert(20);

.root()

returns the root node

console.log(bst.root().getValue()); // 90

.min()

returns the min value binaryNode object (most left node value).

console.log(bst.min().getValue()); // 20

.max()

returns the max value binaryNode object (most right node value).

console.log(bst.max().getValue()); // 90

.count()

returns number of nodes in the tree

console.log(bst.count()); // 7

.find(value)

returns a binaryNode object that contains three functions:

• .getRight() returns the right child binaryNode node object.
• .getLeft() returns the left child binaryNode node object.
• .getValue() returns the node value.

let n = bst.find(30);
console.log(n.getValue()); // 30
console.log(n.getRight().getValue()); // 40
console.log(n.getLeft().getValue()); // 20

.traverse(cb, order)

traverse the tree in the defined order and apply a callback on each node.

• order: 'inOrder' OR 'preOrder' OR 'postOrder'. default is 'inOrder'

// inOrder traverse
bst.traverse((value) => { console.log(value); });

// 20
// 30
// 40
// 50
// 60
// 80
// 90

// preOrder traverse
bst.traverse((value) => { console.log(value) }, 'preOrder');

// 50
// 30
// 20
// 40
// 80
// 60
// 90

// postOrder traverse
bst.traverse((value) => { console.log(value) }, 'postOrder');

// 20
// 40
// 30
// 60
// 90
// 80
// 50

.remove(value)

removes a value's node (if exists) from the tree.

bst.remove(30);
let n50 = bst.find(50);
let n40 = bst.find(40);
console.log(n50.getLeft().getValue()); // 40
console.log(n40.getLeft().getValue()); // 20

.clear()

clears all the nodes from the tree.

bst.clear();
console.log(bst.count()); // 0

AvlTree

construction

let avlTree = ds.avlTree();

// OR

let avlTree = ds.avl();

Implements the same exact BinarySearchTree interface except that it maintains the tree balance automatically upon insertion and deletion.

MinHeap

node value data type: string, number

construction

let minHeap = ds.minHeap();

.insert(value)

inserts a value into the heap.

minHeap.insert(50);
minHeap.insert(80);
minHeap.insert(30);
minHeap.insert(90);
minHeap.insert(60);
minHeap.insert(40);
minHeap.insert(20);

.size()

retrieves the size of the heap

console.log(minHeap.size()); // 7

.min()

retrieves the min value in the heap

console.log(minHeap.min()); // 20

.extractMin()

retrieves and remove the min value from the heap

console.log(minHeap.extractMin()); // 20
console.log(minHeap.min()); // 30

.remove(index)

removes a value at a specific index from the heap

minHeap.remove(3); // removed 90
console.log(minHeap.size()); // 5

.clear()

clears the heap

minHeap.clear();
console.log(minHeap.size()); // 0

MaxHeap

node value data type: string, number

construction

let maxHeap = ds.maxHeap();

.insert(value)

inserts a value into the heap.

maxHeap.insert(50);
maxHeap.insert(80);
maxHeap.insert(30);
maxHeap.insert(90);
maxHeap.insert(60);
maxHeap.insert(40);
maxHeap.insert(20);

.max()

retrieves the max value in the heap

console.log(maxHeap.max()); // 90

.extractMax()

retrieves and remove the max value from the heap

console.log(maxHeap.extractMax()); // 90
console.log(maxHeap.max()); // 80

.remove(index)

removes a value at a specific index from the heap

maxHeap.remove(3); // removed 50
console.log(maxHeap.size()); // 5

.clear()

clears the heap

maxHeap.clear();
console.log(maxHeap.size()); // 0

Trie

construction

let trie = ds.trie();

.insert(word)

inserts a word into the trie

trie.insert('hi');
trie.insert('hit');
trie.insert('hide');
trie.insert('hello');
trie.insert('sand');
trie.insert('safe');
trie.insert('noun');
trie.insert('name');

.search(word)

searches a word in the trie and returns the last char node

returned node is of the type TrieNode or null if word is not found

let node1 = trie.search('hi');

console.log(node1.getChar()); // i

let node2 = trie.search('abc');

console.log(node2); // null

.traverse(cb)

traverse the trie and calls cb for each found word

trie.traverse((word) => console.log(word));

// hi
// hit
// hide
// hello
// sand
// safe
// noun
// name

.remove(word)

removes a word from the trie

trie.remove('hit');

console.log(trie.search('hit')); // null

.countNodes()

gets the count of the characters nodes in the trie

console.log(trie.countNodes()); // 22

.countWords()

gets the count of the words in the trie

console.log(trie.countWords()); // 7

.clear()

clears the trie

trie.clear();
console.log(trie.countNodes()); // 1 (root node is a default)
console.log(trie.countWords()); // 0

Graph

vertex data type: string, number, boolean, null, undefined

construction

let graph = ds.graph();

// OR

let graph = ds.g();

.addVertex(vertex)

adds a vertex to the graph.

graph.addVertex('test');

.hasVertex(vertex)

checks if the graph has a vertex

let check = graph.hasVertex('test'); // true

.removeVertex(vertex)

checks if the graph has a vertex

graph.removeVertex('test');
graph.hasVertex('test'); // false

.addEdge(v1, v2, weight)

adds a weighted edge between two existing vertices.

graph.addVertex('v1');
graph.addVertex('v2');
graph.addEdge('v1', 'v2', 3)

.hasEdge(v1, v2)

checks if the graph has an edge between two exsiting vertices

let check = graph.hasEdge('v1', 'v2'); // true

.getWeight(v1, v2)

returns the weight between two vertices

let w = graph.getWeight('v1', 'v2'); // 3

.removeEdge(v1, v2)

removes an existing edge in the graph

graph.removeEdge('v1', 'v2');
graph.hasEdge('v1', 'v2'); // false
graph.hasEdge('v2', 'v1'); // false

.addPath(v1, v2, weight)

adds an edge between two vertices and creates the vertices if one or both dont exist.

// building the diagram graph
graph.addPath('v1', 'v2', 2);
graph.addPath('v2', 'v3', 3);
graph.addPath('v1', 'v3', 6);
graph.addPath('v2', 'v4', 1);
graph.addPath('v4', 'v3', 1);
graph.addPath('v4', 'v5', 4);
graph.addPath('v3', 'v5', 2);

.countVertices()

returns the number of vertices in the graph.

let count = graph.countVertices(); // 5

.traverse(vertex, cb, type)

traverse the graph.

• type: 'bfs' OR 'dfs' (breadth-first search or depth-first search). default is 'bfs'

// bfs traverse
graph.traverse('v5', (v) => console.log(v), 'bfs');
// v5
// v4
// v3
// v2
// v1

// dfs traverse
graph.traverse('v1', (v) => console.log(v), 'dfs');
// v1
// v2
// v3
// v4
// v5

.findShortestPath(v1, v2)

find all possible shortests paths between two vertices in the graph

let shortestPath = graph.findShortestPath('v1', 'v5'); // [ ['v1', 'v2', 'v4', 'v3', 'v5'] ]

.clear()

clears all the nodes from the graph.

graph.clear();

DirectedGraph

construction

let dgraph = ds.directedGraph();

// OR

let dgraph = ds.dg();

.addVertex(vertex)

adds a vertex to the graph.

dgraph.addVertex('test');

.hasVertex(vertex)

checks if the graph has a vertex

let check = dgraph.hasVertex('test'); // true

.removeVertex(vertex)

checks if the graph has a vertex

dgraph.removeVertex('test');
dgraph.hasVertex('test'); // false

.addEdge(v1, v2, weight)

adds a weighted direction from v1 to v2

dgraph.addVertex('v1');
dgraph.addVertex('v2');
dgraph.addEdge('v1', 'v2', 3);

.hasEdge(v1, v2)

checks if the graph has a direction from v1 to v2

let check1 = dgraph.hasEdge('v1', 'v2'); // true
let check2 = dgraph.hasEdge('v2', 'v1'); // false

.getWeight(v1, v2)

returns the weight from v1 to v2

let w = dgraph.getWeight('v1', 'v2'); // 3

.removeEdge(v1, v2)

removes the direction from v1 to v2

dgraph.removeEdge('v1', 'v2');
dgraph.hasEdge('v1', 'v2'); // false

.addPath(v1, v2, weight)

adds a direction from v1 to v2 and creates both vertices if not exist

// build the diagram dgraph
dgraph.addPath('v1', 'v2', 2);
dgraph.addPath('v1', 'v3', 3);
dgraph.addPath('v1', 'v4', 1);
dgraph.addPath('v2', 'v4', 1);
dgraph.addPath('v3', 'v5', 2);
dgraph.addPath('v4', 'v3', 1);
dgraph.addPath('v4', 'v5', 4);

.countVertices()

returns the number of vertices in the graph.

let count = dgraph.countVertices(); // 5

.traverse(vertex, cb, type)

traverse the graph.

• type: 'bfs' OR 'dfs' (breadth-first search or depth-first search). default is 'bfs'

// bfs traverse
dgraph.traverse('v1', (v) => console.log(v), 'bfs');
// v1
// v2
// v3
// v4
// v5

// dfs traverse
dgraph.traverse('v5', (v) => console.log(v), 'dfs');
// v1
// v2
// v4
// v3
// v5

.findShortestPath(v1, v2)

find all possible shortests paths between two vertices in the graph

let shortestPath = dgraph.findShortestPath('v1', 'v5'); // [ ['v1', 'v4', 'v3', 'v5'] ]

.clear()

clears all the nodes from the graph.

dgraph.clear();

---

Contribution

Fork and then clone the repo:

git clone https://github.com/[your-username]/datastructures-js

Install grunt-cli

npm install -g grunt-cli

install dependencies

npm install

Create a branch from development branch with a name indicatig the fix/feature

git checkout -b fix-branch

run all tasks

grunt build

to run lint only

grunt lint

to run tests only

grunt test

to run test coverage only

grunt coverage

when everything is OK, push the changes to the same branch

git push origin fix-branch

and create a pull request from development branch.

Changes are reviewed and merged if all is ok.

Thanks.

License

The MIT License. Full License is here