A modern TypeScript data structures library — simple, fast, and educational.
npm install dsa-x> A modern, TypeScript-based Data Structures Library for JavaScript developers.
> Build, learn, and use fundamental data structures with clean, production-ready code.
---
DSA-X provides a robust, modular, and type-safe implementation of essential data structures —
from arrays and linked lists to trees, graphs, and tries — written in TypeScript.
The goal of DSA-X is to make data structures easy to use, test, and understand,
both for learners and professionals looking to integrate them into real-world applications.
---
You can install DSA-X using your favorite package manager:
``bashnpm
npm install dsa-x
`
---
---
A resizable array implementation similar to Java's ArrayList.
It automatically grows and shrinks its internal capacity as elements are added or removed.
Perfect for cases where the number of elements can change dynamically.
---
The DynamicArray class provides an efficient, type-safe array structure that supports:
- Constant-time access O(1)
- Amortized constant-time insertion
- Automatic resizing (doubling/halving)
- TypeScript generics for strong typing
---
`ts`
const arr = new DynamicArray
Parameters:
- initialCapacity (optional, default = 4) — Initial internal storage size.
---
#### push(value: T): void
Adds a new element at the end of the array.
Automatically doubles capacity if the array is full.
`ts`
arr.push(10);
arr.push(20);
---
#### pop(): T | null
Removes and returns the last element.
Shrinks capacity if size becomes one-fourth of the total capacity.
`ts`
const last = arr.pop(); // returns last element or null if empty
---
#### get(index: number): T | null
Returns the element at the specified index, or null if out of bounds.
`ts`
console.log(arr.get(1)); // → 20
---
#### set(index: number, value: T): void
Updates the element at a given index.
Throws RangeError if index is invalid.
`ts`
arr.set(0, 99);
---
#### size(): number
Returns the current number of elements.
`ts`
console.log(arr.size()); // → 2
---
#### getCapacity(): number
Returns the current allocated capacity.
`ts`
console.log(arr.getCapacity()); // → 8 (if resized)
---
#### toArray(): (T | null)[]
Returns a trimmed copy of the array (without null padding).
`ts`
console.log(arr.toArray()); // → [99, 20]
---
`ts
import DynamicArray from "./DynamicArray";
const arr = new DynamicArray
arr.push(5);
arr.push(10);
arr.push(15); // triggers resize
console.log(arr.toArray()); // [5, 10, 15]
console.log("Size:", arr.size()); // 3
console.log("Capacity:", arr.getCapacity()); // 4
arr.pop();
console.log(arr.toArray()); // [5, 10]
`
---
| Operation | Time Complexity | Space Complexity |
|------------|----------------|------------------|
| push() | O(1) amortized | O(n) |pop()
| | O(1) | O(n) |get()
| | O(1) | O(1) |set()
| | O(1) | O(1) |resize()
| | O(n) | O(n) |
---
- Uses a private array data: (T | null)[] for storage.length
- Resizing strategy:
- Double capacity when full.
- Halve capacity when utilization drops below 25%.
- Maintains two properties:
- : current number of elements.capacity
- : total allocated space.
---
A memory-efficient array implementation optimized for large arrays with many empty slots.
Internally, it uses a Map to store only the indices that contain values — saving space when most entries are empty.
---
The SparseArray class is ideal for datasets where most indices are unoccupied.
It provides fast lookups and flexible storage without allocating memory for unused elements.
Key Features:
- Stores only non-empty indices.
- Efficient O(1) average-time access and updates.
- Memory-efficient for sparse data.
- TypeScript generics ensure strong typing.
---
`ts`
const arr = new SparseArray
Parameters:
- length (optional, default = 0) — The logical length of the sparse array.
---
#### set(index: number, value: T): void
Sets a value at a specific index.
Automatically expands the logical length if necessary.
Throws a RangeError if the index is negative.
`ts`
arr.set(5, 42);
arr.set(100, 99);
---
#### get(index: number): T | null
Retrieves a value at the given index.
Returns null if the index has no stored value.
`ts`
console.log(arr.get(5)); // → 42
console.log(arr.get(10)); // → null
---
#### delete(index: number): void
Removes the value at the specified index (if any).
`ts`
arr.delete(5);
---
#### size(): number
Returns the logical length of the array (highest index + 1).
`ts`
console.log(arr.size()); // → 101
---
#### keys(): number[]
Returns an array of all active (non-empty) indices.
`ts`
console.log(arr.keys()); // → [100]
---
#### values(): T[]
Returns all stored values without their indices.
`ts`
console.log(arr.values()); // → [99]
---
#### toObject(): Record
Converts the sparse array into a plain JavaScript object
with numeric keys and stored values.
`ts`
console.log(arr.toObject()); // → {100: 99}
---
`ts
import SparseArray from "./SparseArray";
const arr = new SparseArray
arr.set(2, 50);
arr.set(5, 100);
arr.set(100, 999);
console.log(arr.get(5)); // 100
console.log(arr.get(20)); // null
arr.delete(2);
console.log(arr.keys()); // [5, 100]
console.log(arr.toObject()); // {5: 100, 100: 999}
`
---
| Operation | Time Complexity | Space Complexity |
|----------------|----------------|------------------|
| set() | O(1) average | O(n) |get()
| | O(1) average | O(1) |delete()
| | O(1) average | O(1) |keys()
| | O(n) | O(n) |values()
| | O(n) | O(n) |toObject()
| | O(n) | O(n) |
---
- Uses a private Map called data for storage.length
- Maintains a representing the logical array size.
- No preallocation — only indices that have values are stored.
- Efficient for large arrays with many empty elements.
---
A generic singly linked list implementation in TypeScript.
It supports common operations such as append, prepend, delete, find, and traversal.
---
The LinkedList class provides an ordered, dynamic data structure where each node points to the next.
This makes insertion and deletion efficient (O(1) at head or tail).
- Sequential structure with nodes connected by pointers.
- Ideal for use cases where array resizing or index shifting is expensive.
- Type-safe using TypeScript generics.
---
`ts`
const list = new LinkedList
Creates an empty linked list of generic type T.
---
#### append(value: T): void
Adds a new element to the end of the list.
`ts`
list.append(10);
list.append(20);
---
#### prepend(value: T): void
Adds a new element to the beginning of the list.
`ts`
list.prepend(5);
---
#### delete(value: T): boolean
Removes the first occurrence of the specified value.
`ts`
list.delete(10); // returns true if deleted, false otherwise
---
#### find(value: T): Node
Searches for the first node with the given value.
`ts`
const node = list.find(20);
if (node) console.log(node.value);
---
#### toArray(): T[]
Converts the linked list to a regular JavaScript array.
`ts`
console.log(list.toArray()); // [5, 20]
---
#### clear(): void
Removes all nodes from the linked list.
`ts`
list.clear();
---
#### length: number
Returns the total number of nodes in the list.
`ts`
console.log(list.length); // → 0 (after clearing)
---
`ts
import { LinkedList } from "./LinkedList";
const list = new LinkedList
list.append(10);
list.append(20);
list.prepend(5);
console.log(list.toArray()); // [5, 10, 20]
console.log("Length:", list.length); // 3
list.delete(10);
console.log(list.toArray()); // [5, 20]
const found = list.find(20);
console.log(found?.value); // 20
`
---
| Operation | Time Complexity | Space Complexity |
|----------------|----------------|------------------|
| append() | O(1) | O(1) |prepend()
| | O(1) | O(1) |delete()
| | O(n) | O(1) |find()
| | O(n) | O(1) |toArray()
| | O(n) | O(n) |clear()
| | O(1) | O(1) |
---
- Each node is an instance of the Node class with two properties:value
- : the stored datanext
- : pointer to the next node or null
- The linked list maintains:
- : reference to the first nodetail
- : reference to the last nodesize
- : current length of the list
---
A generic doubly linked list implementation supporting bidirectional traversal, efficient insertions, and deletions.
This data structure is ideal when you need quick access to both ends and frequent insertions/removals.
---
The DoubleLinkedList class provides:
- Efficient O(1) insertions and deletions at both ends
- Traversal in both forward and reverse directions
- TypeScript generics for strong typing
- Utility methods for conversion, searching, and clearing
---
`ts`
const list = new DoubleLinkedList
Creates an empty doubly linked list.
---
#### append(value: T): void
Adds an element at the end of the list.
`ts`
list.append(10);
list.append(20);
---
#### prepend(value: T): void
Adds an element at the beginning of the list.
`ts`
list.prepend(5);
---
#### delete(value: T): boolean
Removes the first node that matches the given value.
Returns true if the element was deleted, else false.
`ts`
list.delete(10);
---
#### find(value: T): DoubleNode
Finds and returns the first node with the specified value.
`ts`
const node = list.find(20);
if (node) console.log(node.value); // 20
---
#### toArrayForward(): T[]
Returns all elements in forward order.
`ts`
console.log(list.toArrayForward()); // [5, 20]
---
#### toArrayBackward(): T[]
Returns all elements in reverse order.
`ts`
console.log(list.toArrayBackward()); // [20, 5]
---
#### clear(): void
Clears the entire list, resetting it to an empty state.
`ts`
list.clear();
---
`ts
import { DoubleLinkedList } from "./DoubleLinkedList";
const list = new DoubleLinkedList
list.append(10);
list.append(20);
list.prepend(5);
console.log("Forward:", list.toArrayForward()); // [5, 10, 20]
console.log("Backward:", list.toArrayBackward()); // [20, 10, 5]
list.delete(10);
console.log("After deletion:", list.toArrayForward()); // [5, 20]
`
---
| Operation | Time Complexity | Space Complexity |
|------------------------|----------------|------------------|
| append() / prepend() | O(1) | O(1) |delete()
| | O(n) | O(1) |find()
| | O(n) | O(1) |toArrayForward()
| | O(n) | O(n) |toArrayBackward()
| | O(n) | O(n) |
---
Each node (DoubleNode) stores:
`ts`
{
value: T;
next: DoubleNode
prev: DoubleNode
}
The list maintains two references:
- head — first nodetail
- — last node
This allows traversal and updates from both ends efficiently.
---
File: Stack.ts
Description: A stack is a Last-In-First-Out (LIFO) data structure that supports push, pop, peek, and size operations.
---
`typescript
/**
* Stack Data Structure (Array Implementation)
*
* A stack is a Last-In-First-Out (LIFO) data structure.
* Supports push, pop, peek, and size operations.
*/
export default class Stack
private items: T[];
constructor() {
this.items = [];
}
/* Adds an element to the top of the stack /
push(element: T): void {
this.items.push(element);
}
/* Removes and returns the top element of the stack /
pop(): T | undefined {
return this.items.pop();
}
/* Returns the top element without removing it /
peek(): T | undefined {
return this.items[this.items.length - 1];
}
/* Returns true if the stack is empty /
isEmpty(): boolean {
return this.items.length === 0;
}
/* Returns the number of elements in the stack /
size(): number {
return this.items.length;
}
/* Clears all elements from the stack /
clear(): void {
this.items = [];
}
}
`
---
| Method | Description | Time Complexity |
|---------|--------------|----------------|
| push() | Adds an element to the top | O(1) |pop()
| | Removes the top element | O(1) |peek()
| | Returns the top element without removing it | O(1) |isEmpty()
| | Checks if stack is empty | O(1) |size()
| | Returns number of elements | O(1) |clear()
| | Removes all elements | O(1) |
---
`typescript`
const stack = new Stack
stack.push(10);
stack.push(20);
console.log(stack.peek()); // 20
console.log(stack.pop()); // 20
console.log(stack.size()); // 1
A First-In-First-Out (FIFO) data structure where the first element added is the first one to be removed.
It is ideal for use cases like task scheduling, request handling, and data buffering.
---
The Queue class provides an efficient and simple interface for managing elements in FIFO order.
- Constant-time enqueue and dequeue operations O(1) peek()
- Supports front element access using
- Type-safe using TypeScript generics
- Simple internal array-based implementation
---
`ts`
const queue = new Queue
Parameters:
None — creates an empty queue.
---
#### enqueue(value: T): void
Adds a new element at the end of the queue.
`ts`
queue.enqueue(10);
queue.enqueue(20);
---
#### dequeue(): T | undefined
Removes and returns the front element of the queue.
Returns undefined if the queue is empty.
`ts`
const first = queue.dequeue(); // → 10
---
#### peek(): T | undefined
Returns the front element without removing it.
`ts`
console.log(queue.peek()); // → 20
---
#### isEmpty(): boolean
Checks whether the queue is empty.
`ts`
console.log(queue.isEmpty()); // → false
---
#### size(): number
Returns the number of elements currently in the queue.
`ts`
console.log(queue.size()); // → 1
---
#### clear(): void
Removes all elements from the queue.
`ts`
queue.clear();
console.log(queue.isEmpty()); // → true
---
`ts
import Queue from "./Queue";
const queue = new Queue
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
console.log(queue.peek()); // 10
console.log(queue.dequeue()); // 10
console.log(queue.size()); // 2
console.log("Empty:", queue.isEmpty()); // false
queue.clear();
console.log(queue.isEmpty()); // true
`
---
| Operation | Time Complexity | Space Complexity |
|--------------|----------------|------------------|
| enqueue() | O(1) | O(n) |dequeue()
| | O(1) | O(n) |peek()
| | O(1) | O(1) |isEmpty()
| | O(1) | O(1) |size()
| | O(1) | O(1) |clear()
| | O(1) | O(1) |
---
- Uses a private internal array:
`ts`
private items: T[];
- pushes to the end using Array.push(). dequeue()
- removes from the front using Array.shift().
- Maintains FIFO order naturally via array indexing.
- Simple yet effective for small to medium datasets.
---
A binary heap–based priority queue implementation.
Each element is stored with an associated priority, and the element with the highest or lowest priority is dequeued first.
Supports both min-heap and max-heap configurations for flexible usage.
---
The PriorityQueue class provides an efficient data structure for managing elements by priority, supporting:
- Logarithmic-time insertion and removal O(log n)
- Configurable min-heap (default) or max-heap behavior
- Peek access to the highest/lowest priority element
- Automatic reordering using a binary heap
---
`ts`
const pq = new PriorityQueue
Parameters:
- isMinHeap (optional, default = true) —
Determines whether the queue behaves as a min-heap (smallest priority dequeued first) or max-heap (largest priority dequeued first).
---
#### enqueue(value: T, priority: number): void
Adds an element with the given priority.
Automatically positions it according to the heap order.
`ts`
pq.enqueue("Task A", 5);
pq.enqueue("Task B", 2);
---
#### dequeue(): T | undefined
Removes and returns the element with the highest (max-heap) or lowest (min-heap) priority.
Returns undefined if the queue is empty.
`ts`
const next = pq.dequeue(); // returns element with top priority
---
#### peek(): T | undefined
Returns the element with the top priority without removing it.
`ts`
console.log(pq.peek()); // "Task B" (for min-heap)
---
#### isEmpty(): boolean
Checks whether the priority queue is empty.
`ts`
console.log(pq.isEmpty()); // → false
---
#### size(): number
Returns the current number of elements in the queue.
`ts`
console.log(pq.size()); // → 2
---
`ts
import PriorityQueue from "./PriorityQueue";
// Min-Heap (default)
const minPQ = new PriorityQueue
minPQ.enqueue("Low Priority", 5);
minPQ.enqueue("High Priority", 1);
console.log(minPQ.peek()); // "High Priority"
console.log(minPQ.dequeue()); // "High Priority"
// Max-Heap
const maxPQ = new PriorityQueue
maxPQ.enqueue(10, 10);
maxPQ.enqueue(5, 5);
console.log(maxPQ.peek()); // 10
console.log(maxPQ.dequeue()); // 10
`
---
| Operation | Time Complexity | Space Complexity |
|----------------|----------------|------------------|
| enqueue() | O(log n) | O(n) |dequeue()
| | O(log n) | O(n) |peek()
| | O(1) | O(1) |isEmpty()
| | O(1) | O(1) |size()
| | O(1) | O(1) |
---
- Stores elements in a private array heap: { value: T; priority: number }[].bubbleUp()
- Maintains heap order using two key methods:
- – moves new elements up until the heap property is restored.bubbleDown()
- – moves root elements down after removal.compare(a, b)
- Uses to determine heap type:a < b
- Min-heap →
- Max-heap →
---
A fixed-size circular queue implementation that efficiently reuses memory by wrapping around when the end of the array is reached.
Perfect for bounded buffering, task scheduling, or streaming scenarios where memory usage must remain constant.
---
The CircularQueue class provides a memory-efficient, fixed-size queue implementation with constant-time operations:
- Constant-time enqueue and dequeue O(1)
- No dynamic resizing (fixed capacity)
- Automatically wraps around the array
- Prevents overflow/underflow using modular arithmetic
---
`ts`
const queue = new CircularQueue
Parameters:
- capacity — Total number of elements the queue can hold (must be > 0).
---
#### enqueue(element: T): void
Adds an element to the rear of the queue.
Throws an error if the queue is full.
`ts`
queue.enqueue(10);
queue.enqueue(20);
---
#### dequeue(): T | null
Removes and returns the front element.
Returns null if the queue is empty.
`ts`
console.log(queue.dequeue()); // → 10
---
#### peek(): T | null
Returns the front element without removing it.
Returns null if the queue is empty.
`ts`
console.log(queue.peek()); // → 20
---
#### isEmpty(): boolean
Checks if the queue has no elements.
`ts`
console.log(queue.isEmpty()); // → false
---
#### isFull(): boolean
Checks if the queue is full.
`ts`
console.log(queue.isFull()); // → true
---
#### size(): number
Returns the current number of elements in the queue.
`ts`
console.log(queue.size()); // → 3
---
#### clear(): void
Removes all elements from the queue and resets pointers.
`ts`
queue.clear();
---
`ts
import CircularQueue from "./CircularQueue";
const queue = new CircularQueue
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
console.log(queue.isFull()); // true
console.log(queue.dequeue()); // 1
queue.enqueue(4); // wraps around
console.log(queue.peek()); // 2
console.log(queue.size()); // 3
`
---
| Operation | Time Complexity | Space Complexity |
|----------------|----------------|------------------|
| enqueue() | O(1) | O(n) |dequeue()
| | O(1) | O(n) |peek()
| | O(1) | O(1) |isEmpty()
| | O(1) | O(1) |isFull()
| | O(1) | O(1) |size()
| | O(1) | O(1) |clear()
| | O(n) | O(1) |
---
- Uses a fixed-size array items: (T | null)[] for storage.front
- Maintains three key pointers:
- : index of the next element to dequeue.rear
- : index of the last enqueued element.count
- : number of current elements.(index % capacity)
- Uses modular arithmetic for circular wraparound.
- Throws overflow/underflow errors when attempting invalid operations.
---
A hash table implementation using separate chaining to handle collisions.
Provides efficient O(1) average-time complexity for insert, lookup, and delete operations.
Ideal for fast key-value lookups, caching, or indexing use cases.
---
The HashTable class provides a dynamic, resizable hash map structure with predictable performance:
- Constant-time average lookup, insert, and delete O(1)
- Automatically resizes when load factor exceeds
- Uses separate chaining (linked bucket arrays) to handle collisions
- Supports both and number keys
---
`ts`
const table = new HashTable
Parameters:
- capacity — Initial number of buckets in the hash table (default: 16).
---
#### set(key: K, value: V): void
Inserts or updates a key-value pair in the hash table.
If the key already exists, its value is updated.
If the load factor exceeds 0.75, the table resizes automatically.
`ts`
table.set("username", 101);
table.set("age", 25);
---
#### get(key: K): V | undefined
Retrieves the value associated with the given key.
Returns undefined if the key does not exist.
`ts`
console.log(table.get("age")); // → 25
---
#### has(key: K): boolean
Checks if the given key exists in the table.
`ts`
console.log(table.has("username")); // → true
---
#### delete(key: K): boolean
Removes the key-value pair associated with the given key.
Returns true if the key was found and deleted, false otherwise.
`ts`
table.delete("age");
---
#### size(): number
Returns the total number of key-value pairs currently stored in the hash table.
`ts`
console.log(table.size()); // → 1
---
#### clear(): void
Removes all key-value pairs and resets the table to its initial state.
`ts`
table.clear();
---
`ts
import HashTable from "./HashTable";
const table = new HashTable
table.set("a", 10);
table.set("b", 20);
table.set("c", 30);
console.log(table.get("b")); // → 20
console.log(table.has("a")); // → true
table.delete("a");
console.log(table.size()); // → 2
`
---
| Operation | Average Case | Worst Case | Space Complexity |
|-------------|--------------|-------------|------------------|
| set() | O(1) | O(n) | O(n) |get()
| | O(1) | O(n) | O(1) |has()
| | O(1) | O(n) | O(1) |delete()
| | O(1) | O(n) | O(1) |clear()
| | O(n) | O(n) | O(1) |resize()
| | O(n) | O(n) | O(n) |
---
- Uses an array of buckets → each bucket stores an array of [key, value] pairs.[0, capacity - 1]
- Hash function converts each key to an integer index within .
- Handles collisions using separate chaining — multiple pairs stored in one bucket.
- Automatically resizes (doubles capacity) when load factor > 0.75 to maintain efficiency.
- Keys must be strings or numbers.
---
A Graph data structure implementation using an adjacency list representation.
It supports directed and undirected graphs with efficient methods for managing vertices, edges, and performing graph traversals such as BFS and DFS.
---
The Graph class provides a versatile and type-safe graph representation that supports:
- Both directed and undirected edges
- Efficient vertex and edge manipulation
- Breadth-First Search (BFS) and Depth-First Search (DFS) traversals
- Constant-time neighbor lookups using Map and Set
---
`ts`
const graph = new Graph
Parameters:
- directed (optional, default = false) — true
If , creates a directed graph; otherwise, an undirected graph.
---
#### addVertex(vertex: T): void
Adds a new vertex to the graph if it doesn’t already exist.
`ts`
graph.addVertex("A");
---
#### addEdge(vertex1: T, vertex2: T): void
Adds an edge between two vertices.
Automatically creates vertices if they don’t exist.
For undirected graphs, adds the edge in both directions.
`ts`
graph.addEdge("A", "B");
---
#### removeEdge(vertex1: T, vertex2: T): void
Removes the edge between two vertices.
For undirected graphs, removes the edge in both directions.
`ts`
graph.removeEdge("A", "B");
---
#### removeVertex(vertex: T): void
Removes a vertex and all edges connected to it.
`ts`
graph.removeVertex("A");
---
#### getNeighbors(vertex: T): Set
Returns a set of all neighbors of a given vertex.
Returns undefined if the vertex doesn’t exist.
`ts`
console.log(graph.getNeighbors("B")); // → Set { "C", "D" }
---
#### bfs(start: T): T[]
Performs a Breadth-First Search traversal starting from the given vertex.
Returns the order of visited vertices.
`ts`
console.log(graph.bfs("A")); // → ["A", "B", "C", "D"]
---
#### dfs(start: T): T[]
Performs a Depth-First Search traversal starting from the given vertex.
Returns the order of visited vertices.
`ts`
console.log(graph.dfs("A")); // → ["A", "B", "C", "D"]
---
`ts
import Graph from "./Graph";
const graph = new Graph
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "D");
console.log("BFS:", graph.bfs("A")); // BFS: [ 'A', 'B', 'C', 'D' ]
console.log("DFS:", graph.dfs("A")); // DFS: [ 'A', 'B', 'D', 'C' ]
console.log("Neighbors of B:", graph.getNeighbors("B")); // Set { 'A', 'D' }
`
---
| Operation | Time Complexity | Space Complexity |
|------------------|----------------|------------------|
| addVertex() | O(1) | O(1) |addEdge()
| | O(1) | O(1) |removeEdge()
| | O(1) | O(1) |removeVertex()
| | O(V + E) | O(V + E) |getNeighbors()
| | O(1) | O(1) |bfs()
| | O(V + E) | O(V) |dfs()
| | O(V + E) | O(V) |
---
- Uses a Map adjacencyList: Map to store vertices and their neighbors.bfs
- Each vertex maps to a Set of adjacent vertices for fast lookup and deletion.
- Supports directed or undirected configuration at construction.
- Traversals ( and dfs) use:Set
- for tracking visited nodes.Array
- as a queue (BFS) or recursive stack (DFS).
---
A weighted graph implementation using an adjacency list.
Supports directed and undirected graphs and includes two shortest-path algorithms: Dijkstra (non-negative weights) and Bellman‑Ford (supports negative weights, detects negative cycles).
---
The WeightedGraph class represents a graph where edges have numeric weights. Map
It is implemented with a (map from vertex → map of neighbor → weight), which is memory-efficient for sparse graphs.
- Use adjacency list when the graph is sparse (E ≪ V²).
- Supports both directed and undirected graphs via the constructor flag.
---
`
Graph:
A → B (5) , C (2)
B → D (10)
C → B (-2), D (3)
Adjacency List (Map) representation:
{
"A": { "B": 5, "C": 2 },
"B": { "D": 10 },
"C": { "B": -2, "D": 3 },
"D": {}
}
`
---
`ts
/**
* Weighted Graph (Adjacency List)
*
* Supports directed or undirected graphs with edge weights.
* Includes Dijkstra’s and Bellman-Ford shortest path algorithms.
*/
export default class WeightedGraph
private adjacencyList: Map
private directed: boolean;
constructor(directed: boolean = false) {
this.adjacencyList = new Map();
this.directed = directed;
}
/* Add a vertex if it doesn't exist /
addVertex(vertex: T): void {
if (!this.adjacencyList.has(vertex)) {
this.adjacencyList.set(vertex, new Map());
}
}
/* Add a weighted edge /
addEdge(vertex1: T, vertex2: T, weight: number): void {
this.addVertex(vertex1);
this.addVertex(vertex2);
this.adjacencyList.get(vertex1)?.set(vertex2, weight);
if (!this.directed) {
this.adjacencyList.get(vertex2)?.set(vertex1, weight);
}
}
/* Remove an edge /
removeEdge(vertex1: T, vertex2: T): void {
this.adjacencyList.get(vertex1)?.delete(vertex2);
if (!this.directed) {
this.adjacencyList.get(vertex2)?.delete(vertex1);
}
}
/* Remove a vertex and its edges /
removeVertex(vertex: T): void {
this.adjacencyList.delete(vertex);
for (const [v, edges] of this.adjacencyList.entries()) {
edges.delete(vertex);
}
}
/* Get all edges from a vertex /
getEdges(vertex: T): Map
return this.adjacencyList.get(vertex);
}
/* Dijkstra’s shortest path algorithm /
dijkstra(start: T): Map
const distances = new Map
const visited = new Set
const pq: [T, number][] = [];
for (const vertex of this.adjacencyList.keys()) {
distances.set(vertex, vertex === start ? 0 : Infinity);
}
pq.push([start, 0]);
while (pq.length > 0) {
pq.sort((a, b) => a[1] - b[1]);
const [current, dist] = pq.shift()!;
if (visited.has(current)) continue;
visited.add(current);
const neighbors = this.adjacencyList.get(current);
if (neighbors) {
for (const [neighbor, weight] of neighbors.entries()) {
const newDist = dist + weight;
if (newDist < (distances.get(neighbor) ?? Infinity)) {
distances.set(neighbor, newDist);
pq.push([neighbor, newDist]);
}
}
}
}
return distances;
}
/**
* Bellman-Ford Algorithm
* Works even with negative edge weights.
* Detects negative weight cycles.
*/
bellmanFord(start: T): Map
const distances = new Map
const vertices = Array.from(this.adjacencyList.keys());
// Step 1: Initialize distances
for (const v of vertices) {
distances.set(v, Infinity);
}
distances.set(start, 0);
// Step 2: Relax all edges |V| - 1 times
for (let i = 0; i < vertices.length - 1; i++) {
for (const [u, edges] of this.adjacencyList.entries()) {
const distU = distances.get(u)!;
if (distU === Infinity) continue;
for (const [v, weight] of edges.entries()) {
const newDist = distU + weight;
if (newDist < distances.get(v)!) {
distances.set(v, newDist);
}
}
}
}
// Step 3: Detect negative weight cycle
for (const [u, edges] of this.adjacencyList.entries()) {
const distU = distances.get(u)!;
if (distU === Infinity) continue;
for (const [v, weight] of edges.entries()) {
if (distU + weight < distances.get(v)!) {
throw new Error("Graph contains a negative weight cycle");
}
}
}
return distances;
}
}
`
---
- Use when edge weights are non-negative.
- Idea: Greedy selection of the unvisited vertex with the smallest tentative distance, relax outgoing edges.
- Implementation detail: The example above uses a simple array-based priority queue (sorted array) for clarity. For better performance use a binary heap (min-heap) or Fibonacci heap.
- Complexity with binary heap: O((V + E) log V). With the simple sorted array shown: O(V^2 + E log V) in practice.
---
- Use when negative edge weights exist (but no negative cycles).
- Idea: Relax all edges repeatedly (|V| - 1) times; then check for negative cycles.
- Complexity: O(V * E).
- Detects negative weight cycles and throws an error if found.
---
| Operation | Time Complexity | Space Complexity |
|-------------------|-----------------|------------------|
| addVertex() | O(1) | O(V) |
| addEdge() | O(1) | O(E) |
| getEdges() | O(1) | O(1) |
| dijkstra() | O((V + E) log V) with heap | O(V + E) |
| bellmanFord() | O(V * E) | O(V + E) |
---
`ts
import WeightedGraph from "./WeightedGraph";
const g = new WeightedGraph
g.addEdge("A", "B", 4);
g.addEdge("A", "C", 2);
g.addEdge("C", "B", -2);
g.addEdge("B", "D", 2);
g.addEdge("C", "D", 3);
console.log("Dijkstra from A:", g.dijkstra("A"));
console.log("Bellman-Ford from A:", g.bellmanFord("A"));
`
---
A self-balancing binary search tree (BST) where the height difference between left and right subtrees (the balance factor) is never more than 1.
It ensures O(log n) performance for insertions, deletions, and lookups.
---
The AVLTree class provides a robust, type-safe implementation of an AVL tree that automatically balances itself after every insertion and deletion.
It supports:
- Fast ordered data storage
- Self-balancing rotations (LL, LR, RR, RL)
- Inorder traversal for sorted output
- Custom comparison logic via comparator function
---
`ts`
const tree = new AVLTree
Parameters:
- compareFn (optional) — Custom comparison function for ordering. Defaults to numeric/string comparison.
---
#### insert(value: T): void
Inserts a new value into the tree and rebalances it automatically.
`ts`
tree.insert(10);
tree.insert(5);
tree.insert(15);
---
#### delete(value: T): void
Removes a value from the tree, rebalancing it if needed.
`ts`
tree.delete(10);
---
#### contains(value: T): boolean
Checks whether a given value exists in the tree.
`ts`
console.log(tree.contains(5)); // → true
console.log(tree.contains(99)); // → false
---
#### inorder(): T[]
Performs an inorder traversal, returning sorted values.
`ts`
console.log(tree.inorder()); // → [5, 10, 15]
---
AVL trees use four types of rotations to maintain balance:
| Rotation Type | Trigger Condition | Action |
|----------------|------------------|--------|
| LL (Right Rotation) | Left-heavy after left insert | Rotate right |
| RR (Left Rotation) | Right-heavy after right insert | Rotate left |
| LR (Left-Right) | Left-heavy after right insert | Left rotate child, then right rotate parent |
| RL (Right-Left) | Right-heavy after left insert | Right rotate child, then left rotate parent |
---
`ts
import AVLTree from "./AVLTree";
const tree = new AVLTree
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(10); // triggers rotation
console.log(tree.inorder()); // [10, 20, 30, 40]
tree.delete(20);
console.log(tree.inorder()); // [10, 30, 40]
`
---
| Operation | Time Complexity | Space Complexity |
|------------|----------------|------------------|
| insert() | O(log n) | O(n) |delete()
| | O(log n) | O(n) |contains()
| | O(log n) | O(1) |inorder()
| | O(n) | O(n) |
---
- Each node stores:
- value: The elementheight
- : Node height for balancingleft
- and right: Child pointers
- Balancing uses height difference between left and right subtrees.
- Rotations are used to maintain balance after every modification.
---
A classic Binary Search Tree (BST) implementation supporting insertion, deletion, search, and traversal operations.
Provides an ordered structure for efficient lookups and in-order traversals.
---
The BinarySearchTree class offers:
- Efficient insert, search, and delete operations
- In-order traversal for sorted data output
- Average-case logarithmic performance O(log n) for key operations
---
`ts`
const bst = new BinarySearchTree
Creates an empty binary search tree instance.
---
#### insert(value: T): void
Inserts a new value into the BST, maintaining order.
`ts`
bst.insert(10);
bst.insert(5);
bst.insert(15);
---
#### search(value: T): boolean
Checks whether a value exists in the tree.
`ts`
console.log(bst.search(10)); // → true
console.log(bst.search(7)); // → false
---
#### delete(value: T): void
Removes a value from the tree if present.
Handles all three deletion cases (leaf, one child, two children).
`ts`
bst.delete(5);
---
#### inorder(): T[]
Performs an in-order traversal and returns elements in sorted order.
`ts`
console.log(bst.inorder()); // → [10, 15, 20]
---
`ts
import { BinarySearchTree } from "./BinarySearchTree";
const bst = new BinarySearchTree
bst.insert(50);
bst.insert(30);
bst.insert(70);
bst.insert(20);
bst.insert(40);
bst.insert(60);
bst.insert(80);
console.log("Inorder:", bst.inorder()); // [20, 30, 40, 50, 60, 70, 80]
bst.delete(20);
bst.delete(30);
bst.delete(50);
console.log("After Deletions:", bst.inorder()); // [40, 60, 70, 80]
console.log("Search 60:", bst.search(60)); // true
console.log("Search 100:", bst.search(100)); // false
`
---
| Operation | Average Time | Worst Time | Space Complexity |
|------------|--------------|-------------|------------------|
| insert() | O(log n) | O(n) | O(n) |search()
| | O(log n) | O(n) | O(1) |delete()
| | O(log n) | O(n) | O(n) |inorder()
| | O(n) | O(n) | O(n) |
---
- Each node is represented by the BSTNode class containing:value
- : Node dataleft
- : Left child referenceright
- : Right child reference
- Maintains the BST property:
- Left subtree < Node < Right subtree
- Recursive algorithms handle insertion, deletion, and traversal.
---
A Trie is a tree-based data structure used for efficient retrieval of strings. It is particularly useful for tasks involving prefix matching, autocomplete systems, and dictionary word lookups.
---
The Trie (also known as a Prefix Tree) stores strings character by character, where each node represents a single character of the word. Words that share a common prefix share the same path in the tree up to that prefix.
---
: A map of characters to child nodes.
- isEndOfWord: A boolean flag to indicate whether the current node marks the end of a valid word.$3
The main Trie class provides methods for insertion, searching, prefix checking, and deletion.---
⚙️ Methods
$3
Inserts a word into the Trie, creating nodes for characters as needed.#### Steps
1. Start from the root node.
2. For each character:
- If the character doesn’t exist as a child, create a new TrieNode.
- Move to the child node.
3. Mark the last node’s
isEndOfWord as true.#### Time Complexity
- O(n), where n is the length of the word.
---
$3
Checks whether a word exists in the Trie.#### Steps
1. Traverse character by character from the root.
2. If a character is missing, return
false.
3. After processing all characters, return true only if isEndOfWord is true.#### Time Complexity
- O(n)
---
$3
Checks whether there exists any word in the Trie that starts with the given prefix.#### Steps
1. Traverse through the Trie for each prefix character.
2. If traversal is possible for all prefix characters, return
true.#### Time Complexity
- O(n)
---
$3
Deletes a word from the Trie, removing unnecessary nodes after deletion.#### Steps
1. Traverse recursively using
deleteHelper.
2. When the end of the word is reached, unset isEndOfWord.
3. Backtrack and remove nodes that are no longer needed (no children and not an endpoint).#### Time Complexity
- O(n)
---
🧠 Example Usage
`ts
const trie = new Trie();
trie.insert("apple");
trie.insert("app");console.log(trie.search("apple")); // true
console.log(trie.search("app")); // true
console.log(trie.startsWith("ap")); // true
trie.delete("app");
console.log(trie.search("app")); // false
`---
📈 Summary Table
| Operation | Description | Time Complexity |
|------------|--------------|-----------------|
|
| Add a word to the trie | O(n) |
| search | Check if word exists | O(n) |
| startsWith | Check prefix existence | O(n) |
| delete | Remove word from trie | O(n) |---
🏗️ Use Cases
- Autocomplete systems
- Spell checkers
- IP routing (Longest Prefix Match)
- Dictionary word search
- Search engines
---
🧾 Code Implementation (TypeScript)
`ts
class TrieNode {
children: Map;
isEndOfWord: boolean; constructor() {
this.children = new Map();
this.isEndOfWord = false;
}
}
export default class Trie {
private root: TrieNode;
constructor() {
this.root = new TrieNode();
}
insert(word: string): void {
let node = this.root;
for (const char of word) {
if (!node.children.has(char)) {
node.children.set(char, new TrieNode());
}
node = node.children.get(char)!;
}
node.isEndOfWord = true;
}
search(word: string): boolean {
let node = this.root;
for (const char of word) {
if (!node.children.has(char)) return false;
node = node.children.get(char)!;
}
return node.isEndOfWord;
}
startsWith(prefix: string): boolean {
let node = this.root;
for (const char of prefix) {
if (!node.children.has(char)) return false;
node = node.children.get(char)!;
}
return true;
}
delete(word: string): void {
this.deleteHelper(this.root, word, 0);
}
private deleteHelper(node: TrieNode, word: string, depth: number): boolean {
if (depth === word.length) {
if (!node.isEndOfWord) return false;
node.isEndOfWord = false;
return node.children.size === 0;
}
const char = word[depth];
const child = node.children.get(char);
if (!child) return false;
const shouldDelete = this.deleteHelper(child, word, depth + 1);
if (shouldDelete) {
node.children.delete(char);
return node.children.size === 0 && !node.isEndOfWord;
}
return false;
}
}
`---
🧭 Conclusion
The Trie is a powerful data structure for handling string-based operations efficiently, especially where prefix searches or word retrieval are common. Its node-based structure enables shared memory usage across common prefixes, optimizing space and time for large datasets.
MinHeap
A binary heap data structure that always maintains the smallest element at the top.
Efficiently supports insertion, extraction of the minimum, and peek operations.
Ideal for priority queues, scheduling, and graph algorithms like Dijkstra’s shortest path.
---
$3
The
class is a generic, type-safe heap implementation that maintains the heap invariant —
each parent node is always less than or equal to its child nodes.- Insertions and deletions in O(log n) time.
- Access to the minimum element in O(1) time.
- Can be customized with a custom comparison function.
---
$3
`ts
const heap = new MinHeap();
`or with a custom comparator:
ts
const heap = new MinHeap((a, b) => a - b);
`Parameters:
-
(optional) — A custom comparison function.
Should return:
- -1 if a < b
- if a === b
- if a > b---
$3
####
Returns the number of elements currently in the heap.
ts
console.log(heap.size()); // → 5
`---
####
Returns the smallest element without removing it from the heap.
ts
console.log(heap.peek()); // → 2
`---
####
Inserts a new element into the heap and restores the heap property using heapify-up.
ts
heap.insert(10);
heap.insert(3);
heap.insert(5);
`---
####
Removes and returns the smallest element (root) from the heap.
Rebalances the heap using heapify-down.
ts
console.log(heap.extractMin()); // → 3
`---
$3
ts
import MinHeap from "./MinHeap";const heap = new MinHeap();
heap.insert(5);
heap.insert(2);
heap.insert(8);
heap.insert(1);
console.log("Min:", heap.peek()); // → 1
console.log("Extracted:", heap.extractMin()); // → 1
console.log("Next Min:", heap.peek()); // → 2
console.log("Size:", heap.size()); // → 3
`---
$3
| Operation | Time Complexity | Space Complexity |
|-----------------|----------------|------------------|
|
| O(log n) | O(n) |
| extractMin() | O(log n) | O(n) |
| peek() | O(1) | O(1) |
| size() | O(1) | O(1) |---
$3
- Uses an internal array representation for the binary heap.
- Maintains the heap invariant via:
-
_heapifyUp() — Adjusts new elements upwards after insertion.
- _heapifyDown() — Adjusts root downwards after extraction.
- Supports custom comparators for flexible ordering logic.---
$3
- Priority Queues (task scheduling, resource allocation)
- Graph Algorithms (Dijkstra’s, Prim’s)
- Event Simulation Systems
- Median or Top-K computations
---
MaxHeap
A Max Heap implementation that extends the functionality of a
MinHeap by inverting the comparison logic.
This ensures that the maximum element is always at the root.
Useful for priority scheduling, heap sort, and max-priority queue implementations.---
$3
The
MaxHeap class inherits from the MinHeap and overrides its comparison function to maintain a descending order heap property.- The largest element is always at the top.
- Insertion and extraction operations take
O(log n) time.
- Supports custom comparison functions for complex data types.---
$3
`ts
const maxHeap = new MaxHeap();
`Parameters:
-
: (optional) — A custom comparator function (a, b) => number.
If not provided, the heap uses the default numeric comparison.Default Comparison Logic:
`ts
(a, b) => (a > b ? -1 : a < b ? 1 : 0)
`This reverses the normal MinHeap order, ensuring higher values have higher priority.
---
$3
ts
import MaxHeap from "./MaxHeap";const heap = new MaxHeap();
heap.insert(10);
heap.insert(5);
heap.insert(30);
heap.insert(20);
console.log(heap.extract()); // 30
console.log(heap.peek()); // 20
`With a custom comparator:
ts
const heap = new MaxHeap<{ key: number }>((a, b) => a.key - b.key);heap.insert({ key: 10 });
heap.insert({ key: 50 });
heap.insert({ key: 30 });
console.log(heap.extract()); // { key: 50 }
`---
$3
| Operation | Time Complexity | Space Complexity |
|-----------------|----------------|------------------|
|
| O(log n) | O(n) |
| extract() | O(log n) | O(n) |
| peek() | O(1) | O(1) |
| size() | O(1) | O(1) |
| clear() | O(1) | O(1) |---
$3
- Inherits from the
MinHeap class.
- Overrides the comparator logic to invert priority.
- Uses an internal array to maintain heap structure.Parent–Child Relationships:
-
parent(i) = Math.floor((i - 1) / 2)
-
- This design allows efficient element insertion and removal while maintaining heap balance.
---