Data Structures & Algorithms (DSA) Overview

Data Structures & Algorithms (DSA) Cheatsheet

This cheatsheet provides a quick reference to the most important concepts, data structures, and algorithms that you’ll encounter while studying DSA. It’s perfect for interviews, competitive programming, or just brushing up on key concepts.

1. Time Complexity

Understanding time complexity is key to evaluating the efficiency of your algorithms. Here’s a quick summary of the most common complexities:

ComplexityDescriptionExample
O(1)Constant time (no matter the input size)Accessing an element in an array
O(log n)Logarithmic time (binary search)Binary Search, Balanced BSTs
O(n)Linear time (grows linearly with input size)Traversing an array or list
O(n log n)Linearithmic time (commonly seen in efficient sorting algorithms)Merge Sort, Quick Sort
O(n²)Quadratic time (nested loops)Bubble Sort, Insertion Sort
O(2^n)Exponential time (very slow for large inputs)Brute force solutions for NP problems
O(n!)Factorial time (extremely slow)Solving traveling salesman problem with brute force

2. Arrays

Definition: A collection of elements identified by index or key.

Key Operations:

  • Access: arr[i] → O(1)
  • Insertion/Deletion (at end): O(1)
  • Insertion/Deletion (at start or middle): O(n)
  • Search: O(n) (for unsorted) or O(log n) (for sorted, using binary search)

Common Use Cases:

  • Storing a fixed number of items.
  • Random access by index.

3. Linked List

Definition: A linear collection of elements (nodes), each pointing to the next in sequence.

Key Operations:

  • Access: O(n)
  • Insertion/Deletion: O(1) (at start or end, given a reference to the node)
  • Search: O(n)

Types:

  • Singly Linked List: Each node points to the next.
  • Doubly Linked List: Each node points to both the next and previous node.
  • Circular Linked List: Last node points back to the first node.

4. Stack

Definition: A Last In First Out (LIFO) data structure where the last added element is the first one to be removed.

Key Operations:

  • Push: O(1)
  • Pop: O(1)
  • Peek: O(1)
  • Search: O(n)

Common Use Cases:

  • Undo/Redo operations.
  • Expression evaluation (postfix, prefix).
  • Depth-first search (DFS).

5. Queue

Definition: A First In First Out (FIFO) data structure where the first added element is the first one to be removed.

Key Operations:

  • Enqueue: O(1)
  • Dequeue: O(1)
  • Peek: O(1)
  • Search: O(n)

Common Use Cases:

  • Breadth-first search (BFS).
  • Task scheduling.
  • Call center systems.

6. Hashing

Definition: A technique to map data of arbitrary size to fixed-size values using a hash function.

Key Operations:

  • Insert: O(1) (amortized, unless collisions)
  • Search: O(1) (amortized, unless collisions)
  • Delete: O(1) (amortized, unless collisions)

Common Use Cases:

  • Caching.
  • Frequency counting (e.g., hash maps).
  • Implementing sets or associative arrays.

7. Trees

Definition: A hierarchical data structure consisting of nodes connected by edges. A tree has a root node and child nodes.

Key Types:

  • Binary Tree: Each node has at most 2 children.
  • Binary Search Tree (BST): Left child < parent node < right child.
  • AVL Tree: A self-balancing BST.
  • Red-Black Tree: A balanced binary search tree with additional properties for balancing.
  • Trie: A tree-like data structure used for storing strings.

Key Operations:

  • Insertion/Deletion: O(log n) (for balanced trees)
  • Search: O(log n) (for balanced trees)
  • Traversal: Pre-order, In-order, Post-order, Level-order

Common Use Cases:

  • Hierarchical data representation (e.g., file system).
  • Searching and sorting.

8. Graphs

Definition: A collection of nodes (vertices) and edges that connect pairs of nodes. Can be directed or undirected, and weighted or unweighted.

Key Operations:

  • Add Vertex: O(1)
  • Add Edge: O(1)
  • DFS/BFS Traversal: O(V + E) where V is vertices, E is edges.

Graph Representations:

  • Adjacency Matrix: A 2D array where matrix[i][j] = 1 indicates an edge between vertices i and j.
  • Adjacency List: A list where each node points to a list of adjacent nodes.

Common Use Cases:

  • Social networks (representing users and relationships).
  • Shortest path algorithms (e.g., Dijkstra’s algorithm).
  • Web crawling.

9. Sorting Algorithms

Bubble Sort: O(n²), Simple but inefficient.
Insertion Sort: O(n²), Efficient for small datasets or partially sorted data.
Selection Sort: O(n²), Inefficient but simple.
Merge Sort: O(n log n), Stable, divides and conquers.
Quick Sort: O(n log n) on average, O(n²) worst case (choose pivot wisely).
Heap Sort: O(n log n), Good for sorting large datasets.
Radix Sort: O(n), Non-comparative sorting algorithm used for integers.

Best Sorting Algorithms for Different Scenarios:

  • Merge Sort: When stability is required or working with linked lists.
  • Quick Sort: When average performance is important and working with arrays.
  • Heap Sort: When constant time for retrieving the largest or smallest element is needed.

10. Searching Algorithms

Linear Search: O(n), Check each element in sequence.
Binary Search: O(log n), Requires a sorted array.
Jump Search: O(√n), Steps through elements in blocks.
Exponential Search: O(log n), Finds the range and then applies binary search.

11. Dynamic Programming (DP)

Definition: A method for solving problems by breaking them into subproblems and storing the results of subproblems to avoid redundant computations.

Key Concepts:

  • Memoization: Top-down approach with caching.
  • Tabulation: Bottom-up approach using a table to store intermediate results.

Examples:

  • Fibonacci Sequence.
  • Knapsack Problem.
  • Longest Common Subsequence.

12. Greedy Algorithms

Definition: A strategy for solving optimization problems by selecting the locally optimal choice at each stage, hoping it leads to a globally optimal solution.

Examples:

  • Coin Change Problem.
  • Huffman Coding.
  • Activity Selection Problem.

13. Backtracking

Definition: A technique for finding all solutions to a problem by exploring all possibilities and abandoning a path as soon as it’s determined to lead to an invalid solution.

Examples:

  • N-Queens Problem.
  • Sudoku Solver.
  • Permutations and Combinations.

14. Divide and Conquer

Definition: A strategy that involves dividing the problem into smaller subproblems, solving them independently, and then combining their results.

Examples:

  • Merge Sort.
  • Quick Sort.
  • Binary Search.

15. Bit Manipulation

Definition: Performing operations on binary representations of integers.

Common Operations:

  • AND: x & y
  • OR: x | y
  • XOR: x ^ y
  • NOT: ~x
  • Left Shift: x << 1
  • Right Shift: x >> 1

Use Cases:

  • Checking if a number is even or odd.
  • Swapping two numbers without a temporary variable.
  • Counting the number of set bits (Hamming weight).

Leave a Reply