Data Structures and Algorithms (DSA) - Cheat sheet

DSA Cheat Sheet

Data Structures

Arrays

An array is an ordered collection of elements, each identified by an index. It's a simple data structure used to store a collection of data.

Example: Array: [10, 20, 30, 40, 50]

Accessing the third element (index 2): array[2] results in 30.

Index:  0   1   2   3   4
Array: [10, 20, 30, 40, 50]
        

Linked Lists

A linked list is a linear collection of nodes, where each node contains data and a pointer to the next node.

Example: A simple singly linked list: 10 -> 20 -> 30

Node:  [10|*] -> [20|*] -> [30|NULL]
        

Stacks

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

Initial Stack:  |       |    Push 10  =>     |  10  |    Pop   =>      |      |
                |_______|    Push 20  =>     |  20  |    Result:      Empty Stack
                             |_______|       |  10  |
        

Queues

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

Initial Queue:  |       |  Enqueue 10 =>   Front->|  10  |    Dequeue =>   |      |
                |_______|  Enqueue 20 =>          |  20  |    Result:      Empty Queue
                              |_______|           |______|
        

Trees

A tree is a hierarchical data structure with a root node and sub-nodes. Trees are non-linear and can have multiple levels.

Example: Binary Tree

    10
   /  \
  5    15
 / \   / \
2   7 12  20
        

Graphs

A graph is a non-linear data structure consisting of nodes (vertices) and edges that connect pairs of nodes.

Example: Directed Graph

(0) -> (1)
 |     ^
 v    /
(2)  /
    v
   (3)
        

Hash Tables

A hash table stores key-value pairs and uses a hash function to map keys to indices in an array.

Example: Hash table storing student IDs and names

{123: "Alice", 456: "Bob", 789: "Charlie"}
        

Algorithms

Sorting

Bubble Sort

Repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.

Sorting [5, 2, 9, 1]
Pass 1: [2, 5, 1, 9]
Pass 2: [2, 1, 5, 9]
Pass 3: [1, 2, 5, 9]
        

Selection Sort

Selects the smallest element from unsorted sublist and swaps it with the leftmost unsorted element.

Sorting [5, 2, 9, 1]
Pass 1: [1, 2, 9, 5]
Pass 2: [1, 2, 9, 5]
Pass 3: [1, 2, 5, 9]
        

Insertion Sort

Builds the final sorted array one item at a time by picking elements and inserting them into their correct position.

Sorting [5, 2, 9, 1]
Pass 1: [2, 5, 9, 1]
Pass 2: [2, 5, 9, 1]
Pass 3: [1, 2, 5, 9]
        

Merge Sort

Divides the array into halves, sorts them, and merges them back together.

Split:   [5, 2] [9, 1]
Merge:   [2, 5] [1, 9]
Result:  [1, 2, 5, 9]
        

Quick Sort

Picks an element as pivot and partitions the array around the pivot.

Pivot:     [5]
Partition: [2, 1] [9]
Result:    [1, 2, 5, 9]
        

Heap Sort

Builds a heap from the input data and repeatedly extracts the maximum element to sort it.

Build Heap:   [9, 5, 2, 1]
Extract Max:  [5, 2, 1] -> [1, 2, 5, 9]
        

Searching

Linear Search

Sequentially checks each element of the list until the desired element is found.

Searching for 9 in [5, 2, 9, 1]
Steps: Check each element from left to right until 9 is found.
        

Binary Search

Efficient algorithm for finding an item in a sorted array. It repeatedly divides the search interval in half.

Searching for 9 in [1, 2, 5, 9]
Initial: [1, 2, 5, 9]   -> Mid: 5
Search:  [9]            -> Mid: 9
        

Recursion

A function calls itself directly or indirectly to solve a problem. Example: Factorial of a number n! = n * (n-1)!

Base Case: 0! = 1
Recursive Case: n! = n * (n-1)!
        

Dynamic Programming

Solves problems by breaking them down into simpler subproblems and storing the results of these subproblems to avoid computing the same results multiple times.

Example: Fibonacci sequence using memoization

F(5) = F(4) + F(3)
F(4) = F(3) + F(2)
F(3) = F(2) + F(1)
F(2) = F(1) + F(0)
        

Greedy Algorithms

Makes the best choice at each step with the hope of finding the best overall solution. Example: Coin change problem with minimal coins for a given amount.

Amount: 11
Coins:  [1, 5, 10]
Steps:  10 -> 1
        

Backtracking

Tries to build a solution step by step and removes solutions that fail to satisfy the constraints. Example: Solving a maze or Sudoku.

Path: [Start -> 1 -> 2 -> 3]
Backtrack: [Start -> 1 -> 4]
        

Time and Space Complexity

Big O Notation describes the performance or complexity of an algorithm in terms of time or space as the input size grows. Space Complexity is the amount of memory an algorithm uses relative to the input size.

Example:

• Time Complexity of Bubble Sort: O(n²)
• Space Complexity of Merge Sort: O(n)

Important Tips

• Practice Regularly: Keep coding to reinforce knowledge.
• Understand Complexity: Analyze the time and space requirements.
• Debugging Tools: Use tools like print statements, debuggers.
• Problem Breakdown: Divide complex problems into smaller, manageable parts.
• Data Structure Choice: Choose structures that optimize performance.
• Code Efficiency: Write clean and efficient code.
• Collaboration: Work with peers to learn new techniques.