CMPC-5205

Data Structures
Complete Exam Preparation Notes
Detailed Edition — 40+ Pages

• ADTs & Big O • Stacks • Recursion • Queues & Priority Queues

• Linked Lists • Sorting Algorithms • Searching & Hashing • Trees & AVL
• Heaps & Heap Sort • Graphs (BFS/DFS) • Memory Management • Practice MCQs

Short Questions | Long Questions | C++ Programs | Diagrams | Exam Tips

TABLE OF CONTENTS
1. Abstract Data Types & Complexity Analysis (Big O)

2. Stacks – Array & Linked List Implementations

3. Recursion & Recursive Algorithms

4. Queues, Dequeues & Priority Queues

5. Linked Lists – Singly, Doubly, Circular

6. Sorting Algorithms (All Major Sorts)

7. Searching – Linear, Binary & Hashing

8. Trees – BST, Traversals & AVL Trees

9. Heaps & Heap Sort

10. Graphs – BFS, DFS, Dijkstra, Topological Sort

11. Memory Management & Garbage Collection

12. Quick Reference – Data Structure Comparison

13. Practice MCQs & Exam Tips

 CHAPTER 1

Abstract Data Types & Complexity Analysis

1.1 Abstract Data Types (ADT)

An Abstract Data Type (ADT) is a mathematical model for a data type defined purely by its behavior
(operations and their semantics) from the user's perspective — implementation details are completely hidden.
The concept is similar to a 'black box': you know what it does but not how it does it.

Key Properties of ADTs:

• Abstraction: Users interact through well-defined operations only
• Encapsulation: Internal representation is hidden from users
• Independence: Multiple implementations can satisfy the same ADT
• Reusability: ADT can be used in different programs without change

Common ADT Examples:

ADT Core Operations Common Implementations

Stack push, pop, peek, isEmpty Array, Linked List

Queue enqueue, dequeue, front, isEmpty Array (circular), Linked List

List insert, delete, search, get Array, Doubly Linked List

Tree insert, delete, search, traversal Nodes with pointers

Graph addVertex, addEdge, BFS, DFS Adjacency List/Matrix

Set add, remove, contains, union, intersection Hash Table, BST

Map/Dict put, get, remove, contains Hash Table, BST

Priority Q insert, extractMax/Min, peek Heap

1.2 Big O Notation — Detailed

Big O notation describes the upper bound of an algorithm's time or space complexity as input size n grows
toward infinity. It answers: 'In the worst case, how does the algorithm scale?' We always drop lower-order terms
and constants because only dominant behavior matters for large inputs.

Rules for Calculating Big O:

• Drop constants: O(5n) → O(n), O(100) → O(1)
• Drop non-dominant terms: O(n² + n) → O(n²), O(n + log n) → O(n)
• Sequential steps add: O(n) + O(n²) = O(n²)
• Nested loops multiply: O(n) inside O(n) = O(n²)
• Different inputs → different variables: two arrays A and B → O(a·b) not O(n²)

Notation Name Example Growth Rate

O(1) Constant Array index access Best

O(log n) Logarithmic Binary search Excellent

O(n) Linear Linear search Good

 O(n log n) Linearithmic Merge sort, Heap sort Fair

O(n²) Quadratic Bubble/Insertion/Selection sort Poor

O(n³) Cubic Matrix multiplication (naive) Very Poor

O(2■) Exponential Recursive Fibonacci, subsets Terrible

O(n!) Factorial Permutation generation Worst

1.3 Complexity Analysis Examples

// O(1) - Constant: does not depend on input size
int getFirst(int arr[]) { return arr[0]; }

// O(n) - Linear: one loop through n elements

int sum(int arr[], int n) {
int total = 0;
for (int i = 0; i < n; i++) total += arr[i];
return total;
}

// O(n²) - Quadratic: nested loops

void printPairs(int arr[], int n) {
for (int i = 0; i < n; i++) // n iterations
for (int j = 0; j < n; j++) // n iterations each
cout << arr[i] << "," << arr[j] << endl;
}

// O(log n) - Logarithmic: halves input each time

int binarySearch(int arr[], int n, int x) {
int l=0, r=n-1;
while(l<=r){
int mid = (l+r)/2;
if(arr[mid]==x) return mid;
if(arr[mid]<x) l=mid+1; else r=mid-1;
}
return -1;
}

// O(n log n) - Linearithmic: merge sort, heap sort

// O(2^n) - Exponential: recursive Fibonacci (AVOID for large n!)
int fib(int n){ return n<=1 ? n : fib(n-1)+fib(n-2); }

1.4 Space Complexity

Space complexity measures the total memory an algorithm uses relative to input size. This includes: (1) Input
space — memory for the input itself, (2) Auxiliary space — extra memory used by the algorithm (temp
variables, recursion stack, etc.)

• Merge Sort: O(n) auxiliary space (needs extra array for merging)
• Quick Sort: O(log n) space for recursion call stack
• Bubble/Insertion/Selection Sort: O(1) auxiliary space (in-place)
• Recursive Fibonacci(n): O(n) stack space due to depth of recursion

1.5 Best, Worst, Average Case Analysis

Case Definition Notation Linear Search Example

Best Minimum operations needed Ω (Omega) Element found at index 0 → O(1)

Worst Maximum operations needed O (Big O) Element not found → O(n)

 Average Expected operations over all inputs Θ (Theta) Element found at middle → O(n/2) = O(n)

Short Questions & Answers — Chapter 1

Q: What is an ADT? Give two examples.
Ans: An ADT (Abstract Data Type) defines data and operations without specifying implementation. Examples:
Stack (push/pop/peek — LIFO behavior) and Queue (enqueue/dequeue — FIFO behavior). A Stack can be
implemented as array or linked list, but its ADT remains the same.

Q: What is the difference between O(n) and O(log n)? Which is better?
Ans: O(n) grows linearly — doubling input doubles operations. O(log n) grows logarithmically — doubling
input adds only ONE extra operation. O(log n) is much better. For n=1,000,000: O(n)=1,000,000 steps vs
O(log n)=20 steps. Binary search is O(log n); linear search is O(n).

Q: Why do we drop constants in Big O?

Ans: Constants depend on hardware, compiler, and language — not the algorithm itself. Big O measures
scalability as n→∞. For large n, O(1000n) and O(n) behave identically in terms of growth rate. We care about
growth pattern, not exact count.

Q: What is amortized analysis?

Ans: Amortized analysis finds the average cost per operation over a sequence of operations. Example:
dynamic array doubling. Most insertions are O(1) but occasionally O(n) for resizing. Amortized cost per
insertion = O(1) because expensive operations happen rarely.

Q: What is the time complexity of accessing arr[i] vs searching for value x in an array?
Ans: arr[i] access is O(1) — direct address calculation using base pointer + i*element_size. Searching for
value x in unsorted array is O(n) — must check each element. In sorted array, binary search is O(log n).
 CHAPTER 2

Stacks
A Stack is a linear data structure following LIFO (Last In, First Out) principle. Think of it like a stack of plates —
you always add/remove from the top.

2.1 Stack Operations & Concepts

• push(x) — Add element x to the top. O(1)
• pop() — Remove and return top element. O(1)
• peek()/top() — View top element without removing. O(1)
• isEmpty() — Check if stack is empty. O(1)
• size() — Return number of elements. O(1)
• Stack Overflow: Pushing onto a full stack (array-based)
• Stack Underflow: Popping from an empty stack

