Introduction
This article is your guide to understanding and implementing Data Structures & Algorithms (DSA) using JavaScript and TypeScript. Whether you're a seasoned developer or a beginner, we'll cover practical examples of arrays, linked lists, stacks, queues, trees, and graphs. What's more, all TypeScript examples are available, and if you're a JavaScript enthusiast, the code is right there in my GitHub repository Code Samples. Get ready to strengthen your coding skills, as we unravel the power of DSA in the friendly world of JavaScript and TypeScript.
Note: This article excludes explanations and implementations of Heap
and Trie
. We'll cover these topics in detail when we delve into problemsolving associated with these concepts. Stay tuned for their inclusion!
Stack
Definition:
A Stack is a data structure that follows the Last In, First Out (LIFO) principle, where the last element added is the first one to be removed. It supports fundamental operations such as pushing (adding) an element to the top, popping (removing) the top element, checking if it's empty, obtaining the size, and peeking (viewing) the top element without removal.
Algorithmic Steps:
/**
* Stack Class Definition:
*  Initialize an empty array to store items and a variable to track size.
*  Push: Add an element to the front of the array and increment size.
*  Pop: Remove the first element if the stack is not empty and decrement size.
*  isEmpty: Check if the size is zero to determine if the stack is empty.
*  getSize: Return the current size of the stack.
*  Peek: Return the first element if the stack is not empty.
*  Clear: Reset the array and size if the stack is not empty.
*  Contains: Check if the stack includes a specific value.
*  ToString: Return a string representation of the stack.
*  Clone: Perform a shallow clone of the stack's items.
*/
Complexity Analysis:

Insertion (Push): O(1)
 Adding an element to the top of the stack takes constant time.

Removal (Pop): O(1)
 Removing the top element from the stack also takes constant time.

Searching (Contains): O(n)
 Checking if a specific value is present involves a linear search through the stack.

Access (Peek, Get Size, Is Empty): O(1)
 Accessing the top element, getting the size, and checking for emptiness are constanttime operations.
Implementation:
class Stack<T> {
private size: number;
private items: T[];
constructor() {
this.size = 0;
this.items = [];
}
push(value: T): void {
this.items.push(value);
this.size++;
}
pop(): void {
if (this.isEmpty()) {
throw new Error("Stack underflow: cannot pop from an empty stack");
}
this.items.pop();
this.size;
}
isEmpty(): boolean {
return this.size === 0;
}
getSize(): number {
return this.size;
}
peek(): T  undefined {
if (this.isEmpty()) {
return undefined;
}
return this.items[this.items.length  1];
}
clear(): void {
if (this.isEmpty()) {
throw new Error("Stack empty: Can not clear empty stack");
}
this.items = [];
this.size = 0;
}
contains(value: T): boolean {
if (this.isEmpty()) {
return false;
}
return this.items.includes(value);
}
toString(): string {
return JSON.stringify(this.items);
}
clone(): T[] {
return [...this.items]; // shallow cloning
}
}
const stack = new Stack<number>(); // Generic type in this case it is number type
stack.push(1);
stack.push(2);
console.log("Stack Size:", stack.getSize());
console.log("Stack Peek:", stack.peek());
console.log("Stack Contains 2:", stack.contains(2));
console.log("Stack Contents:", stack.toString());
stack.pop();
console.log("Stack Size after Pop:", stack.getSize());
console.log("Is Stack Empty:", stack.isEmpty());
stack.clear();
console.log("Stack Size after Clear:", stack.getSize());
Queue
Definition:
A Queue is a data structure that follows the First In, First Out (FIFO) principle, where the first element added is the first one to be removed. It supports essential operations such as enqueue (adding) an element to the back, dequeue (removing) the front element, checking if it's empty, obtaining the size, and peeking (viewing) the front element without removal.
Algorithmic Steps:
/**
* Queue Class Definition:
*  Initialize an empty array to store items and a variable to track size.
*  Enqueue: Add an element to the end of the array and increment size.
*  Dequeue: Remove the first element if the queue is not empty and decrement size.
*  isEmpty: Check if the size is zero to determine if the queue is empty.
*  getSize: Return the current size of the queue.
*  Peek: Return the first element if the queue is not empty.
*/
Complexity Analysis:

