Data Structure

Data Structure, We can define it as a way of collecting and organizing data in memory, this way will make performing operations on the data more efficient and easier.

Types

logo

When we can consider the algorithm efficient?

The algorithm is considered to be efficient and has a high performance, If it consumes less time and fewer memory locations during its execution until its completion, and that highlights the terms “Time Complexity” and “Space Complexity” and makes them come to the surface to understand the performance of any algorithm.

Arrays

Arrays store multiple values of the same data type. You can perform various operations on arrays.

int numbers[5] = {1, 2, 3, 4, 5};

Operations:

  • Accessing elements by index
  • Insertion and deletion of elements
  • Searching for an element
  • Updating elements

Important Algorithm:

Linear Search and Binary Search

Recursion and Merge Sort

Recursion

Recursion is a programming technique where a function calls itself to solve a problem. It's particularly useful for solving problems with similar subproblems. Here's an example of a simple recursive function to calculate the factorial of a number:

int factorial(int n) {
          if (n == 0) {
              return 1;
          } else {
              return n * factorial(n - 1);
          }
      }

      int main() {
          int n = 5;
          int result = factorial(n);
          std::cout << "Factorial of " << n << " is " << result << std::endl;
          return 0;
      }

Merge Sort

Merge Sort is a popular sorting algorithm that utilizes the divide-and-conquer strategy. It divides an array into two halves, sorts them separately, and then merges them back together. Here's an example of the Merge Sort algorithm how it works:

logo

Linked Lists

Linked lists are dynamic data structures used to store a collection of elements. They offer various operations.

class Node {
    public:
        int data;
        Node* next;
};

// Linked List operations
// Insertion, Deletion, Traversal, etc.

Operations:

  • Insertion and deletion of nodes
  • Traversing the linked list
  • Searching for a specific value

Important Algorithm:

Floyd's Cycle Detection Algorithm (Tortoise and Hare)

Stacks

Stacks are used for managing data in a Last-In-First-Out (LIFO) order. They support common stack operations.

#include <stack>

std::stack<int> stack;

stack.push(1);
stack.push(2);
int top = stack.top();
stack.pop();

Operations:

  • Push (Add element to the top)
  • Pop (Remove the top element)
  • Peek (Get the top element without removing)

Important Algorithm:

Infix to Postfix Conversion (used in expression evaluation)

Queues

Queues are used for managing data in a First-In-First-Out (FIFO) order. They support common queue operations.

#include <queue>

std::queue<int> queue;

queue.push(1);
queue.push(2);
int front = queue.front();
queue.pop();

Operations:

  • Enqueue (Add element to the rear)
  • Dequeue (Remove the front element)
  • Front (Get the front element without removing)

Important Algorithm:

Breadth-First Search (BFS) for graph traversal

Binary Trees

Binary trees are hierarchical data structures. You can perform various operations on binary trees.

class TreeNode {
    public:
        int data;
        TreeNode* left;
        TreeNode* right;
};

// Binary Tree operations
// Insertion, Traversal, etc.

Operations:

  • Insertion of nodes
  • Traversing the binary tree (preorder, inorder, postorder)
  • Searching for a specific value

Important Algorithm:

Depth-First Search (DFS) for graph traversal

Binary Search Trees (BST)

Binary Search Trees are binary trees with a specific ordering property. You can perform various operations on BST.

class TreeNode {
    public:
        int data;
        TreeNode* left;
        TreeNode* right;
};

// Binary Search Tree operations
// Insertion, Deletion, Search, etc.

Operations:

  • Insertion of nodes while maintaining the BST property
  • Deletion of nodes
  • Searching for a specific value

Important Algorithm:

Inorder Traversal for obtaining elements in sorted order

Heaps

Heaps are binary trees used for efficient data insertion and extraction operations. There are min-heaps and max-heaps.

class MinHeap {
    public:
        // Min Heap operations
        // Insertion, Extract Min, Heapify, etc.
};

class MaxHeap {
    public:
        // Max Heap operations
        // Insertion, Extract Max, Heapify, etc.
}