2.2 Applications of Stacks

Application How Stack is Used

Function Call Stack Each function call pushes a frame; return pops it. Enables recursion.

Expression Evaluation Operators and operands pushed to evaluate infix/postfix/prefix.

Balanced Parentheses Push opening brackets; pop and match when closing bracket found.

Undo/Redo in Editors Each action pushed; Ctrl+Z pops (undo); Ctrl+Y re-pushes (redo).

Browser History Visiting page pushes URL; back button pops.

Backtracking (Maze/DFS) Push current state; backtrack by popping when stuck.

Infix to Postfix Operators managed with stack to handle precedence.

Syntax Parsing Compilers use stacks to parse expressions and code blocks.

2.3 Array Implementation of Stack

#include <iostream>
using namespace std;
#define MAX 100

class Stack {
int arr[MAX];
int top;
public:
Stack() { top = -1; } // Initialize: empty stack

bool push(int x) {
if (top >= MAX - 1) { // Check overflow
cout << "Stack Overflow!" << endl;
return false;
}
arr[++top] = x; // Pre-increment, then assign
return true;
}

int pop() {
 if (top < 0) { // Check underflow
cout << "Stack Underflow!" << endl;
return -1;
}
return arr[top--]; // Return value, then decrement
}

int peek() {
if (top < 0) return -1;
return arr[top]; // Just view, don't remove
}

bool isEmpty() { return top == -1; }

int size() { return top + 1; }
};

int main() {
Stack s;
[Link](10); [Link](20); [Link](30);
cout << "Top: " << [Link]() << endl; // 30
cout << "Pop: " << [Link]() << endl; // 30 (removes it)
cout << "Size: " << [Link]() << endl; // 2
cout << "Empty: " << [Link]() << endl; // 0 (false)
return 0;
}

■ NOTE: Array stack has FIXED size. If MAX=100 and you push 101 elements, overflow occurs! Use linked list
stack for dynamic size.

2.4 Linked List Implementation of Stack

#include <iostream>
using namespace std;

struct Node {
int data;
Node* next;
Node(int d) : data(d), next(nullptr) {}
};

class StackLL {
Node* top;
int sz;
public:
StackLL() : top(nullptr), sz(0) {}

void push(int x) {
Node* newNode = new Node(x); // Allocate new node
newNode->next = top; // Point to current top
top = newNode; // New node becomes top
sz++;
}

int pop() {
if (!top) { cout << "Underflow!" << endl; return -1; }
int val = top->data;
Node* temp = top;
top = top->next; // Move top pointer down
delete temp; // Free memory!
sz--;
return val;
}

int peek() { return top ? top->data : -1; }

bool isEmpty(){ return top == nullptr; }
 int size() { return sz; }

~StackLL() { // Destructor: free all nodes

while(top) pop();
}
};

2.5 Array vs Linked List Stack Comparison

Feature Array Stack Linked List Stack

Size Fixed (static) Dynamic (grows as needed)

Overflow Yes (when array full) No (until heap is full)

Memory Pre-allocated block Allocated per node (+ pointer overhead)

push/pop O(1) O(1)

Cache friendliness Better (contiguous) Worse (scattered in memory)

Implementation Simple Slightly more complex

Use case Size known in advance Size varies at runtime

2.6 Classic Application: Postfix Expression Evaluator

Postfix (Reverse Polish Notation) eliminates need for parentheses. Algorithm: scan left to right — if digit, push; if
operator, pop two operands, apply, push result.
// Evaluate postfix expression: "234*+" means 2 + (3*4) = 14
#include <iostream>
#include <stack>
#include <string>
using namespace std;

int evaluatePostfix(string expr) {

stack<int> s;
for (char c : expr) {
if (isdigit(c)) {
[Link](c - '0'); // Convert char to int
} else {
int b = [Link](); [Link](); // Second operand
int a = [Link](); [Link](); // First operand (order matters!)
if (c == '+') [Link](a + b);
else if (c == '-') [Link](a - b);
else if (c == '*') [Link](a * b);
else if (c == '/') [Link](a / b);
}
}
return [Link]();
}
// Trace "234*+": push 2 → push 3 → push 4 → '*': pop 4,3 push 12
// → '+': pop 12,2 push 14 → return 14

Short Questions & Answers — Chapter 2

Q: What is LIFO? Give a real-world example.
Ans: LIFO = Last In, First Out. The last element added is the first removed. Real world: stack of cafeteria
plates — you always pick the top plate (last placed). Another example: browser back button — most recently
visited page is first to go back to.

Q: What is the difference between peek and pop?

 Ans: peek() (also called top()) READS the top element without removing it — stack size unchanged. pop()
REMOVES and returns the top element — stack size decreases by 1. Both are O(1).

Q: How does the function call stack work in recursion?

Ans: Each function call creates a 'stack frame' containing: local variables, parameters, and return address.
This frame is PUSHED onto the call stack. When function returns, its frame is POPPED. For factorial(5):
frames for f(5), f(4), f(3), f(2), f(1) are pushed, then popped in reverse.

Q: What happens if recursion has no base case?

Ans: Infinite recursion occurs — function keeps calling itself and pushing stack frames until Stack Overflow!
The program crashes with 'Segmentation Fault' or 'Stack Overflow' error. Always ensure base case is
reachable.
 CHAPTER 3

Recursion
Recursion is a technique where a function solves a problem by calling itself on a smaller version of the same
problem. Essential for: trees, graphs, divide & conquer, backtracking.

3.1 Structure of Recursive Functions

• Base Case: Condition that stops recursion (no more recursive calls)
• Recursive Case: Function calls itself with a SMALLER/SIMPLER input
• Progress: Each call must move closer to the base case
• Trust: Assume recursive call works correctly for smaller input

// Pattern of recursive function:

returnType functionName(parameters) {
if (base_condition) { // BASE CASE — stop here
return base_value;
}
// RECURSIVE CASE — must reduce problem toward base case
return functionName(smaller_parameters);
}

// Example: Factorial n! = n × (n-1)!

int factorial(int n) {
if (n <= 1) return 1; // Base case: 0! = 1! = 1
return n * factorial(n - 1); // Recursive case
}
// factorial(5) → 5 × factorial(4) → 5 × 4 × factorial(3)
// → 5 × 4 × 3 × 2 × factorial(1)
// → 5 × 4 × 3 × 2 × 1 = 120

// Example: Fibonacci F(n) = F(n-1) + F(n-2)

int fib(int n) {
if (n <= 1) return n; // Base cases: F(0)=0, F(1)=1
return fib(n-1) + fib(n-2); // O(2^n) — very slow!
}

// Optimized Fibonacci with Memoization (O(n))

int memo[1000] = {0};
int fibMemo(int n) {
if (n <= 1) return n;
if (memo[n]) return memo[n]; // Return cached result
memo[n] = fibMemo(n-1) + fibMemo(n-2);
return memo[n];
}

3.2 Tower of Hanoi — Classic Recursion Problem

Move n disks from source peg to destination peg using an auxiliary peg. Rules: only one disk at a time, never
place larger disk on smaller. Minimum moves = 2■ - 1.
void hanoi(int n, char from, char to, char aux) {
if (n == 1) { // Base case: move single disk
cout << "Move disk 1 from " << from << " to " << to << endl;
return;
}
hanoi(n-1, from, aux, to); // Step 1: Move n-1 disks to aux
cout << "Move disk " << n << " from " << from << " to " << to << endl; // Step 2
hanoi(n-1, aux, to, from); // Step 3: Move n-1 disks from aux to dest
 }
