DSA_LEARN

Arrays

An array is a collection of items stored at contiguous memory locations. It allows fast access using indices.

Syntax (C++):

int arr[5];            // Declaration of array with 5 integers
int arr[] = {1, 2, 3};  // Initialization of array

Traversal Algorithm:

for (int i = 0; i < n; i++) {
    // Access arr[i]
}

Linked Lists

A linked list consists of nodes where each node contains data and a pointer to the next node.

Node Structure (C++):

struct Node {
    int data;
    Node* next;
};

Traversal Algorithm:

Node* curr = head;
while (curr != nullptr) {
    // Process curr->data
    curr = curr->next;
}

Stacks

Stack is a LIFO data structure where elements are added and removed from the top.

Using STL stack (C++):

#include <stack>
std::stack<int> s;
s.push(10);  // Push element
s.pop();     // Pop element

Operations:

push(x)    // Insert element x
pop()       // Remove top element
top()       // Access top element
empty()     // Check if empty

Queues

Queue is a FIFO data structure where elements are added at the rear and removed from the front.

Using STL queue (C++):

#include <queue>
std::queue<int> q;
q.push(10);  // Enqueue
q.pop();     // Dequeue

Operations:

enqueue(x)   // Add element x
dequeue()     // Remove front element
front()       // Access front element
empty()       // Check if empty

Trees

Trees are hierarchical data structures with nodes having children, starting from a root node.

Binary Tree Node (C++):

struct Node {
    int data;
    Node* left;
    Node* right;
};

Inorder Traversal Algorithm:

void inorder(Node* root) {
    if (!root) return;
    inorder(root->left);
    // Process root->data
    inorder(root->right);
}

Graphs

Graphs consist of nodes (vertices) connected by edges; they can be directed or undirected.

Adjacency List (C++):

std::vector<std::vector<int>> adj(n);
adj[u].push_back(v);  // Edge u -> v

Breadth First Search (BFS) Algorithm:

std::queue<int> q;
std::vector<bool> visited(n, false);
q.push(start);
visited[start] = true;

while (!q.empty()) {
    int u = q.front(); q.pop();
    // Process u
    for (auto v : adj[u]) {
        if (!visited[v]) {
            visited[v] = true;
            q.push(v);
        }
    }
}

Sorting Algorithms

Sorting arranges elements in order. Common algorithms include Bubble Sort, Merge Sort, Quick Sort.

Bubble Sort (O(n²)):

for (int i = 0; i < n-1; i++) {
    for (int j = 0; j < n-1-i; j++) {
        if (arr[j] > arr[j+1]) {
            std::swap(arr[j], arr[j+1]);
        }
    }
}

Merge Sort (O(n log n)):

void mergeSort(int arr[], int l, int r);
void merge(int arr[], int l, int m, int r);

Recursively split and merge sorted subarrays.

Quick Sort (O(n log n) avg):

int partition(int arr[], int low, int high);
void quickSort(int arr[], int low, int high);

Partition array around pivot and recursively sort subarrays.

Searching Algorithms

Algorithms to find data. Includes Linear and Binary Search.

Linear Search (O(n)):

for (int i = 0; i < n; i++) {
    if (arr[i] == target) return i;
}
return -1;

Binary Search (O(log n)) (Sorted Array):

int low = 0, high = n - 1;
while (low <= high) {
    int mid = low + (high - low) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) low = mid + 1;
    else high = mid - 1;
}
return -1;

Hashing

Hashes map keys to indices in a table for efficient lookup.

Syntax (C++ STL unordered_map):

#include <unordered_map>
std::unordered_map<int, std::string> hashmap;
hashmap[1] = "one";
auto it = hashmap.find(1);
if (it != hashmap.end()) {
    // Found
}

Concept:

key --hash_function--> index in hash table
Store/retrieve data at that index

Dynamic Programming (DP)

DP solves problems by combining solutions to overlapping subproblems, storing results to avoid recomputation.

Example: Fibonacci (Memoization):

int fib(int n, std::vector<int>& memo) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = fib(n-1, memo) + fib(n-2, memo);
    return memo[n];
}

Example: Fibonacci (Tabulation):

int fib(int n) {
    std::vector<int> dp(n+1);
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}