my-dsa

my-dsa is a JavaScript library that provides a collection of reusable data structures.

Table of Contents

• my-dsa
  • Table of Contents
  • Installation
  • LinkedList
  • Queue
  • Deque
  • Heap
  • DisjointSet
  • Trie
  • Quadtree
  • LRUCache
  • SegmentTree
  • Contributing

Installation

You can install using npm:

npm install my-dsa

or CDN:

https://cdn.jsdelivr.net/npm/my-dsa/dist/umd/index.js

The library will be accessible through the global name mydsa.

LinkedList

import { LinkedList } from "my-dsa";

let list = new LinkedList<number>();

// Or create a linked list from an array
list = LinkedList.fromArray([1, 2, 3]);

// Adds a node to the end of the list
let node = list.append(4);

// Adds a node to the start of the list
let node = list.prepend(4);

// Removes a node from the list
list.deleteNode(node);

// Adds a node after a specific node
let newNodeAfter = list.insertAfter(node, 5);

// Adds a node before a specific node
let newNodeBefore = list.insertBefore(node, 0);

// Finds a node by value
let foundNode = list.find(3);

// Clones the linked list
let clone = list.clone();

// Removes all nodes from the list
list.clear();

// Get the number of nodes in the list
let size = list.size();

// Check if the list is empty
let isEmpty = list.isEmpty();

// Convert the list to an array
let array = list.toArray();

// Get the head node
let headNode = list.head();

// Get the tail node
let tailNode = list.tail();

// Iterate through the linked list
for (let node of list) {
   console.log(node.value);
}

Queue

import { Queue } from "my-dsa";

let queue = new Queue<number>();

// Or create a queue like this:
queue = Queue.fromArray([1, 2, 3]);

// Adds an item in the back
queue.enqueue(2);

// Removes an item in front
let front = queue.dequeue();

// Get the size of the queue
let size = queue.size();

// Clears the queue
queue.clear(); 

// Check if queue is empty
let isEmpty = queue.isEmpty(); 

// Peek the front element
let front = queue.front();

// Peek the back element
let back = queue.back();

// Clones the queue
let clone = queue.clone();

// Convert the queue to array
let array = queue.toArray();

// Iterate through the queue
for (let item of queue) {
   console.log(item);
}

Deque

Deque or Double-Ended Queue is similar to queue except that you can add an element in front and dequeue from the back. It extends the Queue data structure.

import { Deque } from "my-dsa";

const deque = new Deque<number>();

// Adds an item in front
deque.enqueueFront(2);

// Removes an item in the back
deque.dequeueBack();

Heap

import { Heap } from "my-dsa";

let heap = new Heap<number>();

// Or create a heap with a custom comparator
heap = new Heap<number>((a, b) => b - a); // Max-heap

// Or create a heap from an array
heap = Heap.fromArray([4, 2, 7, 1]);

// Or create a max heap from an array
heap = Heap.fromArray([4, 2, 7, 1], (a, b) => b - a);

// Get the size of the heap
let size = heap.size();

// Check if the heap is empty
let isEmpty = heap.isEmpty();

// Peek at the top element
let top = heap.peek();

// Add elements to the heap
heap.push(5, 3, 8, 1);

// Remove the top element
let top = heap.pop();

// Clears the heap
heap.clear();

// Clone the heap
let clone = heap.clone();

// Convert the heap to an array
let array = heap.toArray();

DisjointSet

import { DisjointSet } from "my-dsa";

let ds = new DisjointSet<number>();

// Add nodes to the disjoint set
ds.add(1);
ds.add(2);
ds.add(3);

// Find the root of the set containing a node
let root = ds.find(2);

// Find or add a node to the disjoint set
let root = ds.findOrAdd(4);

// Union two sets containing the specified nodes
let isAlreadyUnified = ds.union(1, 3);

Trie

import { Trie } from "my-dsa";

// Create a new trie
let trie = new Trie();

// Insert words into the trie
trie.insert("apple");
trie.insert("app");

// Search for a word in the trie
let isFound = trie.search("app");

// Check if any word starts with the given prefix
let startsWith = trie.startsWith("ap");

// Delete a word from the trie
let isDeleted = trie.delete("apple");

// Get all words in the trie
let words = trie.getAllWords();

// Check if the trie is empty
let isEmpty = trie.isEmpty();

// Clear all words from the trie
trie.clear();

// Find the longest prefix of the given word that exists in the trie
let longestPrefix = trie.longestPrefixMatch("applepie");

// Autocomplete words with a given prefix
let suggestions = trie.autocomplete("app");

Quadtree

import { Quadtree } from "my-dsa";

// Create a new quadtree with specified bounds and configuration
let bounds = { x: 0, y: 0, width: 100, height: 100 };
let config = { maxDepth: 5 };
let quadtree = new Quadtree(bounds, config);

// Insert an item into the quadtree
let item = { x: 10, y: 10, width: 5, height: 5 };
quadtree.insert(item);

// Retrieve all objects within specified bounds
let searchBounds = { x: 5, y: 5, width: 20, height: 20 };
let retrievedItems = quadtree.retrieve(searchBounds);

LRUCache

LRUCache or Least-Recently-Used Cache acts exactly like a hashmap except that it removes entries that are least recently used when it hits the max capacity.

import { LRUCache } from "my-dsa";

// Create an LRUCache with a specific capacity
let cache = new LRUCache<string, number>(3);

// Adds a new element to the cache
cache.set("a", 1);
cache.set("b", 2);

// Retrieves a value from the cache by key
let value = cache.get("a");

// Check if a key exists in the cache
let exists = cache.has("b");

// Update an existing key with a new value
cache.set("a", 10);

// Deletes an element from the cache
let wasDeleted = cache.delete("a");

// Clear all elements from the cache
cache.clear();

// Get the current size of the cache
let size = cache.size();

// Support for-of iteration to loop over entries
for (let [key, value] of cache) {
    console.log(`${key}: ${value}`);
}

SegmentTree

import { SegmentTree } from "my-dsa";

// Create a SegmentTree (default query is sum)
let segTree = new SegmentTree([1, 2, 3, 4, 5]);

// Query the sum over a range
let sum = segTree.query(1, 3); // 9

// Update an element at a specific index
segTree.update(2, 10);

// Create a SegmentTree for querying min values
let minTree = new SegmentTree([3, 5, 2, 7, 1], (a, b) => Math.min(a, b));

// Query the minimum over a range
// Note that we have to set the initial value of result to Infinity
let min = minTree.query(1, 3, Infinity); // 2

Contributing

Contributions are welcome! Please submit a pull request or open an issue if you have any ideas, improvements, or suggestions.