JS-DSA
JS-DSA(adv-dsa) is an open-source JavaScript library and NPM package that provides a comprehensive collection of data structures and algorithms for software developers and computer science enthusiasts. This library is designed to be versatile, efficient, and easy to use, offering a wide range of implementations for various programming needs. Pabitra Banerjee is the developer and maintainer of this NPM Package.
Contents
Installation
You can install JS-DSA using either npm or yarn. First, clone the repository to your local machine:
git clone https://github.com/pb2204/JS-DSA.git
cd JS-DSA
Using npm
npm install adv-dsa
Using yarn
yarn add adv-dsa
Data Structures
The data-structures folder within the Advanced Data Structures and Algorithms (adv-dsa) project hosts a diverse collection of essential data structures, each encapsulated in its respective module. Organized systematically, this folder encompasses various types of linked lists (singly, doubly, circular), stacks, queues, hash tables, sets, maps, trees (binary, AVL, Red-Black), heaps (min, max), graphs, disjoint sets, trie, and more. Each data structure module is thoughtfully designed to optimize performance and facilitate seamless integration into JavaScript projects. This modular approach enhances code readability and enables developers to choose and implement the most suitable data structures for their specific needs.
Linked Lists
The linked-lists module within the Advanced Data Structures and Algorithms (adv-dsa) project offers a comprehensive suite of linked list implementations. These include the basic singly linked list (SinglyLinkedList.js), doubly linked list (DoublyLinkedList.js), and circular linked list (CircularLinkedList.js). Each linked list is designed to efficiently manage and organize data, providing flexibility in different scenarios. The singly linked list facilitates sequential data storage, the doubly linked list extends this by enabling bidirectional traversal, and the circular linked list forms a loop, allowing for continuous cyclic access. These linked list implementations serve as fundamental building blocks for more complex data structures and algorithms within the larger project, contributing to a well-rounded toolkit for JavaScript developers.
SinglyLinkedList.js
JS-DSA is a JavaScript package that provides a SinglyLinkedList
class, which implements a singly linked list data structure. A singly linked list is a linear data structure where each element (node) points to the next element in the list.
Creating a SinglyLinkedList
To use the SinglyLinkedList
class, first, import it into your JavaScript code:
const SinglyLinkedList = require('adv-dsa'); // Initialize a SinglyLinkedList instance const list = new SinglyLinkedList();
Appending Elements
You can append elements to the singly linked list using the append
method. This method adds elements to the end of the list:
list.append(1); list.append(2); list.append(3);
Displaying the Linked List
To display the elements in the singly linked list, use the display
method. This method returns an array containing the elements in the list:
const elements = list.display(); // Returns [1, 2, 3]
DoublyLinkedList.js
JS-DSA is a JavaScript package that provides a DoublyLinkedList
class, which implements a doubly linked list data structure. A doubly linked list is a type of linked list where each node has both a reference to the next node and a reference to the previous node.
Creating a DoublyLinkedList
To use the DoublyLinkedList
class, first, import it into your JavaScript code:
const DoublyLinkedList = require('adv-dsa'); // Initialize a DoublyLinkedList instance const list = new DoublyLinkedList();
Appending Elements
You can append elements to the doubly linked list using the append
method. This method adds elements to the end of the list and maintains both the forward and backward references:
list.append(1); list.append(2); list.append(3);
Displaying the Linked List
To display the elements in the doubly linked list, you can use two methods:
Displaying Forward
Use the displayForward
method to display the linked list in the forward direction:
const forwardElements = list.displayForward(); // Returns [1, 2, 3]
Displaying Backward
Use the displayBackward
method to display the linked list in the reverse (backward) direction:
const backwardElements = list.displayBackward(); // Returns [3, 2, 1]
CircularLinkedList.js
JS-DSA is a JavaScript package that provides a CircularLinkedList
class, which implements a circular linked list data structure. A circular linked list is a type of linked list where the last node points back to the first node, creating a loop.
Creating a CircularLinkedList
To use the CircularLinkedList
class, first, import it into your JavaScript code:
const CircularLinkedList = require('adv-dsa'); // Initialize a CircularLinkedList instance const list = new CircularLinkedList();
Appending Elements
You can append elements to the circular linked list using the append
method. This method adds elements to the end of the list and maintains the circular structure:
list.append(1); list.append(2); list.append(3);
Displaying the Linked List
To display the elements in the circular linked list, use the display
method. This method returns an array containing the elements in the list, starting from the head node and following the circular references:
const elements = list.display(); // Returns [1, 2, 3]
Stacks & Queues
Within the stacks-and-queues module of the Advanced Data Structures and Algorithms (adv-dsa) project, the Stack.js and Queue.js files encapsulate the implementation of two fundamental data structures—stacks and queues. The Stack.js file defines a class representing a stack, a Last-In-First-Out (LIFO) data structure, where elements are added and removed from the same end, typically referred to as the top. The stack supports essential operations such as push to add elements, pop to remove the top element, peek to inspect the top element without removal, and methods to check if the stack is empty and retrieve its size. Stacks find applications in various algorithms, such as expression evaluation and depth-first search.
On the other hand, the Queue.js file defines a class representing a queue, a First-In-First-Out (FIFO) data structure, where elements are added at the rear and removed from the front. The class provides methods like enqueue to add elements, dequeue to remove the front element, front to inspect the front element without removal, and functions to check if the queue is empty and retrieve its size. Queues are essential in scenarios like breadth-first search and task scheduling.
Together, these implementations in the stacks-and-queues module contribute to the foundational components required for various algorithmic and data manipulation tasks, offering developers versatile tools for managing and processing data in a structured manner.
Stack.js
The JavaScript Stack data structure is implemented in the Stack
class, which allows you to create a stack (LIFO) data structure. Here's how to use the Stack
class:
Example Usage
Creating a Stack
You can create a new Stack using the Stack
class:
const Stack = require('adv-dsa'); // Initialize a new stack const myStack = new Stack();
Adding Elements
You can add elements to the top of the stack using the push
method:
myStack.push(1); myStack.push(2); myStack.push(3); // The stack now contains [1, 2, 3]
Removing Elements
To remove and return the top element from the stack, use the pop
method:
const poppedElement = myStack.pop(); // Removes and returns 3
Checking the Top Element
You can check the top element of the stack without removing it using the peek
method:
const topElement = myStack.peek(); // Returns 2 (top element)
Checking If the Stack Is Empty
You can check if the stack is empty using the isEmpty
method:
const isEmpty = myStack.isEmpty(); // Returns false
Getting the Size of the Stack
You can get the number of elements in the stack using the size
method:
const stackSize = myStack.size(); // Returns 2
Queue.js
The JavaScript Queue data structure is implemented in the Queue
class, which allows you to create a queue (FIFO) data structure. Here's how to use the Queue
class:
Creating a Queue
You can create a new Queue using the Queue
class:
const Queue = require('adv-dsa'); // Initialize a new queue const myQueue = new Queue();
Adding Elements
You can add elements to the end of the queue using the enqueue
method:
myQueue.enqueue(1); myQueue.enqueue(2); myQueue.enqueue(3); // The queue now contains [1, 2, 3]
Removing Elements
To remove and return the front element from the queue, use the dequeue
method:
const dequeuedElement = myQueue.dequeue(); // Removes and returns 1
Checking the Front Element
You can check the front element of the queue without removing it using the front
method:
const frontElement = myQueue.front(); // Returns 2 (front element)
Checking If the Queue Is Empty
You can check if the queue is empty using the isEmpty
method:
const isEmpty = myQueue.isEmpty(); // Returns false
Getting the Size of the Queue
You can get the number of elements in the queue using the size
method:
const queueSize = myQueue.size(); // Returns 2
Hash Table
The hash-tables module within the Advanced Data Structures and Algorithms (adv-dsa) project contains the HashTable.js file, presenting the implementation of a hash table—a dynamic data structure that allows efficient insertion, deletion, and retrieval of key-value pairs. The hash table utilizes a hash function to map keys to specific indices, facilitating quick access to the associated values. The module aims to provide a scalable and performant solution for handling large datasets, ensuring constant-time average complexity for fundamental operations, such as insertion and retrieval, making it suitable for scenarios requiring fast key-based data access and manipulation.
JS-DSA is a JavaScript package that provides a HashTable
class. This class implements a basic hash table data structure, which allows you to store and retrieve key-value pairs efficiently. Hash tables are commonly used to store data with fast access times based on keys.
Creating a HashTable
To use the HashTable
class, first, import it into your JavaScript code:
const HashTable = require('adv-dsa'); // Initialize a HashTable instance with an optional size (default is 100) const table = new HashTable();
Inserting Key-Value Pairs
You can insert key-value pairs into the hash table using the insert
method:
table.insert('name', 'Alice'); table.insert('age', 30);
Retrieving Values
To retrieve the value associated with a key, use the get
method:
const name = table.get('name'); // Returns 'Alice' const age = table.get('age'); // Returns 30
Handling Key Collisions
The hash table handles key collisions by chaining, i.e., multiple key-value pairs with the same index are stored in a linked list:
table.insert('apple', 'fruit'); table.insert('apples', 'fruits'); table.insert('banana', 'yellow'); const apple = table.get('apple'); // Returns 'fruit' const apples = table.get('apples'); // Returns 'fruits' const banana = table.get('banana'); // Returns 'yellow'
Removing Key-Value Pairs
You can remove key-value pairs from the hash table using the remove
method:
table.remove('name');
Handling Nonexistent Keys
If you try to get a value for a key that does not exist, the get
method will return null
.
const nonexistent = table.get('nonexistent'); // Returns null
Sets & Maps
The sets-and-maps module in the Advanced Data Structures and Algorithms (adv-dsa) project encompasses the implementation of two essential data structures—sets and maps. The Set.js file defines a set, a collection of distinct elements with methods for adding, deleting, and checking the existence of elements. Similarly, the Map.js file provides a map, associating keys with values and supporting operations like insertion, retrieval, and deletion. These data structures are designed to efficiently manage unique elements and key-value pairs, offering versatile solutions for scenarios where unique identification or efficient data retrieval is crucial. The module emphasizes simplicity, performance, and versatility in handling data relationships.
Set.js
The JavaScript Set data structure is implemented in the Set
class, which allows you to store a collection of unique elements. In a Set, each element can occur only once. Here is how you can use the Set
class:
Creating a Set
You can create a new Set using the Set
class:
const Set = require('adv-dsa'); // Initialize a new set const mySet = new Set();
Adding Elements
You can add elements to the set using the add
method:
mySet.add(1); mySet.add(2); mySet.add(3); // The set now contains [1, 2, 3]
The add
method returns true
if the element was added and false
if the element is already in the set.
Checking for Element Existence
You can check if an element exists in the set using the has
method:
const hasOne = mySet.has(1); // Returns true const hasFour = mySet.has(4); // Returns false
Removing Elements
To remove an element from the set, use the delete
method:
mySet.delete(2); // Returns true, as 2 was removed mySet.delete(4); // Returns false, as 4 was not in the set
Getting All Elements
You can get an array of all elements in the set using the values
method:
const elements = mySet.values(); // Returns [1, 3]
Checking the Size of the Set
You can get the number of elements in the set using the size
method:
const setSize = mySet.size(); // Returns 2
Clearing the Set
To remove all elements from the set, use the clear
method:
mySet.clear(); // The set is now empty
Map.js
JS-DSA is a JavaScript package that provides a Map
class, which implements a simple key-value map (dictionary) data structure. A map is a collection of key-value pairs, where each key is unique.
Creating a Map
To use the Map
class, first, import it into your JavaScript code:
const Map = require('adv-dsa'); // Initialize a Map instance const map = new Map();
Setting Key-Value Pairs
You can add key-value pairs to the map using the set
method:
map.set('name', 'Alice'); map.set('age', 30);
Getting Values by Key
To retrieve values associated with keys, use the get
method. If a key doesn't exist, it returns undefined
:
const name = map.get('name'); // Returns 'Alice' const age = map.get('age'); // Returns 30
Checking Key Existence
You can check if a key exists in the map using the has
method:
const hasName = map.has('name'); // Returns true const hasEmail = map.has('email'); // Returns false
Deleting Key-Value Pairs
To remove a key-value pair from the map, use the delete
method:
map.delete('name'); map.delete('age');
Retrieving Keys and Values
The keys
and values
methods return arrays of all keys and values in the map, respectively:
const keys = map.keys(); // Returns ['age'] const values = map.values(); // Returns [30]
Checking the Size of the Map
You can get the number of key-value pairs in the map using the size
method:
const mapSize = map.size(); // Returns 1
Clearing the Map
To remove all key-value pairs from the map, use the clear
method:
map.clear();
References
External Links :: These links are added for reference purpose only, not for any advertising or promotion.
GitHub Repo[1] :: https://github.com/PB2204/JS-DSA/
NPM url[2] :: https://www.npmjs.com/package/adv-dsa- ↑ Banerjee, Pabitra (2023-11-11), JS-DSA :: JavaScript Data Structures and Algorithms, https://github.com/PB2204/JS-DSA, retrieved 2023-11-18
- ↑ "adv-dsa" (in en). 2023-10-16. https://www.npmjs.com/package/adv-dsa.