Data Structures Cheatsheet

• Visualgo (visualgo.net)
• Big O Cheat Sheet
• LeetCode Practice

# Python Array
arr = [1, 2, 3, 4, 5]
arr.append(6)      # O(1)
arr.insert(0, 0)   # O(n)
arr.pop()          # O(1)
arr[2]             # O(1) - access

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

# Singly Linked List
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)

# LIFO - Last In, First Out
stack = []
stack.append(1)    # Push
stack.append(2)
stack.append(3)
top = stack[-1]    # Peek
item = stack.pop() # Pop

from collections import deque

# FIFO - First In, First Out
queue = deque()
queue.append(1)    # Enqueue
queue.append(2)
queue.append(3)
front = queue[0]   # Front
item = queue.popleft() # Dequeue

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

# Binary Search Tree
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(7)

# Adjacency List
graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3],
    3: [1, 2]
}

# Adjacency Matrix
matrix = [
    [0, 1, 1, 0],
    [1, 0, 0, 1],
    [1, 0, 0, 1],
    [0, 1, 1, 0]
]

# Dictionary/Hash Map
hash_map = {}
hash_map['key'] = 'value'  # Insert
value = hash_map['key']    # Search
del hash_map['key']        # Delete

# Set
my_set = set()
my_set.add(1)              # Insert
1 in my_set                # Search
my_set.remove(1)           # Delete

import heapq

# Min Heap
heap = []
heapq.heappush(heap, 3)    # Insert
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
min_val = heap[0]          # Peek
min_val = heapq.heappop(heap) # Extract min

# Space Complexity Examples
def constant_space(n):
    return n + 1  # O(1) space

def linear_space(n):
    return [i for i in range(n)]  # O(n) space

def quadratic_space(n):
    return [[0]*n for _ in range(n)]  # O(n²) space

# AVL Tree Node
class AVLNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1

# Red-Black Tree Node
class RBNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.parent = None
        self.color = "RED"  # RED or BLACK

# Dijkstra's Algorithm
import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]
    
    while pq:
        dist, node = heapq.heappop(pq)
        if dist > distances[node]:
            continue
        for neighbor, weight in graph[node].items():
            if distances[node] + weight < distances[neighbor]:
                distances[neighbor] = distances[node] + weight
                heapq.heappush(pq, (distances[neighbor], neighbor))
    return distances

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
    
    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return
        if self.rank[px] < self.rank[py]:
            self.parent[px] = py
        elif self.rank[px] > self.rank[py]:
            self.parent[py] = px
        else:
            self.parent[py] = px
            self.rank[px] += 1

class SegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        self.build(arr, 0, 0, self.n - 1)
    
    def build(self, arr, node, start, end):
        if start == end:
            self.tree[node] = arr[start]
        else:
            mid = (start + end) // 2
            self.build(arr, 2*node + 1, start, mid)
            self.build(arr, 2*node + 2, mid + 1, end)
            self.tree[node] = self.tree[2*node + 1] + self.tree[2*node + 2]
    
    def query(self, node, start, end, l, r):
        if r < start or l > end:
            return 0
        if l <= start and end <= r:
            return self.tree[node]
        mid = (start + end) // 2
        return (self.query(2*node + 1, start, mid, l, r) + 
                self.query(2*node + 2, mid + 1, end, l, r))

class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
    
    def update(self, i, val):
        while i <= self.n:
            self.tree[i] += val
            i += i & -i
    
    def query(self, i):
        res = 0
        while i > 0:
            res += self.tree[i]
            i -= i & -i
        return res
    
    def range_query(self, l, r):
        return self.query(r) - self.query(l - 1)