Insertion (Enqueue): O(1)
 Adding an element to the back of the queue takes constant time.

Removal (Dequeue): O(1)
 Removing the front element from the queue also takes constant time.

Searching (N/A): N/A
 Queues typically do not support searching for specific values.

Access (Peek, Get Size, Is Empty): O(1)
 Accessing the front element, getting the size, and checking for emptiness are constanttime operations.
Implementation:
class Queue<T> {
private items: T[];
private size: number;
constructor() {
this.items = [];
this.size = 0;
}
enqueue(value: T): void {
this.items.push(value);
this.size++;
}
dequeue(): void {
if (this.isEmpty()) {
throw new Error("Dequeue operation on an empty queue");
}
this.items.shift();
this.size;
}
isEmpty(): boolean {
return this.size === 0;
}
getSize(): number {
return this.size;
}
peek(): T  undefined {
return this.isEmpty() ? undefined : this.items[0];
}
}
const queue = new Queue<number>(); // Generic type in this case it is number type
queue.enqueue(1);
queue.enqueue(2);
console.log("Front of the queue:", queue.peek());
console.log("Queue size:", queue.getSize());
queue.dequeue();
console.log("Front of the queue after dequeue:", queue.peek());
console.log("Is the queue empty?", queue.isEmpty());
Priority Queue
Definition:
A Priority Queue is a data structure that maintains a collection of elements, each associated with a priority. The element with the highest priority is served before others. It supports operations such as enqueueing (adding) an element with a priority, dequeueing (removing) the element with the highest priority, checking if it's empty, obtaining the size, and peeking (viewing) the element with the highest priority without removal.
Algorithmic Steps:
/**
* Priority Queue Class Definition:
*  Initialize an empty array to store items as priorityvalue pairs and a variable to track size.
*  Enqueue: Add an element with a priority, maintaining order based on priorities.
*  Dequeue: Remove the element with the highest priority if the queue is not empty and decrement size.
*  isEmpty: Check if the size is zero to determine if the priority queue is empty.
*  getSize: Return the current size of the priority queue.
*  Peek: Return the element with the highest priority without removal if the priority queue is not empty.
*/
Complexity Analysis:

Insertion (Enqueue): O(n) in the worst case
 Enqueueing involves finding the correct position based on priorities, which may require traversing the entire queue.

Removal (Dequeue): O(1)
 Dequeueing the element with the highest priority is a constanttime operation.

Searching (Contains): O(n)
 Checking if a specific value is present involves a linear search through the priority queue.

Access (Peek, Get Size, Is Empty): O(1)
 Accessing the element with the highest priority, getting the size, and checking for emptiness are constanttime operations.
Implementation
type PriorityQueueItem<T> = [number, T];
class PriorityQueue<T> {
private items: PriorityQueueItem<T>[];
private size: number;
constructor() {
this.items = [];
this.size = 0;
}
enqueue(item: PriorityQueueItem<T>) {
if (this.isEmpty()) {
this.items.push(item);
} else {
let added = false;
for (let i = 0; i < this.items.length; i++) {
if (item[0] < this.items[i][0]) {
this.items.splice(i, 0, item);
added = true;
break;
}
}
if (!added) {
this.items.push(item);
}
}
this.size++;
}
dequeue() {
if (this.isEmpty()) {
throw new Error("Dequeue operation on an empty queue");
}
this.items.shift();
this.size;
}
isEmpty() {
return this.size === 0;
}
getSize() {
return this.size;
}
peek(): T  undefined {
return this.isEmpty() ? undefined : this.items[0][1];
}
}
const priorityQueue = new PriorityQueue<string>(); // Generic type in this case it is string type
priorityQueue.enqueue([1, "Ramu"]);
priorityQueue.enqueue([2, "Kumar"]);
console.log("Front of the priorityQueue:", priorityQueue.peek());
console.log("Queue size:", priorityQueue.getSize());
priorityQueue.dequeue();
console.log("Front of the priorityQueue after dequeue:", priorityQueue.peek());
console.log("Is the priorityQueue empty?", priorityQueue.isEmpty());
Linked List
Definition:
A Linked List is a linear data structure consisting of nodes, where each node points to the next one in the sequence. It provides dynamic memory allocation and efficient insertion and deletion operations compared to arrays. The linked list can be singly or doubly linked, and in our case, it is a singly linked list.
Algorithmic Steps:
/**
* LNode Class Definition:
*  Represents a node with a value and a reference to the next node.
*
* LinkedList Class Definition:
*  Initialize the head as null.
*  Push: Add a new node with the given value to the end of the list.
*  Pop: Remove and return the value of the last node in the list.
*  ToArray: Convert the linked list to an array.
*  Delete: Remove the first occurrence of a node with the given value.
*  Print: Output the values of all nodes in the list.
*  Find: Check if a node with the given value exists in the list.
*  Reverse: Reverse the order of nodes in the list.
*  Size: Return the number of nodes in the list.
*/
Complexity Analysis:

