Data Structures and Algorithms Cheatsheet

Introduction

Data Structures and Algorithms (DSA) are the foundation of computer science. They are used to solve problems efficiently and write optimized code. A data structure organizes and stores data, while an algorithm is a step-by-step process to solve a problem. This cheatsheet covers the most essential DSA topics in simple words with short definitions, code examples, and key points.

1. Arrays

Definition: A collection of elements stored in a continuous memory block, accessed by index.

Code Example (Python)

      
        arr = [10, 20, 30]
print(arr[1])  # Output: 20

Key Point: Fast access with O(1) complexity, but insertion/deletion in the middle is costly, with O(n) complexity.

2. Linked List

Definition: A sequence of nodes where each node stores data and a pointer to the next node.

Code Example (Python)

      
        class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

Key Point: Efficient insertions/deletions O(1), but slower access O(n).

3. Stack

Definition: A collection that follows LIFO (Last In, First Out).

Code Example (Python)

      
        stack = []
stack.append(10)  # push
stack.append(20)
print(stack.pop())  # Output: 20

Key Point: Used in function calls, undo operations, and expression evaluation.

4. Queue

Definition: A collection that follows FIFO (First In, First Out).

Code Example (Python)

      
        from collections import deque
q = deque([1, 2])
q.append(3)       # enqueue
print(q.popleft()) # dequeue → 1

Key Point: Used in scheduling, BFS traversal.

5. Hash Table / Dictionary

Definition: Stores data as key-value pairs for fast access.

Code Example (Python)

      
        ht = {"a": 1, "b": 2}
print(ht["b"])  # Output: 2

Key Point: Average O(1) access, collisions handled by chaining or probing.

6. Binary Tree

Definition: A tree structure where each node has at most two children (left and right).

Code Example (Python)

      
        class Node:
    def __init__(self, data):
        self.data = data
        self.left = self.right = None

Key Point: Basis for many advanced structures (BST, Heaps).

7. Binary Search Tree (BST)

Definition: A binary tree where left child < parent < right child.

Code Example (Search)

      
        def search(root, key):
    if not root or root.data == key:
        return root
    if key < root.data:
        return search(root.left, key)
    return search(root.right, key)

Key Point: Efficient search O(log n) if balanced.

8. Heap

Definition: A binary tree-based structure used for priority queues.

Code Example (Python min-heap)

      
        import heapq
arr = [3, 1, 4]
heapq.heapify(arr)
print(heapq.heappop(arr))  # Output: 1

Key Point: Used in priority queues, heapsort, and graph algorithms.

9. Graph

Definition: A collection of nodes (vertices) connected by edges. Can be directed/undirected, weighted/unweighted.

Code Example (Adjacency List)

      
        graph = {1: [2, 3], 2: [4], 3: []}

Key Point: Used in social networks, maps, and routing.

10. Searching Algorithms

Linear Search: Check each element one by one. O(n).

      
        def linear_search(arr, x):
    for i in range(len(arr)):
        if arr[i] == x:
            return i
    return -1

Binary Search: Works on sorted arrays. O(log n).

      
        def binary_search(arr, x):
    low, high = 0, len(arr)-1
    while low <= high:
        mid = (low + high)//2
        if arr[mid] == x:
            return mid
        elif arr[mid] < x:
            low = mid + 1
        else:
            high = mid - 1
    return -1

11. Sorting Algorithms

Bubble Sort: Compare adjacent elements repeatedly. O(n²).
Merge Sort: Divide and merge sorted halves—O (n log n).
Quick Sort: Partition around a pivot. O(n log n) average.
Heap Sort: Use heap to extract max/min repeatedly—o (n log n).

Example (Python Merge Sort)

  
    def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr)//2
        L, R = arr[:mid], arr[mid:]
        merge_sort(L); merge_sort(R)
        i = j = k = 0
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]; i += 1
            else:
                arr[k] = R[j]; j += 1
            k += 1
        arr[k:] = L[i:] + R[j:]

12. Recursion

Definition: A function calling itself to solve more minor parts of a problem.

Example: Factorial

      
        def fact(n):
    return 1 if n == 0 else n * fact(n-1)

Key Point: Used in divide-and-conquer, tree/graph traversal.

13. Dynamic Programming (DP)

Definition: A Technique to solve problems by breaking them into subproblems and storing results to avoid repetition.

Example (Fibonacci with DP)

      
        def fib(n, memo={}):
    if n in memo: return memo[n]
    if n <= 1: return n
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

Key Point: Used in optimization problems (shortest path, knapsack).

14. Greedy Algorithms

Definition: Make the best choice at each step to achieve the solution.
Example: Coin change problem (minimum coins).
Key Point: Works when the local optimum converges to the global optimum.

15. Graph Algorithms

BFS (Breadth-First Search): Visit level by level using a queue. O(V+E).
DFS (Depth-First Search): Visit deep before backtracking using recursion/stack. O(V+E).
Dijkstra’s Algorithm: Shortest path from one source. O(E log V).
Kruskal/Prim: Minimum Spanning Tree.

Conclusion

Data Structures and Algorithms are the backbone of problem-solving in programming. Arrays, linked lists, stacks, queues, trees, graphs, searching, sorting, recursion, dynamic programming, and greedy methods are essential building blocks. Learning their definitions, time complexities, and practical uses will help you write faster and more reliable code. This cheatsheet provides a quick guide for revision and interview preparation.