Data Structures & Algorithms

Cheatsheet Content

### Arrays & Basic Operations #### Context Arrays are contiguous memory blocks for same-type data. Accessing elements by index is $O(1)$. #### Code: Array Initialization & Access (C++) ```cpp #include #include // For dynamic arrays int main() { // Static array int static_arr[5] = {10, 20, 30, 40, 50}; std::cout dynamic_arr = {5, 4, 3, 2, 1}; dynamic_arr.push_back(0); // Add element std::cout ### Linear Search #### Context Searches for an element in an **unsorted** array by checking each item sequentially. Time complexity: $O(n)$. #### Code: Linear Search (C++) ```cpp #include #include int linearSearch(const std::vector & arr, int key) { for (int i = 0; i nums = {15, 23, 7, 42, 10, 5}; std::cout ### Find Min/Max Elements #### Context Locating the smallest and largest values in an array. A single pass is $O(n)$. #### Code: Find Min/Max (C++) ```cpp #include #include void findMinMax(const std::vector & arr) { if (arr.empty()) { std::cout max_val) max_val = arr[i]; } std::cout nums = {15, 23, 7, 42, 10, 5}; findMinMax(nums); // Output: Min: 5, Max: 42 return 0; } ``` ### Binary Search #### Context Efficiently finds an element in a **sorted** array by repeatedly halving the search interval. Time complexity: $O(\log n)$. #### Code: Binary Search (C++) ```cpp #include #include // For std::sort #include int binarySearch(const std::vector & arr, int key) { int low = 0; int high = arr.size() - 1; while (low nums = {15, 23, 7, 42, 10, 5}; std::sort(nums.begin(), nums.end()); // Must be sorted! // nums is now: {5, 7, 10, 15, 23, 42} std::cout ### Find Peak Element #### Context Finds an element greater than its neighbors. A binary search approach ($O(\log n)$) is efficient for this. #### Code: Find Peak Element (C++) ```cpp #include #include int findPeakElement(const std::vector & nums) { int n = nums.size(); if (n == 0) return -1; if (n == 1) return 0; int low = 0; int high = n - 1; while (low arr1 = {1, 2, 3, 1}; std::cout arr2 = {1, 2, 1, 3, 5, 6, 4}; std::cout ### Stacks (LIFO) #### Context LIFO (Last In, First Out) data structure. Operations: `push`, `pop`, `peek`, `isEmpty`. Array-based implementation is common. #### Code: Array-Based Stack (C++) ```cpp #include #include class Stack { private: std::vector arr; int top_idx; int capacity; public: Stack(int size) : capacity(size), top_idx(-1) { arr.resize(capacity); } bool isEmpty() const { return top_idx == -1; } bool isFull() const { return top_idx == capacity - 1; } void push(int value) { if (isFull()) {std::cout ### Queues (FIFO) #### Context FIFO (First In, First Out) data structure. Operations: `enqueue`, `dequeue`, `peek`, `isEmpty`. Circular array implementation is space-efficient. #### Code: Array-Based Circular Queue (C++) ```cpp #include #include class Queue { private: std::vector arr; int front_idx, rear_idx, capacity, count; public: Queue(int size) : capacity(size), front_idx(0), rear_idx(-1), count(0) { arr.resize(capacity); } bool isEmpty() const { return count == 0; } bool isFull() const { return count == capacity; } void enqueue(int value) { if (isFull()) {std::cout ### Singly Linked List #### Context Nodes contain data and a pointer to the next node. Allows dynamic memory allocation and efficient insertions/deletions at ends. #### Code: Singly Linked List (C++) ```cpp #include struct Node { int data; Node* next; Node(int val) : data(val), next(nullptr) {} }; class SLL { private: Node* head; public: SLL() : head(nullptr) {} ~SLL() { // Free memory Node* current = head; while (current) { Node* temp = current; current = current->next; delete temp; } } void insertAtBeginning(int val) { Node* newNode = new Node(val); newNode->next = head; head = newNode; std::cout next) current = current->next; current->next = newNode; std::cout data == val) { Node* temp = head; head = head->next; std::cout data data != val) { prev = current; current = current->next; } if (!current) { std::cout next = current->next; std::cout data data "; current = current->next; } std::cout 10 -> 20 -> nullptr list.deleteValue(10); list.display(); // 5 -> 20 -> nullptr list.deleteValue(50); // Not found return 0; } ``` ### Doubly Linked List #### Context Each node has pointers to both previous and next nodes, allowing bidirectional traversal. Useful for operations requiring backward movement. #### Code: Doubly Linked List (C++) ```cpp #include struct DNode { int data; DNode* prev; DNode* next; DNode(int val) : data(val), prev(nullptr), next(nullptr) {} }; class DLL { private: DNode* head; DNode* tail; public: DLL() : head(nullptr), tail(nullptr) {} ~DLL() { // Free memory DNode* current = head; while (current) { DNode* temp = current; current = current->next; delete temp; } } void insertAtBeginning(int val) { DNode* newNode = new DNode(val); if (!head) { head = newNode; tail = newNode; } else { newNode->next = head; head->prev = newNode; head = newNode; } std::cout next = newNode; newNode->prev = tail; tail = newNode; } std::cout next; head->prev = nullptr; } std::cout data data "; current = current->next; } std::cout 10 20 nullptr list.deleteFromBeginning(); list.displayForward(); // 10 20 nullptr return 0; } ``` ### Binary Tree #### Context A hierarchical structure where each node has at most two children. Traversals (Inorder, Preorder, Postorder) are key operations. #### Code: Binary Tree Node & Traversals (C++) ```cpp #include struct TNode { int data; TNode* left; TNode* right; TNode(int val) : data(val), left(nullptr), right(nullptr) {} }; class BinaryTree { public: TNode* root; BinaryTree() : root(nullptr) {} ~BinaryTree() { deleteTree(root); } // Free memory private: void deleteTree(TNode* node) { if (!node) return; deleteTree(node->left); deleteTree(node->right); delete node; } void inorderRec(TNode* node) const { if (!node) return; inorderRec(node->left); std::cout data right); } void preorderRec(TNode* node) const { if (!node) return; std::cout data left); preorderRec(node->right); } void postorderRec(TNode* node) const { if (!node) return; postorderRec(node->left); postorderRec(node->right); std::cout data q; q.push(root); while (!q.empty()) { TNode* curr = q.front(); q.pop(); if (!curr->left) { curr->left = newNode; return; } else { q.push(curr->left); } if (!curr->right) { curr->right = newNode; return; } else { q.push(curr->right); } } } void inorder() const { std::cout ### Binary Search Tree (BST) #### Context A BST maintains a property: left child struct BSTNode { int data; BSTNode* left; BSTNode* right; BSTNode(int val) : data(val), left(nullptr), right(nullptr) {} }; class BST { public: BSTNode* root; BST() : root(nullptr) {} ~BST() { deleteTree(root); } private: void deleteTree(BSTNode* node) { if (!node) return; deleteTree(node->left); deleteTree(node->right); delete node; } BSTNode* insertRec(BSTNode* node, int val) { if (!node) return new BSTNode(val); if (val data) node->left = insertRec(node->left, val); else if (val > node->data) node->right = insertRec(node->right, val); return node; } BSTNode* findMin(BSTNode* node) { // Helper for deletion (2 children) BSTNode* current = node; while (current && current->left) current = current->left; return current; } BSTNode* deleteRec(BSTNode* node, int val) { if (!node) return node; if (val data) node->left = deleteRec(node->left, val); else if (val > node->data) node->right = deleteRec(node->right, val); else { // Node found for deletion if (!node->left) { BSTNode* temp = node->right; delete node; return temp; } else if (!node->right) { BSTNode* temp = node->left; delete node; return temp; } // Node with two children: get inorder successor BSTNode* temp = findMin(node->right); node->data = temp->data; // Copy successor's data node->right = deleteRec(node->right, temp->data); // Delete successor } return node; } bool searchRec(BSTNode* node, int val) const { if (!node) return false; if (node->data == val) return true; return (val data) ? searchRec(node->left, val) : searchRec(node->right, val); } void inorderRec(BSTNode* node) const { if (!node) return; inorderRec(node->left); std::cout data right); } public: void insert(int val) { root = insertRec(root, val); std::cout