Data-Structures-JavaScript.md

Data Structures and Algorithms: Core Concepts and JavaScript Implementations

This document covers fundamental data structures and algorithms, including Binary Trees, Graphs, Stacks, Queues, Linked Lists, Hash Tables, Sorting, and an introduction to Recursion. Each section explains the concept and provides a JavaScript class implementation with example usage.

Binary Trees

Concept

A Binary Tree is a hierarchical data structure where each node has at most two children, referred to as the left child and the right child. It is commonly used for searching, hierarchical data representation, and efficient insertion/deletion operations. Key properties include:

• Root: The topmost node.
• Leaf: A node with no children.
• Height: The length of the longest path from the root to a leaf.
• Traversal: Common methods include in-order, pre-order, and post-order.

Implementation

Below is a JavaScript class for a Binary Tree with a Node class and methods for insertion and in-order traversal.

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

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

  // Insert a value into the binary tree
  insert(value) {
    const newNode = new Node(value);
    if (!this.root) {
      this.root = newNode;
      return this;
    }
    let current = this.root;
    while (true) {
      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;
      }
    }
  }

  // In-order traversal (left, root, right)
  inOrder() {
    const result = [];
    function traverse(node) {
      if (node) {
        traverse(node.left);
        result.push(node.value);
        traverse(node.right);
      }
    }
    traverse(this.root);
    return result;
  }
}

// Example usage
const bt = new BinaryTree();
bt.insert(10).insert(5).insert(15).insert(3).insert(7);
console.log(bt.inOrder()); // Output: [3, 5, 7, 10, 15]

Graphs

Concept

A Graph is a collection of nodes (vertices) connected by edges. Graphs can be directed or undirected, weighted or unweighted. They are used in networks, social media analysis, and shortest-path algorithms. Key concepts:

• Adjacency List: Represents edges as a list for each vertex.
• Adjacency Matrix: A 2D array where entries indicate edges.
• Common algorithms include Depth-First Search (DFS) and Breadth-First Search (BFS).

Implementation

Below is a JavaScript class for an undirected Graph using an adjacency list with methods for adding vertices/edges and performing DFS.

class Graph {
  constructor() {
    this.adjacencyList = new Map();
  }

  // Add a vertex
  addVertex(vertex) {
    if (!this.adjacencyList.has(vertex)) {
      this.adjacencyList.set(vertex, []);
    }
  }

  // Add an edge between two vertices
  addEdge(vertex1, vertex2) {
    this.addVertex(vertex1);
    this.addVertex(vertex2);
    this.adjacencyList.get(vertex1).push(vertex2);
    this.adjacencyList.get(vertex2).push(vertex1); // Undirected
  }

  // Depth-First Search
  dfs(start) {
    const result = [];
    const visited = new Set();
    const adjacencyList = this.adjacencyList;

    function dfsHelper(vertex) {
      if (!vertex) return;
      visited.add(vertex);
      result.push(vertex);
      const neighbors = adjacencyList.get(vertex);
      for (const neighbor of neighbors) {
        if (!visited.has(neighbor)) {
          dfsHelper(neighbor);
        }
      }
    }

    dfsHelper(start);
    return result;
  }
}

// Example usage
const g = new Graph();
g.addEdge('A', 'B');
g.addEdge('A', 'C');
g.addEdge('B', 'D');
g.addEdge('C', 'E');
console.log(g.dfs('A')); // Output: ['A', 'B', 'D', 'C', 'E']

Stacks

Concept

A Stack is a linear data structure following the Last-In-First-Out (LIFO) principle. Elements are added (pushed) and removed (popped) from the top. Stacks are used in function call management, undo mechanisms, and expression parsing.

Implementation

Below is a JavaScript class for a Stack with push, pop, and peek methods.

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

  // Add element to the top
  push(element) {
    this.items.push(element);
  }

  // Remove and return the top element
  pop() {
    if (this.isEmpty()) return null;
    return this.items.pop();
  }

  // Return the top element without removing it
  peek() {
    if (this.isEmpty()) return null;
    return this.items[this.items.length - 1];
  }

  // Check if stack is empty
  isEmpty() {
    return this.items.length === 0;
  }
}

// Example usage
const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop()); // Output: 3
console.log(stack.peek()); // Output: 2

Queues

Concept

A Queue is a linear data structure following the First-In-First-Out (FIFO) principle. Elements are added (enqueued) at the rear and removed (dequeued) from the front. Queues are used in task scheduling, breadth-first search, and resource sharing.

Implementation