Insertion (Push): O(n)
 Adding a new node to the end of the linked list requires traversing the entire list, resulting in a linear time complexity.

Deletion (Pop, Delete): O(n)
 Removing the last node or a specific value involves traversing the list, leading to a linear time complexity.

Searching (Find): O(n)
 Checking for the existence of a specific value requires a linear search through the list.

Access (ToArray, Print): O(n)
 Converting the linked list to an array or printing its values involves traversing the entire list, resulting in linear time complexity.

Size: O(n)
 Calculating the size of the linked list requires traversing all nodes, resulting in linear time complexity.

Reversal (Reverse): O(n)
 Reversing the linked list involves traversing it once, resulting in linear time complexity.
Implementation:
class LNode<T> {
value: T;
next: LNode<T>  null;
constructor(value: T) {
this.value = value;
this.next = null;
}
}
class LinkedList<T> {
head: LNode<T>  null;
constructor() {
this.head = null;
}
push(value: T): void {
const newLNode = new LNode(value);
if (!this.head) {
this.head = newLNode;
} else {
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = newLNode;
}
}
pop(): T  null {
let current = this.head;
let prev: LNode<T>  null = null;
if (!current) {
return null;
}
while (current.next) {
prev = current;
current = current.next;
}
if (!prev) {
this.head = null;
} else {
prev.next = null;
}
return current.value;
}
toArray(): T[] {
let current = this.head;
const result: T[] = [];
while (current) {
result.push(current.value);
current = current.next;
}
return result;
}
delete(value: T): T  null {
let current = this.head;
let prev: LNode<T>  null = null;
while (current && current.value !== value) {
prev = current;
current = current.next;
}
if (current) {
if (!prev) {
this.head = current.next;
} else {
prev.next = current.next;
}
return current.value;
}
return null;
}
print(): void {
let current = this.head;
while (current) {
console.log(current.value);
current = current.next;
}
}
find(value: T): boolean {
let current = this.head;
while (current) {
if (current.value === value) {
return true;
}
current = current.next;
}
return false;
}
reverse(): void {
let current = this.head;
let prev: LNode<T>  null = null;
while (current) {
const next = current.next;
current.next = prev;
prev = current;
current = next;
}
this.head = prev;
}
size(): number {
let count = 0;
let current = this.head;
while (current) {
count++;
current = current.next;
}
return count;
}
}
const linkedList = new LinkedList<number>();
linkedList.push(1);
linkedList.push(2);
linkedList.push(3);
console.log("Original Linked List:");
linkedList.print();
const poppedValue = linkedList.pop();
console.log(`Popped Value: ${poppedValue}`);
console.log("\nLinked List After Pop:");
linkedList.print();
const arrayRepresentation = linkedList.toArray();
console.log("\nArray Representation of Linked List:", arrayRepresentation);
Binary Search Tree
Definition:
A Binary Search Tree (BST) is a hierarchical data structure that follows the binary tree property: for each node, all elements in its left subtree are less than the node, and all elements in its right subtree are greater. It allows for efficient search, insertion, and deletion operations.
Algorithmic Steps:
/**
* TreeNode Class Definition:
*  Define a class for tree nodes with left, right, and value properties.
*
* BinarySearchTree Class Definition:
*  Initialize the tree with a null root.
*  Insert: Add a new node with the given value while maintaining the BST property.
*  Find: Search for a node with the given value and return the value if found, else 1.
*  GetMin: Find and return the minimum value in the BST.
*  GetMax: Find and return the maximum value in the BST.
*  Remove: Remove a node with the given value while maintaining the BST property.
*  BreadthFirstSearch: Traverse the tree in breadthfirst order and return an array of values.
*  DepthFirstSearchPreOrder: Traverse the tree in preorder and return an array of values.
*  DepthFirstSearchInOrder: Traverse the tree in inorder and return an array of values.
*  DepthFirstSearchPostOrder: Traverse the tree in postorder and return an array of values.
*/
Complexity Analysis:

