Data Structures Complete Guide 2025: Array to Trie, B-Tree — Every Structure for Interviews

O(1)        — Constant time     e.g., Array index access
O(log n)    — Logarithmic time  e.g., Binary search
O(n)        — Linear time       e.g., Array traversal
O(n log n)  — Linearithmic      e.g., Merge sort
O(n^2)      — Quadratic time    e.g., Bubble sort
O(2^n)      — Exponential time  e.g., Fibonacci recursion
O(n!)       — Factorial          e.g., Permutation generation

n       O(1)  O(log n)  O(n)   O(n log n)  O(n^2)     O(2^n)
10      1     3         10     33          100        1,024
100     1     7         100    664         10,000     1.27e30
1000    1     10        1000   9,966       1,000,000  ---
10000   1     13        10000  132,877     100M       ---

Dynamic array append:
  Usually: O(1) — add to empty slot
  Occasionally: O(n) — copy to 2x array when full

  Total cost for n appends: n + n/2 + n/4 + ... ~ 2n
  Amortized cost: O(2n/n) = O(1)

Index:   0    1    2    3    4
       [10] [20] [30] [40] [50]
        ^                    ^
     arr[0]              arr[4]

# Dynamic array implementation
class DynamicArray:
    def __init__(self):
        self.size = 0
        self.capacity = 1
        self.data = [None] * self.capacity

    def append(self, value):
        if self.size == self.capacity:
            self._resize(2 * self.capacity)
        self.data[self.size] = value
        self.size += 1

    def _resize(self, new_capacity):
        new_data = [None] * new_capacity
        for i in range(self.size):
            new_data[i] = self.data[i]
        self.data = new_data
        self.capacity = new_capacity

    def get(self, index):
        if 0 <= index < self.size:
            return self.data[index]
        raise IndexError("Index out of range")

Singly Linked List:
  [10|->] -> [20|->] -> [30|->] -> [40|->] -> None

Doubly Linked List:
  None <- [<-|10|->] <-> [<-|20|->] <-> [<-|30|->] -> None

Circular Linked List:
  [10|->] -> [20|->] -> [30|->] -> [10|->] (back to start)

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class LinkedList:
    def __init__(self):
        self.head = None

    def prepend(self, val):
        new_node = ListNode(val, self.head)
        self.head = new_node

    def delete(self, val):
        dummy = ListNode(0, self.head)
        prev, curr = dummy, self.head
        while curr:
            if curr.val == val:
                prev.next = curr.next
                break
            prev, curr = curr, curr.next
        self.head = dummy.next

    def reverse(self):
        prev, curr = None, self.head
        while curr:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        self.head = prev

push(10) -> push(20) -> push(30) -> pop()

  |    |   |    |   | 30 |   | 20 |
  |    |   | 20 |   | 20 |   |    | <- 30 returned
  | 10 |   | 10 |   | 10 |   | 10 |
  +----+   +----+   +----+   +----+

# Stack — implemented with Python list
class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.items.pop()

    def peek(self):
        return self.items[-1] if self.items else None

    def is_empty(self):
        return len(self.items) == 0

enqueue(10) -> enqueue(20) -> enqueue(30) -> dequeue()

Front ->                                    Front ->
[10]      [10][20]     [10][20][30]       [20][30]  <- 10 returned

Insert/Delete at front <- [10][20][30] -> Insert/Delete at back

key: "apple" -> hash("apple") -> 3
key: "banana" -> hash("banana") -> 7
key: "cherry" -> hash("cherry") -> 3  <- Collision!

Buckets:
[0] ->
[1] ->
[2] ->
[3] -> ("apple", 100) -> ("cherry", 300)  <- Chaining
[4] ->
[5] ->
[6] ->
[7] -> ("banana", 200)

[3] -> ("apple", 100) -> ("cherry", 300) -> None

Linear Probing:
  hash("cherry") = 3 -> already occupied -> check 4 -> empty -> store

Quadratic Probing:
  hash("cherry") = 3 -> 3+1^2=4 -> 3+2^2=7 -> ...

Double Hashing:
  hash("cherry") = 3 -> 3 + hash2("cherry") -> ...

Load Factor = number of stored elements / number of buckets

LF > 0.75 -> Rehash (double the buckets, redistribute all elements)