// For n=3: requires 2³-1 = 7 moves
// Recursion tree depth = n, total calls = 2^(n+1) - 1

3.3 Recursion vs Iteration — Detailed Comparison

Aspect Recursion Iteration

Mechanism Function calls itself Uses loops (for/while/do-while)

Memory O(n) stack space for call frames O(1) — no extra stack

Speed Slower (function call overhead) Faster (no overhead)

Readability Often cleaner for tree/graph problems Cleaner for simple loops

Termination Base case Loop condition

Stack overflow Possible with deep recursion Not possible

Use cases Trees, graphs, divide & conquer Simple array processing

■ TIP: When to use recursion: problem has natural sub-structure (trees, graphs), code is much simpler recursive
than iterative. When to use iteration: performance critical, deep recursion possible.

Short Questions & Answers — Chapter 3

Q: What are the two essential parts of a recursive function?
Ans: (1) Base Case: The stopping condition — a simple case that can be solved directly without further
recursion. Without it, function runs forever. (2) Recursive Case: The general case where function calls itself
with a SMALLER input, progressively moving toward the base case.

Q: What is tail recursion? Why is it important?

Ans: Tail recursion: the recursive call is the LAST operation in the function — no computation happens after it
returns. Example: tail_fact(n, acc) where acc accumulates result. Importance: compilers can optimize tail
recursion to use O(1) stack space (reuse same frame) instead of O(n), preventing stack overflow.

Q: What is the time complexity of recursive Fibonacci and how to improve it?
Ans: Naive recursive Fibonacci is O(2^n) — exponential. For fib(50), it makes ~10^15 calls! Improvement 1:
Memoization (top-down DP) — store computed values in array → O(n) time, O(n) space. Improvement 2:
Bottom-up DP with loop → O(n) time, O(1) space. Improvement 3: Matrix exponentiation → O(log n) time.

Q: What is Divide and Conquer? Give an algorithm example.

Ans: Divide and Conquer: (1) DIVIDE problem into smaller sub-problems, (2) CONQUER by solving
sub-problems recursively, (3) COMBINE solutions. Example: Merge Sort — divides array in half recursively
until single elements, then merges sorted halves. T(n) = 2T(n/2) + O(n) → O(n log n).
 CHAPTER 4

Queues, Dequeues & Priority Queues

A Queue follows FIFO (First In, First Out) — like a line at a ticket counter. First person to join the line is first to be
served.

4.1 Queue Operations

• enqueue(x): Add element to REAR. O(1)
• dequeue(): Remove element from FRONT. O(1)
• front()/peek(): View front element. O(1)
• isEmpty(): Check if empty. O(1)
• size(): Number of elements. O(1)

4.2 Queue Applications

• CPU scheduling — processes wait in queue for CPU time
• Printer spooling — print jobs queued in order
• BFS (Breadth First Search) — explores nodes level by level
• Network packet handling — packets queued and processed in order
• Keyboard buffer — keystrokes stored in queue
• Call center — customer calls held in order

4.3 Circular Queue Implementation

Regular array queue wastes space after dequeue. Circular queue reuses empty slots by wrapping indices: rear
= (rear+1) % MAX. This solves the 'false full' problem.
#include <iostream>
using namespace std;
#define MAX 6

class CircularQueue {
int arr[MAX], front, rear, count;
public:
CircularQueue() : front(0), rear(-1), count(0) {}

void enqueue(int x) {
if (count == MAX) { cout << "Queue Full!"; return; }
rear = (rear + 1) % MAX; // Circular wrap-around
arr[rear] = x;
count++;
}

int dequeue() {
if (count == 0) { cout << "Queue Empty!"; return -1; }
int val = arr[front];
front = (front + 1) % MAX; // Circular wrap-around
count--;
return val;
}

int peek() { return count ? arr[front] : -1; }

bool isEmpty() { return count == 0; }
bool isFull() { return count == MAX; }
int size() { return count; }
 };
// Example: MAX=6, enqueue 1,2,3,4 → dequeue 1,2 → enqueue 5,6,7
// front and rear wrap around the array circularly

4.4 Dequeue (Double-Ended Queue)

A Dequeue allows insertion and deletion at BOTH ends — combines features of stack and queue.
#include <deque>
using namespace std;

deque<int> dq;
dq.push_back(10); // [10] — insert at rear
dq.push_back(20); // [10,20] — insert at rear
dq.push_front(5); // [5,10,20] — insert at front
dq.pop_front(); // [10,20] — remove from front
dq.pop_back(); // [10] — remove from rear
cout << [Link](); // 10 — view front
cout << [Link](); // 10 — view back
cout << [Link](); // 1 — size

4.5 Priority Queue & Heap-Based Implementation

Priority Queue dequeues the HIGHEST PRIORITY element first, regardless of insertion order. Implemented with
a Binary Heap (Max-Heap or Min-Heap).

• Insert: O(log n) — add to end, bubble up

• Extract Max/Min: O(log n) — remove root, restructure
• Peek: O(1) — just view root
#include <queue>
#include <vector>
using namespace std;

// MAX-HEAP (default) — largest element has highest priority

priority_queue<int> maxPQ;
[Link](30); [Link](10); [Link](50); [Link](20);
while(![Link]()) {
cout << [Link]() << " "; // 50 30 20 10
[Link]();
}

// MIN-HEAP — smallest element has highest priority

priority_queue<int, vector<int>, greater<int>> minPQ;
[Link](30); [Link](10); [Link](50);
cout << [Link](); // 10 (minimum is at top)

4.6 Stack vs Queue vs Dequeue — Comparison

Feature Stack Queue Dequeue

Principle LIFO FIFO Both ends

Insert at Top only Rear only Both ends

Remove from Top only Front only Both ends

Operations push, pop enqueue, dequeue pushF/B, popF/B

Use case Undo, recursion Scheduling, BFS Sliding window

Short Questions & Answers — Chapter 4

Q: What is a circular queue? Why is it better than a linear queue?
 Ans: A circular queue reuses freed positions by treating the array as circular using modulo arithmetic (index =
(index+1) % MAX). Linear queue problem: after many enqueue/dequeue operations, front pointer moves
right, wasting empty slots at the beginning even when queue appears 'full'. Circular queue solves this 'false
full' problem with O(1) enqueue/dequeue.

Q: What is the difference between priority queue and regular queue?

Ans: Regular Queue: FIFO — elements dequeued in order of insertion. Priority Queue: dequeues the
HIGHEST PRIORITY element first, regardless of insertion order. Implemented with a heap for O(log n)
insert/delete. Used in Dijkstra's algorithm, Huffman coding, OS process scheduling.
 CHAPTER 5

Linked Lists — Singly, Doubly & Circular

A linked list is a dynamic data structure where elements (nodes) are stored in non-contiguous memory locations.
Each node contains data and a pointer to the next node.

5.1 Array vs Linked List — Fundamental Comparison

Feature Array Linked List

Memory layout Contiguous Non-contiguous (scattered)

Size Fixed (static) Dynamic (grows/shrinks)

Access by index O(1) — direct O(n) — must traverse from head