Insertion: O(log n) on average, O(n) in the worst case
 Adding a node involves traversing the height of the tree, which is logarithmic on average, but in the worst case (unbalanced tree), it becomes linear.

Search (Find): O(log n) on average, O(n) in the worst case
 Searching for a value involves traversing the height of the tree, which is logarithmic on average, but becomes linear in the worst case.

GetMin and GetMax: O(log n) on average, O(n) in the worst case
 Finding the minimum or maximum value involves traversing the left or right subtree, respectively, which is logarithmic on average, but becomes linear in the worst case.

Removal: O(log n) on average, O(n) in the worst case
 Removing a node involves traversing the height of the tree, which is logarithmic on average, but becomes linear in the worst case.

Traversal (BFS, DFS): O(n)
 Traversing the entire tree requires visiting each node once, resulting in linear time complexity.
Implementation:
class TreeNode<T> {
left: TreeNode<T>  null;
right: TreeNode<T>  null;
value: T;
constructor(value: T) {
this.left = null;
this.right = null;
this.value = value;
}
}
class BinarySearchTree<T> {
root: TreeNode<T>  null;
constructor() {
this.root = null;
}
insert(value: T): BinarySearchTree<T>  undefined {
const newNode = new TreeNode(value);
if (!this.root) {
this.root = newNode;
return this;
}
let current: TreeNode<T>  null = this.root;
while (true) {
if (value === current.value) return undefined;
if (value < current.value) {
if (!current.left) {
current.left = newNode;
return this;
}
current = current.left;
} else {
if (!current.right) {
current.right = newNode;
return this;
}
current = current.right;
}
}
}
find(value: T): T  1 {
let current: TreeNode<T>  null = this.root;
if (!current) return 1;
while (current) {
if (value === current.value) return current.value;
if (value < current.value) {
current = current.left;
} else {
current = current.right;
}
}
return 1;
}
getMin(): T  undefined {
let current: TreeNode<T>  null = this.root;
while (current?.left) {
current = current.left;
}
return current?.value;
}
getMax(): T  undefined {
let current: TreeNode<T>  null = this.root;
while (current?.right) {
current = current.right;
}
return current?.value;
}
remove(value: T): void {
let current: TreeNode<T>  null = this.root;
this.root = this.removeNode(current, value) as TreeNode<T>;
}
removeNode(node: TreeNode<T>  null, value: T): TreeNode<T>  null {
if (!node) return null;
if (value < node.value) {
node.left = this.removeNode(node.left, value);
} else if (value > node.value) {
node.right = this.removeNode(node.right, value);
} else {
if (!node.left) {
return node.right;
} else if (!node.right) {
return node.left;
}
node.value = this.getMinValue(node.right) as T;
node.right = this.removeNode(node.right, node.value);
}
return node;
}
private getMinValue(node: TreeNode<T>): T  undefined {
let current: TreeNode<T> = node;
while (current.left) {
current = current.left;
}
return current.value;
}
breadthFirstSearch(): T[] {
const queue: TreeNode<T>[] = [];
const visited: T[] = [];
let current: TreeNode<T>  null = this.root;
if (!current) return visited;
queue.push(current);
while (queue.length) {
current = queue.shift() as TreeNode<T>;
visited.push(current.value);
if (current.left) queue.push(current.left);
if (current.right) queue.push(current.right);
}
return visited;
}
depthFirstSearchPreOrder(): T[] {
const visited: T[] = [];
this.traversePreOrder(this.root, visited);
return visited;
}
private traversePreOrder(node: TreeNode<T>  null, visited: T[]): void {
if (node) {
visited.push(node.value);
this.traversePreOrder(node.left, visited);
this.traversePreOrder(node.right, visited);
}
}
depthFirstSearchInOrder(): T[] {
const visited: T[] = [];
this.traverseInOrder(this.root, visited);
return visited;
}
private traverseInOrder(node: TreeNode<T>  null, visited: T[]): void {
if (node) {
this.traverseInOrder(node.left, visited);
visited.push(node.value);
this.traverseInOrder(node.right, visited);
}
}
depthFirstSearchPostOrder(): T[] {
const visited: T[] = [];
this.traversePostOrder(this.root, visited);
return visited;
}
private traversePostOrder(node: TreeNode<T>  null, visited: T[]): void {
if (node) {
this.traversePostOrder(node.left, visited);
this.traversePostOrder(node.right, visited);
visited.push(node.value);
}
}
}
const tree = new BinarySearchTree<number>(); // Generic type in this case it is number type
tree.insert(5);
tree.insert(3);
tree.insert(1);
tree.insert(7);
tree.insert(2);
tree.breadthFirstSearch(); // [ 5, 3, 7, 1, 2 ]
tree.depthFirstSearchPreOrder(); // [ 5, 3, 1, 2, 7 ]
tree.depthFirstSearchInOrder(); // [ 1, 2, 3, 5, 7 ]
tree.depthFirstSearchPostOrder(); // [ 2, 1, 3, 7, 5 ]
tree.getMin(); // 1
tree.getMax(); // 7
// Tree representation
/*
5
3 7
2
1
*/
Graph
Definition:
A Graph is a data structure that consists of a set of vertices and edges, where each edge connects two vertices. It models relationships and connections between entities. Graphs can be directed (edges have a specific direction) or undirected, and they may include weighted edges.
Algorithmic Steps:
/**
* Graph Class Definition:
*  Initialize an adjacency list using a Map to store vertices and their neighbors.
*  Add Vertex: Add a new vertex to the graph.
*  Add Edge: Connect two vertices by adding edges.
*  Remove Vertex: Remove a vertex and its associated edges.
*  Remove Edge: Remove an edge between two vertices.
*  Get Vertices: Return an array of all vertices in the graph.
*  Get Edges: Return an array of all edges in the graph.
*  Has Vertex: Check if a vertex exists in the graph.
*  Has Edge: Check if an edge exists between two vertices.
*  Get Neighbors: Return an array of neighbors for a given vertex.
*  Is Empty: Check if the graph is empty.
*  Clear: Remove all vertices and edges from the graph.
*  Size: Return the number of vertices in the graph.
*  DepthFirst Search: Traverse the graph using depthfirst search.
*  BreadthFirst Search: Traverse the graph using breadthfirst search.
*/
Complexity Analysis:

