Complete Data Structures C++ Implementation Templates
Summary
This document provides comprehensive C++ code templates and explanations for fundamental data structures and algorithms. It covers arrays, singly and doubly linked lists, circular lists, stacks, queues, recursion, and merge sort, complete with safety checks and edge cases for academic exams.
Key points
- Arrays support operations like traversal, searching, insertion, deletion, and sorting with O(n) or O(n log n) complexities.
- Singly and doubly linked lists manage dynamic data using pointers like head, tail, next, and prev.
- Stacks follow the LIFO principle, implemented using arrays or linked lists, essential for expression evaluation and parentheses matching.
- Queues follow the FIFO principle, featuring linear, circular, and linked queue implementations.
- Recursion and divide-and-conquer techniques are demonstrated through factorial, Fibonacci, Towers of Hanoi, and merge sort.
Lecture 1 — Introduction to Data Structures
Is lecture mein mostly theory, ADT, data organization, time aur space complexity aati hai. Is mein koi specific data structure implementation template nahi.
Basic program template:
#include <iostream>
using namespace std;
int main()
{
// Declare variables
// Take input
// Perform operation
// Display output
return 0;
}Algorithm likhne ka template:
START
Input data
Perform required operation
Display result
STOPADT (Abstract Data Type) ka answer likhne ke liye:
Data structure ka naam
Data kis tarah store hota hai
Available operations
Operations ka expected behaviour
Example: Stack ADT mein push, pop, top, isEmpty operations hoti hain.
Lecture 2 — Arrays
1. Array declaration and input/output
Ye sab se basic template hai.
#include <iostream>
using namespace std;
int main()
{
int arr[100];
int n;
cout << "Enter size: ";
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
return 0;
}Kis question mein? Array input lena, display karna, traverse karna.
2. Traversal
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}3. Sum of array
int sum = 0;
for (int i = 0; i < n; i++)
{
sum = sum + arr[i];
}
cout << sum;4. Maximum element
int maxValue = arr[0];
for (int i = 1; i < n; i++)
{
if (arr[i] > maxValue)
{
maxValue = arr[i];
}
}
cout << maxValue;5. Minimum element
int minValue = arr[0];
for (int i = 1; i < n; i++)
{
if (arr[i] < minValue)
{
minValue = arr[i];
}
}
cout << minValue;6. Linear Search
int key;
cin >> key;
int found = -1;
for (int i = 0; i < n; i++)
{
if (arr[i] == key)
{
found = i;
break;
}
}
if (found != -1)
cout << "Found at index " << found;
else
cout << "Not found";Kis question mein? Kisi value ko array mein search karna.
7. Insertion at a given index
int pos, value;
cin >> pos >> value;
for (int i = n; i > pos; i--)
{
arr[i] = arr[i - 1];
}
arr[pos] = value;
n++;Samjho: Right side se elements shift karte hain taake position empty ho jaye.
8. Deletion at a given index
int pos;
cin >> pos;
for (int i = pos; i < n - 1; i++)
{
arr[i] = arr[i + 1];
}
n--;Samjho: Left side se elements shift karke deleted position fill kar dete hain.
9. Bubble Sort — Ascending
for (int i = 0; i < n - 1; i++)
{
for (int j = 0; j < n - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}Descending ke liye sirf condition change:
if (arr[j] < arr[j + 1])10. Binary Search
Condition: Array sorted hona chahiye.
int key;
cin >> key;
int low = 0;
int high = n - 1;
int found = -1;
while (low <= high)
{
int mid = low + (high - low) / 2;
if (arr[mid] == key)
{
found = mid;
break;
}
else if (arr[mid] < key)
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
cout << found;11. Reverse an array
int start = 0;
int end = n - 1;
while (start < end)
{
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}12. Dynamic Array
int n;
cin >> n;
int* arr = new int[n];
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
delete[] arr;13. 2D Array
int arr[3][3];
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
cin >> arr[i][j];
}
}
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
cout << arr[i][j] << " ";
}
cout << endl;
}14. Vector Template
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.pop_back();
for (int i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
return 0;
}Array ke questions mein yaad rakho:
Question | Template |
|---|---|
Display | Traversal |
Total | Sum |
Largest | Maximum |
Smallest | Minimum |
Find value | Linear/Binary Search |
Add value | Insertion |
Remove value | Deletion |
Arrange values | Sorting |
Reverse | Two pointers |
Lecture 3 — Singly Linked List
Is lecture ka sab se important part Node aur pointers hain.
1. Node class — Ye sab se pehle likhni hai
class Node
{
public:
int data;
Node* next;
Node(int value)
{
data = value;
next = NULL;
}
};Meaning:
data= value store karta hai.next= next node ka address store karta hai.NULL= aage koi node nahi.
2. Linked List class ka basic structure
class LinkedList
{
Node* head;
public:
LinkedList()
{
head = NULL;
}
};head first node ka address rakhta hai.
3. Insertion at Beginning
void insertAtBeginning(int value)
{
Node* newNode = new Node(value);
newNode->next = head;
head = newNode;
}Diagram:
Before:
head → 10 → 20 → NULL
Insert 5
After:
head → 5 → 10 → 20 → NULL4. Insertion at End
void insertAtEnd(int value)
{
Node* newNode = new Node(value);
if (head == NULL)
{
head = newNode;
return;
}
Node* temp = head;
while (temp->next != NULL)
{
temp = temp->next;
}
temp->next = newNode;
}5. Insertion at Position
Yahan position 1-based hai.
void insertAtPosition(int value, int pos)
{
Node* newNode = new Node(value);
if (pos == 1)
{
newNode->next = head;
head = newNode;
return;
}
Node* temp = head;
for (int i = 1; i < pos - 1; i++)
{
temp = temp->next;
}
newNode->next = temp->next;
temp->next = newNode;
}6. Deletion from Beginning
void deleteFromBeginning()
{
if (head == NULL)
return;
Node* temp = head;
head = head->next;
delete temp;
}7. Deletion from End
void deleteFromEnd()
{
if (head == NULL)
return;
if (head->next == NULL)
{
delete head;
head = NULL;
return;
}
Node* temp = head;
while (temp->next->next != NULL)
{
temp = temp->next;
}
delete temp->next;
temp->next = NULL;
}8. Deletion at Position
void deleteAtPosition(int pos)
{
if (head == NULL)
return;
if (pos == 1)
{
Node* temp = head;
head = head->next;
delete temp;
return;
}
Node* temp = head;
for (int i = 1; i < pos - 1; i++)
{
temp = temp->next;
}
Node* delNode = temp->next;
temp->next = delNode->next;
delete delNode;
}9. Traversal / Display
void display()
{
Node* temp = head;
while (temp != NULL)
{
cout << temp->data << " ";
temp = temp->next;
}
}10. Search
bool search(int key)
{
Node* temp = head;
while (temp != NULL)
{
if (temp->data == key)
return true;
temp = temp->next;
}
return false;
}11. Count Nodes
int countNodes()
{
int count = 0;
Node* temp = head;
while (temp != NULL)
{
count++;
temp = temp->next;
}
return count;
}12. Delete a Specific Value
void deleteValue(int value)
{
if (head == NULL)
return;
if (head->data == value)
{
Node* temp = head;
head = head->next;
delete temp;
return;
}
Node* prev = head;
Node* curr = head->next;
while (curr != NULL && curr->data != value)
{
prev = curr;
curr = curr->next;
}
if (curr == NULL)
return;
prev->next = curr->next;
delete curr;
}13. Concatenate Two Linked Lists
void concatenate(Node* head2)
{
if (head == NULL)
{
head = head2;
return;
}
Node* temp = head;
while (temp->next != NULL)
{
temp = temp->next;
}
temp->next = head2;
}Important linked list patterns:
Question | Kya use hoga? |
|---|---|
Start par insert |
|
End par insert |
|
Start se delete |
|
End se delete | Second-last node find karo |
Traverse |
|
Search |
|
Specific delete |
|
Lecture 4 — Doubly and Circular Linked Lists
Part A: Doubly Linked List
Singly linked list mein aik pointer hota hai: next.
Doubly linked list mein two pointers hote hain:
next= next node ka addressprev= previous node ka address
Diagram:
NULL ← 10 ⇄ 20 ⇄ 30 → NULL
head tail1. Node Class
class Node
{
public:
int data;
Node* next;
Node* prev;
Node(int value)
{
data = value;
next = NULL;
prev = NULL;
}
};2. Doubly Linked List Structure
class DoublyList
{
Node* head;
Node* tail;
public:
DoublyList()
{
head = NULL;
tail = NULL;
}
};3. Insert at Beginning
void insertAtBeginning(int value)
{
Node* newNode = new Node(value);
if (head == NULL)
{
head = tail = newNode;
return;
}
newNode->next = head;
head->prev = newNode;
head = newNode;
}4. Insert at End
void insertAtEnd(int value)
{
Node* newNode = new Node(value);
if (head == NULL)
{
head = tail = newNode;
return;
}
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
}5. Delete from Beginning
void deleteFromBeginning()
{
if (head == NULL)
return;
Node* temp = head;
if (head == tail)
{
head = tail = NULL;
}
else
{
head = head->next;
head->prev = NULL;
}
delete temp;
}6. Delete from End
void deleteFromEnd()
{
if (tail == NULL)
return;
Node* temp = tail;
if (head == tail)
{
head = tail = NULL;
}
else
{
tail = tail->prev;
tail->next = NULL;
}
delete temp;
}7. Forward Traversal
void displayForward()
{
Node* temp = head;
while (temp != NULL)
{
cout << temp->data << " ";
temp = temp->next;
}
}8. Backward Traversal
void displayBackward()
{
Node* temp = tail;
while (temp != NULL)
{
cout << temp->data << " ";
temp = temp->prev;
}
}9. Delete a Specific Value
void deleteValue(int value)
{
Node* temp = head;
while (temp != NULL && temp->data != value)
{
temp = temp->next;
}
if (temp == NULL)
return;
if (temp == head)
{
deleteFromBeginning();
return;
}
if (temp == tail)
{
deleteFromEnd();
return;
}
temp->prev->next = temp->next;
temp->next->prev = temp->prev;
delete temp;
}Doubly linked list ka golden rule: Beech mein insertion/deletion karte waqt dono directions ke links update karne hain.
Part B: Circular Singly Linked List
Circular list mein last node ka next, NULL nahi hota. Woh first node ko point karta hai.
head → 10 → 20 → 30
↑ |
└─────────┘Lecture mein circular singly linked list ko tail pointer se implement kiya gaya hai.
tail->next first node hota hai.
1. Node Class
class Node
{
public:
int data;
Node* next;
Node(int value)
{
data = value;
next = NULL;
}
};2. Circular List Structure
class CircularList
{
Node* tail;
public:
CircularList()
{
tail = NULL;
}
};3. Insert at Beginning
void insertAtBeginning(int value)
{
Node* newNode = new Node(value);
if (tail == NULL)
{
tail = newNode;
tail->next = tail;
}
else
{
newNode->next = tail->next;
tail->next = newNode;
}
}4. Insert at End
void insertAtEnd(int value)
{
Node* newNode = new Node(value);
if (tail == NULL)
{
tail = newNode;
tail->next = tail;
}
else
{
newNode->next = tail->next;
tail->next = newNode;
tail = newNode;
}
}5. Delete from Beginning
void deleteFromBeginning()
{
if (tail == NULL)
return;
Node* head = tail->next;
if (head == tail)
{
delete head;
tail = NULL;
}
else
{
tail->next = head->next;
delete head;
}
}6. Delete from End
void deleteFromEnd()
{
if (tail == NULL)
return;
Node* head = tail->next;
if (head == tail)
{
delete tail;
tail = NULL;
return;
}
Node* temp = head;
while (temp->next != tail)
{
temp = temp->next;
}
temp->next = tail->next;
delete tail;
tail = temp;
}7. Display Circular List
void display()
{
if (tail == NULL)
return;
Node* temp = tail->next;
do
{
cout << temp->data << " ";
temp = temp->next;
}
while (temp != tail->next);
}Important: Circular list mein normal while(temp != NULL) traversal nahi karte, kyun ke NULL aata hi nahi. Is liye do-while use hota hai.
Part C: Circular Doubly Linked List
Is mein har node ke next aur prev pointers hote hain, aur dono ends circularly connected hote hain.
10 ⇄ 20 ⇄ 30
↑ ↓
└──────────┘Agar head aur tail dono available hon:
Insert at Beginning
void insertAtBeginning(int value)
{
Node* newNode = new Node(value);
if (head == NULL)
{
head = tail = newNode;
newNode->next = newNode;
newNode->prev = newNode;
}
else
{
newNode->next = head;
newNode->prev = tail;
head->prev = newNode;
tail->next = newNode;
head = newNode;
}
}Insert at End
void insertAtEnd(int value)
{
Node* newNode = new Node(value);
if (head == NULL)
{
head = tail = newNode;
newNode->next = newNode;
newNode->prev = newNode;
}
else
{
newNode->prev = tail;
newNode->next = head;
tail->next = newNode;
head->prev = newNode;
tail = newNode;
}
}Exam mein yaad rakhna:
Type | Node pointers | Last node |
|---|---|---|
Singly |
|
|
Doubly |
|
|
Circular Singly |
|
|
Circular Doubly |
|
|
Lecture 5 — Stack
Stack LIFO follow karta hai:
Last In, First Out
Jo element last mein insert hota hai, woh pehle remove hota hai.
Important operations:
push()= insertpop()= removetop()/peek()= top element dekhnaisEmpty()= check emptyisFull()= check full
Part A: Stack Using Array
1. Complete Stack Class
#include <iostream>
using namespace std;
#define SIZE 5
class Stack
{
int arr[SIZE];
int top;
public:
Stack()
{
top = -1;
}
bool isEmpty()
{
return top == -1;
}
bool isFull()
{
return top == SIZE - 1;
}
void push(int value)
{
if (isFull())
{
cout << "Stack Overflow\n";
return;
}
top++;
arr[top] = value;
}
int pop()
{
if (isEmpty())
{
cout << "Stack Underflow\n";
return -1;
}
return arr[top--];
}
int peek()
{
if (isEmpty())
return -1;
return arr[top];
}
void display()
{
for (int i = top; i >= 0; i--)
{
cout << arr[i] << " ";
}
cout << endl;
}
};2. Main Function
int main()
{
Stack s;
s.push(10);
s.push(20);
s.push(30);
s.display();
cout << s.peek() << endl;
cout << s.pop() << endl;
s.display();
return 0;
}Output:
30 20 10
30
30
20 10Part B: Stack Using Linked List
1. Node Class
class Node
{
public:
int data;
Node* next;
Node(int value)
{
data = value;
next = NULL;
}
};2. Stack Class
class Stack
{
Node* topNode;
public:
Stack()
{
topNode = NULL;
}
bool isEmpty()
{
return topNode == NULL;
}
void push(int value)
{
Node* newNode = new Node(value);
newNode->next = topNode;
topNode = newNode;
}
int pop()
{
if (isEmpty())
return -1;
Node* temp = topNode;
int value = temp->data;
topNode = topNode->next;
delete temp;
return value;
}
int peek()
{
if (isEmpty())
return -1;
return topNode->data;
}
void display()
{
Node* temp = topNode;
while (temp != NULL)
{
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
};Difference yaad rakho:
Array Stack | Linked List Stack |
|---|---|
Fixed size | Dynamic size |
|
|
| New node at beginning |
| Delete first node |
Part C: Reverse a String Using Stack
string str = "HELLO";
Stack s;
for (int i = 0; i < str.length(); i++)
{
s.push(str[i]);
}
while (!s.isEmpty())
{
cout << (char)s.pop();
}Output:
OLLEHPart D: Parentheses Matching
Ye bohat common stack question hai.
bool isBalanced(string str)
{
Stack s;
for (int i = 0; i < str.length(); i++)
{
char ch = str[i];
if (ch == '(' || ch == '[' || ch == '{')
{
s.push(ch);
}
else if (ch == ')' || ch == ']' || ch == '}')
{
if (s.isEmpty())
return false;
char x = s.pop();
if (ch == ')' && x != '(')
return false;
if (ch == ']' && x != '[')
return false;
if (ch == '}' && x != '{')
return false;
}
}
return s.isEmpty();
}Example:
{[()]} → Balanced
([)] → Not Balanced
((()) → Not BalancedPart E: Postfix Evaluation
Example:
23+Is ka answer 5 hai.
Rule: Left operand pehle pop karo, right operand doosre pop karo.
int evaluatePostfix(string exp)
{
Stack s;
for (int i = 0; i < exp.length(); i++)
{
char ch = exp[i];
if (ch >= '0' && ch <= '9')
{
s.push(ch - '0');
}
else
{
int b = s.pop();
int a = s.pop();
if (ch == '+')
s.push(a + b);
else if (ch == '-')
s.push(a - b);
else if (ch == '*')
s.push(a * b);
else if (ch == '/')
s.push(a / b);
}
}
return s.pop();
}Ye basic template single-digit operands aur + - * / ke liye hai.
Part F: Infix to Postfix — Basic Template
Example:
A+B*CPostfix:
ABC*+Operator priority:
Operator | Priority |
|---|---|
| 3 |
| 2 |
| 1 |
Priority function:
int priority(char ch)
{
if (ch == '^')
return 3;
if (ch == '*' || ch == '/')
return 2;
if (ch == '+' || ch == '-')
return 1;
return 0;
}Basic conversion logic:
string infixToPostfix(string exp)
{
Stack s;
string postfix = "";
for (int i = 0; i < exp.length(); i++)
{
char ch = exp[i];
if (ch >= 'A' && ch <= 'Z')
{
postfix += ch;
}
else if (ch == '(')
{
s.push(ch);
}
else if (ch == ')')
{
while (!s.isEmpty() && s.peek() != '(')
{
postfix += (char)s.pop();
}
s.pop();
}
else
{
while (!s.isEmpty() && s.peek() != '(' &&
priority(s.peek()) >= priority(ch))
{
postfix += (char)s.pop();
}
s.push(ch);
}
}
while (!s.isEmpty())
{
postfix += (char)s.pop();
}
return postfix;
}Important limitation: Ye basic conversion template ^ ki right associativity handle nahi karta. Agar paper mein exponent ^ ho, toh equal priority par >= ki jagah associativity check karni hogi. A^B^C ka correct postfix ABC^^ hota hai.
Lecture 6 — Queues
Queue FIFO follow karti hai:
First In, First Out
enqueue()= insert from reardequeue()= remove from frontfront= first elementrear= last element
Part A: Linear Queue Using Array
#include <iostream>
using namespace std;
#define SIZE 5
class Queue
{
int arr[SIZE];
int front, rear;
public:
Queue()
{
front = -1;
rear = -1;
}
bool isEmpty()
{
return front == -1;
}
bool isFull()
{
return rear == SIZE - 1;
}
void enqueue(int value)
{
if (isFull())
{
cout << "Queue Overflow\n";
return;
}
if (front == -1)
front = 0;
rear++;
arr[rear] = value;
}
int dequeue()
{
if (isEmpty())
{
cout << "Queue Underflow\n";
return -1;
}
int value = arr[front];
if (front == rear)
{
front = rear = -1;
}
else
{
front++;
}
return value;
}
void display()
{
if (isEmpty())
return;
for (int i = front; i <= rear; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
};Part B: Circular Queue Using Array
Circular queue mein empty spaces dobara use ho sakti hain.
Magic formula:
(rear + 1) % SIZE
(front + 1) % SIZEComplete template:
#include <iostream>
using namespace std;
#define SIZE 5
class CircularQueue
{
int arr[SIZE];
int front, rear, count;
public:
CircularQueue()
{
front = 0;
rear = -1;
count = 0;
}
bool isEmpty()
{
return count == 0;
}
bool isFull()
{
return count == SIZE;
}
void enqueue(int value)
{
if (isFull())
{
cout << "Queue Full\n";
return;
}
rear = (rear + 1) % SIZE;
arr[rear] = value;
count++;
}
int dequeue()
{
if (isEmpty())
{
cout << "Queue Empty\n";
return -1;
}
int value = arr[front];
front = (front + 1) % SIZE;
count--;
return value;
}
void display()
{
for (int i = 0; i < count; i++)
{
cout << arr[(front + i) % SIZE] << " ";
}
cout << endl;
}
};Part C: Queue Using Linked List
1. Node Class
class Node
{
public:
int data;
Node* next;
Node(int value)
{
data = value;
next = NULL;
}
};2. Linked Queue Class
class LinkedQueue
{
Node* front;
Node* rear;
public:
LinkedQueue()
{
front = rear = NULL;
}
bool isEmpty()
{
return front == NULL;
}
void enqueue(int value)
{
Node* newNode = new Node(value);
if (isEmpty())
{
front = rear = newNode;
return;
}
rear->next = newNode;
rear = newNode;
}
int dequeue()
{
if (isEmpty())
return -1;
Node* temp = front;
int value = temp->data;
front = front->next;
if (front == NULL)
rear = NULL;
delete temp;
return value;
}
int getFront()
{
if (isEmpty())
return -1;
return front->data;
}
void display()
{
Node* temp = front;
while (temp != NULL)
{
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
};Queue ke important differences
Linear Queue | Circular Queue | Linked Queue |
|---|---|---|
Array | Circular array | Linked nodes |
Fixed size | Fixed size | Dynamic |
Empty spaces waste ho sakti hain | Empty spaces reuse hoti hain | Nodes as needed |
Front/rear indexes | Front/rear with modulo | Front/rear pointers |
Priority Queue aur Deque: Lecture mein inki types aur concepts bhi diye gaye hain. Inhein normal queue ke same code se implement nahi karna; priority queue mein priority ke hisaab se removal hota hai aur deque mein dono ends se insertion/deletion ho sakti hai.
Lecture 7 — Recursion and Divide & Conquer
1. Basic Recursion Template
Har recursive question mein ye pattern yaad rakho:
returnType functionName(int n)
{
if (baseCondition)
return baseValue;
return operation + functionName(smallerInput);
}Do cheezein lazmi hain:
Base case — recursion stop karne ke liye.
Recursive call — smaller input ke saath function ko dobara call karna.
2. Factorial
int factorial(int n)
{
if (n == 0)
return 1;
return n * factorial(n - 1);
}3. Sum from 1 to n
int sum(int n)
{
if (n == 1)
return 1;
return n + sum(n - 1);
}4. Fibonacci
int fib(int n)
{
if (n == 0)
return 0;
if (n == 1)
return 1;
return fib(n - 1) + fib(n - 2);
}5. Power xⁿ
int power(int x, int n)
{
if (n == 0)
return 1;
return x * power(x, n - 1);
}6. GCD
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}7. Recursive Binary Search
int binarySearch(int arr[], int low, int high, int key)
{
if (low > high)
return -1;
int mid = low + (high - low) / 2;
if (arr[mid] == key)
return mid;
if (arr[mid] < key)
return binarySearch(arr, mid + 1, high, key);
return binarySearch(arr, low, mid - 1, key);
}8. Towers of Hanoi
void hanoi(int n, char from, char to, char spare)
{
if (n == 0)
return;
hanoi(n - 1, from, spare, to);
cout << from << " -> " << to << endl;
hanoi(n - 1, spare, to, from);
}Moves ka formula:
9. Find Maximum Using Divide and Conquer
int findMax(int arr[], int low, int high)
{
if (low == high)
return arr[low];
int mid = low + (high - low) / 2;
int left = findMax(arr, low, mid);
int right = findMax(arr, mid + 1, high);
if (left > right)
return left;
else
return right;
}10. Merge Sort
Merge Sort Function
void mergeSort(int arr[], int low, int high)
{
if (low >= high)
return;
int mid = low + (high - low) / 2;
mergeSort(arr, low, mid);
mergeSort(arr, mid + 1, high);
merge(arr, low, mid, high);
}Merge Function
void merge(int arr[], int low, int mid, int high)
{
int temp[100];
int i = low;
int j = mid + 1;
int k = low;
while (i <= mid && j <= high)
{
if (arr[i] <= arr[j])
{
temp[k] = arr[i];
i++;
}
else
{
temp[k] = arr[j];
j++;
}
k++;
}
while (i <= mid)
{
temp[k] = arr[i];
i++;
k++;
}
while (j <= high)
{
temp[k] = arr[j];
j++;
k++;
}
for (int x = low; x <= high; x++)
{
arr[x] = temp[x];
}
}Main Function
int main()
{
int arr[] = {38, 27, 43, 3};
int n = 4;
mergeSort(arr, 0, n - 1);
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
return 0;
}Output:
3 27 38 43Lecture 7 ki complexities:
Algorithm | Complexity |
|---|---|
Factorial | O(n) |
Sum | O(n) |
Fibonacci | O(2ⁿ) approximately |
Power | O(n) |
GCD | O(log n) |
Binary Search | O(log n) |
Hanoi | O(2ⁿ) |
Find Maximum | O(n) |
Merge Sort | O(n log n) |
Master Revision — Question dekh kar kaunsa template likhna hai?
Ye table paper mein bohat help karegi.
Question mein ye words hon | Tumhara template |
|---|---|
Insert element in array | Array insertion |
Delete element from array | Array deletion |
Find largest/smallest | Maximum/minimum |
Search an element | Linear/Binary Search |
Sort array | Bubble Sort / Merge Sort |
Reverse array | Two pointers |
Insert node at start | Linked List insertion beginning |
Insert node at end | Linked List insertion end |
Delete first node | Delete beginning |
Delete last node | Delete end |
Search in linked list | Linked List search |
Print all nodes | Traversal |
Previous and next pointer | Doubly Linked List |
Last points to first | Circular Linked List |
Add at top | Stack push |
Remove from top | Stack pop |
Last element first | Stack / LIFO |
First element first | Queue / FIFO |
Add at rear | Enqueue |
Remove from front | Dequeue |
Reuse empty queue positions | Circular Queue |
Function calls itself | Recursion |
Find factorial | Factorial recursion |
Find GCD | Euclid recursion |
Search sorted array recursively | Recursive Binary Search |
Divide into halves and merge | Merge Sort |
Move disks between rods | Towers of Hanoi |
Most Important Patterns to Memorize
Ye 12 lines tumhare liye bohat valuable hain:
Arrays
arr[i] = value;Array shifting
arr[i] = arr[i - 1];
arr[i] = arr[i + 1];Singly Linked List
temp = temp->next;
newNode->next = head;
head = newNode;Doubly Linked List
newNode->next = head;
head->prev = newNode;Stack
arr[++top] = value;
arr[top--];Queue
arr[++rear] = value;
arr[++front];Circular Queue
rear = (rear + 1) % SIZE;
front = (front + 1) % SIZE;Recursion
if (n == 0) return 1;
return n * factorial(n - 1);Paper ke liye priority list
Agar time kam ho toh is order mein code practice karo:
Priority 1 — Pehle ye complete karo
- Array insertion and deletion
- Linear and Binary Search
- Bubble Sort
- Singly Linked List insertion/deletion
- Doubly Linked List insertion/deletion
- Stack push/pop
- Queue enqueue/dequeue
- Circular Queue
- Factorial and Fibonacci
- Recursive Binary Search
- Merge Sort
Priority 2 — Iske baad
- Circular Linked List
- Linked Stack and Linked Queue
- Parentheses Matching
- Postfix Evaluation
- Infix to Postfix
- GCD and Towers of Hanoi
- Find Maximum using Divide and Conquer
Ab ek important exam tip
Code likhte waqt har question mein ye 5 steps follow karna:
Pehle data structure identify karo.
Required variables/pointers declare karo.
Empty condition check karo.
Main operation perform karo.
Result display ya return karo.
Aur ek baat: Is template book mein core lecture operations cover hain, lekin kuch templates basic versions hain. Jaise array insertion mein valid index aur capacity check, linked list mein invalid position check, aur stack expression conversion mein operator associativity jaise cases question ke mutabiq add karne honge.
Meri advice hai ke ab hum in templates ka exam-style practice paper solve karein: main tumhein question doon, tum template identify karo aur code likho; jahan mistake ho main Roman Urdu mein samjha doon. Is se tumhein actual paper mein template apply karna aa jayega.
1. Arrays — Insertion aur Deletion with Checks
A. Array mein insertion (valid position + capacity check)
#include <iostream>
using namespace std;
int main() {
int arr[100], n, pos, value;
int capacity = 100;
cout << "Enter size: ";
cin >> n;
if (n < 0 || n > capacity) {
cout << "Invalid size";
return 0;
}
for (int i = 0; i < n; i++)
cin >> arr[i];
cout << "Enter position (0 to " << n << "): ";
cin >> pos;
cout << "Enter value: ";
cin >> value;
if (n == capacity) {
cout << "Array is full";
}
else if (pos < 0 || pos > n) {
cout << "Invalid position";
}
else {
for (int i = n; i > pos; i--) {
arr[i] = arr[i - 1];
}
arr[pos] = value;
n++;
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
return 0;
}Samjho:
n == capacitycheck karta hai ke array full toh nahi.pos < 0 || pos > ninvalid position check karta hai.i = nse shifting start hoti hai.arr[i] = arr[i-1]elements ko right shift karta hai.arr[pos] = valuenew value insert karta hai.n++size increase karta hai.
Example: [10, 20, 30] mein position 1 par 15 insert karna hai.
Result: [10, 15, 20, 30]
B. Array mein deletion (valid position check)
int pos;
cout << "Enter position: ";
cin >> pos;
if (pos < 0 || pos >= n) {
cout << "Invalid position";
}
else {
for (int i = pos; i < n - 1; i++) {
arr[i] = arr[i + 1];
}
n--;
}Yaad rakho:
Insertion mein valid position
0 to nhoti hai.Deletion mein valid position
0 to n-1hoti hai.Insertion mein right shift.
Deletion mein left shift.
2. Singly Linked List — Invalid Position Checks
Position-based insertion aur deletion mein sabse important cheez hai ke pointer NULL tak na pohanch jaye.
A. Insert at position (1-based indexing)
void insertAtPosition(int value, int pos) {
if (pos < 1) {
cout << "Invalid position";
return;
}
Node* newNode = new Node(value);
if (pos == 1) {
newNode->next = head;
head = newNode;
return;
}
Node* temp = head;
for (int i = 1; i < pos - 1 && temp != NULL; i++) {
temp = temp->next;
}
if (temp == NULL) {
cout << "Invalid position";
delete newNode;
return;
}
newNode->next = temp->next;
temp->next = newNode;
}Samjho:
Position 1 se chhoti hai toh invalid.
Agar position 1 hai toh beginning par insert.
tempko insertion wali position se ek node pehle le jao.Agar
temp == NULLho gaya toh position invalid.New node ko links ke darmiyan connect kar do.
Example:
10 → 20 → 30 → NULL
Position 2 par 15 insert:
10 → 15 → 20 → 30 → NULL
B. Delete at position (1-based indexing)
void deleteAtPosition(int pos) {
if (head == NULL || pos < 1) {
cout << "Invalid position";
return;
}
if (pos == 1) {
Node* temp = head;
head = head->next;
delete temp;
return;
}
Node* temp = head;
for (int i = 1; i < pos - 1 && temp != NULL; i++) {
temp = temp->next;
}
if (temp == NULL || temp->next == NULL) {
cout << "Invalid position";
return;
}
Node* delNode = temp->next;
temp->next = delNode->next;
delete delNode;
}Important lines:
Node* delNode = temp->next;
temp->next = delNode->next;
delete delNode;Pehle delete hone wale node ka address save hota hai, phir links connect hotay hain aur aakhir mein memory free hoti hai.
3. Doubly Linked List — Safe Deletion
Doubly linked list mein prev aur next dono links update karne hote hain.
Delete a node at a given position
void deleteAtPosition(int pos) {
if (head == NULL || pos < 1) {
cout << "Invalid position";
return;
}
Node* temp = head;
for (int i = 1; i < pos && temp != NULL; i++) {
temp = temp->next;
}
if (temp == NULL) {
cout << "Invalid position";
return;
}
if (temp == head)
head = temp->next;
if (temp == tail)
tail = temp->prev;
if (temp->prev != NULL)
temp->prev->next = temp->next;
if (temp->next != NULL)
temp->next->prev = temp->prev;
delete temp;
}Iska main concept:
Doubly linked list mein middle node delete karna
Delete 20 from this list:
10 ka next ab 30, aur 30 ka prev ab 10.
4. Stack — Overflow, Underflow aur Safe Operations
Array stack ka corrected template:
#define SIZE 5
class Stack {
int arr[SIZE];
int top;
public:
Stack() {
top = -1;
}
bool isEmpty() {
return top == -1;
}
bool isFull() {
return top == SIZE - 1;
}
void push(int value) {
if (isFull()) {
cout << "Stack Overflow";
return;
}
arr[++top] = value;
}
int pop() {
if (isEmpty()) {
cout << "Stack Underflow";
return -1;
}
return arr[top--];
}
int peek() {
if (isEmpty()) {
cout << "Stack is empty";
return -1;
}
return arr[top];
}
};Do terms yaad rakho:
Overflow: full stack mein push karne ki koshish.
Underflow: empty stack se pop karne ki koshish.
5. Infix to Postfix — Operator Precedence aur Associativity
Ye exam ke liye bohat important hai, especially ^ operator.
Operator precedence
Operator | Priority | Associativity |
|---|---|---|
| 3 | Right to Left |
| 2 | Left to Right |
| 1 | Left to Right |
| 0 | Special |
A. Priority function
int priority(char ch) {
if (ch == '^')
return 3;
if (ch == '*' || ch == '/')
return 2;
if (ch == '+' || ch == '-')
return 1;
return 0;
}B. Correct operator popping condition
while (!s.empty() && s.top() != '(' &&
(priority(s.top()) > priority(ch) ||
(priority(s.top()) == priority(ch) && ch != '^'))) {
postfix += s.top();
s.pop();
}Ye condition kyun important hai?
Normally equal priority par pehle wala operator pop hota hai, lekin ^ right-to-left hota hai. Isliye jab current operator ^ ho, equal priority par pop nahi karna.
Example:
Expression 1
A + B * C
ABC*+
Multiplication ki priority addition se zyada hai.
Expression 2
A ^ B ^ C
ABC^^
Pehle B^C, phir A^(B^C). Isliye right-to-left.
Expression 3
A - B - C
AB-C-
Minus left-to-right hota hai: (A-B)-C.
C. Complete infix-to-postfix function
Ye version single-character operands ke liye hai, jaise A+B*C:
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int priority(char ch) {
if (ch == '^') return 3;
if (ch == '*' || ch == '/') return 2;
if (ch == '+' || ch == '-') return 1;
return 0;
}
string toPostfix(string infix) {
stack<char> s;
string postfix = "";
for (int i = 0; i < infix.length(); i++) {
char ch = infix[i];
if (ch == ' ')
continue;
if ((ch >= 'A' && ch <= 'Z') ||
(ch >= 'a' && ch <= 'z') ||
(ch >= '0' && ch <= '9')) {
postfix += ch;
}
else if (ch == '(') {
s.push(ch);
}
else if (ch == ')') {
while (!s.empty() && s.top() != '(') {
postfix += s.top();
s.pop();
}
if (!s.empty())
s.pop();
}
else {
while (!s.empty() && s.top() != '(' &&
(priority(s.top()) > priority(ch) ||
(priority(s.top()) == priority(ch) && ch != '^'))) {
postfix += s.top();
s.pop();
}
s.push(ch);
}
}
while (!s.empty()) {
if (s.top() != '(')
postfix += s.top();
s.pop();
}
return postfix;
}
int main() {
string infix;
cout << "Enter infix: ";
cin >> infix;
cout << "Postfix: " << toPostfix(infix);
return 0;
}6. Postfix Evaluation — Stack Empty Check
Postfix mein operator milne par do operands pop karte hain. Isliye check karna zaroori hai ke stack mein do operands available hain.
int evaluatePostfix(string exp) {
stack<int> s;
for (int i = 0; i < exp.length(); i++) {
char ch = exp[i];
if (ch >= '0' && ch <= '9') {
s.push(ch - '0');
}
else {
if (s.size() < 2) {
cout << "Invalid Expression";
return -1;
}
int b = s.top();
s.pop();
int a = s.top();
s.pop();
if (ch == '+') s.push(a + b);
else if (ch == '-') s.push(a - b);
else if (ch == '*') s.push(a * b);
else if (ch == '/') {
if (b == 0) {
cout << "Division by zero";
return -1;
}
s.push(a / b);
}
else {
cout << "Invalid operator";
return -1;
}
}
}
if (s.size() != 1) {
cout << "Invalid Expression";
return -1;
}
return s.top();
}Important: b pehle pop hota hai aur a baad mein. Calculation hamesha a operator b hoti hai. Example 82- ka answer 8-2 = 6 hai, 2-8 nahi.
7. Queue — Overflow, Underflow aur Circular Conditions
A. Linear queue ke important checks
bool isEmpty() {
return front == -1;
}
bool isFull() {
return rear == SIZE - 1;
}Enqueue:
if (isFull()) {
cout << "Queue Overflow";
return;
}
if (front == -1)
front = 0;
arr[++rear] = value;Dequeue:
if (isEmpty()) {
cout << "Queue Underflow";
return -1;
}
int value = arr[front];
if (front == rear)
front = rear = -1;
else
front++;
return value;B. Circular queue ke checks
bool isEmpty() {
return count == 0;
}
bool isFull() {
return count == SIZE;
}Enqueue:
if (isFull()) {
cout << "Queue Full";
return;
}
rear = (rear + 1) % SIZE;
arr[rear] = value;
count++;Dequeue:
if (isEmpty()) {
cout << "Queue Empty";
return -1;
}
int value = arr[front];
front = (front + 1) % SIZE;
count--;
return value;Circular queue ka formula yaad rakho:
Is se rear last index ke baad dobara 0 par aa jata hai.
8. Recursion — Base Case aur Invalid Input
Recursion mein sabse important safety condition base case hai. Base case nahi hoga toh function continuously call hota rahega.
A. Factorial with negative input check
int factorial(int n) {
if (n < 0)
return -1;
if (n == 0 || n == 1)
return 1;
return n * factorial(n - 1);
}B. Power with negative exponent check
int power(int x, int n) {
if (n < 0)
return -1;
if (n == 0)
return 1;
return x * power(x, n - 1);
}C. Recursive binary search with valid bounds
int binarySearch(int arr[], int low, int high, int key) {
if (low > high)
return -1;
int mid = low + (high - low) / 2;
if (arr[mid] == key)
return mid;
if (arr[mid] < key)
return binarySearch(arr, mid + 1, high, key);
return binarySearch(arr, low, mid - 1, key);
}Call:
int result = binarySearch(arr, 0, n - 1, key);Array sorted hona zaroori hai.
9. Exam ke liye final safety checklist
Isko achi tarah yaad kar lena. Question mein jab bhi operation likho, ye checks sochna.
Topic | Kya check karna hai? |
|---|---|
Array insertion | Full array? Valid position? |
Array deletion | Valid index? |
Linked list insertion | Position valid? |
Linked list deletion | List empty? Node exists? |
Doubly linked list |
|
Circular linked list | Last node ka link head par? |
Stack push |
|
Stack pop |
|
Queue enqueue |
|
Queue dequeue |
|
Infix conversion | Precedence + associativity |
Postfix evaluation | 2 operands available? |
Recursion | Base case present? |
Binary search | Array sorted? |
Meri advice: Har code mein sabse pehle boundary conditions check karna seekho. Exam mein sirf operation likhna kaafi nahi hota; empty list, full array, invalid position aur special cases handle karna bhi marks dilata hai.
Ab tumhari template book mein basic operations ke saath ye important edge cases bhi cover ho gaye hain. ❤️
Download
PDF Word HTMLFAQ
What is the difference between linear queues and circular queues?
Linear queues can suffer from wasted space after multiple deletions, whereas circular queues reuse empty spaces by utilizing the modulo operator for indices.
How do you implement a stack using an array in C++?
An array stack uses a top variable initialized to -1. The push operation increments top and stores the value, while the pop operation retrieves and decrements top.
Why are boundary checks important in linked list operations?
Boundary checks prevent segmentation faults by ensuring that pointers do not access null addresses and that insertion or deletion positions are valid.
Test yourself
Flashcards
Click a card to see the answer.
Quiz
Questions generated by AI from the document: check the answers against the text.