Insert at front O(n) — shift elements O(1) — update head pointer

Insert at end O(1) if space available O(n) — traverse to tail

Insert at middle O(n) — shift elements O(n) — find position, O(1) insert

Delete O(n) — shift elements O(1) if pointer known, else O(n)

Extra memory None Pointer per node (4-8 bytes)

Cache performance Excellent Poor (pointer chasing)

5.2 Singly Linked List — Complete Implementation

#include <iostream>
using namespace std;

struct Node {
int data;
Node* next;
Node(int d) : data(d), next(nullptr) {}
};

class LinkedList {
Node* head;
int sz;
public:
LinkedList() : head(nullptr), sz(0) {}

void insertFront(int d) {
Node* n = new Node(d);
n->next = head; // Point new node to current head
head = n; // New node becomes head
sz++;
}

void insertEnd(int d) {
Node* n = new Node(d);
if (!head) { head = n; sz++; return; }
Node* cur = head;
while (cur->next) cur = cur->next; // Find last node
cur->next = n;
sz++;
}

void insertAt(int pos, int d) { // 0-indexed

 if (pos == 0) { insertFront(d); return; }
Node* cur = head;
for (int i = 0; i < pos-1 && cur; i++) cur = cur->next;
if (!cur) return; // position out of range
Node* n = new Node(d);
n->next = cur->next;
cur->next = n;
sz++;
}

void deleteNode(int d) {
if (!head) return;
if (head->data == d) {
Node* tmp = head; head = head->next;
delete tmp; sz--; return;
}
Node* cur = head;
while (cur->next && cur->next->data != d) cur = cur->next;
if (cur->next) {
Node* tmp = cur->next;
cur->next = tmp->next;
delete tmp; sz--;
}
}

void reverse() {
Node *prev=nullptr, *curr=head, *next=nullptr;
while (curr) {
next = curr->next; // Save next
curr->next = prev; // Reverse link
prev = curr; // Move prev forward
curr = next; // Move curr forward
}
head = prev; // prev is new head
}

Node* findMiddle() {
Node *slow=head, *fast=head;
while (fast && fast->next) {
slow = slow->next; // 1 step
fast = fast->next->next; // 2 steps
}
return slow; // slow is at middle when fast reaches end
}

bool hasCycle() {
Node *slow=head, *fast=head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true; // Cycle detected!
}
return false;
}

void display() {
Node* cur = head;
while (cur) { cout << cur->data << " -> "; cur = cur->next; }
cout << "NULL" << endl;
}
int size() { return sz; }
};

5.3 Doubly Linked List

Each node has TWO pointers: next and prev. Allows bidirectional traversal. Deletion is O(1) if pointer to node is
known (unlike singly where we need previous node).
struct DNode {
int data;
DNode *prev, *next;
DNode(int d) : data(d), prev(nullptr), next(nullptr) {}
};

class DoublyLL {
DNode* head;
DNode* tail; // Keep tail pointer for O(1) insertEnd
public:
DoublyLL() : head(nullptr), tail(nullptr) {}

void insertEnd(int d) {
DNode* n = new DNode(d);
if (!tail) { head = tail = n; return; }
n->prev = tail; // New node's prev = current tail
tail->next = n; // Current tail's next = new node
tail = n; // Update tail
}

void deleteNode(DNode* node) { // O(1) deletion given pointer!

if (node->prev) node->prev->next = node->next;
else head = node->next; // Deleting head
if (node->next) node->next->prev = node->prev;
else tail = node->prev; // Deleting tail
delete node;
}

void displayForward() { DNode* c=head; while(c){cout<<c->data<<" <-> "; c=c->next;} cout<<"NULL"<<endl; }

void displayBackward() { DNode* c=tail; while(c){cout<<c->data<<" <-> "; c=c->prev;} cout<<"NULL"<<endl; }
};

5.4 Circular Linked List

Last node's next points back to HEAD (no nullptr at end). Used in: round-robin scheduling, circular buffers,
carousel/slideshow navigation.
// In circular LL, last node->next = head (not nullptr)
// Traversal: start at head, stop when you reach head again
void displayCircular(Node* head) {
if (!head) return;
Node* cur = head;
do {
cout << cur->data << " -> ";
cur = cur->next;
} while (cur != head); // Stop when back at head
cout << "(back to head)" << endl;
}

Short Questions & Answers — Chapter 5

Q: How does Floyd's cycle detection algorithm work?
Ans: Uses two pointers: slow (moves 1 step) and fast (moves 2 steps). If a cycle exists, fast eventually 'laps'
slow and they meet at the same node. If fast reaches nullptr, no cycle. Time: O(n), Space: O(1). Also called
'tortoise and hare' algorithm.

Q: How do you find the middle of a linked list in one pass?

Ans: Use slow and fast pointers. Slow moves 1 step, fast moves 2 steps per iteration. When fast reaches the
end, slow is at the middle. For list 1→2→3→4→5: when fast=5 (end), slow=3 (middle). For even-length list
1→2→3→4: when fast=nullptr, slow=2 (first middle).
Q: What is the difference between singly and doubly linked list?
Ans: Singly: each node has one pointer (next). Traversal only forward. Deletion requires previous node (O(n)
to find). Less memory per node. Doubly: each node has two pointers (prev, next). Bidirectional traversal.
Deletion O(1) if pointer to node is given. More memory (extra pointer per node).
 CHAPTER 6

Sorting Algorithms
Sorting is arranging elements in a specified order (ascending/descending). Choosing the right sorting algorithm
depends on data size, memory constraints, and stability requirements.

6.1 Complete Complexity & Properties Table

Algorithm Best Average Worst Space Stable When to Use

Bubble Sort O(n) O(n²) O(n²) O(1) Yes Learning only

Selection Sort O(n²) O(n²) O(n²) O(1) No Small arrays

Insertion Sort O(n) O(n²) O(n²) O(1) Yes Nearly sorted

Merge Sort O(n log n) O(n log n) O(n log n) O(n) Yes Large datasets, stable needed

Quick Sort O(n log n) O(n log n) O(n²) O(log n) No General purpose (fastest avg)

Heap Sort O(n log n) O(n log n) O(n log n) O(1) No Memory limited, guaranteed

Shell Sort O(n log n) O(n log n) O(n²) O(1) No Medium arrays

Radix Sort O(nk) O(nk) O(nk) O(n+k) Yes Integer keys

Counting Sort O(n+k) O(n+k) O(n+k) O(k) Yes Small integer range

6.2 Simple Sorts — Bubble, Selection, Insertion

void bubbleSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
bool swapped = false;
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
swap(arr[j], arr[j+1]);
swapped = true;
}
}
if (!swapped) break; // Optimization: already sorted → O(n) best case
}
}
// Trace [64,34,25,12]: Pass1→[34,25,12,64], Pass2→[25,12,34,64], Pass3→[12,25,34,64]

void selectionSort(int arr[], int n) {

for (int i = 0; i < n-1; i++) {
int minIdx = i;
for (int j = i+1; j < n; j++)
if (arr[j] < arr[minIdx]) minIdx = j;
swap(arr[i], arr[minIdx]); // Place minimum in correct position
}
}
// Always O(n²) — never better. Minimum swaps = O(n) — good when swap is costly.

