Data Structures in C: Roadmap

Cheatsheet Content

1. Introduction to Data Structures Definition: Way to organize and store data efficiently. Types: Linear: Arrays, Linked Lists, Stacks, Queues Non-Linear: Trees, Graphs, Hash Tables Algorithm Analysis: Time Complexity: Measures execution time (e.g., $O(1)$, $O(\log n)$, $O(n)$, $O(n \log n)$, $O(n^2)$). Space Complexity: Measures memory usage. Big O Notation: Asymptotic upper bound. 2. Arrays Definition: Collection of elements of the same data type stored at contiguous memory locations. Declaration: int arr[10]; Operations: Accessing: $O(1)$ Insertion/Deletion (end): $O(1)$ Insertion/Deletion (middle): $O(n)$ Searching (linear): $O(n)$ Searching (binary, sorted): $O(\log n)$ Important Concepts: Multi-dimensional arrays (2D arrays/Matrices). Passing arrays to functions. 3. Pointers Definition: Variable that stores the memory address of another variable. Declaration: int *ptr; Operators: Address-of operator: & Dereference operator: * Pointer Arithmetic: Incrementing/decrementing pointers. Pointers and Arrays: Arrays names often decay to pointers. Dynamic Memory Allocation: malloc() : Allocates a block of memory. calloc() : Allocates memory and initializes to zero. realloc() : Resizes previously allocated memory. free() : Deallocates memory. 4. Linked Lists Definition: Collection of nodes where each node contains data and a pointer to the next node. Types: Singly Linked List: Node $\rightarrow$ data, next pointer. Doubly Linked List: Node $\rightarrow$ prev pointer, data, next pointer. Circular Linked List: Last node points to the first node. Node Structure (Singly): struct Node { int data; struct Node *next; }; Operations (Singly): Insertion (beginning/end/middle): $O(1)$ or $O(n)$ Deletion (beginning/end/middle): $O(1)$ or $O(n)$ Traversal: $O(n)$ Searching: $O(n)$ Key Advantages: Dynamic size, efficient insertions/deletions. Disadvantages: Random access not possible, extra space for pointers. 5. Stacks Definition: LIFO (Last In, First Out) data structure. Operations: push() : Adds an element to the top. pop() : Removes an element from the top. peek() / top() : Returns the top element without removing. isEmpty() , isFull() . Implementations: Array-based: Fixed size, simple. Linked List-based: Dynamic size, more flexible. Applications: Function call stack, expression evaluation (infix to postfix), undo/redo. 6. Queues Definition: FIFO (First In, First Out) data structure. Operations: enqueue() : Adds an element to the rear. dequeue() : Removes an element from the front. front() / peek() : Returns the front element without removing. isEmpty() , isFull() . Implementations: Array-based: Can lead to "queue full" even with empty slots (linear array). Circular Array-based: Efficient use of space, wraps around. Linked List-based: Dynamic size. Applications: CPU scheduling, printer queues, breadth-first search. 7. Trees Definition: Non-linear data structure with a root node and child nodes. Terminology: Root, Node, Edge, Parent, Child, Sibling, Leaf, Depth, Height, Subtree. Binary Tree: Each node has at most two children (left and right). Binary Search Tree (BST): Left child's key $ Right child's key $>$ parent's key. Operations (search, insertion, deletion): $O(\log n)$ on average, $O(n)$ worst case. Tree Traversals: Inorder: Left $\rightarrow$ Root $\rightarrow$ Right (sorted output for BST). Preorder: Root $\rightarrow$ Left $\rightarrow$ Right. Postorder: Left $\rightarrow$ Right $\rightarrow$ Root. AVL Trees / Red-Black Trees: Self-balancing BSTs (advanced, but good to know for interviews). 8. Graphs Definition: Set of vertices (nodes) and edges connecting them. Terminology: Vertex, Edge, Adjacency, Path, Cycle, Degree, Directed/Undirected, Weighted/Unweighted. Representations: Adjacency Matrix: $A[i][j]=1$ if an edge exists between $i$ and $j$. Space: $O(V^2)$. Adjacency List: Array of linked lists. Space: $O(V+E)$. Graph Traversals: Breadth-First Search (BFS): Uses a queue, finds shortest path in unweighted graphs. Depth-First Search (DFS): Uses a stack (or recursion), useful for cycle detection, topological sort. Minimum Spanning Tree (MST): Prim's and Kruskal's algorithms. Shortest Path Algorithms: Dijkstra's (single source, non-negative weights), Bellman-Ford (single source, handles negative weights). 9. Hashing Definition: Technique to convert a range of key values into a range of array indices. Hash Function: Maps a key to an index in a hash table. Hash Table: Array used to store data, with indices generated by a hash function. Collisions: When two different keys map to the same index. Collision Resolution Techniques: Chaining: Each hash table slot points to a linked list of elements. Open Addressing: Probing for the next available slot (linear probing, quadratic probing, double hashing). Load Factor: $\alpha = \frac{\text{number of elements}}{\text{table size}}$. Operations (average case): Insertion, Deletion, Search: $O(1)$. Worst case: $O(n)$. 10. Sorting Algorithms Bubble Sort: Repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. $O(n^2)$. Selection Sort: Finds the minimum element from the unsorted part and puts it at the beginning. $O(n^2)$. Insertion Sort: Builds the final sorted array one item at a time. $O(n^2)$. Merge Sort: Divide and conquer. Divides the array into two halves, sorts them, and then merges the sorted halves. $O(n \log n)$. Quick Sort: Divide and conquer. Picks an element as a pivot and partitions the array around the picked pivot. $O(n \log n)$ average, $O(n^2)$ worst case. Heap Sort: Uses a binary heap data structure. $O(n \log n)$. 11. Searching Algorithms Linear Search: Checks each element in the list sequentially until a match is found or the list ends. $O(n)$. Binary Search: Efficiently locates an item in a sorted list by repeatedly dividing the search interval in half. $O(\log n)$.