Data Structures and Algorithms (DSA) in C++
1. Introduction to DSA
• Data Structure: A way to store and organize data efficiently.
• Algorithm: A step-by-step procedure to solve a problem.
• Complexity Analysis: Measures efficiency in terms of time and space.
o Big-O Notation (O): Worst-case complexity.
o Omega (Ω): Best-case complexity.
o Theta (Θ): Average-case complexity.
2. Arrays
Definition:
A contiguous block of memory storing elements of the same type.
Operations:
• Traversal
• Insertion
• Deletion
• Searching
• Sorting
Example:
#include<iostream>
using namespace std;
int main() {
int arr[] = {10, 20, 30, 40, 50};
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Array elements: ";
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
return 0;
}
3. Linked List
Definition:
A dynamic data structure consisting of nodes.
• Singly Linked List
• Doubly Linked List
• Circular Linked List
Example (Singly Linked List):
#include<iostream>
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int val) { data = val; next = NULL; }
};
void printList(Node* head) {
while (head) {
cout << head->data << " -> ";
head = head->next;
}
cout << "NULL\n";
}
int main() {
Node* head = new Node(10);
head->next = new Node(20);
head->next->next = new Node(30);
printList(head);
return 0;
}
4. Stack
Definition:
LIFO (Last In, First Out) data structure.
Operations:
• Push
• Pop
• Peek
• isEmpty
Example:
#include<iostream>
#include<stack>
using namespace std;
int main() {
stack<int> s;
s.push(10);
s.push(20);
s.push(30);
cout << "Top element: " << s.top() << endl;
s.pop();
cout << "After popping, top element: " << s.top() << endl;
return 0;
}
5. Queue
Definition:
FIFO (First In, First Out) data structure.
Example:
#include<iostream>
#include<queue>
using namespace std;
int main() {
queue<int> q;
q.push(10);
q.push(20);
q.push(30);
cout << "Front: " << q.front() << " Back: " << q.back() << endl;
q.pop();
cout << "After popping, front: " << q.front() << endl;
return 0;
}
6. Sorting Algorithms
• Bubble Sort
• Selection Sort
• Insertion Sort
• Merge Sort
• Quick Sort
Example (Bubble Sort):
#include<iostream>
using namespace std;
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1])
swap(arr[j], arr[j+1]);
}
}
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr)/sizeof(arr[0]);
bubbleSort(arr, n);
cout << "Sorted array: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
7. Searching Algorithms
• Linear Search
• Binary Search
Example (Binary Search):
#include<iostream>
using namespace std;
int binarySearch(int arr[], int n, int key) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == key)
return mid;
else if (arr[mid] < key)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
int main() {
int arr[] = {10, 20, 30, 40, 50};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 30;
int result = binarySearch(arr, n, key);
if (result != -1)
cout << "Element found at index " << result;
else
cout << "Element not found";
return 0;
}
8. Trees
• Binary Tree
• Binary Search Tree (BST)
• Traversal Methods (Inorder, Preorder, Postorder)
Example (BST Insertion):
#include<iostream>
using namespace std;
class Node {
public:
int data;
Node* left, *right;
Node(int val) { data = val; left = right = NULL; }
};
Node* insert(Node* root, int key) {
if (!root) return new Node(key);
if (key < root->data)
root->left = insert(root->left, key);
else
root->right = insert(root->right, key);
return root;
}
void inorder(Node* root) {
if (root) {
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
}
int main() {
Node* root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 70);
insert(root, 20);
insert(root, 40);
insert(root, 60);
insert(root, 80);
inorder(root);
return 0;
}
More topics like Graphs, Dynamic Programming, and Hashing can be added. Let me know if you
need further details!
