# Data Structures and Associated Algorithms

## Introductions​

We are going to cover some of the data structures which are commonly used in algorithms, and which are not the super common ones like arrays, strings, and objects. We will also cover some of the algorithms that are associated with these data structures.

Definition: A series of nodes, where each node contains data and a reference to the next node.

Key Operations: Insertion/Deletion (O(1)), Access (O(n))

Use Cases: Implementing dynamic data structures, like stacks and queues.

Code Sample:

``class Node {  constructor(data) {    this.data = data;    this.next = null;  }}class LinkedList {  constructor() {    this.head = null;  }  // Insert at the beginning  insertAtBeginning(data) {    const newNode = new Node(data);    newNode.next = this.head;    this.head = newNode;  }  // Insert at the end  insertAtEnd(data) {    const newNode = new Node(data);    if (!this.head) {      this.head = newNode;      return;    }    let current = this.head;    while (current.next) {      current = current.next;    }    current.next = newNode;  }  // Delete by value  deleteByValue(data) {    if (!this.head) return;    if (this.head.data === data) {      this.head = this.head.next;      return;    }    let current = this.head;    while (current.next && current.next.data !== data) {      current = current.next;    }    if (current.next) {      current.next = current.next.next;    }  }  // Traverse and print the list  printList() {    let current = this.head;    while (current) {      console.log(current.data);      current = current.next;    }  }}// Usage exampleconst list = new LinkedList();list.insertAtBeginning(10);list.insertAtBeginning(20);list.insertAtEnd(30);list.printList(); // Output: 20 10 30list.deleteByValue(10);list.printList(); // Output: 20 30``

## Stacks and Queues​

Stacks and queues are abstract data types built on arrays or linked lists, used for handling collections in a specific order.

### Stacks​

Definition: A collection following Last-In-First-Out (LIFO) principle.

The simplest way to implement a stack is using an array, add to it with `push()` and remove from it with `pop()`.

### Queues​

Definition: A collection following First-In-First-Out (FIFO) principle.

Key Operations: Enqueue (O(1)), Dequeue (O(1))

The simplest way to implement a queue is an array, add to it with `push()` and remove from it with `shift()`.

## Binary Trees, Binary Search Trees (BST)​

Binary trees are hierarchical structures, with each node having at most two children. Binary search trees (BSTs) are a specialized form where each node's left subtree contains values less than the node, and the right subtree contains values greater.

### Binary Trees​

Definition: A tree where each node has up to two children.

Key Operations: Traversal (O(n)), Insertion/Deletion (O(log n) in balanced trees)

Use Cases: Hierarchical data representation, expression parsing.

Code Sample:

``class Node {  constructor(data) {    this.data = data;    this.left = null;    this.right = null;  }}class BinaryTree {  constructor() {    this.root = null;  }  // Insert a node in the binary tree  insert(data) {    const newNode = new Node(data);    if (!this.root) {      this.root = newNode;    } else {      this.insertNode(this.root, newNode);    }  }  insertNode(node, newNode) {    if (newNode.data < node.data) {      if (!node.left) {        node.left = newNode;      } else {        this.insertNode(node.left, newNode);      }    } else {      if (!node.right) {        node.right = newNode;      } else {        this.insertNode(node.right, newNode);      }    }  }  // In-order traversal (Left, Root, Right)  inOrderTraversal(node) {    if (node) {      this.inOrderTraversal(node.left);      console.log(node.data);      this.inOrderTraversal(node.right);    }  }  // Pre-order traversal (Root, Left, Right)  preOrderTraversal(node) {    if (node) {      console.log(node.data);      this.preOrderTraversal(node.left);      this.preOrderTraversal(node.right);    }  }  // Post-order traversal (Left, Right, Root)  postOrderTraversal(node) {    if (node) {      this.postOrderTraversal(node.left);      this.postOrderTraversal(node.right);      console.log(node.data);    }  }  // Find a node  find(data) {    return this.findNode(this.root, data);  }  findNode(node, data) {    if (!node) {      return null;    }    if (data < node.data) {      return this.findNode(node.left, data);    } else if (data > node.data) {      return this.findNode(node.right, data);    } else {      return node;    }  }}// Usage exampleconst binaryTree = new BinaryTree();binaryTree.insert(15);binaryTree.insert(25);binaryTree.insert(10);binaryTree.insert(7);binaryTree.insert(22);binaryTree.insert(17);binaryTree.insert(13);binaryTree.insert(5);binaryTree.insert(9);binaryTree.insert(27);console.log('In-order Traversal:');binaryTree.inOrderTraversal(binaryTree.root); // Output: 5 7 9 10 13 15 17 22 25 27console.log('Pre-order Traversal:');binaryTree.preOrderTraversal(binaryTree.root); // Output: 15 10 7 5 9 13 25 22 17 27console.log('Post-order Traversal:');binaryTree.postOrderTraversal(binaryTree.root); // Output: 5 9 7 13 10 17 22 27 25 15console.log('Find Node with data 22:');const foundNode = binaryTree.find(22);if (foundNode) {  console.log('Node found:', foundNode.data); // Output: Node found: 22} else {  console.log('Node not found');}``

### Binary Search Trees (BST)​

Definition: A binary tree with ordered nodes.

Key Operations: Search (O(log n)), Insertion/Deletion (O(log n))

Use Cases: Efficient searching and sorting.

Code Sample:

``class Node {  constructor(data) {    this.data = data;    this.left = null;    this.right = null;  }}class BinarySearchTree {  constructor() {    this.root = null;  }  // Insert a node in the BST  insert(data) {    const newNode = new Node(data);    if (!this.root) {      this.root = newNode;    } else {      this.insertNode(this.root, newNode);    }  }  insertNode(node, newNode) {    if (newNode.data < node.data) {      if (!node.left) {        node.left = newNode;      } else {        this.insertNode(node.left, newNode);      }    } else {      if (!node.right) {        node.right = newNode;      } else {        this.insertNode(node.right, newNode);      }    }  }  // Search for a node with a given data  search(node, data) {    if (!node) {      return null;    }    if (data < node.data) {      return this.search(node.left, data);    } else if (data > node.data) {      return this.search(node.right, data);    } else {      return node;    }  }  // Delete a node with a given data  delete(data) {    this.root = this.deleteNode(this.root, data);  }  deleteNode(node, data) {    if (!node) {      return null;    }    if (data < node.data) {      node.left = this.deleteNode(node.left, data);      return node;    } else if (data > node.data) {      node.right = this.deleteNode(node.right, data);      return node;    } else {      // Node to be deleted found      // Case 1: No children (leaf node)      if (!node.left && !node.right) {        node = null;        return node;      }      // Case 2: One child      if (!node.left) {        return node.right;      } else if (!node.right) {        return node.left;      }      // Case 3: Two children      const aux = this.findMinNode(node.right);      node.data = aux.data;      node.right = this.deleteNode(node.right, aux.data);      return node;    }  }  // Find the minimum node in the tree/subtree  findMinNode(node) {    while (node.left) {      node = node.left;    }    return node;  }  // In-order traversal (Left, Root, Right)  inOrderTraversal(node) {    if (node) {      this.inOrderTraversal(node.left);      console.log(node.data);      this.inOrderTraversal(node.right);    }  }}// Usage exampleconst bst = new BinarySearchTree();bst.insert(15);bst.insert(25);bst.insert(10);bst.insert(7);bst.insert(22);bst.insert(17);bst.insert(13);bst.insert(5);bst.insert(9);bst.insert(27);console.log('In-order Traversal:');bst.inOrderTraversal(bst.root); // Output: 5 7 9 10 13 15 17 22 25 27console.log('Search for 22:');const foundNode = bst.search(bst.root, 22);if (foundNode) {  console.log('Node found:', foundNode.data); // Output: Node found: 22} else {  console.log('Node not found');}console.log('Delete 22:');bst.delete(22);bst.inOrderTraversal(bst.root); // Output: 5 7 9 10 13 15 17 25 27``

## Heaps and Priority Queues​

Heaps are a special tree-based structure satisfying the heap property, where each parent node is greater (max-heap) or lesser (min-heap) than its children. Priority queues are abstract data types built on heaps.

### Heaps​

Definition: A complete binary tree maintaining the heap property.

JavaScript does not have a built in heap data structure, but you can implement one using arrays. There are also libraries like `heap.js` that provide heap implementations.

Key Operations: Insertion (O(log n)), Extract Max/Min (O(log n))

Use Cases: Implementing priority queues, heap sort.

Code Sample:

``class MinHeap {  constructor() {    this.heap = [];  }  // Get the parent index of a node  getParentIndex(index) {    return Math.floor((index - 1) / 2);  }  // Get the left child index of a node  getLeftChildIndex(index) {    return 2 * index + 1;  }  // Get the right child index of a node  getRightChildIndex(index) {    return 2 * index + 2;  }  // Swap two nodes in the heap  swap(index1, index2) {    [this.heap[index1], this.heap[index2]] = [      this.heap[index2],      this.heap[index1],    ];  }  // Insert a node into the heap (O(log n))  insert(data) {    this.heap.push(data);    this.heapifyUp(this.heap.length - 1);  }  // Heapify up to maintain the heap property  heapifyUp(index) {    let currentIndex = index;    let parentIndex = this.getParentIndex(currentIndex);    while (      currentIndex > 0 &&      this.heap[currentIndex] < this.heap[parentIndex]    ) {      this.swap(currentIndex, parentIndex);      currentIndex = parentIndex;      parentIndex = this.getParentIndex(currentIndex);    }  }  // Extract the minimum element (O(log n))  extractMin() {    if (this.heap.length === 0) {      console.log('Heap is empty');      return null;    }    if (this.heap.length === 1) {      return this.heap.pop();    }    const min = this.heap[0];    this.heap[0] = this.heap.pop();    this.heapifyDown(0);    return min;  }  // Heapify down to maintain the heap property  heapifyDown(index) {    let smallest = index;    const leftChildIndex = this.getLeftChildIndex(index);    const rightChildIndex = this.getRightChildIndex(index);    if (      leftChildIndex < this.heap.length &&      this.heap[leftChildIndex] < this.heap[smallest]    ) {      smallest = leftChildIndex;    }    if (      rightChildIndex < this.heap.length &&      this.heap[rightChildIndex] < this.heap[smallest]    ) {      smallest = rightChildIndex;    }    if (smallest !== index) {      this.swap(index, smallest);      this.heapifyDown(smallest);    }  }  // Print the heap  printHeap() {    console.log(this.heap);  }}// Usage exampleconst minHeap = new MinHeap();minHeap.insert(10);minHeap.insert(20);minHeap.insert(5);minHeap.insert(6);minHeap.insert(1);minHeap.insert(8);minHeap.insert(9);minHeap.printHeap(); // Output: [ 1, 6, 5, 20, 10, 8, 9 ]console.log('Extracted Min:', minHeap.extractMin()); // Output: Extracted Min: 1minHeap.printHeap(); // Output: [ 5, 6, 8, 20, 10, 9 ]``

### Priority Queues​

Definition: An abstract data type where each element has a priority.

Key Operations: Insert (O(log n)), Extract Max/Min (O(log n))

Use Cases: Scheduling algorithms, Dijkstra's algorithm.

Code Sample:

``class MinHeap {  constructor() {    this.heap = [];  }  // Get the parent index of a node  getParentIndex(index) {    return Math.floor((index - 1) / 2);  }  // Get the left child index of a node  getLeftChildIndex(index) {    return 2 * index + 1;  }  // Get the right child index of a node  getRightChildIndex(index) {    return 2 * index + 2;  }  // Swap two nodes in the heap  swap(index1, index2) {    [this.heap[index1], this.heap[index2]] = [      this.heap[index2],      this.heap[index1],    ];  }  // Insert a node into the heap (O(log n))  insert(data) {    this.heap.push(data);    this.heapifyUp(this.heap.length - 1);  }  // Heapify up to maintain the heap property  heapifyUp(index) {    let currentIndex = index;    let parentIndex = this.getParentIndex(currentIndex);    while (      currentIndex > 0 &&      this.heap[currentIndex].priority < this.heap[parentIndex].priority    ) {      this.swap(currentIndex, parentIndex);      currentIndex = parentIndex;      parentIndex = this.getParentIndex(currentIndex);    }  }  // Extract the minimum element (O(log n))  extractMin() {    if (this.heap.length === 0) {      console.log('Heap is empty');      return null;    }    if (this.heap.length === 1) {      return this.heap.pop();    }    const min = this.heap[0];    this.heap[0] = this.heap.pop();    this.heapifyDown(0);    return min;  }  // Heapify down to maintain the heap property  heapifyDown(index) {    let smallest = index;    const leftChildIndex = this.getLeftChildIndex(index);    const rightChildIndex = this.getRightChildIndex(index);    if (      leftChildIndex < this.heap.length &&      this.heap[leftChildIndex].priority < this.heap[smallest].priority    ) {      smallest = leftChildIndex;    }    if (      rightChildIndex < this.heap.length &&      this.heap[rightChildIndex].priority < this.heap[smallest].priority    ) {      smallest = rightChildIndex;    }    if (smallest !== index) {      this.swap(index, smallest);      this.heapifyDown(smallest);    }  }  // Print the heap  printHeap() {    console.log(this.heap);  }}class PriorityQueue {  constructor() {    this.minHeap = new MinHeap();  }  // Insert an element with a priority  insert(element, priority) {    this.minHeap.insert({element, priority});  }  // Extract the element with the highest priority (minimum priority value)  extractMin() {    return this.minHeap.extractMin();  }  // Print the priority queue  printQueue() {    this.minHeap.printHeap();  }}// Usage exampleconst pq = new PriorityQueue();pq.insert('Task 1', 3);pq.insert('Task 2', 1);pq.insert('Task 3', 2);pq.printQueue(); // Output: [ { element: 'Task 2', priority: 1 }, { element: 'Task 1', priority: 3 }, { element: 'Task 3', priority: 2 } ]console.log('Extracted Min:', pq.extractMin()); // Output: Extracted Min: { element: 'Task 2', priority: 1 }pq.printQueue(); // Output: [ { element: 'Task 3', priority: 2 }, { element: 'Task 1', priority: 3 } ]``

## Hash Tables​

Hash tables are powerful data structures that map keys to values using a hash function. They provide average-case constant-time complexity for search, insertion, and deletion.

In JavaScript, Hash Tables are implemented using Objects or Maps.

Definition: A data structure that uses a hash function to map keys to buckets.

Key Operations: Insertion/Deletion/Lookup (O(1) average case)

Use Cases: Fast data retrieval, implementing associative arrays.

## Graphs​

Graphs represent networks of nodes (vertices) connected by edges. They are versatile structures used to model relationships and paths.

Definition: A 2D array representing graph connections.

Key Operations: Edge Check (O(1)), Space Complexity (O(V^2))

Use Cases: Dense graphs, algorithms requiring quick edge checks.

Code Sample:

``class Graph {  constructor(size) {    this.size = size;    this.adjacencyMatrix = Array.from({length: size}, () =>      Array(size).fill(0),    );  }  // Add an edge to the graph  addEdge(vertex1, vertex2) {    if (vertex1 < this.size && vertex2 < this.size) {      this.adjacencyMatrix[vertex1][vertex2] = 1;      this.adjacencyMatrix[vertex2][vertex1] = 1; // For undirected graph    }  }  // Remove an edge from the graph  removeEdge(vertex1, vertex2) {    if (vertex1 < this.size && vertex2 < this.size) {      this.adjacencyMatrix[vertex1][vertex2] = 0;      this.adjacencyMatrix[vertex2][vertex1] = 0; // For undirected graph    }  }  // Check if there is an edge between two vertices  hasEdge(vertex1, vertex2) {    if (vertex1 < this.size && vertex2 < this.size) {      return this.adjacencyMatrix[vertex1][vertex2] === 1;    }    return false;  }  // Print the adjacency matrix  printMatrix() {    console.log(this.adjacencyMatrix);  }}// Usage exampleconst graph = new Graph(5);graph.addEdge(0, 1);graph.addEdge(0, 2);graph.addEdge(1, 2);graph.addEdge(1, 3);graph.addEdge(2, 4);console.log('Adjacency Matrix:');graph.printMatrix();// Output:// [//   [0, 1, 1, 0, 0],//   [1, 0, 1, 1, 0],//   [1, 1, 0, 0, 1],//   [0, 1, 0, 0, 0],//   [0, 0, 1, 0, 0]// ]console.log('Edge between 0 and 1:', graph.hasEdge(0, 1)); // Output: trueconsole.log('Edge between 0 and 3:', graph.hasEdge(0, 3)); // Output: falsegraph.removeEdge(0, 1);console.log('Adjacency Matrix after removing edge between 0 and 1:');graph.printMatrix();// Output:// [//   [0, 0, 1, 0, 0],//   [0, 0, 1, 1, 0],//   [1, 1, 0, 0, 1],//   [0, 1, 0, 0, 0],//   [0, 0, 1, 0, 0]// ]``

Definition: An array of lists, where each list represents connections of a node.

Key Operations: Edge Check (O(V)), Space Complexity (O(V + E))

Use Cases: Sparse graphs, algorithms focusing on traversal.

Code Sample:

``class Graph {  constructor() {    this.adjacencyList = new Map();  }  // Add a vertex to the graph  addVertex(vertex) {    if (!this.adjacencyList.has(vertex)) {      this.adjacencyList.set(vertex, []);    }  }  // Add an edge to the graph  addEdge(vertex1, vertex2) {    if (!this.adjacencyList.has(vertex1)) {      this.addVertex(vertex1);    }    if (!this.adjacencyList.has(vertex2)) {      this.addVertex(vertex2);    }    this.adjacencyList.get(vertex1).push(vertex2);    this.adjacencyList.get(vertex2).push(vertex1); // For undirected graph  }  // Remove an edge from the graph  removeEdge(vertex1, vertex2) {    if (this.adjacencyList.has(vertex1)) {      this.adjacencyList.set(        vertex1,        this.adjacencyList.get(vertex1).filter((v) => v !== vertex2),      );    }    if (this.adjacencyList.has(vertex2)) {      this.adjacencyList.set(        vertex2,        this.adjacencyList.get(vertex2).filter((v) => v !== vertex1),      );    }  }  // Check if there is an edge between two vertices  hasEdge(vertex1, vertex2) {    if (this.adjacencyList.has(vertex1)) {      return this.adjacencyList.get(vertex1).includes(vertex2);    }    return false;  }  // Print the adjacency list  printGraph() {    const keys = this.adjacencyList.keys();    for (let key of keys) {      const values = this.adjacencyList.get(key);      console.log(`\${key} -> \${values.join(', ')}`);    }  }}// Usage exampleconst graph = new Graph();graph.addVertex('A');graph.addVertex('B');graph.addVertex('C');graph.addVertex('D');graph.addEdge('A', 'B');graph.addEdge('A', 'C');graph.addEdge('B', 'D');graph.addEdge('C', 'D');console.log('Adjacency List:');graph.printGraph();// Output:// A -> B, C// B -> A, D// C -> A, D// D -> B, Cconsole.log('Edge between A and B:', graph.hasEdge('A', 'B')); // Output: trueconsole.log('Edge between A and D:', graph.hasEdge('A', 'D')); // Output: falsegraph.removeEdge('A', 'B');console.log('Adjacency List after removing edge between A and B:');graph.printGraph();// Output:// A -> C// B -> D// C -> A, D// D -> B, C``

## Union-Find (Disjoint Set)​

The Union-Find data structure manages a partition of a set into disjoint subsets, supporting efficient union and find operations. It's crucial in network connectivity and Kruskal's algorithm for minimum spanning trees.

Definition: A data structure for tracking a set of elements split into disjoint subsets.

Key Operations: Find (O(α(n))), Union (O(α(n)))

Use Cases: Network connectivity, Kruskal's algorithm.

Code Sample:

``class UnionFind {  constructor(size) {    this.parent = Array.from({length: size}, (_, index) => index);    this.rank = Array(size).fill(0);  }  // Find the root of the set containing element x with path compression  find(x) {    if (this.parent[x] !== x) {      this.parent[x] = this.find(this.parent[x]); // Path compression    }    return this.parent[x];  }  // Union two sets by rank  union(x, y) {    const rootX = this.find(x);    const rootY = this.find(y);    if (rootX !== rootY) {      // Union by rank      if (this.rank[rootX] > this.rank[rootY]) {        this.parent[rootY] = rootX;      } else if (this.rank[rootX] < this.rank[rootY]) {        this.parent[rootX] = rootY;      } else {        this.parent[rootY] = rootX;        this.rank[rootX]++;      }    }  }  // Check if two elements are in the same set  connected(x, y) {    return this.find(x) === this.find(y);  }}// Usage exampleconst uf = new UnionFind(10);uf.union(1, 2);uf.union(2, 3);uf.union(4, 5);uf.union(6, 7);console.log('1 and 3 connected?', uf.connected(1, 3)); // Output: trueconsole.log('1 and 4 connected?', uf.connected(1, 4)); // Output: falseuf.union(3, 4);console.log('1 and 5 connected?', uf.connected(1, 5)); // Output: true``

Explanation:

1. Initialization:
• parent: An array where parent[i] is the parent of i. Initially, each element is its own parent.
• rank: An array to keep track of the rank (approximate depth) of each tree.
1. Find:

This method finds the root of the set containing x and applies path compression, which flattens the structure of the tree whenever find is called. This helps in speeding up future operations.

1. Union:

This method unites the sets containing x and y by connecting the roots of the trees. Union by rank attaches the shorter tree under the root of the taller tree to keep the tree as flat as possible.

1. Connected:

This method checks if two elements are in the same set by comparing their roots.

# Automated Amazon Reports

Automatically download Amazon Seller and Advertising reports to a private database. View beautiful, on demand, exportable performance reports.