Theory & Data Structures

Master fundamental concepts with detailed explanations and visual examples

Arrays & Strings Linked Lists Stacks & Queues Trees Graphs Sorting Searching Dynamic Programming Complexity Analysis OOP Concepts

📊 Arrays & Strings

What is an Array?

An array is a collection of elements stored at contiguous memory locations. It's one of the most fundamental data structures.

Key Characteristics:

  • Fixed Size: Size is determined at creation (in most languages)
  • Homogeneous: All elements are of the same type
  • Random Access: O(1) time to access any element by index
  • Contiguous Memory: Elements stored sequentially

Visual Representation:

10
0
20
1
30
2
40
3
50
4

Common Operations:

// Declaration and Initialization
int arr[5] = {10, 20, 30, 40, 50};

// Access element: O(1)
int value = arr[2];  // Returns 30

// Update element: O(1)
arr[2] = 35;

// Traverse array: O(n)
for (int i = 0; i < 5; i++) {
    cout << arr[i] << " ";
}

// Search element: O(n)
int target = 30;
for (int i = 0; i < 5; i++) {
    if (arr[i] == target) {
        // Found at index i
    }
}

Time Complexity:

Operation Time Complexity
Access by Index O(1)
Search (unsorted) O(n)
Insert at End O(1)
Insert at Beginning/Middle O(n)
Delete O(n)

