# Data Structures > Implements and compares fundamental data structures (hash tables, balanced BSTs, tries, heaps, linked lists, graphs) with O(1) through O(n log n) complexity analysis for optimal algorithm selection. - Skill: `paulpas/data-structures` (Agent Skill) - Install (CLI): `npx skillmds@latest add paulpas/data-structures` - Raw SKILL.md: https://api.skillmd.com/api/skills/paulpas/data-structures/raw - Safety review: pending - Works with: Claude Code, Claude.ai, OpenAI Codex - Category: Coding & Dev Tools - License: MIT - Author: paulpas (https://skillmd.com/u/paulpas) - Updated: 2026-09-17 - Page: https://skillmd.com/skills/paulpas/data-structures --- # Data Structures Reference Senior engineer selecting optimal data structures based on access patterns, mutation frequency, and complexity constraints. This skill makes the model reason about space-time trade-offs, memory layout implications, and language-specific implementations before recommending or implementing any data structure. ## TL;DR Checklist - [ ] Match access pattern (random lookup → hash table, ordered traversal → BST, prefix search → trie) - [ ] Consider mutation frequency — linked lists beat arrays for frequent insertions in the middle - [ ] Verify space overhead of tree-based structures vs flat array or hash table layouts - [ ] Prefer language-native implementations (Python dict, list, heapq) before rolling custom solutions - [ ] Check complexity at boundaries: worst-case, average-case, and amortized - [ ] For ordered operations, prefer red-black trees (self-balancing) over AVL when writes are frequent --- ## When to Use - Choosing between data structures for a new module or function where performance characteristics matter - Diagnosing a bottleneck caused by suboptimal data structure selection (e.g., O(n) lookups in a loop) - Interview preparation or code review where you need to justify structural choices - Implementing autocomplete, caching, priority scheduling, or pathfinding systems - Comparing trade-offs between multiple candidate structures for the same problem --- ## When NOT to Use - Simple scripts with tiny datasets (< 100 items) where O(n²) is imperceptible — optimize only when profiling shows a real bottleneck - When domain constraints (persistence, serialization format, database schema) dictate the structure regardless of algorithmic preference - For in-memory caching that should use LRU/TTL semantics — use `functools.lru_cache`, `cachetools.TTLCache`, or a dedicated cache library instead of rolling your own hash table - When you need full-text search with fuzzy matching — use an inverted index with a library like Whoosh or Elasticsearch, not a raw trie --- ## Core Reference Guide ### 1. Hash Tables (Dicts / Maps) Hash tables provide O(1) average-case lookup, insertion, and deletion by mapping keys to indices via a hash function. They are the most frequently used data structure in practice. **Internal Mechanics (Python dict):** - Uses open addressing with a perturb-based probing scheme (not separate chaining). - The table grows when it reaches 2/3 capacity (load factor threshold of ~0.667). - Key order is preserved in insertion order since Python 3.7+ (guaranteed in 3.8+). - Each entry stores key, value, and hash; dummy entries handle tombstones during deletion. - Hash collisions are resolved via pseudo-random probing with a perturb shift that decreases by right-shifting on each probe. **Collision Resolution Strategies:** | Strategy | Mechanism | Pros | Cons | |---|---|---|---| | Separate Chaining | Each bucket holds a linked list of entries | Simple, no upper limit on load factor | Pointer overhead, poor cache locality | | Open Addressing — Linear Probing | Next free slot found by sequential scan | Excellent cache locality | Clustering degrades performance at high load | | Open Addressing — Quadratic Probing | Probe distance grows quadratically | Reduces primary clustering | Secondary clustering, may not find empty slot | | Open Addressing — Double Hashing | Second hash determines probe step | Best distribution of all open addressing methods | Requires two hash functions, careful prime table sizing | **Load Factor Guidelines:** - Target load factor: 0.5–0.75 for best average performance - Above 0.8: expect significant degradation due to clustering - Below 0.3: wasting space — consider shrinking the table ### 2. Balanced Binary Search Trees (AVL, Red-Black) Binary search trees maintain sorted order with O(log n) operations when balanced. Self-balancing variants guarantee worst-case bounds by restructuring on inserts/deletes. **AVL Trees:** - Balance factor of each node is the height difference between left and right subtrees; must be -1, 0, or +1. - More rigidly balanced than red-black trees → faster lookups but more rotations on insertion. - Ideal when reads heavily outnumber writes (search-heavy workloads). - Rotation types: single (LL, RR) and double (LR, RL). **Red-Black Trees:** - Properties ensure the path from root to any leaf is no more than twice as long as any other path → O(log n) guaranteed. - Fewer rotations on insertion/deletion than AVL since balance is "good enough" rather than "optimal." - Used by Java's `TreeMap`/`TreeSet`, C++ `std::map`/`std::set`, Python's `sortedcontainers`. - Node color (red/black) encodes structural invariants instead of explicit height. **Rotation Operations (Conceptual):** ``` Left Rotation on node X: X Y / \ / \ A Y → X Z / \ / \ B Z A B Right Rotation on node Y: Y X / \ / \ X C → A Y / \ / \ A B B C ``` ### 3. Tries (Prefix Trees) Tries store characters along paths from root to nodes, making prefix operations exceptionally fast. The depth of the trie equals the key length. **Key Properties:** - Lookup time is O(k) where k = key length, independent of n (number of keys). - No hash function needed — structure encodes the key directly. - Naturally supports prefix matching and autocomplete. - Space can be wasteful: many nodes with few children; use compressed tries (radix trees) or Patricia tries when memory is tight. **Character-Level Insertion:** ``` Insert "cat": root → 'c' → 'a' → 't' ★ (★ = end-of-word marker) Insert "car": root → 'c' → 'a' → 'r' ★ ↑ shares 'c'→'a' path with "cat" ``` **Auto-complete Pattern:** - Given prefix "app", traverse to node for 'p', then collect all end-of-word markers reachable via DFS from that node. - Time: O(k + m) where k = prefix length, m = number of completions returned. ### 4. Heaps / Priority Queues Heaps are complete binary trees maintaining the heap property (min-heap: parent ≤ children; max-heap: parent ≥ children). Implemented efficiently as arrays. **Array Representation:** For a node at index `i` (0-based): - Parent: `(i - 1) // 2` - Left child: `2 * i + 1` - Right child: `2 * i + 2` **Operations:** | Operation | Min-Heap | Description | |---|---|---| | Insert | O(log n) | Append at end, sift up | | Extract min | O(log n) | Replace root with last element, sift down | | Peek / get-min | O(1) | Root is always the minimum | | Build heap | O(n) | Heapify from bottom-up (not n individual inserts) | **Heapify — Bottom-Up Construction:** - Start from the last non-leaf node at index `(n // 2 - 1)` down to 0. - Sift each node down to restore heap property. - Total work: O(n), not O(n log n), because most nodes are near the bottom and move very few positions. **Heap Sort:** 1. Build max-heap from the array — O(n) 2. Repeatedly swap root (max) with last element, reduce heap size by 1, sift down — O(log n) per step 3. Total: O(n log n), in-place, not stable ### 5. Linked Lists (Singly, Doubly, Circular) Linked lists trade random access for O(1) insertion/deletion when the node reference is known. They are fundamental building blocks for stacks, queues, and LRU caches. **Memory Layout:** ``` Singly Linked List: [data|next] → [data|next] → [data|next] → None Doubly Linked List: None ← [prev|data|next] ↔ [prev|data|next] ↔ [prev|data|next] → None Circular (singly): [data|next] → [data|next] → back to first node ``` **When Linked Lists Excel:** - Implementing a stack or queue where you only access the head/tail - LRU cache implementation (doubly linked list + hash map for O(1) operations) - Merging sorted sequences without extra allocation - Undo/redo stacks where bidirectional traversal is needed **When Linked Lists Fail:** - Random access — O(n) per lookup vs O(1) in arrays - Cache unfriendliness — nodes are scattered in memory, causing cache misses - Memory overhead — 2 pointers per node (4–8 bytes each on 64-bit systems) ### 6. Graph Representations Graphs model relationships between entities. The choice of representation affects traversal speed, memory usage, and mutation cost. **Adjacency Matrix:** ``` A B C D +---+---+---+---+ A | 0 | 1 | 0 | 1 | B | 1 | 0 | 1 | 0 | C | 0 | 1 | 0 | 1 | D | 1 | 0 | 1 | 0 | +---+---+---+---+ ``` | Property | Adjacency Matrix | Adjacency List | |---|---|---| | Space | O(V²) | O(V + E) | | Edge lookup | O(1) | O(degree of source node) | | Add edge | O(1) | O(1) (append to list) | | Iterate neighbors | O(V) — scans entire row | O(degree) — only traverses existing edges | | Dense graph suitability | ✅ Excellent | Good but wasteful | | Sparse graph suitability | ❌ Wasteful | ✅ Optimal | **Rule of thumb:** Use adjacency list for sparse graphs (E << V²). Use adjacency matrix when the graph is dense or you need O(1) edge existence checks in hot loops. --- ## Implementation Patterns ### Pattern 1: Hash Table with Open Addressing (Probing) ```python class OpenAddressingHashTable: """Hash table using open addressing with linear probing and tombstone deletion. This is a teaching implementation illustrating how hash tables resolve collisions. For production use, prefer Python's built-in dict. Attributes: capacity: Total number of buckets in the table (must be prime for best distribution) size: Number of active (non-tombstone) entries load_threshold: Load factor above which the table resizes """ EMPTY = None # Unused slot marker TOMBSTONE = object() # Deleted slot marker def __init__(self, capacity: int = 7, load_threshold: float = 0.65) -> None: """Initialize hash table with given capacity. Args: capacity: Initial number of buckets (will be adjusted to prime if not prime) load_threshold: Load factor triggering resize; default 0.65 matches CPython dict behavior """ self.capacity = self._next_prime(max(capacity, 7)) self.load_threshold = load_threshold self.keys = [self.EMPTY] * self.capacity self.values = [None] * self.capacity self.size = 0 @staticmethod def _next_prime(n: int) -> int: """Find the smallest prime number >= n for table sizing.""" while True: if all(n % i != 0 for i in range(2, int(n**0.5) + 1)): return n n += 1 def _hash(self, key: object) -> int: """Compute initial probe index from key hash.""" return hash(key) % self.capacity def insert(self, key: object, value: object) -> None: """Insert or update a key-value pair. Resizes table if load factor exceeds threshold. Args: key: Hashable key (must be immutable for correctness) value: Any value to associate with the key Raises: TypeError: If key is not hashable """ if self.size / self.capacity >= self.load_threshold: self._resize() index = self._hash(key) first_tombstone = -1 while True: if self.keys[index] == self.EMPTY: # Found a genuinely empty slot — key cannot exist in table pos = index if first_tombstone == -1 else first_tombstone self.keys[pos] = key self.values[pos] = value self.size += 1 return elif self.keys[index] == self.TOMBSTONE: # Mark first tombstone position for potential reuse if first_tombstone == -1: first_tombstone = index elif self.keys[index] == key: # Key exists — update value in place self.values[index] = value return # Linear probe to next slot index = (index + 1) % self.capacity def search(self, key: object) -> object | None: """Look up a key. Returns value or None if not found. Args: key: Hashable key to look up Returns: Associated value, or None if key does not exist """ index = self._hash(key) while True: if self.keys[index] == self.EMPTY: # Reached genuinely empty slot — key not in table return None elif self.keys[index] == key: return self.values[index] index = (index + 1) % self.capacity def delete(self, key: object) -> bool: """Remove a key-value pair. Marks slot as tombstone to preserve probe chains. Args: key: Hashable key to remove Returns: True if key was found and removed, False if not found """ index = self._hash(key) while True: if self.keys[index] == self.EMPTY: return False # Key not in table elif self.keys[index] == key: self.keys[index] = self.TOMBSTONE self.values[index] = None self.size -= 1 return True index = (index + 1) % self.capacity def _resize(self) -> None: """Double the table capacity and rehash all active entries.""" old_keys = list(self.keys) old_values = list(self.values) new_capacity = self._next_prime(self.capacity * 2) self.capacity = new_capacity self.keys = [self.EMPTY] * new_capacity self.values = [None] * new_capacity self.size = 0 for k, v in zip(old_keys, old_values): if k != self.EMPTY and k != self.TOMBSTONE: self.insert(k, v) @property def load_factor(self) -> float: """Current load factor of the hash table.""" return self.size / self.capacity ``` ### Pattern 2: Red-Black Tree (Insert with Self-Balancing) ```python from typing import Generic, TypeVar, Optional K = TypeVar('K', bound='Comparable') V = TypeVar('V') class Comparable: """Base class defining comparison protocol for generic tree keys.""" def __lt__(self, other: object) -> bool: ... def __eq__(self, other: object) -> bool: ... class RBNode(Generic[K, V]): """Node in a red-black tree. Attributes: key: The comparison key (must implement __lt__, __eq__) value: Associated payload color: True = RED, False = BLACK left: Left child subtree right: Right child subtree parent: Parent node reference (None for root) """ __slots__ = ('key', 'value', 'color', 'left', 'right', 'parent') def __init__(self, key: K, value: V, color: bool = True) -> None: # True = RED self.key = key self.value = value self.color = color self.left: Optional['RBNode[K, V]'] = None self.right: Optional['RBNode[K, V]'] = None self.parent: Optional['RBNode[K, V]'] = None class RedBlackTree(Generic[K, V]): """Self-balancing binary search tree with O(log n) worst-case operations. Maintains the red-black invariants through color flips and rotations after insertion. Used as the basis for ordered maps in many standard libraries. Invariants: 1. Every node is either RED or BLACK 2. Root is always BLACK 3. RED nodes cannot have RED children (no two consecutive reds) 4. Every path from root to leaf has the same number of black nodes (black-height) """ RED = True BLACK = False def __init__(self) -> None: self.root: Optional[RBNode[K, V]] = None self.size: int = 0 def insert(self, key: K, value: V) -> None: """Insert a key-value pair and rebalance to restore red-black invariants. Args: key: Comparison key value: Associated payload Time Complexity: O(log n) amortized """ node = RBNode(key, value, color=self.RED) self.size += 1 if self.root is None: self.root = node node.color = self.BLACK return current = self.root while True: if key < current.key: if current.left is None: current.left = node node.parent = current break current = current.left elif key > current.key: if current.right is None: current.right = node node.parent = current break current = current.right else: # Key already exists — update value, no rebalancing needed current.value = value self.size -= 1 return self._fix_insert(node) def _fix_insert(self, node: RBNode[K, V]) -> None: """Restore red-black invariants after insertion by recoloring and rotating.""" while node != self.root and node.parent.color == self.RED: parent = node.parent grandparent = parent.parent if parent is grandparent.left: uncle = grandparent.right if uncle and uncle.color == self.RED: # Case 1: Recolor — both parent and uncle are red parent.color = self.BLACK uncle.color = self.BLACK grandparent.color = self.RED node = grandparent else: if node is parent.right: # Case 2: Left rotation on parent (reorient to case 3) self._rotate_left(parent) node = parent parent = node.parent grandparent = parent.parent # Case 3: Right rotate on grandparent + recolor parent.color = self.BLACK grandparent.color = self.RED self._rotate_right(grandparent) else: uncle = grandparent.left if uncle and uncle.color == self.RED: parent.color = self.BLACK uncle.color = self.BLACK grandparent.color = self.RED node = grandparent else: if node is parent.left: self._rotate_right(parent) node = parent parent = node.parent grandparent = parent.parent parent.color = self.BLACK grandparent.color = self.RED self._rotate_left(grandparent) self.root.color = self.BLACK def _rotate_left(self, pivot: RBNode[K, V]) -> None: """Perform left rotation around pivot. Right child becomes new root of subtree.""" right = pivot.right if right is None: return pivot.right = right.left if right.left: right.left.parent = pivot right.parent = pivot.parent if pivot.parent is None: self.root = right elif pivot is pivot.parent.left: pivot.parent.left = right else: pivot.parent.right = right right.left = pivot pivot.parent = right def _rotate_right(self, pivot: RBNode[K, V]) -> None: """Perform right rotation around pivot. Left child becomes new root of subtree.""" left = pivot.left if left is None: return pivot.left = left.right if left.right: left.right.parent = pivot left.parent = pivot.parent if pivot.parent is None: self.root = left elif pivot is pivot.parent.right: pivot.parent.right = left else: pivot.parent.left = left left.right = pivot pivot.parent = left def search(self, key: K) -> Optional[V]: """Find value associated with key using BST property. Args: key: Key to look up Returns: Value if found, None otherwise """ current = self.root while current is not None: if key == current.key: return current.value elif key < current.key: current = current.left else: current = current.right return None def min_key(self) -> Optional[K]: """Return the smallest key in the tree.""" if self.root is None: return None current = self.root while current.left: current = current.left return current.key def max_key(self) -> Optional[K]: """Return the largest key in the tree.""" if self.root is None: return None current = self.root while current.right: current = current.right return current.key ``` ### Pattern 3: Trie with Auto-Complete ```python class TrieNode: """Single node in a trie (prefix tree). Attributes: children: Mapping from character to child TrieNode end_of_word: True if this node marks the end of a valid word value: Associated payload for dictionary-style lookups """ __slots__ = ('children', 'end_of_word', 'value') def __init__(self) -> None: self.children: dict[str, 'TrieNode'] = {} self.end_of_word: bool = False self.value: object | None = None class Trie: """Prefix tree optimized for string prefix operations and auto-complete. Insertion, search, and prefix-match are all O(k) where k = key length, independent of the total number of stored keys. Space is O(k * n) in the worst case where every character of every key requires a unique node. """ def __init__(self) -> None: self.root = TrieNode() self.size: int = 0 def insert(self, word: str, value: object | None = None) -> bool: """Insert a word into the trie. Args: word: String key to store (any iterable of hashable characters) value: Optional payload associated with the complete word Returns: True if this was a new word, False if it already existed """ node = self.root for char in word: if char not in node.children: node.children[char] = TrieNode() node = node.children[char] was_new = not node.end_of_word node.end_of_word = True node.value = value if was_new: self.size += 1 return was_new def search(self, word: str) -> object | None: """Check if an exact word exists in the trie. Args: word: String to look up Returns: Associated value if found, None otherwise """ node = self._traverse(word) if node is None or not node.end_of_word: return None return node.value def starts_with(self, prefix: str) -> bool: """Check if any word in the trie has the given prefix. Args: prefix: String prefix to check Returns: True if at least one stored word starts with prefix """ return self._traverse(prefix) is not None def autocomplete(self, prefix: str, max_results: int = 10) -> list[tuple[str, object | None]]: """Find all complete words matching a prefix. Uses DFS from the prefix node, collecting every end-of-word marker encountered along with its accumulated path. Results are limited by max_results to prevent unbounded output on broad prefixes. Args: prefix: String prefix to search for max_results: Maximum number of completions to return Returns: List of (word, value) tuples sorted lexicographically """ node = self._traverse(prefix) if node is None: return [] results: list[tuple[str, object | None]] = [] self._collect_words(node, prefix, max_results, results) results.sort(key=lambda x: x[0]) return results[:max_results] def delete(self, word: str) -> bool: """Delete a word from the trie, pruning empty branches. Args: word: String to remove Returns: True if the word existed and was removed, False otherwise """ deleted = self._delete_recursive(self.root, word, 0) if deleted: self.size -= 1 return deleted def _traverse(self, key: str) -> TrieNode | None: """Walk down the trie following key characters. Returns None if path breaks.""" node = self.root for char in key: if char not in node.children: return None node = node.children[char] return node def _collect_words(self, node: TrieNode, prefix: str, limit: int, results: list) -> int: """DFS helper that collects all complete words under a node.""" count = 0 if node.end_of_word and node.value is not None: results.append((prefix, node.value)) count += 1 if count >= limit: return count for char in sorted(node.children): collected = self._collect_words( node.children[char], prefix + char, limit - count, results ) count += collected if count >= limit: break return count def _delete_recursive(self, node: TrieNode, word: str, depth: int) -> bool: """Recursively delete a word. Returns True if the current node can be pruned.""" if depth == len(word): if not node.end_of_word: return False node.end_of_word = False node.value = None return len(node.children) == 0 char = word[depth] if char not in node.children: return False should_delete_child = self._delete_recursive( node.children[char], word, depth + 1 ) if should_delete_child: del node.children[char] return (not node.end_of_word) and len(node.children) == 0 return False ``` ### Pattern 4: Min-Heap / Priority Queue via Array Heapify ```python import heapq from typing import Generic, TypeVar, list as typelist T = TypeVar('T') class MinHeap(Generic[T]): """Array-based min-heap with O(1) peek, O(log n) insert/extract-min. The heap is stored in a flat list where the array representation satisfies: parent(i) = (i - 1) // 2 left_child(i) = 2 * i + 1 right_child(i) = 2 * i + 2 Time Complexity: insert: O(log n) amortized extract_min: O(log n) peek: O(1) build_heap: O(n) using Floyd's bottom-up heapify size check: O(1) """ def __init__(self, items: typelist[T] | None = None) -> None: """Initialize heap from optional list. Args: items: Initial collection of comparable items. If provided, uses O(n) Floyd's heapify instead of n individual inserts. """ self._heap: list[T] = [] if items is not None: self._heap = list(items) self._heapify() def _parent(self, i: int) -> int: """Return index of parent node.""" return (i - 1) // 2 def _left_child(self, i: int) -> int: """Return index of left child node.""" return 2 * i + 1 def _right_child(self, i: int) -> int: """Return index of right child node.""" return 2 * i + 2 def _sift_up(self, i: int) -> None: """Restore heap property by moving element at index i upward. Swaps with parent while the element is smaller than its parent. Runs in O(log n). """ while i > 0: parent_idx = self._parent(i) if self._heap[i] < self._heap[parent_idx]: self._heap[i], self._heap[parent_idx] = self._heap[parent_idx], self._heap[i] i = parent_idx else: break def _sift_down(self, i: int) -> None: """Restore heap property by moving element at index i downward. Swaps with the smaller child while the element is larger than both children. Runs in O(log n). """ n = len(self._heap) while True: smallest = i left = self._left_child(i) right = self._right_child(i) 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: self._heap[i], self._heap[smallest] = self._heap[smallest], self._heap[i] i = smallest else: break def _heapify(self) -> None: """Build heap from arbitrary list in O(n) using bottom-up sifting. Floyd's algorithm: start from the last non-leaf node and sift each down. Most nodes are near the bottom and require at most one or two swaps, so total work is linear, not O(n log n). """ n = len(self._heap) for i in range(n // 2 - 1, -1, -1): self._sift_down(i) def insert(self, item: T) -> None: """Add an item to the heap. Appends at end and sifts up to maintain heap property. Args: item: Comparable item to add """ self._heap.append(item) self._sift_up(len(self._heap) - 1) def extract_min(self) -> T: """Remove and return the smallest element. Replaces root with last element, removes last, then sifts down from root. Returns: The minimum element Raises: IndexError: If the heap is empty """ if not self._heap: raise IndexError("extract_min from empty heap") if len(self._heap) == 1: return self._heap.pop() root = self._heap[0] self._heap[0] = self._heap.pop() self._sift_down(0) return root def peek(self) -> T: """Return the smallest element without removing it. Returns: The minimum element Raises: IndexError: If the heap is empty """ if not self._heap: raise IndexError("peek on empty heap") return self._heap[0] def __len__(self) -> int: return len(self._heap) def __bool__(self) -> bool: return bool(self._heap) def heap_sort(items: typelist[int]) -> typelist[int]: """Sort a list using heap sort — O(n log n) in-place, not stable. Builds a max-heap then repeatedly extracts the maximum to fill the result. This is an in-place algorithm with guaranteed O(n log n) worst case. Args: items: List of comparable elements to sort Returns: New sorted list in ascending order (original list is modified in place) """ heap = MinHeap(items) result: typelist[int] = [] while heap: result.append(heap.extract_min()) return result ``` ### Pattern 5: Doubly Linked List for LRU Cache ```python from collections.abc import MutableMapping class _DLLNode: """Doubly linked list node for O(1) insertion and removal.""" __slots__ = ('key', 'value', 'prev', 'next') def __init__(self, key: object, value: object) -> None: self.key = key self.value = value self.prev: '_DLLNode | None' = None self.next: '_DLLNode | None' = None class LRUCache(MutableMapping): """Least Recently Used cache using a hash map + doubly linked list. Achieves O(1) for get, put, and delete by maintaining two data structures: - A dict mapping keys to DLL nodes (for O(1) lookup) - A doubly linked list ordering nodes by recency (newest at tail) When the cache exceeds capacity, the oldest node (head sentinel's next) is evicted. Accessing or inserting a key moves it to the tail (most recently used). """ def __init__(self, capacity: int) -> None: """Initialize LRU cache with fixed capacity. Args: capacity: Maximum number of items; must be positive Raises: ValueError: If capacity is not a positive integer """ if capacity <= 0: raise ValueError(f"Capacity must be positive, got {capacity}") self.capacity = capacity self._cache: dict[object, _DLLNode] = {} # Sentinel nodes eliminate edge-case checks for empty/full lists self._head = _DLLNode(None, None) # Dummy head (oldest end) self._tail = _DLLNode(None, None) # Dummy tail (newest end) self._head.next = self._tail self._tail.prev = self._head def get(self, key: object) -> object | None: """Retrieve a value and mark the key as recently used. Args: key: Cache key Returns: Cached value, or None if key is not present """ if key not in self._cache: return None node = self._cache[key] self._move_to_tail(node) # Mark as most recently used return node.value def put(self, key: object, value: object) -> None: """Insert or update a key-value pair. If the key exists, updates its value and moves it to most-recently-used. If inserting would exceed capacity, evicts the least recently used item. Args: key: Cache key value: Value to cache """ if key in self._cache: node = self._cache[key] node.value = value self._move_to_tail(node) return if len(self._cache) >= self.capacity: self._evict_oldest() node = _DLLNode(key, value) self._cache[key] = node self._add_to_tail(node) def __setitem__(self, key: object, value: object) -> None: self.put(key, value) def __getitem__(self, key: object) -> object: value = self.get(key) if value is None: raise KeyError(key) return value def __delitem__(self, key: object) -> None: if key not in self._cache: raise KeyError(key) node = self._cache.pop(key) self._unlink(node) def __contains__(self, key: object) -> bool: return key in self._cache def __len__(self) -> int: return len(self._cache) def __iter__(self): return iter(self._cache) def _add_to_tail(self, node: _DLLNode) -> None: """Insert node right before the tail sentinel (most recent position).""" prev = self._tail.prev prev.next = node node.prev = prev node.next = self._tail self._tail.prev = node def _move_to_tail(self, node: _DLLNode) -> None: """Remove node from its current position and reinsert at tail.""" self._unlink(node) self._add_to_tail(node) def _unlink(self, node: _DLLNode) -> None: """Remove a node from the doubly linked list without freeing it.""" prev_node = node.prev next_node = node.next if prev_node is not None: prev_node.next = next_node if next_node is not None: next_node.prev = prev_node def _evict_oldest(self) -> None: """Remove the least recently used entry (node right after head sentinel).""" oldest = self._head.next if oldest is self._tail: return # Cache is empty (shouldn't happen if capacity check passed) del self._cache[oldest.key] self._unlink(oldest) ``` --- ### BAD vs GOOD Example Pairs #### Pair 1: Linear Search in Unsorted List vs. Hash Table Lookup ```python # ❌ BAD: O(n) lookup inside a loop — quadratic overall when checking many items def find_common_bad(items_a: list[int], items_b: list[int]) -> list[int]: """Find all elements present in both lists. Uses nested linear search.""" result = [] for item_a in items_a: for item_b in items_b: # O(n) per iteration → O(n*m) total if item_a == item_b: result.append(item_a) break return result # ✅ GOOD: O(n + m) using a hash set for O(1) lookups def find_common_good(items_a: list[int], items_b: list[int]) -> set[int]: """Find all elements present in both lists. Uses hash set for O(1) lookup.""" set_b = set(items_b) # O(m) — build hash table once return {item for item in items_a if item in set_b} # O(n) — one pass with O(1) checks ``` #### Pair 2: Array Insertion in Middle vs. Linked List (when appropriate) ```python # ❌ BAD: list.insert(0, x) is O(n) because it shifts all elements def process_stream_bad(items: list[int]) -> list[int]: """Process a stream by always prepending results — catastrophic for large streams.""" result: list[int] = [] for item in items: result.insert(0, item * 2) # O(n) per insert → O(n²) total return result # ✅ GOOD: Use collections.deque for O(1) end-appends, then reverse at the end from collections import deque def process_stream_good(items: list[int]) -> list[int]: """Process a stream with O(1) appends, reverse once at O(n).""" result = deque() for item in items: result.appendleft(item * 2) # O(1) per insert → O(n) total return list(result) ``` --- ## Complexity Comparison Table | Operation | Hash Table (dict) | AVL Tree | Red-Black Tree | Trie | Min-Heap (array) | Singly Linked List | Doubly Linked List | Adjacency List | Adjacency Matrix | |---|---|---|---|---|---|---|---|---|---| | **Lookup** | O(1) avg / O(n) worst | O(log n) | O(log n) | O(k) | — | O(n) | O(n) | O(degree) | O(1) | | **Insert** | O(1) amortized | O(log n) | O(log n) | O(k) | O(log n) | O(1)* | O(1)* | O(1) | O(1) | | **Delete** | O(1) avg / O(n) worst | O(log n) | O(log n) | O(k) | O(log n) | O(1)* | O(1)* | O(degree) | O(1) | | **Find Min/Max** | — (unordered) | O(log n) | O(log n) | — | O(1) | O(n) | O(n) | O(V log V) | O(V²) | | **Iterate Sorted** | O(n) | O(n) | O(n) | O(k + m) | — | O(n) | O(n) | O(V log V) | O(V²) | | **Space** | O(n) | O(n) | O(n) | O(k * n) worst | O(n) | O(n) | O(n) | O(V + E) | O(V²) | *O(1) requires a reference to the node; finding the node by key/value is O(n). `k` = key length, `n` = number of elements, `V` = vertices, `E` = edges, `m` = completions returned. **Quick Selection Guide:** | Need | Best Choice | Why | |---|---|---| | Fastest lookups by arbitrary key | Hash table (dict) | O(1) average, language-native | | Ordered traversal / range queries | Red-black tree | Balanced, O(log n) for all ops | | Prefix matching / autocomplete | Trie | O(k) independent of total entries | | Top-k elements / scheduling | Min/max-heap | O(1) peek, O(log n) update | | Frequent middle insertions/deletions | Doubly linked list | O(1) with node reference | | Shortest path (unweighted) | Adjacency list + BFS | Only traverses existing edges | | Dense graph / fast edge checks | Adjacency matrix | O(1) edge lookup, compact for full graphs | --- ## Constraints ### MUST DO - Always consider the access pattern before selecting a structure — …(truncated)