💻 CS Core
Data Structures & Algorithms Complete Cheatsheet
Arrays, linked lists, trees, graphs, sorting, and searching — your complete DSA reference.
01
Arrays & Strings
▼
Array
Fixed-size, indexed. O(1) access. O(n) insert/delete.
Dynamic Array
Auto-resizing. Amortized O(1) append. Python list, JS Array.
String
Immutable in most languages. Concatenation is O(n).
Two Pointers
Left+right approach. O(n) time. Solves palindrome, pair-sum.
Sliding Window
Fixed/variable window over array. O(n). For subarray problems.
DSAArray operations
# O(1) access arr[i] # O(n) linear search for x in arr: if x==target: return # O(log n) binary search (SORTED array) lo,hi=0,len(arr)-1 while lo<=hi: mid=(lo+hi)//2 if arr[mid]==target: return mid elif arr[mid]
02
Linked Lists
▼
Singly Linked
Node: data + next pointer. O(1) insert at head. O(n) search.
Doubly Linked
Node: data + prev + next. O(1) insert/delete at any node if pointer known.
Cycle Detection
Floyd's algorithm: slow+fast pointers. If they meet → cycle.
Reverse
Iterative: prev=None, cur=head, next=cur.next, cur.next=prev
DSAReverse a linked list
prev, cur = None, head
while cur:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
return prev
03
Stacks & Queues
▼
Stack
LIFO. push/pop O(1). Use: DFS, undo, bracket matching.
Queue
FIFO. enqueue/dequeue O(1). Use: BFS, scheduling.
Monotonic Stack
Maintains increasing or decreasing order. Next greater element.
Deque
Double-ended queue. O(1) both ends. Python: collections.deque
DSAValid parentheses
stack=[]
for c in s:
if c in "([{": stack.append(c)
else:
if not stack: return False
m={")":" (","}":" {","]":" ["}
if stack[-1]!=m[c]: return False
stack.pop()
return len(stack)==0
04
Trees & BST
▼
Binary Tree
Each node: left + right child. Height h, nodes up to 2^(h+1)-1.
BST Property
left < root < right. Search/insert/delete O(h). Balanced: O(log n).
Traversals
Inorder (LNR): sorted. Preorder (NLR): serialise. Postorder (LRN): delete.
AVL / Red-Black
Self-balancing BSTs. Guarantee O(log n) operations.
Heap
Complete binary tree. Max-heap: parent ≥ children. Priority queue.
DSATree traversals
def inorder(node):
if not node: return
inorder(node.left)
print(node.val)
inorder(node.right)
def bfs(root): # level order
from collections import deque
q=deque([root])
while q:
node=q.popleft()
print(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
05
Graphs
▼
Representation
Adjacency list: O(V+E) space. Matrix: O(V²). List preferred.
DFS
Stack/recursion. O(V+E). Detects cycle, topo sort, components.
BFS
Queue. O(V+E). Shortest path in unweighted graph.
Dijkstra
Shortest path weighted graph. Priority queue. O((V+E) log V).
Topological Sort
DFS + reverse post-order. Only for DAGs.
DSADFS & BFS templates
def dfs(graph, start, visited=set()):
visited.add(start)
for nb in graph[start]:
if nb not in visited: dfs(graph,nb,visited)
def bfs(graph, start):
from collections import deque
visited,q=set([start]),deque([start])
while q:
node=q.popleft()
for nb in graph[node]:
if nb not in visited:
visited.add(nb); q.append(nb)
06
Sorting & Searching
▼
| Algorithm | Time (avg) | Time (worst) | Space | Stable |
|---|---|---|---|---|
| Bubble | O(n²) | O(n²) | O(1) | Yes |
| Selection | O(n²) | O(n²) | O(1) | No |
| Insertion | O(n²) | O(n²) | O(1) | Yes |
| Merge | O(n log n) | O(n log n) | O(n) | Yes |
| Quick | O(n log n) | O(n²) | O(log n) | No |
| Heap | O(n log n) | O(n log n) | O(1) | No |
| Counting | O(n+k) | O(n+k) | O(k) | Yes |
DSAMerge sort
def merge_sort(arr): if len(arr)<=1: return arr mid=len(arr)//2 L=merge_sort(arr[:mid]); R=merge_sort(arr[mid:]) res,i,j=[],0,0 while i
07
Big-O Complexity
▼
| Notation | Name | Example |
|---|---|---|
| O(1) | Constant | Array access, hash map lookup |
| O(log n) | Logarithmic | Binary search, BST search |
| O(n) | Linear | Linear search, traversal |
| O(n log n) | Linearithmic | Merge sort, heap sort |
| O(n²) | Quadratic | Bubble/insertion sort, nested loops |
| O(2ⁿ) | Exponential | Subset enumeration, fibonacci (naive) |
| O(n!) | Factorial | Permutations, brute-force TSP |
💡
Space complexity follows same rules. Recursion depth = O(h) stack space. Always optimise the bottleneck.
08
Dynamic Programming
▼
Definition
Break problem into overlapping subproblems. Store results (memoization/tabulation).
Top-down (Memo)
Recursion + cache. Natural to write. Uses call stack.
Bottom-up (Tab)
Fill table iteratively. No recursion overhead.
Key patterns
Fibonacci, 0/1 knapsack, LCS, LIS, coin change, grid paths.
DSACoin change (bottom-up)
def coinChange(coins, amount):
dp=[float("inf")]*(amount+1)
dp[0]=0
for a in range(1,amount+1):
for c in coins:
if c<=a: dp[a]=min(dp[a],dp[a-c]+1)
return dp[amount] if dp[amount]!=float("inf") else -1❓ Quiz
What is the time complexity of binary search?
Binary search halves the search space each step → O(log n). Requires sorted input.