Important Array Problems:

  • Two Sum Problem
  • Maximum Subarray (Kadane's Algorithm)
  • Rotate Array
  • Find Duplicates
  • Merge Two Sorted Arrays
  • Remove Duplicates from Sorted Array
  • Best Time to Buy and Sell Stock

Strings

Strings are sequences of characters. In C++, they can be represented as character arrays or using the string class.

String Operations:

// C++ String Operations
string str = "Hello";

// Length: O(1)
int len = str.length();

// Access character: O(1)
char ch = str[0];

// Concatenation: O(n)
string result = str + " World";

// Substring: O(n)
string sub = str.substr(1, 3);  // "ell"

// Find: O(n*m)
int pos = str.find("ll");

// Reverse: O(n)
reverse(str.begin(), str.end());

// Compare: O(n)
if (str1 == str2) { }

Important String Problems:

  • Reverse a String
  • Check Palindrome
  • Anagram Detection
  • Longest Common Prefix
  • String Pattern Matching
  • Valid Parentheses
  • Longest Substring Without Repeating Characters

🔗 Linked Lists

What is a Linked List?

A linked list is a linear data structure where elements are stored in nodes. Each node contains data and a reference (pointer) to the next node.

Types of Linked Lists:

  • Singly Linked List: Each node points to the next node
  • Doubly Linked List: Each node points to both next and previous nodes
  • Circular Linked List: Last node points back to the first node

Singly Linked List Structure:

10
→
20
→
30
→
NULL

Node Structure & Basic Operations:

// Node Structure
struct Node {
    int data;
    Node* next;
    
    Node(int val) : data(val), next(nullptr) {}
};

// Insert at Beginning: O(1)
void insertAtBeginning(Node*& head, int value) {
    Node* newNode = new Node(value);
    newNode->next = head;
    head = newNode;
}

// Insert at End: O(n)
void insertAtEnd(Node*& head, int value) {
    Node* newNode = new Node(value);
    if (!head) {
        head = newNode;
        return;
    }
    Node* temp = head;
    while (temp->next) {
        temp = temp->next;
    }
    temp->next = newNode;
}

// Delete a Node: O(n)
void deleteNode(Node*& head, int value) {
    if (!head) return;
    
    if (head->data == value) {
        Node* temp = head;
        head = head->next;
        delete temp;
        return;
    }
    
    Node* current = head;
    while (current->next && current->next->data != value) {
        current = current->next;
    }
    
    if (current->next) {
        Node* temp = current->next;
        current->next = current->next->next;
        delete temp;
    }
}

// Traverse: O(n)
void printList(Node* head) {
    while (head) {
        cout << head->data << " -> ";
        head = head->next;
    }
    cout << "NULL" << endl;
}

Array vs Linked List:

Feature Array Linked List
Memory Contiguous Non-contiguous
Size Fixed Dynamic
Access Time O(1) O(n)
Insert at Beginning O(n) O(1)
Memory Overhead Low High (pointers)

Important Linked List Problems:

  • Reverse a Linked List
  • Detect Cycle (Floyd's Algorithm)
  • Find Middle Element
  • Merge Two Sorted Lists
  • Remove Nth Node from End
  • Check if Palindrome
  • Intersection of Two Lists

📚 Stacks & Queues

Stack (LIFO - Last In First Out)

A stack is a linear data structure that follows the LIFO principle. Think of it like a stack of plates.

Stack Operations:

30
20
10
Push(30)
→
40
30
20
10
Push(40)
→
30
20
10
Pop() returns 40

Stack Implementation:

// Using STL Stack
#include <stack>

stack<int> st;

// Push: O(1)
st.push(10);
st.push(20);
st.push(30);

// Pop: O(1)
st.pop();  // Removes 30

// Top: O(1)
int top = st.top();  // Returns 20

// Empty: O(1)
bool isEmpty = st.empty();

// Size: O(1)
int size = st.size();

Queue (FIFO - First In First Out)

A queue is a linear data structure that follows the FIFO principle. Think of it like a line at a ticket counter.

Queue Operations:

Front →
10
20
30
40
← Rear

Enqueue at Rear, Dequeue from Front

Queue Implementation:

// Using STL Queue
#include <queue>

queue<int> q;

// Enqueue: O(1)
q.push(10);
q.push(20);
q.push(30);

// Dequeue: O(1)
q.pop();  // Removes 10

// Front: O(1)
int front = q.front();  // Returns 20

// Back: O(1)
int back = q.back();  // Returns 30

// Empty: O(1)
bool isEmpty = q.empty();

// Size: O(1)
int size = q.size();

Important Stack Problems:

  • Valid Parentheses
  • Next Greater Element
  • Implement Stack using Queues
  • Min Stack (with O(1) min operation)
  • Evaluate Postfix Expression
  • Reverse a Stack

Important Queue Problems:

  • Implement Queue using Stacks
  • Circular Queue Implementation
  • First Non-Repeating Character in Stream
  • Level Order Traversal (BFS)

⏱️ Time & Space Complexity

What is Complexity Analysis?

Complexity analysis helps us understand how an algorithm's performance scales with input size. It's crucial for writing efficient code.

Big-O Notation:

Big-O describes the upper bound of time/space an algorithm takes. It focuses on the worst-case scenario.

Common Time Complexities (from best to worst):

Notation Name Example n=100
O(1) Constant Array access, Hash lookup 1
O(log n) Logarithmic Binary search 7
O(n) Linear Linear search, Array traversal 100
O(n log n) Linearithmic Merge sort, Quick sort 700
O(n²) Quadratic Bubble sort, Nested loops 10,000
O(2ⁿ) Exponential Recursive Fibonacci 1.27 × 10³⁰
O(n!) Factorial Permutations 9.3 × 10¹⁵⁷

Complexity Examples:

// O(1) - Constant Time
int getFirstElement(vector<int>& arr) {
    return arr[0];  // Always 1 operation
}

// O(n) - Linear Time
int findMax(vector<int>& arr) {
    int max = arr[0];
    for (int i = 1; i < arr.size(); i++) {  // n iterations
        if (arr[i] > max) max = arr[i];
    }
    return max;
}

// O(log n) - Logarithmic Time
int binarySearch(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;  // Divides search space by 2 each time
}

// O(n²) - Quadratic Time
void printPairs(vector<int>& arr) {
    for (int i = 0; i < arr.size(); i++) {      // n times
        for (int j = 0; j < arr.size(); j++) {  // n times
            cout << arr[i] << ", " << arr[j] << endl;
        }
    }
}

// O(n log n) - Linearithmic Time
void mergeSort(vector<int>& arr) {
    // Divides array log n times (like binary search)
    // Each level does n work to merge
    // Total: n * log n
}

💡 Tips for Analyzing Complexity:

  • Drop constants: O(2n) becomes O(n)
  • Drop lower terms: O(n² + n) becomes O(n²)
  • Nested loops: Usually multiply complexities
  • Consecutive loops: Add complexities (then drop lower terms)
  • Recursion: Draw recursion tree to analyze

Space Complexity

Space complexity measures the total memory an algorithm uses, including input space and auxiliary space.

Space Complexity Examples:

// O(1) Space - Constant Space
int sum(int a, int b) {
    return a + b;  // Only stores result
}

// O(n) Space - Linear Space
vector<int> createCopy(vector<int>& arr) {
    vector<int> copy = arr;  // Stores n elements
    return copy;
}

// O(n) Space - Recursion Stack
int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n-1) + fibonacci(n-2);
    // Maximum recursion depth is n
}

