Day 17: Data Structures Explained in a Beginner-Friendly Way

Screenshot:-

Understanding data structures is key to writing efficient code. Today, we’ll explore some fundamental data structures: Linked Lists, Stacks, Queues, Binary Trees, and optionally, Graphs. We’ll break down each data structure with simple examples and code.

Activity 1: Linked List

A Linked List is a collection of nodes where each node points to the next node in the sequence.

Task 1: Node Class

First, create a Node class to represent each element in the linked list.

Example Code:

class Node {
  constructor(value) {
    this.value = value; // Node value
    this.next = null;  // Pointer to the next node
  }
}

Explanation:

• value: Holds the data for the node.

• next: Points to the next node in the list (initially set to null).

Task 2: LinkedList Class

Next, implement a LinkedList class with methods to add, remove, and display nodes.

Example Code:

class LinkedList {
  constructor() {
    this.head = null; // Start with an empty list
  }

  add(value) {
    const newNode = new Node(value);
    if (this.head === null) {
      this.head = newNode;
    } else {
      let current = this.head;
      while (current.next !== null) {
        current = current.next;
      }
      current.next = newNode;
    }
  }

  remove() {
    if (this.head === null) return;
    if (this.head.next === null) {
      this.head = null;
      return;
    }
    let current = this.head;
    while (current.next.next !== null) {
      current = current.next;
    }
    current.next = null;
  }

  display() {
    let current = this.head;
    while (current !== null) {
      console.log(current.value);
      current = current.next;
    }
  }
}

Explanation:

• add(value): Adds a new node with the given value to the end of the list.

• remove(): Removes the last node from the list.

• display(): Prints the values of all nodes in the list.

Activity 2: Stack

A Stack is a collection of elements that follows Last-In-First-Out (LIFO) order.

Task 3: Stack Class

Implement a Stack class with methods to add, remove, and view the top element.

Example Code:

class Stack {
  constructor() {
    this.items = [];
  }

  push(element) {
    this.items.push(element);
  }

  pop() {
    return this.items.pop();
  }

  peek() {
    return this.items[this.items.length - 1];
  }
}

Explanation:

• push(element): Adds an element to the top of the stack.

• pop(): Removes the top element from the stack.

• peek(): Returns the top element without removing it.

Task 4: Reverse a String Using Stack

Use the Stack class to reverse a string by pushing all characters onto the stack and then popping them off.

Example Code:

function reverseString(str) {
  const stack = new Stack();
  for (let char of str) {
    stack.push(char);
  }
  let reversed = '';
  while (stack.peek() !== undefined) {
    reversed += stack.pop();
  }
  return reversed;
}

console.log(reverseString("hello")); // Output: "olleh"

Explanation:

1. Push each character of the string onto the stack.

2. Pop characters from the stack to form the reversed string.

Activity 3: Queue

A Queue is a collection of elements that follows First-In-First-Out (FIFO) order.

Task 5: Queue Class

Implement a Queue class with methods to add, remove, and view the first element.

Example Code:

class Queue {
  constructor() {
    this.items = [];
  }

  enqueue(element) {
    this.items.push(element);
  }

  dequeue() {
    return this.items.shift();
  }

  front() {
    return this.items[0];
  }
}

Explanation:

• enqueue(element): Adds an element to the end of the queue.

• dequeue(): Removes the first element from the queue.

• front(): Returns the first element without removing it.

Task 6: Simulate a Printer Queue

Use the Queue class to simulate a printer queue where print jobs are added and processed.

Example Code:

function printJobs(jobs) {
  const queue = new Queue();
  for (let job of jobs) {
    queue.enqueue(job);
  }
  while (queue.front() !== undefined) {
    console.log(`Printing: ${queue.dequeue()}`);
  }
}

printJobs(["Document1", "Document2", "Document3"]);
// Output:
// Printing: Document1
// Printing: Document2
// Printing: Document3

Explanation:

1. Add print jobs to the queue.

2. Process (print) jobs in the order they were added.

Activity 4: Binary Tree

A Binary Tree is a tree data structure where each node has at most two children (left and right).

Task 7: TreeNode Class

Create a TreeNode class to represent each node in the binary tree.

Example Code:

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

Explanation:

• value: Holds the data for the node.

• left: Points to the left child node.

• right: Points to the right child node.

Task 8: BinaryTree Class

Implement a BinaryTree class with methods for inserting values and performing in-order traversal.

Example Code:

class BinaryTree {
  constructor() {
    this.root = null;
  }

  insert(value) {
    const newNode = new TreeNode(value);
    if (this.root === null) {
      this.root = newNode;
      return;
    }
    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (current.left === null) {
          current.left = newNode;
          return;
        }
        current = current.left;
      } else {
        if (current.right === null) {
          current.right = newNode;
          return;
        }
        current = current.right;
      }
    }
  }

  inOrderTraversal(node = this.root) {
    if (node === null) return;
    this.inOrderTraversal(node.left);
    console.log(node.value);
    this.inOrderTraversal(node.right);
  }
}

Explanation:

• insert(value): Adds a value to the tree, ensuring it goes to the correct position.

• inOrderTraversal(node): Visits nodes in the left subtree, then the current node, and finally the right subtree.

Activity 5: Graph (Optional)

Graphs are used to represent networks where nodes (vertices) are connected by edges.

Task 9: Graph Class

Implement a Graph class with methods to add vertices, add edges, and perform breadth-first search (BFS).

Example Code:

class Graph {
  constructor() {
    this.vertices = {};
  }

  addVertex(vertex) {
    if (!this.vertices[vertex]) {
      this.vertices[vertex] = [];
    }
  }

  addEdge(vertex1, vertex2) {
    if (this.vertices[vertex1] && this.vertices[vertex2]) {
      this.vertices[vertex1].push(vertex2);
      this.vertices[vertex2].push(vertex1); // For undirected graph
    }
  }

  bfs(start) {
    const visited = new Set();
    const queue = [start];
    while (queue.length > 0) {
      const vertex = queue.shift();
      if (!visited.has(vertex)) {
        visited.add(vertex);
        console.log(vertex);
        queue.push(...this.vertices[vertex]);
      }
    }
  }
}

Explanation:

• addVertex(vertex): Adds a vertex to the graph.

• addEdge(vertex1, vertex2): Connects two vertices with an edge.

• bfs(start): Performs a breadth-first search starting from a vertex.

Task 10: Simple Network Example

Use the Graph class to represent a simple network and perform BFS.

Example Code:

const network = new Graph();
network.addVertex("A");
network.addVertex("B");
network.addVertex("C");
network.addEdge("A", "B");
network.addEdge("A", "C");

network.bfs("A"); // Output: A B C

Explanation:

1. Add vertices to represent nodes in the network.

2. Add edges to represent connections.

3. Perform BFS to explore nodes starting from a given node.

Conclusion

By implementing and using these data structures, you'll gain a solid understanding of how to manage and manipulate data efficiently. Practice these concepts to build a strong foundation in computer science. Happy coding!