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.