🎯 Object-Oriented Programming (OOP)

Four Pillars of OOP

1. Encapsulation

Bundling data and methods that operate on that data within a single unit (class). Hide internal details and expose only necessary information.

class BankAccount {
private:
    double balance;  // Hidden from outside
    
public:
    void deposit(double amount) {
        if (amount > 0) {
            balance += amount;
        }
    }
    
    double getBalance() {
        return balance;
    }
};

2. Abstraction

Hiding complex implementation details and showing only essential features. Focus on "what" rather than "how".

// Abstract class
class Shape {
public:
    virtual double area() = 0;  // Pure virtual
    virtual void draw() = 0;
};

class Circle : public Shape {
private:
    double radius;
    
public:
    double area() override {
        return 3.14 * radius * radius;
    }
    
    void draw() override {
        // Drawing implementation
    }
};

3. Inheritance

A mechanism where a new class derives properties and behaviors from an existing class. Promotes code reusability.

class Animal {
protected:
    string name;
    
public:
    void eat() {
        cout << "Eating..." << endl;
    }
};

class Dog : public Animal {
public:
    void bark() {
        cout << "Woof!" << endl;
    }
};

// Dog inherits eat() from Animal

4. Polymorphism

The ability of objects to take multiple forms. Same interface, different implementations.

class Animal {
public:
    virtual void sound() {
        cout << "Animal sound" << endl;
    }
};

class Dog : public Animal {
public:
    void sound() override {
        cout << "Bark!" << endl;
    }
};

class Cat : public Animal {
public:
    void sound() override {
        cout << "Meow!" << endl;
    }
};

// Runtime polymorphism
Animal* animal = new Dog();
animal->sound();  // Outputs: Bark!

Access Specifiers:

Specifier Same Class Derived Class Outside Class
public ✓ ✓ ✓
protected ✓ ✓ ✗
private ✓ ✗ ✗

Other Important OOP Concepts:

  • Constructor: Special method called when object is created
  • Destructor: Called when object is destroyed
  • Method Overloading: Same method name, different parameters
  • Method Overriding: Redefining parent class method in child class
  • Virtual Functions: Enable runtime polymorphism
  • Abstract Class: Cannot be instantiated, has pure virtual functions
  • Interface: Pure abstract class with only virtual functions

📌 Quick Reference Cheat Sheet

Sorting Algorithms

  • Bubble Sort: O(n²)
  • Selection Sort: O(n²)
  • Insertion Sort: O(n²)
  • Merge Sort: O(n log n)
  • Quick Sort: O(n log n) avg
  • Heap Sort: O(n log n)

Searching Algorithms

  • Linear Search: O(n)
  • Binary Search: O(log n)
  • Jump Search: O(√n)
  • Interpolation Search: O(log log n)

Tree Traversals

  • Inorder: Left → Root → Right
  • Preorder: Root → Left → Right
  • Postorder: Left → Right → Root
  • Level Order: BFS

Graph Algorithms

  • BFS: O(V + E)
  • DFS: O(V + E)
  • Dijkstra: O((V+E) log V)
  • Topological Sort: O(V + E)