void insertionSort(int arr[], int n) {

for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) { // Shift larger elements right
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key; // Insert key at correct position
 }
}
// Best for nearly sorted arrays! O(n) when already sorted.
// Trace [5,3,4,1,2]: i=1: key=3,shift5→[3,5,4,1,2]; i=2: key=4,shift5→[3,4,5,1,2] ...

6.3 Merge Sort — Divide & Conquer

void merge(int arr[], int l, int m, int r) {
int n1 = m-l+1, n2 = r-m;
int L[n1], R[n2];
for(int i=0; i<n1; i++) L[i] = arr[l+i];
for(int j=0; j<n2; j++) R[j] = arr[m+1+j];

int i=0, j=0, k=l;

while(i<n1 && j<n2) {
if(L[i] <= R[j]) arr[k++] = L[i++];
else arr[k++] = R[j++];
}
while(i<n1) arr[k++] = L[i++];
while(j<n2) arr[k++] = R[j++];
}

void mergeSort(int arr[], int l, int r) {

if(l >= r) return; // Base case: single element
int m = l + (r-l)/2;
mergeSort(arr, l, m); // Sort left half
mergeSort(arr, m+1, r); // Sort right half
merge(arr, l, m, r); // Merge sorted halves
}
// Trace [38,27,43,3]:
// Divide: [38,27][43,3] → [38][27][43][3]
// Merge: [27,38][3,43] → [3,27,38,43] ✓
// Always O(n log n) — best, average, worst! Stable. Needs O(n) extra space.

6.4 Quick Sort

int partition(int arr[], int low, int high) {
int pivot = arr[high]; // Choose last element as pivot
int i = low - 1; // i = index of smaller element
for(int j = low; j < high; j++) {
if(arr[j] <= pivot) {
i++;
swap(arr[i], arr[j]); // Place smaller element before pivot
}
}
swap(arr[i+1], arr[high]); // Place pivot in correct position
return i+1;
}

void quickSort(int arr[], int low, int high) {

if(low < high) {
int pi = partition(arr, low, high); // Partition index
quickSort(arr, low, pi-1); // Sort left of pivot
quickSort(arr, pi+1, high); // Sort right of pivot
}
}
// Best/Avg: O(n log n) — pivot splits array evenly
// Worst: O(n²) — when array is sorted and pivot is always min/max
// Fix worst case: random pivot or median-of-three pivot selection

6.5 When to Choose Which Sorting Algorithm?

Situation Best Algorithm Reason

Small array (n < 20) Insertion Sort Low overhead, nearly in-place
 Large data, stability needed Merge Sort O(n log n) guaranteed, stable

General purpose, in-memory Quick Sort Fastest in practice on average

Guaranteed O(n log n), O(1) space Heap Sort No worst-case O(n²)

Nearly sorted data Insertion Sort O(n) for almost-sorted

Integer keys in small range Counting/Radix Sort O(n) — beats comparison sorts

Cannot load all data at once External Merge Sort Processes data in chunks

Short Questions & Answers — Chapter 6

Q: What makes a sorting algorithm 'stable'? Give examples.
Ans: A stable sort preserves the RELATIVE ORDER of elements with equal keys. If A and B are equal and A
appears before B in input, A still appears before B in output. Stable: Bubble, Insertion, Merge Sort, Counting,
Radix. Unstable: Selection, Quick, Heap Sort. Stability matters when sorting objects by multiple keys (e.g.,
sort students by grade, then name).

Q: Explain why Quick Sort is O(n²) in worst case. How to avoid it?
Ans: Worst case: pivot is always the smallest or largest element (e.g., sorted array with last-element pivot).
Partition produces sub-arrays of size 0 and n-1. T(n)=T(n-1)+O(n) → O(n²). Solutions: (1) Random pivot —
pick random element as pivot. (2) Median-of-three — pick median of first, middle, last as pivot. (3) Introsort
(used in std::sort) — switches to heap sort if recursion depth exceeds threshold.

Q: What is the difference between comparison-based and non-comparison-based sorting?

Ans: Comparison-based sorts (bubble, merge, quick, heap) determine order by comparing pairs. Lower bound
is Ω(n log n) — proven by decision tree argument. Non-comparison sorts (counting, radix, bucket) use specific
properties of keys (e.g., integer values, digits) to achieve O(n) in best case, beating the O(n log n) lower
bound.
 CHAPTER 7

Searching — Linear, Binary & Hashing

7.1 Linear Search — O(n)

• Works on ANY array (sorted or unsorted)
• Check each element one by one until found or end reached
• Best: O(1) — found at index 0. Worst: O(n) — not found. Average: O(n/2) = O(n)
int linearSearch(int arr[], int n, int x) {
for (int i = 0; i < n; i++)
if (arr[i] == x) return i; // Return index if found
return -1; // Return -1 if not found
}

7.2 Binary Search — O(log n)

REQUIREMENT: Array must be SORTED! Eliminates half the search space in each step.
// Iterative Binary Search
int binarySearch(int arr[], int n, int x) {
int l=0, r=n-1;
while(l <= r) {
int mid = l + (r-l)/2; // Avoid overflow: (l+r)/2 can overflow!
if(arr[mid] == x) return mid;
if(arr[mid] < x) l = mid+1; // Search right half
else r = mid-1; // Search left half
}
return -1;
}

// Trace: search 23 in [2,5,8,12,16,23,38,56,72,91] (n=10)

// Step 1: l=0,r=9 → mid=4, arr[4]=16 < 23 → l=5
// Step 2: l=5,r=9 → mid=7, arr[7]=56 > 23 → r=6
// Step 3: l=5,r=6 → mid=5, arr[5]=23 == 23 → FOUND at index 5!
// Only 3 steps for 10 elements! log■(10) ≈ 3.32 ✓

7.3 Hashing — O(1) Average

Hashing maps keys to array indices using a hash function. Ideal: O(1) search, insert, delete.

• Hash Function: h(k) = k % tableSize (Division method)

• Collision: Two different keys map to the same index
• Load Factor λ = n/m (n = elements, m = table size). Keep λ < 0.7
• Rehashing: When λ > 0.7, create new table (double size), re-insert all elements

7.4 Collision Resolution Techniques

Method Description Pros Cons

Separate Chaining Each slot holds a linked list of items Simple, handles high load Extra pointer memory, cache miss

Linear Probing If slot taken, try slot+1, slot+2, ... Cache friendly Primary clustering

Quadratic Probing Try slot+1², slot+2², slot+3², ... Less clustering Secondary clustering

Double Hashing Second hash fn gives step size Nearly no cluster Two hash functions needed

// Hash Table with Separate Chaining

#include <list>
 class HashTable {
int size;
list<int>* table;
public:
HashTable(int s) : size(s) { table = new list<int>[s]; }
int hash(int key) { return key % size; }
void insert(int key) { table[hash(key)].push_back(key); }
bool search(int key) {
for (int x : table[hash(key)])
if (x == key) return true;
return false;
}
void remove(int key) { table[hash(key)].remove(key); }
};
// Example: tableSize=7, insert 10,17,24
// 10%7=3 → slot 3: [10]
// 17%7=3 → slot 3: [10,17] (collision! chaining)
// 24%7=3 → slot 3: [10,17,24] (another collision)

Short Questions & Answers — Chapter 7

Q: Why can't binary search be used on unsorted arrays?
Ans: Binary search works by comparing the target with the middle element and eliminating half the array. This
logic only works if we can determine WHICH half contains the target — only possible if array is sorted. For
unsorted arrays, a larger middle value doesn't mean target is in the left half.