Below is a JavaScript class for a Queue with enqueue, dequeue, and front methods.

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

  // Add element to the rear
  enqueue(element) {
    this.items.push(element);
  }

  // Remove and return the front element
  dequeue() {
    if (this.isEmpty()) return null;
    return this.items.shift();
  }

  // Return the front element without removing it
  front() {
    if (this.isEmpty()) return null;
    return this.items[0];
  }

  // Check if queue is empty
  isEmpty() {
    return this.items.length === 0;
  }
}

// Example usage
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
console.log(queue.dequeue()); // Output: 1
console.log(queue.front()); // Output: 2

Linked Lists

Concept

A Linked List is a linear data structure where elements (nodes) are stored non-contiguously, each containing a value and a reference to the next node. Types include singly and doubly linked lists. They are used for dynamic memory allocation and efficient insertions/deletions.

Implementation

Below is a JavaScript class for a Singly Linked List with methods for appending and displaying nodes.

class ListNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
  }

  // Append a node to the end
  append(value) {
    const newNode = new ListNode(value);
    if (!this.head) {
      this.head = newNode;
      return this;
    }
    let current = this.head;
    while (current.next) {
      current = current.next;
    }
    current.next = newNode;
    return this;
  }

  // Display all nodes
  display() {
    const result = [];
    let current = this.head;
    while (current) {
      result.push(current.value);
      current = current.next;
    }
    return result;
  }
}

// Example usage
const ll = new LinkedList();
ll.append(1).append(2).append(3);
console.log(ll.display()); // Output: [1, 2, 3]

Hash Tables

Concept

A Hash Table is a data structure that maps keys to values using a hash function to compute an index into an array. It provides average-case O(1) time complexity for lookups, insertions, and deletions. Collisions are handled using techniques like chaining or open addressing.

Implementation

Below is a JavaScript class for a Hash Table using chaining (linked lists for collisions).

class HashTable {
  constructor(size = 53) {
    this.keyMap = new Array(size);
  }

  // Hash function
  _hash(key) {
    let total = 0;
    const prime = 31;
    for (let i = 0; i < Math.min(key.length, 100); i++) {
      let char = key[i];
      let value = char.charCodeAt(0) - 96;
      total = (total * prime + value) % this.keyMap.length;
    }
    return total;
  }

  // Set key-value pair
  set(key, value) {
    const index = this._hash(key);
    if (!this.keyMap[index]) {
      this.keyMap[index] = [];
    }
    this.keyMap[index].push([key, value]);
  }

  // Get value by key
  get(key) {
    const index = this._hash(key);
    if (this.keyMap[index]) {
      for (let [k, v] of this.keyMap[index]) {
        if (k === key) return v;
      }
    }
    return undefined;
  }
}

// Example usage
const ht = new HashTable();
ht.set("hello", "world");
ht.set("name", "Grok");
console.log(ht.get("hello")); // Output: world
console.log(ht.get("name")); // Output: Grok

Sorting

Concept

Sorting arranges elements in a specific order (e.g., ascending or descending). Common algorithms include:

• Bubble Sort: Repeatedly swaps adjacent elements if out of order (O(n²)).
• Quick Sort: Partitions the array and recursively sorts (average O(n log n)).
• Merge Sort: Divides the array, sorts, and merges (O(n log n)).

Implementation

Below is a JavaScript implementation of Quick Sort.

class Sorting {
  // Quick Sort
  quickSort(arr) {
    if (arr.length <= 1) return arr;
    
    const pivot = arr[Math.floor(arr.length / 2)];
    const left = [];
    const right = [];
    const equal = [];

    for (let element of arr) {
      if (element < pivot) left.push(element);
      else if (element > pivot) right.push(element);
      else equal.push(element);
    }

    return [
      ...this.quickSort(left),
      ...equal,
      ...this.quickSort(right)
    ];
  }
}

// Example usage
const sorter = new Sorting();
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log(sorter.quickSort(arr)); // Output: [11, 12, 22, 25, 34, 64, 90]

Introduction to Recursion

Concept

Recursion is a process where a function calls itself to solve smaller instances of the same problem. It consists of:

• Base Case: The condition to stop recursion.
• Recursive Case: The part where the function calls itself. Recursion is used in problems like tree traversals, factorial calculation, and divide-and-conquer algorithms.

Implementation

Below is a JavaScript class demonstrating recursion with a factorial function.

class Recursion {
  // Calculate factorial
  factorial(n) {
    // Base case
    if (n <= 1) return 1;
    // Recursive case
    return n * this.factorial(n - 1);
  }
}

// Example usage
const rec = new Recursion();
console.log(rec.factorial(5)); // Output: 120

Conclusion

These data structures and algorithms form the foundation of computer science. The JavaScript implementations provided demonstrate their core functionality. Practice using these structures in different scenarios to deepen your understanding.