DEV Community

Cover image for Data Structures Implementation in JavaScript or TypeScript
bugudiramu
bugudiramu

Posted on

Data Structures Implementation in JavaScript or TypeScript

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 problem-solving 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.
 */
Enter fullscreen mode Exit fullscreen mode

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 constant-time 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());
Enter fullscreen mode Exit fullscreen mode

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.
 */
Enter fullscreen mode Exit fullscreen mode

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 constant-time 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());
Enter fullscreen mode Exit fullscreen mode

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 priority-value 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.
 */
Enter fullscreen mode Exit fullscreen mode

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 constant-time 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 constant-time 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());
Enter fullscreen mode Exit fullscreen mode

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.
 */
Enter fullscreen mode Exit fullscreen mode

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);
Enter fullscreen mode Exit fullscreen mode

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 breadth-first order and return an array of values.
 * - DepthFirstSearchPreOrder: Traverse the tree in pre-order and return an array of values.
 * - DepthFirstSearchInOrder: Traverse the tree in in-order and return an array of values.
 * - DepthFirstSearchPostOrder: Traverse the tree in post-order and return an array of values.
 */
Enter fullscreen mode Exit fullscreen mode

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
*/
Enter fullscreen mode Exit fullscreen mode

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.
 * - Depth-First Search: Traverse the graph using depth-first search.
 * - Breadth-First Search: Traverse the graph using breadth-first search.
 */
Enter fullscreen mode Exit fullscreen mode

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.
  • Depth-First Search (DepthFirstSearch): O(V + E)

    • Traversing the graph using depth-first search takes time proportional to the number of vertices (V) and edges (E) in the graph.
  • Breadth-First Search (BreadthFirstSearch): O(V + E)

    • Traversing the graph using breadth-first 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`));
Enter fullscreen mode Exit fullscreen mode

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)

Collapse
 
miketalbot profile image
Mike Talbot โญ • Edited

You've made your stack have an O(n) performance on insertion and removal because you are using shift and unshift. These operations require the movement of the entire array contents. push and pop on an array operate at the other end and require no such operations. Seems odd not to use push and pop for operations you actually called those names.

Collapse
 
bugudiramu profile image
bugudiramu

Good catch! I've fixed it, just take a look.