Q: What is hashing? What are its time complexities?

Ans: Hashing maps keys to indices using a hash function. Average: O(1) for insert, search, delete. Worst
case: O(n) when all keys collide (one giant chain). To keep O(1) average: maintain load factor < 0.7 and use a
good hash function that distributes keys uniformly.
 CHAPTER 8

Trees — BST, Traversals & AVL Trees

A tree is a hierarchical data structure. Binary Search Trees provide O(log n) search/insert/delete for balanced
trees. AVL trees self-balance to maintain this guarantee.

8.1 Tree Terminology

Term Definition Example

Root Topmost node, no parent Node 50 in a BST

Leaf Node with no children External node

Height Length of longest path from root to leaf Height = log■n for balanced

Depth Distance from root to a node Root depth = 0

Degree Number of children of a node Max 2 for binary tree

Subtree Tree rooted at any node Left/right subtrees

Balanced tree Height difference of left/right subtrees ≤ 1 AVL tree

Complete tree All levels full except possibly last (filled left→right) Heap is complete

8.2 BST Insert, Search, Delete

struct TreeNode {
int data; TreeNode *left, *right;
TreeNode(int d) : data(d), left(nullptr), right(nullptr) {}
};

// Insert: left < node < right

TreeNode* insert(TreeNode* node, int d) {
if (!node) return new TreeNode(d);
if (d < node->data) node->left = insert(node->left, d);
else if (d > node->data) node->right = insert(node->right, d);
return node; // Duplicate ignored
}

// Search: O(h) where h = height

bool search(TreeNode* node, int d) {
if (!node) return false;
if (d == node->data) return true;
if (d < node->data) return search(node->left, d);
return search(node->right, d);
}

// Delete: 3 cases
TreeNode* deleteNode(TreeNode* node, int d) {
if (!node) return node;
if (d < node->data) node->left = deleteNode(node->left, d);
else if (d > node->data) node->right = deleteNode(node->right, d);
else {
// Case 1: No child — just delete
if (!node->left && !node->right) { delete node; return nullptr; }
// Case 2: One child — replace with child
if (!node->left) { TreeNode* t=node->right; delete node; return t; }
if (!node->right) { TreeNode* t=node->left; delete node; return t; }
// Case 3: Two children — replace with in-order successor
 TreeNode* successor = node->right;
while (successor->left) successor = successor->left; // Find min of right subtree
node->data = successor->data; // Copy successor data
node->right = deleteNode(node->right, successor->data); // Delete successor
}
return node;
}

8.3 Tree Traversals — All Four Methods

Traversal Order Algorithm Use Case Output for [50,30,70,20,40]

In-order Left→Root→Right LNR Get sorted sequence 20 30 40 50 70

Pre-order Root→Left→Right NLR Copy/serialize tree 50 30 20 40 70

Post-order Left→Right→Root LRN Delete tree safely 20 40 30 70 50

Level-order Level by level BFS with queue

Print level by level 50 | 30 70 | 20 40

void inorder (TreeNode* n){ if(!n) return; inorder(n->left); cout<<n->data<<" "; inorder(n->right); }
void preorder (TreeNode* n){ if(!n) return; cout<<n->data<<" "; preorder(n->left); preorder(n->right); }
void postorder(TreeNode* n){ if(!n) return; postorder(n->left); postorder(n->right); cout<<n->data<<" "; }

// Level-order (BFS)
void levelOrder(TreeNode* root) {
if (!root) return;
queue<TreeNode*> q;
[Link](root);
while (![Link]()) {
TreeNode* node = [Link](); [Link]();
cout << node->data << " ";
if (node->left) [Link](node->left);
if (node->right) [Link](node->right);
}
}

8.4 AVL Trees — Self-Balancing BST

AVL tree maintains Balance Factor = height(left) - height(right) ∈ {-1, 0, +1} for every node. After
insertion/deletion, if balance is violated, rotations restore it.

Imbalance Case Condition Fix

LL (Left-Left) New node in left subtree of left child Single Right Rotation

RR (Right-Right) New node in right subtree of right child Single Left Rotation

LR (Left-Right) New node in right subtree of left child Left Rotation on child, then Right Rotation

RL (Right-Left) New node in left subtree of right child Right Rotation on child, then Left Rotation

■ TIP: All AVL operations (insert, delete, search) are O(log n) guaranteed because height is always O(log n).
Regular BST degrades to O(n) for sorted input!

Short Questions & Answers — Chapter 8

Q: Why is in-order traversal of BST important?
Ans: In-order traversal (Left-Root-Right) of a BST visits nodes in ASCENDING sorted order. This is because
BST property ensures: all left subtree values < root < all right subtree values. Use case: print BST as sorted
sequence, check if BST is valid.

Q: What is the worst case for BST operations? How does AVL fix it?
Ans: Worst case BST: inserting already-sorted data (1,2,3,4,5) creates a skewed tree (linear chain). All
operations become O(n). AVL tree detects imbalance via balance factor after each insert/delete and performs
O(1) rotations to restore balance. Guarantees O(log n) for all operations.
 CHAPTER 9

Heaps & Heap Sort

A Heap is a complete binary tree satisfying the heap property. Max-Heap: parent ≥ children. Min-Heap: parent ≤
children. Stored efficiently as an array.

9.1 Heap Array Representation

• For node at index i: Left child = 2i+1, Right child = 2i+2, Parent = (i-1)/2
• Array [10, 9, 8, 7, 6, 5, 4] represents a valid Max-Heap
• Root is always at index 0 (maximum for max-heap, minimum for min-heap)
class MaxHeap {
int* arr; int capacity, size;
public:
MaxHeap(int cap) : capacity(cap), size(0) { arr = new int[cap]; }

void insert(int key) {

if (size == capacity) { cout << "Heap full!"; return; }
arr[size++] = key; // Add at end
heapifyUp(size-1); // Restore heap property upward
}

void heapifyUp(int i) {
while (i > 0 && arr[i] > arr[(i-1)/2]) { // While child > parent
swap(arr[i], arr[(i-1)/2]);
i = (i-1)/2;
}
}

int extractMax() {
if (size == 0) return -1;
int maxVal = arr[0]; // Save root (max)
arr[0] = arr[--size]; // Replace root with last element
heapifyDown(0); // Restore heap property downward
return maxVal;
}

void heapifyDown(int i) {
int largest = i;
int l = 2*i+1, r = 2*i+2;
if (l < size && arr[l] > arr[largest]) largest = l;
if (r < size && arr[r] > arr[largest]) largest = r;
if (largest != i) {
swap(arr[i], arr[largest]);
heapifyDown(largest); // Recurse on swapped child
}
}

int peek() { return size ? arr[0] : -1; } // O(1)!

};

9.2 Build Heap from Array — O(n)

Instead of inserting one by one (O(n log n)), we can build a heap in O(n) by heapifying from the last internal
node up to the root.
void buildHeap(int arr[], int n) {
// Start from last non-leaf node: n/2 - 1
for (int i = n/2 - 1; i >= 0; i--) {
 heapifyDown(arr, n, i);
}
}
// Proof O(n): Most nodes are near leaves and heapify takes O(1) for them.
// Total work = O(n) by summation of geometric series.

9.3 Heap Sort Algorithm