Add Vertex (AddVertex): O(1)
 Adding a vertex to the graph takes constant time.

Add Edge (AddEdge): O(1)
 Connecting two vertices with an edge takes constant time.

Remove Vertex (RemoveVertex): O(V + E)
 Removing a vertex involves removing its associated edges. The time complexity is proportional to the number of vertices (V) and edges (E) in the graph.

Remove Edge (RemoveEdge): O(1)
 Removing an edge between two vertices takes constant time.

Get Vertices (GetVertices): O(V)
 Obtaining an array of all vertices takes linear time.

Get Edges (GetEdges): O(V + E)
 Obtaining an array of all edges takes time proportional to the number of vertices (V) and edges (E) in the graph.

Has Vertex (HasVertex): O(1)
 Checking if a vertex exists in the graph takes constant time.

Has Edge (HasEdge): O(1)
 Checking if an edge exists between two vertices takes constant time.

Get Neighbors (GetNeighbors): O(1)
 Obtaining the neighbors of a vertex takes constant time.

Is Empty (IsEmpty): O(1)
 Checking if the graph is empty takes constant time.

Clear (Clear): O(1)
 Clearing the graph (removing all vertices and edges) takes constant time.

Size (Size): O(1)
 Obtaining the number of vertices in the graph takes constant time.

