Scribd
Upload
8 views7 pages

DSA_cheatsheet

The document provides an overview of Data Structures and Algorithms (DSA) in C++, covering key concepts such as data structures (arrays, linked lists, stacks, queues, trees), algorithms (sorting and searching), and complexity analysis. It includes definitions, operations, and example code snippets for each data structure and algorithm. Additional topics like graphs, dynamic programming, and hashing are mentioned as potential areas for further exploration.

Uploaded by

arsalaan272158
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
8 views7 pages

DSA_cheatsheet

The document provides an overview of Data Structures and Algorithms (DSA) in C++, covering key concepts such as data structures (arrays, linked lists, stacks, queues, trees), algorithms (sorting and searching), and complexity analysis. It includes definitions, operations, and example code snippets for each data structure and algorithm. Additional topics like graphs, dynamic programming, and hashing are mentioned as potential areas for further exploration.

Uploaded by

arsalaan272158
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 7

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!

You might also like