void heapSort(int arr[], int n) {
// Phase 1: Build max heap — O(n)
for (int i = n/2-1; i >= 0; i--)
heapifyDown(arr, n, i);

// Phase 2: Extract max n-1 times — O(n log n)

for (int i = n-1; i > 0; i--) {
swap(arr[0], arr[i]); // Move current max to end
heapifyDown(arr, i, 0); // Heapify reduced heap
}
}
// Trace [4,10,3,5,1]:
// Build heap: [10,5,3,4,1]
// Extract: swap 10↔1 → [1,5,3,4|10] → heapify → [5,4,3,1|10]
// Extract: swap 5↔1 → [1,4,3|5,10] → heapify → [4,1,3|5,10]
// Extract: swap 4↔3 → [3,1|4,5,10] → heapify → [3,1|4,5,10]
// Extract: swap 3↔1 → [1|3,4,5,10] → DONE: [1,3,4,5,10] ✓
// Total: O(n log n) time, O(1) space, NOT stable

Short Questions & Answers — Chapter 9

Q: What is the difference between Max-Heap and Min-Heap?
Ans: Max-Heap: every parent ≥ its children. Root = maximum element. Used for: max priority queue, heap
sort. Min-Heap: every parent ≤ its children. Root = minimum element. Used for: min priority queue, Dijkstra's
algorithm, Prim's algorithm (finding minimum spanning tree).

Q: Why is heap sort not stable?

Ans: During heapification, elements are swapped non-locally (e.g., root swapped with last element). This can
change the relative order of equal elements. Example: if array has [5a, 5b] where a comes first, heap sort may
output [5b, 5a]. Merge sort is preferred when stability is required.

Q: What is the time complexity of building a heap? Why O(n) and not O(n log n)?
Ans: Building a heap by heapifying from index n/2-1 down to 0 is O(n). Intuition: half the nodes are leaves
(require 0 work), quarter require O(1) work, etc. Summing: n/2*0 + n/4*1 + n/8*2 + ... = O(n) by geometric
series. Inserting n elements one by one would be O(n log n).
 CHAPTER 10

Graphs — BFS, DFS, Dijkstra & Topological Sort

A Graph G=(V,E) consists of vertices (nodes) and edges (connections). Used to model networks, maps, social
connections, dependencies, and more.

10.1 Graph Types & Terminology

Type Description Example

Undirected Edges have no direction Facebook friendship

Directed (Digraph) Edges have direction (u→v) Twitter follow, web links

Weighted Edges have costs/distances Road map with distances

Unweighted All edges equal Social network (friend/not)

Cyclic Contains at least one cycle Road network with roundabouts

Acyclic No cycles Tree is a special acyclic graph

DAG Directed Acyclic Graph Task dependencies, build systems

Connected Path exists between all vertex pairs One-component network

Sparse Few edges (E << V²) Road network

Dense Many edges (E ≈ V²) Social network among small group

10.2 Graph Representations

Feature Adjacency Matrix Adjacency List

Space O(V²) O(V + E)

Check edge (u,v) O(1) O(degree of u)

Find all neighbors O(V) O(degree of u)

Best for Dense graphs Sparse graphs (most real-world)

Add vertex O(V²) — resize matrix O(1)

Add edge O(1) O(1)

10.3 BFS & DFS Implementations

#include <vector>
#include <queue>
using namespace std;

class Graph {
int V;
vector<int>* adj;
public:
Graph(int v) : V(v) { adj = new vector<int>[v]; }
void addEdge(int u, int v) { adj[u].push_back(v); adj[v].push_back(u); }

// BFS — Level by Level, uses QUEUE, O(V+E)

void BFS(int start) {
vector<bool> visited(V, false);
 queue<int> q;
visited[start] = true;
[Link](start);
while (![Link]()) {
int v = [Link](); [Link]();
cout << v << " ";
for (int u : adj[v])
if (!visited[u]) { visited[u]=true; [Link](u); }
}
}

// DFS — Goes Deep First, uses STACK/RECURSION, O(V+E)

void DFSUtil(int v, vector<bool>& visited) {
visited[v] = true;
cout << v << " ";
for (int u : adj[v])
if (!visited[u]) DFSUtil(u, visited);
}
void DFS(int start) {
vector<bool> visited(V, false);
DFSUtil(start, visited);
}
};
// Graph: 0-1, 0-2, 1-3, 2-4, 3-5, 4-5
// BFS from 0: 0 1 2 3 4 5 (level by level)
// DFS from 0: 0 1 3 5 4 2 (goes deep first)

10.4 BFS vs DFS Applications

Aspect BFS DFS

Data Structure Queue (FIFO) Stack / Recursion

Order Level by level Depth first (as far as possible)

Space O(V) — stores level nodes O(V) — stores recursion stack

Shortest path Yes (unweighted graphs) No (not guaranteed)

Cycle detection Yes Yes

Topological sort No Yes (DFS-based)

Shortest path, web crawler, peer-to-peer, Maze solving, topological sort,

Applications social network levels strongly connected components

10.5 Dijkstra's Shortest Path Algorithm

// Dijkstra: single-source shortest path, weighted graph (no negative weights)
// Time: O((V+E) log V) with priority queue
void dijkstra(vector<pair<int,int>> adj[], int V, int src) {
vector<int> dist(V, INT_MAX); // All distances = infinity
priority_queue<pair<int,int>,
vector<pair<int,int>>,
greater<>> pq; // Min-heap: {distance, vertex}
dist[src] = 0;
[Link]({0, src});

while (![Link]()) {
auto [d, u] = [Link](); [Link]();
if (d > dist[u]) continue; // Outdated entry, skip

for (auto [w, v] : adj[u]) { // For each neighbor

if (dist[u] + w < dist[v]) { // Relaxation step
dist[v] = dist[u] + w;
[Link]({dist[v], v});
}
 }
}
for (int i=0; i<V; i++)
cout << "dist[" << i << "] = " << dist[i] << endl;
}
// Dijkstra does NOT work with negative weight edges!
// For negative edges, use Bellman-Ford: O(VE)

Short Questions & Answers — Chapter 10

Q: What is topological sorting? When is it possible?
Ans: Topological sort is a linear ordering of vertices in a DAG (Directed Acyclic Graph) such that for every
directed edge u→v, vertex u comes before v. Possible ONLY for DAGs — if graph has a cycle, topological
sort is impossible (cycle creates circular dependency). Used in: build systems (compile order), task
scheduling, course prerequisites.

Q: Why doesn't Dijkstra work with negative weight edges?

Ans: Dijkstra greedily assumes: once a vertex is extracted from the min-heap as 'settled' with distance d, no
shorter path exists. With negative edges, a later path through a negative edge could be shorter, violating this
assumption. Use Bellman-Ford for negative edges — it relaxes all edges V-1 times, correctly handling
negative weights. O(VE) time.
 CHAPTER 11

Memory Management & Garbage Collection

11.1 Stack vs Heap Memory

Aspect Stack Memory Heap Memory