class HashMap:
    def __init__(self, capacity=16):
        self.capacity = capacity
        self.size = 0
        self.buckets = [[] for _ in range(capacity)]
        self.load_factor_threshold = 0.75

    def _hash(self, key):
        return hash(key) % self.capacity

    def put(self, key, value):
        if self.size / self.capacity >= self.load_factor_threshold:
            self._rehash()

        idx = self._hash(key)
        for i, (k, v) in enumerate(self.buckets[idx]):
            if k == key:
                self.buckets[idx][i] = (key, value)
                return
        self.buckets[idx].append((key, value))
        self.size += 1

    def get(self, key):
        idx = self._hash(key)
        for k, v in self.buckets[idx]:
            if k == key:
                return v
        raise KeyError(key)

    def _rehash(self):
        old_buckets = self.buckets
        self.capacity *= 2
        self.buckets = [[] for _ in range(self.capacity)]
        self.size = 0
        for bucket in old_buckets:
            for key, value in bucket:
                self.put(key, value)

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

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

class BST:
    def __init__(self):
        self.root = None

    def insert(self, val):
        self.root = self._insert(self.root, val)

    def _insert(self, node, val):
        if not node:
            return TreeNode(val)
        if val < node.val:
            node.left = self._insert(node.left, val)
        elif val > node.val:
            node.right = self._insert(node.right, val)
        return node

    def search(self, val):
        return self._search(self.root, val)

    def _search(self, node, val):
        if not node or node.val == val:
            return node
        if val < node.val:
            return self._search(node.left, val)
        return self._search(node.right, val)

    def inorder(self, node, result=None):
        if result is None:
            result = []
        if node:
            self.inorder(node.left, result)
            result.append(node.val)
            self.inorder(node.right, result)
        return result

Rotations to restore balance when imbalanced:

LL Rotation (Right Rotation):      RR Rotation (Left Rotation):
    z                              z
   /                                \
  y         ->      y                 y       ->      y
 /                 / \                \             / \
x                 x   z                x           z   x

LR Rotation:                        RL Rotation:
    z                              z
   /                                \
  x         ->      y                x       ->      y
   \               / \             /               / \
    y             x   z           y               z   x

Rules:
1. Every node is red or black
2. Root is black
3. All leaves (NIL) are black
4. Red node children must all be black (no consecutive reds)
5. Equal black node count from any node to all its leaves

        (B:8)
       /      \
    (R:3)    (R:10)
    / \        \
 (B:1)(B:6)  (B:14)
       / \     /
    (R:4)(R:7)(R:13)

B-Tree (order 3):
          [10, 20]
         /   |    \
   [3,7]  [12,15] [25,30,40]

B+Tree (order 3):
          [10, 20]
         /   |    \
   [3,7]  [10,15] [20,25,30]
      -> -> -> -> ->     <- Leaf nodes form a linked list

Array: [1, 3, 5, 7, 9, 11]

Range Sum Segment Tree:
              [36]           (0-5)
           /        \
        [9]          [27]     (0-2), (3-5)
       /   \        /    \
     [4]   [5]   [16]   [11]  (0-1),(2),(3-4),(5)
    / \          / \
  [1] [3]     [7] [9]

class SegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        self.build(arr, 1, 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, start, mid)
            self.build(arr, 2 * node + 1, mid + 1, end)
            self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

    def query(self, node, start, end, l, r):
        if r < start or end < l:
            return 0
        if l <= start and end <= r:
            return self.tree[node]
        mid = (start + end) // 2
        left = self.query(2 * node, start, mid, l, r)
        right = self.query(2 * node + 1, mid + 1, end, l, r)
        return left + right

Min Heap:                 Max Heap:
      1                        9
     / \                      / \
    3   5                    7   8
   / \ / \                  / \ / \
  7  8 9  10               3  5 4  6

Index:   0  1  2  3  4  5  6
Min:   [ 1, 3, 5, 7, 8, 9, 10]

Parent: (i-1) // 2
Left child: 2*i + 1
Right child: 2*i + 2

class MinHeap:
    def __init__(self):
        self.heap = []

    def push(self, val):
        self.heap.append(val)
        self._sift_up(len(self.heap) - 1)

    def pop(self):
        if not self.heap:
            raise IndexError("Heap is empty")
        self._swap(0, len(self.heap) - 1)
        val = self.heap.pop()
        if self.heap:
            self._sift_down(0)
        return val

    def _sift_up(self, i):
        parent = (i - 1) // 2
        while i > 0 and self.heap[i] < self.heap[parent]:
            self._swap(i, parent)
            i = parent
            parent = (i - 1) // 2

    def _sift_down(self, i):
        n = len(self.heap)
        while True:
            smallest = i
            left = 2 * i + 1
            right = 2 * i + 2
            if left < n and self.heap[left] < self.heap[smallest]:
                smallest = left
            if right < n and self.heap[right] < self.heap[smallest]:
                smallest = right
            if smallest == i:
                break
            self._swap(i, smallest)
            i = smallest

    def _swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