DepthFirst Search (DepthFirstSearch): O(V + E)
 Traversing the graph using depthfirst search takes time proportional to the number of vertices (V) and edges (E) in the graph.

BreadthFirst Search (BreadthFirstSearch): O(V + E)
 Traversing the graph using breadthfirst search takes time proportional to the number of vertices (V) and edges (E) in the graph.
Implementation:
class Graph<T> {
private adjacencyList: Map<T, Set<T>>;
constructor() {
this.adjacencyList = new Map();
}
addVertex(vertex: T): this {
if (!this.adjacencyList.has(vertex)) {
this.adjacencyList.set(vertex, new Set());
}
return this;
}
addEdge(vertex1: T, vertex2: T): this {
this.addVertex(vertex1).addVertex(vertex2);
this.adjacencyList.get(vertex1)!.add(vertex2);
this.adjacencyList.get(vertex2)!.add(vertex1);
return this;
}
removeVertex(vertex: T): this {
if (this.adjacencyList.has(vertex)) {
for (const adjacentVertex of this.adjacencyList.get(vertex)!) {
this.removeEdge(vertex, adjacentVertex);
}
this.adjacencyList.delete(vertex);
}
return this;
}
removeEdge(vertex1: T, vertex2: T): this {
if (this.adjacencyList.has(vertex1) && this.adjacencyList.has(vertex2)) {
this.adjacencyList.get(vertex1)!.delete(vertex2);
this.adjacencyList.get(vertex2)!.delete(vertex1);
}
return this;
}
getVertices(): T[] {
return [...this.adjacencyList.keys()];
}
getEdges(): [T, T][] {
const edges: [T, T][] = [];
for (const [vertex, neighbors] of this.adjacencyList) {
for (const neighbor of neighbors) {
edges.push([vertex, neighbor]);
}
}
return edges;
}
hasVertex(vertex: T): boolean {
return this.adjacencyList.has(vertex);
}
hasEdge(vertex1: T, vertex2: T): boolean {
return (
this.adjacencyList.has(vertex1) &&
this.adjacencyList.get(vertex1)!.has(vertex2)
);
}
getNeighbors(vertex: T): T[] {
return [...this.adjacencyList.get(vertex)!];
}
isEmpty(): boolean {
return this.adjacencyList.size === 0;
}
clear(): this {
this.adjacencyList.clear();
return this;
}
size(): number {
return this.adjacencyList.size;
}
depthFirstSearch(startVertex: T, callback: (vertex: T) => void): this {
const visited = new Set<T>();
function traverse(vertex: T): void {
visited.add(vertex);
callback(vertex);
for (const neighbor of this.adjacencyList.get(vertex)!) {
if (!visited.has(neighbor)) {
traverse.call(this, neighbor);
}
}
}
traverse.call(this, startVertex);
return this;
}
breadthFirstSearch(startVertex: T, callback: (vertex: T) => void): this {
const visited = new Set<T>();
const queue: T[] = [startVertex];
visited.add(startVertex);
while (queue.length > 0) {
const currentVertex = queue.shift()!;
callback(currentVertex);
for (const neighbor of this.adjacencyList.get(currentVertex)!) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
return this;
}
}
const graph = new Graph<string>(); // Generic type in this case it is number type
graph
.addVertex("A")
.addVertex("B")
.addVertex("C")
.addEdge("A", "B")
.addEdge("B", "C")
.depthFirstSearch("A", (vertex) => console.log(`Visited ${vertex} in DFS`))
.breadthFirstSearch("A", (vertex) => console.log(`Visited ${vertex} in BFS`));
Thank you for reading this far; your support means a lot! If you have any questions, please don't hesitate to ask in the comments. Don't forget to like and share the article โ your appreciation is highly valued. Your feedback and suggestions are also more than welcome. ๐๐๐
Top comments (2)
You've made your stack have an O(n) performance on insertion and removal because you are using
shift
andunshift
. These operations require the movement of the entire array contents.push
andpop
on an array operate at the other end and require no such operations. Seems odd not to usepush
andpop
for operations you actually called those names.Good catch! I've fixed it, just take a look.