Management Automatic (OS managed) Manual (C++) or GC (Java/C#)

Size Fixed, limited (usually 1-8 MB) Large (GBs), limited by RAM

Speed Very fast (pointer arithmetic) Slower (allocator overhead)

Structure LIFO — grows/shrinks with call stack Random access, fragmented

Stores Local variables, function parameters Objects, dynamic arrays, nodes

Allocation Compile time (size known) Runtime (size can vary)

Lifetime Until function returns Until freed/collected

Overflow Stack overflow (deep recursion) Out of memory (allocation fails)

11.2 Dynamic Memory in C++

// Stack allocation — automatic
int x = 10; // On stack, freed when scope exits
int arr[100]; // Fixed-size array on stack

// Heap allocation — manual

int* ptr = new int(42); // Single integer on heap
int* arr2 = new int[100]; // Array on heap
delete ptr; // MUST free! else memory leak
delete[] arr2; // Use delete[] for arrays!

// Common Memory Errors:

// 1. Memory Leak — forgot to delete
void leak() {
int* p = new int(5);
// No delete p! — p is lost when function returns
}

// 2. Dangling Pointer — using freed memory

int* dp = new int(10);
delete dp;
// dp still holds old address — accessing it is UNDEFINED BEHAVIOR!
dp = nullptr; // Fix: set to nullptr after delete

// 3. Double Free — freeing same memory twice (CRASH!)

int* df = new int(5);
delete df;
// delete df; // ERROR! Already freed!

// Smart Pointers — C++11 (PREFER these over raw new/delete)

#include <memory>
unique_ptr<int> up = make_unique<int>(42); // Auto-deleted when out of scope
shared_ptr<int> sp = make_shared<int>(10); // Reference counted

11.3 Garbage Collection Strategies

Strategy How it Works Pros Cons Used In
Reference CountingCount references to each object; Immediate reclaim, simple
Can't handle cycles Python (+ cycle detector)
free when count=0

Mark and Sweep Mark all reachable objects from roots,

Handles cycles 'Stop-the-world' pauses
Java, C#, JavaScript
then sweep (free) unmarked

Stop-and-Copy Copy live objects to new space, No fragmentation Uses 2x memory Early Java VMs
free entire old space

Generational GC Young generation (collected often), Fast for short-lived objects

Complex implementation
JVM, .NET CLR, Python
old generation (rarely)

Incremental GC GC runs in small increments, Low pause times Complexity, synchronization

Modern JS engines
interleaved with program
 CHAPTER 12

Quick Reference — Data Structure Comparison

Master Comparison Table — All Data Structures

Operation Array Linked List Stack Queue BST (bal.) Hash Table

Access O(1) O(n) O(n) O(n) O(log n) O(1) avg

Search O(n) O(n) O(n) O(n) O(log n) O(1) avg

Insert (begin) O(n) O(1) O(1)* O(n) O(log n) O(1) avg

Insert (end) O(1)* O(n) O(1)* O(1)* O(log n) O(1) avg

Delete O(n) O(1)** O(1) O(1) O(log n) O(1) avg

Space O(n) O(n) O(n) O(n) O(n) O(n)

■ NOTE: * = amortized O(1) ** = O(1) if pointer to node is known

When to Use Which Data Structure

Use Case Best Data Structure Reason

Fast insert/delete at front Linked List O(1) vs array's O(n)

Fast random access Array O(1) index access

LIFO operations Stack push/pop O(1)

FIFO operations Queue enqueue/dequeue O(1)

Priority-based processing Priority Queue (Heap) O(log n) insert/extract

Fast search by key Hash Table O(1) average lookup

Sorted data with fast search BST / AVL Tree O(log n) all operations

Hierarchical data Tree Natural parent-child model

Network/relationship modeling Graph Vertices + edges model

Guaranteed O(log n) ops AVL / Red-Black Tree Self-balancing

Find max/min quickly Heap O(1) peek, O(log n) extract

Range queries (find values in a-b) BST / Sorted Array In-order traversal
 CHAPTER 13

Practice MCQs & Exam Tips

Practice MCQs
Q1. What is the time complexity of accessing element arr[i] in an array?
A) O(n) B) O(log n) C) O(1) D) O(n²)
✓ Answer: C

Q2. Which data structure is used for function call management?

A) Queue B) Stack C) Tree D) Graph
✓ Answer: B

Q3. What traversal of BST gives elements in sorted order?

A) Pre-order B) Post-order C) Level-order D) In-order
✓ Answer: D

Q4. What is the worst-case time complexity of Quick Sort?

A) O(n log n) B) O(n²) C) O(n) D) O(log n)
✓ Answer: B

Q5. Which sorting algorithm is stable AND has O(n log n) worst case?
A) Quick Sort B) Heap Sort C) Merge Sort D) Shell Sort
✓ Answer: C

Q6. In a Max-Heap with n elements, the maximum is at index:

A) n-1 B) n/2 C) 0 D) 1
✓ Answer: C

Q7. What is the space complexity of Merge Sort?

A) O(1) B) O(log n) C) O(n) D) O(n²)
✓ Answer: C

Q8. Which algorithm finds shortest path in unweighted graph?

A) DFS B) Dijkstra C) BFS D) Topological Sort
✓ Answer: C

Q9. Hash table average case time complexity for search is:
A) O(n) B) O(log n) C) O(n²) D) O(1)
✓ Answer: D

Q10. For AVL tree, balance factor must be:

A) 0 only B) -1, 0, or +1 C) Any value D) -2 to +2
✓ Answer: B

Q11. Which data structure is best for implementing Dijkstra's algorithm?

A) Stack B) Queue C) Priority Queue (Min-Heap) D) Array
✓ Answer: C

Q12. What is the time complexity of building a heap from n elements?

A) O(n log n) B) O(n²) C) O(n) D) O(log n)
✓ Answer: C

Q13. Circular queue uses modulo to handle:

 A) Overflow B) Underflow C) Wrap-around D) Sorting
✓ Answer: C

Q14. Which is NOT a collision resolution technique?

A) Chaining B) Linear Probing C) Heapify D) Double Hashing
✓ Answer: C

Q15. Post-order traversal visits nodes in which order?

A) Root-Left-Right B) Left-Root-Right C) Left-Right-Root D) Right-Left-Root
✓ Answer: C

Exam Tips & Strategy

■ TIP: Always state time AND space complexity when asked about an algorithm — examiners expect both.
■ TIP: For BST questions, always trace through an example — insert 50,30,70,20,40,60,80 to visualize.
■ TIP: Remember: in-order BST = sorted output. This is a very common exam question.
■ TIP: For sorting: know which are stable (Merge, Insertion, Bubble, Counting, Radix) vs unstable (Quick, Heap,
Selection).
■ TIP: Big O rules: drop constants, keep dominant term only. 3n²+5n+100 → O(n²).
■ TIP: Linked list pointer questions: always draw a diagram. Mistakes happen when you don't visualize pointer
changes.
■ TIP: For recursion questions: identify base case first, then recursive case. Write recurrence relation.
■ TIP: AVL rotations: LL→right rotate, RR→left rotate, LR→left then right, RL→right then left.
■ TIP: Dijkstra: only for non-negative weights. Bellman-Ford for negative weights. BFS for unweighted.
■ TIP: Hash table: load factor λ = n/m. Keep < 0.7 for O(1) performance. Rehash when exceeded.
■ TIP: Heap array: left child = 2i+1, right = 2i+2, parent = (i-1)/2. Memorize these formulas!
■ TIP: For C++ programs: always include necessary headers, handle edge cases (empty/null checks), free
memory.

Best of Luck on Your Exam! ■

Review all C++ programs, practice tracing algorithms manually, and understand WHY each complexity is
what it is.