def heap_sort(arr):
    import heapq
    heapq.heapify(arr)
    return [heapq.heappop(arr) for _ in range(len(arr))]

Words: "cat", "car", "card", "dog", "do"

Root
+-- c
|   +-- a
|       +-- t (*)
|       +-- r (*)
|           +-- d (*)
+-- d
    +-- o (*)
        +-- g (*)

(*) = end of word

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._find_node(word)
        return node is not None and node.is_end

    def starts_with(self, prefix):
        return self._find_node(prefix) is not None

    def _find_node(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

    def autocomplete(self, prefix):
        """Return all words starting with prefix"""
        node = self._find_node(prefix)
        if not node:
            return []
        results = []
        self._dfs(node, prefix, results)
        return results

    def _dfs(self, node, path, results):
        if node.is_end:
            results.append(path)
        for char, child in node.children.items():
            self._dfs(child, path + char, results)

Graph:
  A --- B
  |   / |
  |  /  |
  C --- D

Adjacency List:
  A: [B, C]
  B: [A, C, D]
  C: [A, B, D]
  D: [B, C]

Adjacency Matrix:
     A  B  C  D
  A [0, 1, 1, 0]
  B [1, 0, 1, 1]
  C [1, 1, 0, 1]
  D [0, 1, 1, 0]

from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

BFS order (starting from A):
Level 0: A
Level 1: B, C
Level 2: D

Queue: [A] -> [B, C] -> [C, D] -> [D] -> []

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    result = [start]
    for neighbor in graph[start]:
        if neighbor not in visited:
            result.extend(dfs(graph, neighbor, visited))
    return result

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]  # (distance, node)

    while pq:
        dist, node = heapq.heappop(pq)
        if dist > distances[node]:
            continue
        for neighbor, weight in graph[node]:
            new_dist = dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))

    return distances

from collections import deque

def topological_sort(graph, in_degree):
    queue = deque([v for v in graph if in_degree[v] == 0])
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return result if len(result) == len(graph) else []  # cycle detection

def bellman_ford(edges, num_vertices, start):
    distances = [float('inf')] * num_vertices
    distances[start] = 0

    for _ in range(num_vertices - 1):
        for u, v, w in edges:
            if distances[u] + w < distances[v]:
                distances[v] = distances[u] + w

    # Negative cycle detection
    for u, v, w in edges:
        if distances[u] + w < distances[v]:
            return None  # Negative cycle exists

    return distances

Initial: Each node represents itself
{0} {1} {2} {3} {4}

union(0, 1): {0, 1} {2} {3} {4}
union(2, 3): {0, 1} {2, 3} {4}
union(0, 3): {0, 1, 2, 3} {4}

find(1) == find(3)?  -> Yes (same set)
find(1) == find(4)?  -> No (different sets)

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        # Path Compression
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        # Union by Rank
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

Level 3: HEAD -------------------- 50 ------- NIL
Level 2: HEAD ---- 20 ----------- 50 --- 70 -- NIL
Level 1: HEAD -- 10 -- 20 -- 30 -- 50 -- 70 -- 80 -- NIL
Level 0: HEAD -- 10 -- 20 -- 30 -- 40 -- 50 -- 60 -- 70 -- 80 -- NIL

k=3 hash functions, m=10 bit array

insert("apple"):
  h1("apple")=2, h2("apple")=5, h3("apple")=8
  Bit array: [0,0,1,0,0,1,0,0,1,0]

query("apple"): positions 2,5,8 all 1 -> "probably exists"
query("grape"): h1=1, h2=5, h3=7 -> position 1 is 0 -> "definitely not"

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

Need fast insert/delete? -> Hash table or linked list
Need sorted order? -> BST family (AVL, Red-Black)
Need fast min/max? -> Heap
Need string prefix search? -> Trie
Need range queries? -> Segment tree or B-Tree
Need fast set membership? -> HashSet or Bloom filter
Need connected component management? -> Union-Find
Need shortest path? -> Graph + Dijkstra/BFS
FIFO? -> Queue
LIFO? -> Stack