Operations:

  • Insertion of elements while maintaining the heap property
  • Extraction of the minimum/maximum element
  • Heapify to ensure the heap property is maintained

Important Algorithm:

Heap Sort

Backtracking

Backtracking is a technique for finding all (or some) solutions to a problem by incrementally building a solution. It's often used in puzzles and optimization problems.

// Backtracking algorithm example
// N-Queens, Sudoku, Permutations, etc.

Operations:

  • Solving puzzles and optimization problems
  • Generating permutations and combinations
  • Exploring all possible solutions

Important Algorithm:

N-Queens Problem, Sudoku Solver, Knight's Tour Problem

Graphs and Graph Algorithms

Graphs are versatile data structures used to represent connections between elements. They have a wide range of applications in various domains.

class Graph {
    public:
        // Graph operations
        // Add Vertex, Add Edge, Traversal, etc.
};

// Graph algorithms
// Depth-First Search (DFS), Breadth-First Search (BFS), Shortest Path, etc.

Operations:

  • Adding vertices and edges
  • Graph traversal (DFS, BFS)
  • Shortest path and minimum spanning tree algorithms

Important Algorithm:

Dijkstra's Algorithm, Kruskal's Algorithm, Topological Sort, etc.

Dynamic Programming

Introduction

Dynamic Programming (DP) is a powerful technique used to solve problems by breaking them down into smaller overlapping subproblems. DP is particularly useful for optimization problems and can significantly improve the efficiency of your algorithms.

Fibonacci Series

The Fibonacci series is a classic example to illustrate dynamic programming concepts. Here's an example of calculating the nth Fibonacci number using DP:

const int MAX = 100;
      int dp[MAX];

      int fibonacci(int n) {
          if (n <= 1) {
              return n;
          }

          if (dp[n] != -1) {
              return dp[n];
          }

          dp[n] = fibonacci(n - 1) + fibonacci(n - 2);
          return dp[n];
      }

      int main() {
          int n = 10;
          memset(dp, -1, sizeof(dp));
          int result = fibonacci(n);
          std::cout << "Fibonacci(" << n << ") = " << result << std::endl;
          return 0;
      }

Knapsack Problem

The Knapsack problem is another well-known problem solved using dynamic programming. It deals with maximizing the value of items in a knapsack under given weight constraints. Here's an example of solving the 0/1 Knapsack problem:

int knapsack(int W, int wt[], int val[], int n) {
          int dp[n + 1][W + 1];

          for (int i = 0; i <= n; i++) {
              for (int w = 0; w <= W; w++) {
                  if (i == 0 || w == 0) {
                      dp[i][w] = 0;
                  } else if (wt[i - 1] <= w) {
                      dp[i][w] = std::max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);
                  } else {
                      dp[i][w] = dp[i - 1][w];
                  }
              }
          }

          return dp[n][W];
      }

      int main() {
          int val[] = {60, 100, 120};
          int wt[] = {10, 20, 30};
          int W = 50;
          int n = sizeof(val) / sizeof(val[0]);
          int result = knapsack(W, wt, val, n);
          std::cout << "Maximum value: " << result << std::endl;
          return 0;
      }

Longest Common Subsequence

The Longest Common Subsequence (LCS) problem is another classic application of dynamic programming. It aims to find the longest subsequence that two sequences have in common. Here's an example of finding the LCS between two strings:

int lcs(const std::string& X, const std::string& Y) {
          int m = X.length();
          int n = Y.length();
          std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));

          for (int i = 1; i <= m; i++) {
              for (int j = 1; j <= n; j++) {
                  if (X[i - 1] == Y[j - 1]) {
                      dp[i][j] = dp[i - 1][j - 1] + 1;
                  } else {
                      dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
                  }
              }
          }

          return dp[m][n];
      }

      int main() {
          std::string X = "AGGTAB";
          std::string Y = "GXTXAYB";
          int result = lcs(X, Y);
          std::cout << "Length of Longest Common Subsequence: " << result << std::endl;
          return 0;
      }