C++ Data Structure Programs – Explained Step by Step
1. Insert and Delete Element in an Array
#include <iostream>
using namespace std;
int main() {
int arr[100], n, pos, val;
cout << "Enter
number of elements: ";
cin >> n;
cout << "Enter " << n << " elements: ";
for (int i = 0; i < n;
i++)
cin >> arr[i];
cout << "Enter position and value to insert: ";
cin >> pos >> val;
for (int i = n; i >= pos; i--)
arr[i] = arr[i - 1];
arr[pos - 1] = val;
n++;
cout <<
"Array after insertion: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
cout << "Enter position to delete: ";
cin >> pos;
for (int i = pos - 1; i < n - 1; i++)
arr[i]
= arr[i + 1];
n--;
cout << "Array after deletion: ";
for (int i = 0; i < n; i++)
cout <<
arr[i] << " ";
return 0;
}
Step-by-step Explanation:
1. Include iostream to use input/output (cin and cout).
2. Use 'using namespace std;' so we don't write std:: each time.
3. Declare array arr with capacity 100 and variables n, pos, val.
4. Read n from user: how many elements they will give.
5. Read n elements into arr using a for loop.
6. Read position and value to insert (pos is 1-based).
7. Shift elements from the end to pos to make space for new value.
8. Place the new value at arr[pos-1] and increase n.
9. Print array after insertion.
10. Read position to delete, shift elements left to remove it, and decrease n.
11. Print array after deletion and end program.
Concept Recap:
Array stores elements in contiguous memory.
Insertion/deletion require shifting elements to maintain order.
User-side positions are 1-based; array indexes are 0-based.
2. Linear Search
#include <iostream>
using namespace std;
int main() {
int n, key, arr[50];
cout << "Enter size: ";
cin >> n;
cout << "Enter elements: ";
for (int i = 0; i < n; i++)
cin >> arr[i];
cout <<
"Enter key to search: ";
cin >> key;
for (int i = 0; i < n; i++) {
if (arr[i] == key) {
cout << "Element found at position " << i + 1;
return 0;
}
}
cout << "Element not
found.";
return 0;
}
Step-by-step Explanation:
1. Declare array arr and variables n and key.
2. Read number of elements n and then read n values into arr.
3. Read the key value to search for.
4. Loop through each element comparing with key.
5. If match found, print position (i+1) and exit program.
6. If loop ends with no match, print not found and exit.
Concept Recap:
Linear search checks elements one by one from start to end.
Works on unsorted arrays and is simple to implement.
3. Binary Search (sorted array required)
#include <iostream>
using namespace std;
int main() {
int n, key;
cout << "Enter size: ";
cin >>
n;
int arr[n];
cout << "Enter elements in sorted order: ";
for (int i = 0; i < n; i++) cin >>
arr[i];
cout << "Enter key: ";
cin >> key;
int low = 0, high = n - 1, mid;
while (low <=
high) {
mid = (low + high) / 2;
if (arr[mid] == key) {
cout << "Found at position
" << mid + 1;
return 0;
} else if (arr[mid] < key)
low = mid + 1;
else
high = mid - 1;
}
cout << "Not found";
return 0;
}
Step-by-step Explanation:
1. Declare variables and read n, then read a sorted array of size n.
2. Read the search key.
3. Initialize low to 0 and high to n-1 to represent search window.
4. While low <= high: compute mid = (low+high)/2 to check middle element.
5. If middle equals key, print position and stop.
6. If middle is less than key, move low to mid+1 to search right half.
7. If middle is greater, move high to mid-1 to search left half.
8. If loop ends, key is not present; print not found.
Concept Recap:
Binary search requires a sorted array.
It narrows the search window by half each step.
4. Selection Sort
#include <iostream>
using namespace std;
int main() {
int n;
cout << "Enter number of elements: ";
cin >> n;
int arr[n];
cout << "Enter elements: ";
for (int i = 0; i < n; i++)
cin >>
arr[i];
for (int i = 0; i < n - 1; i++) {
int min = i;
for (int j = i + 1; j < n; j++)
if (arr[j] < arr[min])
min = j;
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
cout << "Sorted array: ";
for (int i = 0; i < n; i++)
cout << arr[i]
<< " ";
return 0;
}
Step-by-step Explanation:
1. Read n and the n elements into an array.
2. Outer loop i picks the position to fill in the sorted portion.
3. Assume current position i has the smallest element (min = i).
4. Inner loop j searches the remaining unsorted part for a smaller element and updates min.
5. After inner loop, swap arr[i] and arr[min] to place smallest at i.
6. Repeat until the array is sorted and print the result.
Concept Recap:
Selection sort repeatedly selects the smallest from unsorted portion and places it next.
Simple to implement but not efficient for large lists.
5. Quick Sort
#include <iostream>
using namespace std;
int partition(int arr[], int low, int high) {
int pivot =
arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int p = partition(arr, low,
high);
quickSort(arr, low, p - 1);
quickSort(arr, p + 1, high);
}
}
int main() {
int
n;
cout << "Enter number of elements: ";
cin >> n;
int arr[n];
for (int i = 0; i < n; i++)
cin >> arr[i];
quickSort(arr, 0, n - 1);
cout << "Sorted array: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
Step-by-step Explanation:
1. partition chooses pivot (last element) and arranges smaller elements to left and larger to right.
2. i marks the boundary of elements smaller than pivot.
3. Loop j moves through array; when arr[j] < pivot, increase i and swap arr[i] with arr[j].
4. After loop, put pivot at correct position by swapping arr[i+1] and arr[high].
5. quickSort calls partition then recursively sorts left and right parts around pivot.
6. In main: read array, call quickSort, and print sorted array.
Concept Recap:
Quick sort is divide-and-conquer: partition then sort subarrays.
It sorts in place using recursion and swapping.
6. Insertion Sort
#include <iostream>
using namespace std;
int main() {
int n;
cout << "Enter number of elements: ";
cin >> n;
int arr[n];
cout << "Enter elements: ";
for (int i = 0; i < n; i++)
cin >>
arr[i];
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j
>= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
cout << "Sorted array: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
Step-by-step Explanation:
1. Read n and the array elements.
2. Start from second element (i = 1) and treat it as key.
3. Compare key with elements on its left and shift larger elements one step right.
4. When correct position is found, insert key at arr[j+1].
5. Repeat for all elements to get sorted array.
Concept Recap:
Insertion sort builds the sorted portion by inserting each element at correct spot in left part.
Good for small or nearly-sorted arrays.
7. Stack (Push and Pop)
#include <iostream>
using namespace std;
#define MAX 5
int stackArr[MAX], top = -1;
void push(int val) {
if (top == MAX - 1)
cout << "Stack Overflow\n";
else
stackArr[++top] = val;
}
void pop()
{
if (top == -1)
cout << "Stack Underflow\n";
else
cout << "Popped element: " <<
stackArr[top--] << "\n";
}
void display() {
if (top == -1)
cout << "Stack is empty\n";
else {
cout << "Stack elements: ";
for (int i = 0; i <= top; i++)
cout << stackArr[i] << " ";
cout << "\n";
}
}
int main() {
push(10);
push(20);
push(30);
display();
pop();
display();
return 0;
}
Step-by-step Explanation:
1. Define stackArr with fixed size MAX and initialize top = -1 meaning empty.
2. push checks if stack is full (top == MAX-1); if not, increments top and stores value.
3. pop checks if stack is empty (top == -1); if not, prints top value and decrements top.
4. display prints stack contents from bottom to top.
5. main demonstrates pushing three values, showing stack, popping once, and showing again.
Concept Recap:
Stack is Last-In-First-Out (LIFO).
Top variable indicates the index of current top element.
8. Circular Queue (Insert and Delete)
#include <iostream>
using namespace std;
#define SIZE 5
int cq[SIZE];
int front = -1, rear = -1;
void
insert(int val) {
if ((rear + 1) % SIZE == front)
cout << "Queue Overflow\n";
else {
if (front == -1) front = 0;
rear = (rear + 1) % SIZE;
cq[rear] = val;
}
}
void
removeElement() {
if (front == -1)
cout << "Queue Underflow\n";
else {
cout <<
"Deleted: " << cq[front] << "\n";
if (front == rear)
front = rear = -1;
else
front = (front + 1) % SIZE;
}
}
void display() {
if (front == -1)
cout << "Queue is empty\n";
else {
cout << "Queue elements: ";
int i = front;
while (true) {
cout <<
cq[i] << " ";
if (i == rear) break;
i = (i + 1) % SIZE;
}
cout <<
"\n";
}
}
int main() {
insert(10);
insert(20);
insert(30);
display();
removeElement();
display();
insert(40);
display();
return 0;
}
Step-by-step Explanation:
1. Initialize front and rear to -1 indicating empty queue.
2. Insert checks full condition using (rear+1)%SIZE == front. If empty set front=0. Then advance rear
circularly and store value.
3. removeElement checks if empty, prints deleted value, and if it was last element resets front and rear to
-1; otherwise advances front circularly.
4. display starts at front and prints elements until it reaches rear, using modulo arithmetic to wrap around.
5. main demonstrates insertion, deletion, and display operations.
Concept Recap:
Circular queue reuses freed slots by wrapping indices using modulo.
front points to the first element; rear points to the last element.
9. Infix to Postfix Conversion Using Stack
#include <iostream>
#include <stack>
#include <cctype>
using namespace std;
int precedence(char op) {
if
(op == '^') return 3;
if (op == '*' || op == '/') return 2;
if (op == '+' || op == '-') return 1;
return 0;
}
string infixToPostfix(string infix) {
stack<char> s;
string postfix = "";
for (char c
: infix) {
if (isalnum(c))
postfix += c;
else if (c == '(')
[Link](c);
else if (c == ')') {
while (![Link]() && [Link]() != '(') {
postfix += [Link]();
[Link]();
}
[Link]();
} else {
while (![Link]() &&
precedence([Link]()) >= precedence(c)) {
postfix += [Link]();
[Link]();
}
[Link](c);
}
}
while (![Link]()) {
postfix += [Link]();
[Link]();
}
return postfix;
}
int main() {
string infix;
cout << "Enter infix expression: ";
cin >>
infix;
cout << "Postfix expression: " << infixToPostfix(infix);
return 0;
}
Step-by-step Explanation:
1. Include stack from STL and cctype for isalnum.
2. precedence returns priority of operators.
3. infixToPostfix uses a stack to hold operators and parentheses.
4. For each character: if operand append to result, if '(' push it, if ')' pop until '(' , if operator pop
higher-or-equal precedence operators to result then push current operator.
5. After processing all chars, pop remaining operators to result and return postfix string.
6. main reads an expression (no spaces) and prints postfix.
Concept Recap:
Postfix (RPN) is useful for easy evaluation as operators come after operands.
Use a stack to temporarily hold operators while scanning the expression.
10. Create and Traverse a Linked List
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
int main() {
Node *head = NULL, *temp = NULL, *newNode = NULL;
int n, val;
cout << "Enter number of nodes: ";
cin >> n;
for (int i = 0; i < n; i++) {
newNode = new Node;
cout << "Enter data: ";
cin >> val;
newNode->data = val;
newNode->next = NULL;
if (head == NULL)
head = newNode;
else
temp->next = newNode;
temp = newNode;
}
cout <<
"Linked List: ";
temp = head;
while (temp != NULL) {
cout << temp->data << " ";
temp =
temp->next;
}
return 0;
}
Step-by-step Explanation:
1. Define Node struct with data and next pointer.
2. Initialize head to NULL meaning empty list.
3. For each node to create: allocate new node with 'new', read data and set next to NULL.
4. If list is empty set head to new node; otherwise link previous node's next to new node.
5. Move temp pointer to new node and repeat until all nodes created.
6. Traverse from head, following next pointers and print each data.
Concept Recap:
Linked list stores nodes scattered in memory linked by pointers.
head points to the first node; each node points to the next.
11. Linked List Operations (Insert and Delete)
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* head = NULL;
void insert(int val) {
Node* newNode = new Node;
newNode->data = val;
newNode->next = head;
head = newNode;
}
void deleteNode() {
if (head == NULL)
cout << "List is empty\n";
else {
Node* temp = head;
head = head->next;
delete temp;
}
}
void display() {
Node* temp =
head;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
cout
<< "\n";
}
int main() {
insert(10);
insert(20);
insert(30);
cout << "Linked List: ";
display();
deleteNode();
cout << "After deletion: ";
display();
return 0;
}
Step-by-step Explanation:
1. Define Node and a global head pointer initialized to NULL.
2. insert creates a new node, sets its next to current head, and updates head to the new node (insert at
front).
3. deleteNode removes the first node by moving head to head->next and deleting old head.
4. display traverses and prints the list.
5. main demonstrates inserting three nodes and deleting one.
Concept Recap:
Insert at front is quick because it changes only head and new node's next.
Always free memory (delete) when removing nodes in larger programs.
12. Traversing a Binary Tree (Inorder)
#include <iostream>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
};
Node* newNode(int val) {
Node* node = new Node;
node->data = val;
node->left = node->right = NULL;
return node;
}
void inorder(Node* root) {
if (root == NULL) return;
inorder(root->left);
cout <<
root->data << " ";
inorder(root->right);
}
int main() {
Node* root = newNode(1);
root->left =
newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right =
newNode(5);
cout << "Inorder Traversal: ";
inorder(root);
return 0;
}
Step-by-step Explanation:
1. Define Node with data and left/right child pointers.
2. newNode allocates and initializes a node with given value and NULL children.
3. inorder recursively visits left subtree, prints node data, then visits right subtree.
4. main builds a small tree by linking nodes and calls inorder to print values.
Concept Recap:
Binary tree nodes can have up to two children: left and right.
Inorder prints left, root, right order.