Data Structures in Javascript

Background

There are neither a lot of resources on internet nor any book which guides and dictates best practices in the implementation of popular Data Structures using Javascript. The purpose of this library is to provide cooked implementation of populare data structures in javascript.

Installation

npm - npm install es6-data-structures

Getting hands dirty

Clone the repo git clone https://github.com/linux-nerd/data-structures.js.git

Install the dependencies npm install

Run dev build npm run dev

To execute unit test cases npm test

Trigger production build npm run build

List of Data Structures

Data structures covered so far -

• Binary Search Tree
• Graph
• Queue

Contribution

Your contribution is highly appreciated. You can contribute in several ways -

• Opening an issue in the tracker
• Updating and adding documentaion
• Adding new features
• Adding demo

Vision

Once development is complete. This library will work in -

• All supported Browsers
• Node

and can be written in -

• es5
• es6
• typescript

and will be published in

• npm
• bower

Binary Search Tree

Import BST class and instantiate it

import { BST } from 'es6-data-structures/lib/ds';
const bst = new BST

Insert values in binary search Tree

bst.insert(5);
bst.insert(20);
bst.insert(10);

Find size of the binary search tree

bst.len() // 3

Find an item in the binary search tree

bst.lookup(10) // returns an object with keys hasVal, currentNode and parentNode

Height of the binary search tree or a node

bst.height() //gives height of the BST 1
bst.height(bst.lookup(10).currentNode) // gives the height of the node - 0

Traverse the BST and return a List

bst.traverse('inOrder') // traverse method expects a parameter - inOrder|preOrder|postOrder| levelOrder

Delete elements from binary search tree

bst.delete(10);
bst.delete(20);

Graph

Import Graph class and instantiate it and create an object of adjacency list implementation of Graph. To create a directed graph pass the string argument 'directed'. If the Graph class is called without a parameter then by default its undirected graph.

import { Graph } from 'es6-data-structures/lib/ds';
const graph = new Graph; // this will create an undirected Graph
const graph = new Graph('directed'); // this will create a directed graph or diGraph

const adjList = graph.createGraph('adjList'); // create Adjacency List implementation of graph

Add and remove a node to the graph

// add a node
adjList.addNode('A');
adjList.addNode('B');

// remove a node
adjList.removeNode('A');
adjList.removeNode('B');

Add and remove an edge between two nodes to the graph. iF a node is not added, then it first adds the node and then create an edge.

// add an edge
adjList.addEdge('A', 'B', 200); // it will add an edge between A and B of weight 200
adjList.addEdge('B', 'C'); // it will first add node C and then create an edge b/w B and C

// remove an edge
adjList.removeEdge('A', 'B');
adjList.removeEdge('B', 'C');

Find size of the graph.

adjList.size // 3

Find weight of the edge in weighted graph

adjList.getEdgeWeight('A', 'B');

Queue

Import Queue class and create a queue object.

import { Queue } from 'es6-data-structures/lib/ds';
const queue = new Queue;

Add and remove elements to and from the created queue respectively

// add elements to the queue
queue.enqueue('A');
queue.enqueue(123);

// remove elements from the queue
queue.dequeue();
queue.dequeue();

Get size and top element in the queue

queue.size() // 2
queue.top() // A

Clear the entire queue at once

queue.clear() // this will empty the queue