Data Structures
Disclaimer: These are my personal notes compiled for my own reference and learning. They may contain errors, incomplete information, or personal interpretations. While I strive for accuracy, these notes are not peer-reviewed and should not be considered authoritative sources. Please consult official textbooks, research papers, or other reliable sources for academic or professional purposes.
1. Introduction to Data Structures
Data structures are ways of organizing and storing data to enable efficient access and modification. The choice of data structure affects the complexity of algorithms that operate on the data.
2. Arrays and Dynamic Arrays
2.1 Static Arrays
- Access: $O(1)$ - Direct indexing
- Search: $O(n)$ - Linear scan (unsorted), $O(\log n)$ (sorted with binary search)
- Insertion/Deletion: $O(n)$ - Need to shift elements
- Space: $O(n)$
2.2 Dynamic Arrays (Python Lists)
class DynamicArray:
def __init__(self):
self.capacity = 1
self.size = 0
self.data = [None] * self.capacity
def __getitem__(self, index):
if not 0 <= index < self.size:
raise IndexError("Index out of range")
return self.data[index]
def __setitem__(self, index, value):
if not 0 <= index < self.size:
raise IndexError("Index out of range")
self.data[index] = value
def append(self, value):
if self.size == self.capacity:
self._resize()
self.data[self.size] = value
self.size += 1
def insert(self, index, value):
if not 0 <= index <= self.size:
raise IndexError("Index out of range")
if self.size == self.capacity:
self._resize()
# Shift elements to the right
for i in range(self.size, index, -1):
self.data[i] = self.data[i-1]
self.data[index] = value
self.size += 1
def delete(self, index):
if not 0 <= index < self.size:
raise IndexError("Index out of range")
# Shift elements to the left
for i in range(index, self.size - 1):
self.data[i] = self.data[i+1]
self.size -= 1
def _resize(self):
old_capacity = self.capacity
self.capacity *= 2
new_data = [None] * self.capacity
for i in range(self.size):
new_data[i] = self.data[i]
self.data = new_data
def __len__(self):
return self.size
def __str__(self):
return str([self.data[i] for i in range(self.size)])
# Usage example
arr = DynamicArray()
for i in range(5):
arr.append(i)
print(arr) # [0, 1, 2, 3, 4]
3. Linked Lists
3.1 Singly Linked List
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class LinkedList:
def __init__(self):
self.head = None
self.size = 0
def append(self, val):
new_node = ListNode(val)
if not self.head:
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
self.size += 1
def prepend(self, val):
new_node = ListNode(val, self.head)
self.head = new_node
self.size += 1
def insert(self, index, val):
if index == 0:
self.prepend(val)
return
if index < 0 or index > self.size:
raise IndexError("Index out of range")
current = self.head
for _ in range(index - 1):
current = current.next
new_node = ListNode(val, current.next)
current.next = new_node
self.size += 1
def delete(self, index):
if index < 0 or index >= self.size:
raise IndexError("Index out of range")
if index == 0:
self.head = self.head.next
self.size -= 1
return
current = self.head
for _ in range(index - 1):
current = current.next
current.next = current.next.next
self.size -= 1
def find(self, val):
current = self.head
index = 0
while current:
if current.val == val:
return index
current = current.next
index += 1
return -1
def __len__(self):
return self.size
def __str__(self):
result = []
current = self.head
while current:
result.append(str(current.val))
current = current.next
return " -> ".join(result)
# Complexity Analysis:
# Access: O(n) - must traverse from head
# Search: O(n) - linear scan
# Insertion: O(1) at head, O(n) at arbitrary position
# Deletion: O(1) at head, O(n) at arbitrary position
# Space: O(n)
3.2 Doubly Linked List
class DoublyListNode:
def __init__(self, val=0, prev=None, next=None):
self.val = val
self.prev = prev
self.next = next
class DoublyLinkedList:
def __init__(self):
# Sentinel nodes to simplify edge cases
self.head = DoublyListNode()
self.tail = DoublyListNode()
self.head.next = self.tail
self.tail.prev = self.head
self.size = 0
def _add_node(self, node, prev_node):
"""Add node after prev_node"""
next_node = prev_node.next
prev_node.next = node
node.prev = prev_node
node.next = next_node
next_node.prev = node
self.size += 1
def _remove_node(self, node):
"""Remove node from list"""
prev_node = node.prev
next_node = node.next
prev_node.next = next_node
next_node.prev = prev_node
self.size -= 1
def append(self, val):
new_node = DoublyListNode(val)
self._add_node(new_node, self.tail.prev)
def prepend(self, val):
new_node = DoublyListNode(val)
self._add_node(new_node, self.head)
def delete_val(self, val):
current = self.head.next
while current != self.tail:
if current.val == val:
self._remove_node(current)
return True
current = current.next
return False
def __len__(self):
return self.size
def __str__(self):
result = []
current = self.head.next
while current != self.tail:
result.append(str(current.val))
current = current.next
return " <-> ".join(result)
4. Stacks and Queues
4.1 Stack (LIFO - Last In, First Out)
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item) # O(1) amortized
def pop(self):
if self.is_empty():
raise IndexError("Stack is empty")
return self.items.pop() # O(1)
def peek(self):
if self.is_empty():
raise IndexError("Stack is empty")
return self.items[-1] # O(1)
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
# Applications: Expression evaluation, function calls, undo operations
def is_valid_parentheses(s):
"""Check if parentheses are balanced using stack"""
stack = Stack()
pairs = {'(': ')', '[': ']', '{': '}'}
for char in s:
if char in pairs:
stack.push(char)
elif char in pairs.values():
if stack.is_empty() or pairs[stack.pop()] != char:
return False
return stack.is_empty()
4.2 Queue (FIFO - First In, First Out)
from collections import deque
class Queue:
def __init__(self):
self.items = deque()
def enqueue(self, item):
self.items.append(item) # O(1)
def dequeue(self):
if self.is_empty():
raise IndexError("Queue is empty")
return self.items.popleft() # O(1)
def front(self):
if self.is_empty():
raise IndexError("Queue is empty")
return self.items[0] # O(1)
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
# Circular Queue implementation
class CircularQueue:
def __init__(self, capacity):
self.capacity = capacity
self.queue = [None] * capacity
self.head = 0
self.tail = 0
self.size = 0
def enqueue(self, item):
if self.is_full():
raise OverflowError("Queue is full")
self.queue[self.tail] = item
self.tail = (self.tail + 1) % self.capacity
self.size += 1
def dequeue(self):
if self.is_empty():
raise IndexError("Queue is empty")
item = self.queue[self.head]
self.queue[self.head] = None
self.head = (self.head + 1) % self.capacity
self.size -= 1
return item
def is_empty(self):
return self.size == 0
def is_full(self):
return self.size == self.capacity
5. Trees
5.1 Binary Tree
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class BinaryTree:
def __init__(self, root=None):
self.root = root
def inorder_traversal(self, node=None):
"""Left -> Root -> Right"""
if node is None:
node = self.root
result = []
if node:
result.extend(self.inorder_traversal(node.left))
result.append(node.val)
result.extend(self.inorder_traversal(node.right))
return result
def preorder_traversal(self, node=None):
"""Root -> Left -> Right"""
if node is None:
node = self.root
result = []
if node:
result.append(node.val)
result.extend(self.preorder_traversal(node.left))
result.extend(self.preorder_traversal(node.right))
return result
def postorder_traversal(self, node=None):
"""Left -> Right -> Root"""
if node is None:
node = self.root
result = []
if node:
result.extend(self.postorder_traversal(node.left))
result.extend(self.postorder_traversal(node.right))
result.append(node.val)
return result
def level_order_traversal(self):
"""Breadth-first traversal"""
if not self.root:
return []
result = []
queue = Queue()
queue.enqueue(self.root)
while not queue.is_empty():
node = queue.dequeue()
result.append(node.val)
if node.left:
queue.enqueue(node.left)
if node.right:
queue.enqueue(node.right)
return result
def height(self, node=None):
"""Calculate height of tree"""
if node is None:
node = self.root
if not node:
return -1
return 1 + max(self.height(node.left), self.height(node.right))
def is_balanced(self, node=None):
"""Check if tree is height-balanced"""
if node is None:
node = self.root
def check_balance(node):
if not node:
return 0, True
left_height, left_balanced = check_balance(node.left)
right_height, right_balanced = check_balance(node.right)
balanced = (left_balanced and right_balanced and
abs(left_height - right_height) <= 1)
height = 1 + max(left_height, right_height)
return height, balanced
_, balanced = check_balance(node)
return balanced
5.2 Binary Search Tree
class BST:
def __init__(self):
self.root = None
def insert(self, val):
self.root = self._insert_recursive(self.root, val)
def _insert_recursive(self, node, val):
if not node:
return TreeNode(val)
if val < node.val:
node.left = self._insert_recursive(node.left, val)
elif val > node.val:
node.right = self._insert_recursive(node.right, val)
return node
def search(self, val):
return self._search_recursive(self.root, val)
def _search_recursive(self, node, val):
if not node or node.val == val:
return node
if val < node.val:
return self._search_recursive(node.left, val)
else:
return self._search_recursive(node.right, val)
def delete(self, val):
self.root = self._delete_recursive(self.root, val)
def _delete_recursive(self, node, val):
if not node:
return node
if val < node.val:
node.left = self._delete_recursive(node.left, val)
elif val > node.val:
node.right = self._delete_recursive(node.right, val)
else:
# Node to be deleted found
if not node.left:
return node.right
elif not node.right:
return node.left
# Node has two children
# Find inorder successor (smallest in right subtree)
successor = self._find_min(node.right)
node.val = successor.val
node.right = self._delete_recursive(node.right, successor.val)
return node
def _find_min(self, node):
while node.left:
node = node.left
return node
def inorder(self):
"""Returns sorted order for BST"""
result = []
self._inorder_recursive(self.root, result)
return result
def _inorder_recursive(self, node, result):
if node:
self._inorder_recursive(node.left, result)
result.append(node.val)
self._inorder_recursive(node.right, result)
# Complexity Analysis:
# Average case: O(log n) for search, insert, delete
# Worst case: O(n) when tree becomes skewed (like a linked list)
# Space: O(n)
5.3 AVL Tree (Self-balancing BST)
class AVLNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.height = 1
class AVLTree:
def __init__(self):
self.root = None
def _get_height(self, node):
if not node:
return 0
return node.height
def _get_balance(self, node):
if not node:
return 0
return self._get_height(node.left) - self._get_height(node.right)
def _update_height(self, node):
if node:
node.height = 1 + max(self._get_height(node.left),
self._get_height(node.right))
def _rotate_right(self, y):
x = y.left
T2 = x.right
# Perform rotation
x.right = y
y.left = T2
# Update heights
self._update_height(y)
self._update_height(x)
return x
def _rotate_left(self, x):
y = x.right
T2 = y.left
# Perform rotation
y.left = x
x.right = T2
# Update heights
self._update_height(x)
self._update_height(y)
return y
def insert(self, val):
self.root = self._insert_recursive(self.root, val)
def _insert_recursive(self, node, val):
# Standard BST insertion
if not node:
return AVLNode(val)
if val < node.val:
node.left = self._insert_recursive(node.left, val)
elif val > node.val:
node.right = self._insert_recursive(node.right, val)
else:
return node # Duplicate values not allowed
# Update height
self._update_height(node)
# Get balance factor
balance = self._get_balance(node)
# Left Left Case
if balance > 1 and val < node.left.val:
return self._rotate_right(node)
# Right Right Case
if balance < -1 and val > node.right.val:
return self._rotate_left(node)
# Left Right Case
if balance > 1 and val > node.left.val:
node.left = self._rotate_left(node.left)
return self._rotate_right(node)
# Right Left Case
if balance < -1 and val < node.right.val:
node.right = self._rotate_right(node.right)
return self._rotate_left(node)
return node
# AVL Tree guarantees O(log n) for all operations
6. Heaps
6.1 Binary Heap (Min-Heap)
class MinHeap:
def __init__(self):
self.heap = []
def _parent(self, i):
return (i - 1) // 2
def _left_child(self, i):
return 2 * i + 1
def _right_child(self, i):
return 2 * i + 2
def _swap(self, i, j):
self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
def insert(self, val):
self.heap.append(val)
self._heapify_up(len(self.heap) - 1)
def _heapify_up(self, i):
parent = self._parent(i)
if i > 0 and self.heap[i] < self.heap[parent]:
self._swap(i, parent)
self._heapify_up(parent)
def extract_min(self):
if not self.heap:
raise IndexError("Heap is empty")
if len(self.heap) == 1:
return self.heap.pop()
min_val = self.heap[0]
self.heap[0] = self.heap.pop()
self._heapify_down(0)
return min_val
def _heapify_down(self, i):
left = self._left_child(i)
right = self._right_child(i)
smallest = i
if left < len(self.heap) and self.heap[left] < self.heap[smallest]:
smallest = left
if right < len(self.heap) and self.heap[right] < self.heap[smallest]:
smallest = right
if smallest != i:
self._swap(i, smallest)
self._heapify_down(smallest)
def peek(self):
if not self.heap:
raise IndexError("Heap is empty")
return self.heap[0]
def size(self):
return len(self.heap)
def is_empty(self):
return len(self.heap) == 0
# Heap Sort implementation
def heap_sort(arr):
"""Sort array using heap sort - O(n log n)"""
heap = MinHeap()
# Insert all elements
for num in arr:
heap.insert(num)
# Extract all elements in sorted order
sorted_arr = []
while not heap.is_empty():
sorted_arr.append(heap.extract_min())
return sorted_arr
# Priority Queue using heap
import heapq
class PriorityQueue:
def __init__(self):
self.heap = []
self.index = 0
def push(self, item, priority):
heapq.heappush(self.heap, (priority, self.index, item))
self.index += 1
def pop(self):
if not self.heap:
raise IndexError("Priority queue is empty")
return heapq.heappop(self.heap)[2]
def is_empty(self):
return len(self.heap) == 0
# Complexity:
# Insert: O(log n)
# Extract min/max: O(log n)
# Peek: O(1)
# Build heap: O(n)
7. Hash Tables
7.1 Hash Table with Chaining
class HashTable:
def __init__(self, capacity=10):
self.capacity = capacity
self.size = 0
self.buckets = [[] for _ in range(capacity)]
def _hash(self, key):
"""Simple hash function"""
if isinstance(key, int):
return key % self.capacity
elif isinstance(key, str):
return sum(ord(c) for c in key) % self.capacity
else:
return hash(key) % self.capacity
def put(self, key, value):
index = self._hash(key)
bucket = self.buckets[index]
# Check if key already exists
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
# Add new key-value pair
bucket.append((key, value))
self.size += 1
# Resize if load factor is too high
if self.size > self.capacity * 0.75:
self._resize()
def get(self, key):
index = self._hash(key)
bucket = self.buckets[index]
for k, v in bucket:
if k == key:
return v
raise KeyError(key)
def delete(self, key):
index = self._hash(key)
bucket = self.buckets[index]
for i, (k, v) in enumerate(bucket):
if k == key:
del bucket[i]
self.size -= 1
return v
raise KeyError(key)
def _resize(self):
old_buckets = self.buckets
self.capacity *= 2
self.size = 0
self.buckets = [[] for _ in range(self.capacity)]
# Rehash all elements
for bucket in old_buckets:
for key, value in bucket:
self.put(key, value)
def __contains__(self, key):
try:
self.get(key)
return True
except KeyError:
return False
def keys(self):
result = []
for bucket in self.buckets:
for key, _ in bucket:
result.append(key)
return result
def values(self):
result = []
for bucket in self.buckets:
for _, value in bucket:
result.append(value)
return result
def items(self):
result = []
for bucket in self.buckets:
for item in bucket:
result.append(item)
return result
# Hash table with open addressing (linear probing)
class OpenAddressingHashTable:
def __init__(self, capacity=10):
self.capacity = capacity
self.size = 0
self.keys = [None] * capacity
self.values = [None] * capacity
self.deleted = [False] * capacity
def _hash(self, key):
return hash(key) % self.capacity
def _find_slot(self, key):
index = self._hash(key)
original_index = index
while (self.keys[index] is not None and
self.keys[index] != key and
not self.deleted[index]):
index = (index + 1) % self.capacity
if index == original_index:
raise Exception("Hash table is full")
return index
def put(self, key, value):
if self.size >= self.capacity * 0.75:
self._resize()
index = self._find_slot(key)
if self.keys[index] is None or self.deleted[index]:
self.size += 1
self.keys[index] = key
self.values[index] = value
self.deleted[index] = False
def get(self, key):
index = self._find_slot(key)
if self.keys[index] == key and not self.deleted[index]:
return self.values[index]
raise KeyError(key)
def delete(self, key):
index = self._find_slot(key)
if self.keys[index] == key and not self.deleted[index]:
self.deleted[index] = True
self.size -= 1
return self.values[index]
raise KeyError(key)
def _resize(self):
old_keys = self.keys[:]
old_values = self.values[:]
old_deleted = self.deleted[:]
self.capacity *= 2
self.size = 0
self.keys = [None] * self.capacity
self.values = [None] * self.capacity
self.deleted = [False] * self.capacity
for i in range(len(old_keys)):
if old_keys[i] is not None and not old_deleted[i]:
self.put(old_keys[i], old_values[i])
# Average case complexity:
# Search, Insert, Delete: O(1)
# Worst case: O(n) when many collisions occur
8. Graphs
8.1 Graph Representations
class Graph:
def __init__(self, directed=False):
self.directed = directed
self.adj_list = {}
def add_vertex(self, vertex):
if vertex not in self.adj_list:
self.adj_list[vertex] = []
def add_edge(self, u, v, weight=1):
self.add_vertex(u)
self.add_vertex(v)
self.adj_list[u].append((v, weight))
if not self.directed:
self.adj_list[v].append((u, weight))
def remove_edge(self, u, v):
if u in self.adj_list:
self.adj_list[u] = [(vertex, weight) for vertex, weight in self.adj_list[u] if vertex != v]
if not self.directed and v in self.adj_list:
self.adj_list[v] = [(vertex, weight) for vertex, weight in self.adj_list[v] if vertex != u]
def get_neighbors(self, vertex):
return self.adj_list.get(vertex, [])
def has_edge(self, u, v):
if u not in self.adj_list:
return False
return any(vertex == v for vertex, _ in self.adj_list[u])
def vertices(self):
return list(self.adj_list.keys())
def edges(self):
edges = []
for u in self.adj_list:
for v, weight in self.adj_list[u]:
if self.directed or u <= v: # Avoid duplicates in undirected graph
edges.append((u, v, weight))
return edges
# Matrix representation for dense graphs
class GraphMatrix:
def __init__(self, num_vertices, directed=False):
self.num_vertices = num_vertices
self.directed = directed
self.matrix = [[0] * num_vertices for _ in range(num_vertices)]
def add_edge(self, u, v, weight=1):
self.matrix[u][v] = weight
if not self.directed:
self.matrix[v][u] = weight
def remove_edge(self, u, v):
self.matrix[u][v] = 0
if not self.directed:
self.matrix[v][u] = 0
def has_edge(self, u, v):
return self.matrix[u][v] != 0
def get_neighbors(self, vertex):
neighbors = []
for i in range(self.num_vertices):
if self.matrix[vertex][i] != 0:
neighbors.append((i, self.matrix[vertex][i]))
return neighbors
8.2 Graph Traversal Algorithms
# Depth-First Search (DFS)
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
result = [start]
for neighbor, _ in graph.get_neighbors(start):
if neighbor not in visited:
result.extend(dfs(graph, neighbor, visited))
return result
def dfs_iterative(graph, start):
visited = set()
stack = [start]
result = []
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
result.append(vertex)
# Add neighbors to stack (reverse order for consistent traversal)
neighbors = [neighbor for neighbor, _ in graph.get_neighbors(vertex)]
for neighbor in reversed(neighbors):
if neighbor not in visited:
stack.append(neighbor)
return result
# Breadth-First Search (BFS)
def bfs(graph, start):
visited = set()
queue = Queue()
queue.enqueue(start)
visited.add(start)
result = []
while not queue.is_empty():
vertex = queue.dequeue()
result.append(vertex)
for neighbor, _ in graph.get_neighbors(vertex):
if neighbor not in visited:
visited.add(neighbor)
queue.enqueue(neighbor)
return result
# Shortest path in unweighted graph using BFS
def shortest_path_bfs(graph, start, end):
if start == end:
return [start]
visited = set()
queue = Queue()
queue.enqueue((start, [start]))
visited.add(start)
while not queue.is_empty():
vertex, path = queue.dequeue()
for neighbor, _ in graph.get_neighbors(vertex):
if neighbor == end:
return path + [neighbor]
if neighbor not in visited:
visited.add(neighbor)
queue.enqueue((neighbor, path + [neighbor]))
return None # No path found
# Dijkstra's Algorithm for shortest path in weighted graph
def dijkstra(graph, start):
distances = {vertex: float('inf') for vertex in graph.vertices()}
distances[start] = 0
previous = {}
pq = PriorityQueue()
pq.push(start, 0)
while not pq.is_empty():
current = pq.pop()
for neighbor, weight in graph.get_neighbors(current):
distance = distances[current] + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
previous[neighbor] = current
pq.push(neighbor, distance)
return distances, previous
def reconstruct_path(previous, start, end):
path = []
current = end
while current is not None:
path.append(current)
current = previous.get(current)
path.reverse()
if path[0] == start:
return path
else:
return None # No path exists
9. Advanced Data Structures
9.1 Trie (Prefix Tree)
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
current = self.root
for char in word:
if char not in current.children:
current.children[char] = TrieNode()
current = current.children[char]
current.is_end_of_word = True
def search(self, word):
current = self.root
for char in word:
if char not in current.children:
return False
current = current.children[char]
return current.is_end_of_word
def starts_with(self, prefix):
current = self.root
for char in prefix:
if char not in current.children:
return False
current = current.children[char]
return True
def delete(self, word):
def _delete_helper(node, word, index):
if index == len(word):
if not node.is_end_of_word:
return False
node.is_end_of_word = False
return len(node.children) == 0
char = word[index]
if char not in node.children:
return False
should_delete_child = _delete_helper(node.children[char], word, index + 1)
if should_delete_child:
del node.children[char]
return not node.is_end_of_word and len(node.children) == 0
return False
_delete_helper(self.root, word, 0)
def get_all_words_with_prefix(self, prefix):
current = self.root
for char in prefix:
if char not in current.children:
return []
current = current.children[char]
words = []
self._dfs_words(current, prefix, words)
return words
def _dfs_words(self, node, current_word, words):
if node.is_end_of_word:
words.append(current_word)
for char, child_node in node.children.items():
self._dfs_words(child_node, current_word + char, words)
# Applications: Autocomplete, spell checker, IP routing
9.2 Union-Find (Disjoint Set)
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.components = n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # Path compression
return self.parent[x]
def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x != root_y:
# Union by rank
if self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
elif self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
else:
self.parent[root_y] = root_x
self.rank[root_x] += 1
self.components -= 1
return True
return False
def connected(self, x, y):
return self.find(x) == self.find(y)
def count_components(self):
return self.components
# Application: Kruskal's Minimum Spanning Tree
def kruskal_mst(graph):
edges = graph.edges()
edges.sort(key=lambda x: x[2]) # Sort by weight
vertices = graph.vertices()
vertex_to_index = {v: i for i, v in enumerate(vertices)}
uf = UnionFind(len(vertices))
mst_edges = []
total_weight = 0
for u, v, weight in edges:
u_idx = vertex_to_index[u]
v_idx = vertex_to_index[v]
if uf.union(u_idx, v_idx):
mst_edges.append((u, v, weight))
total_weight += weight
return mst_edges, total_weight
10. Complexity Summary
| Data Structure | Search | Insert | Delete | Space |
|---|---|---|---|---|
| Array | O(n) | O(n) | O(n) | O(n) |
| Dynamic Array | O(n) | O(1) amortized | O(n) | O(n) |
| Linked List | O(n) | O(1) | O(1) | O(n) |
| Stack | O(n) | O(1) | O(1) | O(n) |
| Queue | O(n) | O(1) | O(1) | O(n) |
| BST (Average) | O(log n) | O(log n) | O(log n) | O(n) |
| AVL Tree | O(log n) | O(log n) | O(log n) | O(n) |
| Hash Table (Average) | O(1) | O(1) | O(1) | O(n) |
| Binary Heap | O(n) | O(log n) | O(log n) | O(n) |
| Trie | O(m) | O(m) | O(m) | O(ALPHABET_SIZE × N × M) |
Where n is the number of elements and m is the length of the string for Trie operations.
11. References
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms.
- Weiss, M. A. (2011). Data Structures and Algorithm Analysis in C++.
- Sedgewick, R., & Wayne, K. (2011). Algorithms.