What’s one thing you learned? What’s still confusing?
Stacks, Queues & Deque
LIFO and FIFO using lists and deque. MinStack, circular queue, monotonic stack.
Trees & BST, Part 1: Binary Trees & Traversals
Tree terminology, the TreeNode class, BST insert/search, and all four traversals (BFS, inorder, preorder, postorder) recursively and iteratively.
Trees & BST, Part 2: Balanced Trees & Trie
BST deletion (all three cases), validation with min/max bounds, self-balancing AVL/Red-Black trees, Tries for autocomplete, and expression-tree evaluation.
Interactive Labs for This Track
Loop Visualizer
You're a factory robot repeating the same task on an assembly line — watch how loops automate repetitive work
List Slicing
You have a playlist of 50 songs — grab just tracks 10 through 20 with a single slice expression
Sorting Algorithms
You're organizing a library of 10,000 books — which sorting method is fastest?
Ask questions, share insights
prev pointers unlock O(1) deletion when you hold a node reference, merge-sorted-lists is the merge step of merge sort, and LRU cache is the canonical interview problem that Redis, Memcached, and functools.lru_cache all solve internally.prev pointer to each node, enabling backward traversal and — far more importantly — O(1) deletion when you hold a direct node reference.from __future__ import annotations
from typing import Any, Iterator, Optional
class DoublyNode:
"""Node for a doubly linked list — knows both neighbors."""
def __init__(self, data: Any) -> None:
self.data = data
self.prev: Optional[DoublyNode] = None
self.next: Optional[DoublyNode] = None
def __repr__(self) -> str:
return f"DoublyNode({self.data!r})"
class DoublyLinkedList:
"""
Doubly linked list.
Key advantage over singly: O(1) deletion given the node itself,
and O(1) tail deletion without needing to re-find the new tail.
Python's collections.deque is a doubly linked list of fixed-size blocks.
"""
def __init__(self) -> None:
self.head: Optional[DoublyNode] = None
self.tail: Optional[DoublyNode] = None
self._size: int = 0
def append(self, data: Any) -> DoublyNode:
"""Add to end. Returns the new node (caller can cache for O(1) removal)."""
node = DoublyNode(data)
if self.tail is None:
self.head = self.tail = node
else:
node.prev = self.tail
self.tail.next = node
self.tail = node
self._size += 1
return node
def prepend(self, data: Any) -> DoublyNode:
"""Add to front. O(1)."""
node = DoublyNode(data)
if self.head is None:
self.head = self.tail = node
else:
node.next = self.head
self.head.prev = node
self.head = node
self._size += 1
return node
def remove_node(self, node: DoublyNode) -> None:
"""
Remove a specific node in O(1).
This is THE killer feature of doubly linked lists — you must hold
a reference to the node directly (not search for it). Used by LRU cache.
"""
if node.prev is not None:
node.prev.next = node.next
else:
self.head = node.next # node was the head
if node.next is not None:
node.next.prev = node.prev
else:
self.tail = node.prev # node was the tail
node.prev = node.next = None # help garbage collection
self._size -= 1
def pop_front(self) -> Any:
"""Remove and return front value. O(1)."""
if self.head is None:
raise IndexError("pop from empty list")
value = self.head.data
self.remove_node(self.head)
return value
def pop_back(self) -> Any:
"""Remove and return back value. O(1) — impossible with singly LL without O(n) traversal."""
if self.tail is None:
raise IndexError("pop from empty list")
value = self.tail.data
self.remove_node(self.tail)
return value
def __len__(self) -> int:
return self._size
def __str__(self) -> str:
"""Forward traversal: '1 <-> 2 <-> 3'"""
parts = []
current = self.head
while current is not None:
parts.append(str(current.data))
current = current.next
return " <-> ".join(parts) if parts else "empty"
def backward_str(self) -> str:
"""Backward traversal using prev pointers."""
parts = []
current = self.tail
while current is not None:
parts.append(str(current.data))
current = current.prev
return " <-> ".join(parts) if parts else "empty"
def __iter__(self) -> Iterator[Any]:
current = self.head
while current is not None:
yield current.data
current = current.nextdll = DoublyLinkedList()
n1 = dll.append(10)
n2 = dll.append(20)
n3 = dll.append(30)
print(dll) # 10 <-> 20 <-> 30
print(dll.backward_str()) # 30 <-> 20 <-> 10
# O(1) removal of the middle node — we hold a direct reference
dll.remove_node(n2)
print(dll) # 10 <-> 30
# O(1) tail pop
val = dll.pop_back()
print(val) # 30
print(dll) # 10if self.head is None checks in insertion and deletion. Doubly linked lists used in production (including Python's collections.deque) use two sentinels so every insertion and deletion operates between two existing nodes — no boundary branching at all.from typing import Optional
class Node:
def __init__(self, data):
self.data = data
self.next: Optional[Node] = None
def merge_sorted_iterative(l1: Optional[Node], l2: Optional[Node]) -> Optional[Node]:
"""
Merge two sorted linked lists into one sorted list.
O(n + m) time, O(1) space (just pointer manipulation).
"""
# Dummy head simplifies edge cases — we return dummy.next at the end
dummy = Node(0)
current = dummy
while l1 is not None and l2 is not None:
if l1.data <= l2.data:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
current = current.next
# Attach whichever list still has nodes remaining
current.next = l1 if l1 is not None else l2
return dummy.next
def merge_sorted_recursive(l1: Optional[Node], l2: Optional[Node]) -> Optional[Node]:
"""Recursive version — cleaner but O(n + m) stack space."""
if l1 is None:
return l2
if l2 is None:
return l1
if l1.data <= l2.data:
l1.next = merge_sorted_recursive(l1.next, l2)
return l1
else:
l2.next = merge_sorted_recursive(l1, l2.next)
return l2dummy.next at the end. This pattern — "use a dummy node to remove the first-element special case" — comes up constantly in linked list problems.Part 1 covered the three-pointer iterative reversal. The recursive version is elegant but uses O(n) call stack space.
def reverse_recursive(head: Optional[Node]) -> Optional[Node]:
"""
Recursive reversal. Elegant but uses O(n) call stack space.
Base case: empty list or single node — already reversed.
"""
if head is None or head.next is None:
return head
# Recursively reverse everything after head
new_head = reverse_recursive(head.next)
# head.next still points to the old second node.
# Make that node point back to head, then cut head's forward link.
head.next.next = head
head.next = None
return new_headRecursionError on long lists (Python's default recursion limit is 1000). Use the recursive version only when the surrounding code is already recursive (e.g., problems on tree-like structures where the list is short).functools.lru_cache, browser caches) uses this pattern. The implementation combines two data structures:dict) — maps cache key → node in the linked list. O(1) lookup.get and O(1) put, with automatic eviction.class DoublyNode:
"""LRU cache node — stores key AND value (key needed for dict cleanup on eviction)."""
def __init__(self, key, value):
self.key = key
self.value = value
self.prev: Optional[DoublyNode] = None
self.next: Optional[DoublyNode] = None
class LRUCache:
"""
Least-Recently-Used cache with O(1) get and put.
Uses a doubly linked list (most-recent at head, least-recent at tail)
plus a dict (key -> node) for O(1) lookups. The list provides O(1)
move-to-front on access and O(1) eviction of the tail.
Two sentinel nodes (head and tail dummies) eliminate all boundary checks.
"""
def __init__(self, capacity: int) -> None:
if capacity <= 0:
raise ValueError("capacity must be positive")
self.capacity = capacity
self.cache: dict = {} # key -> DoublyNode
# Sentinels — never hold real data, always present
self._head = DoublyNode(None, None) # MRU side
self._tail = DoublyNode(None, None) # LRU side
self._head.next = self._tail
self._tail.prev = self._head
def _remove(self, node: DoublyNode) -> None:
"""Unlink a node from the list. O(1) — both neighbors exist (sentinels)."""
node.prev.next = node.next
node.next.prev = node.prev
def _add_to_front(self, node: DoublyNode) -> None:
"""Insert node right after the head sentinel (the MRU slot). O(1)."""
node.prev = self._head
node.next = self._head.next
self._head.next.prev = node
self._head.next = node
def get(self, key) -> int:
"""O(1). Returns -1 if key missing. Touching a key marks it most recent."""
if key not in self.cache:
return -1
node = self.cache[key]
# Move to front: unlink, then re-insert at head
self._remove(node)
self._add_to_front(node)
return node.value
def put(self, key, value) -> None:
"""O(1). Updates existing or inserts new; evicts LRU if over capacity."""
if key in self.cache:
# Update value and move to front
node = self.cache[key]
node.value = value
self._remove(node)
self._add_to_front(node)
return
if len(self.cache) >= self.capacity:
# Evict the LRU (just before the tail sentinel)
lru = self._tail.prev
self._remove(lru)
del self.cache[lru.key]
node = DoublyNode(key, value)
self.cache[key] = node
self._add_to_front(node)
# Demo
cache = LRUCache(capacity=3)
cache.put("a", 1)
cache.put("b", 2)
cache.put("c", 3)
print(cache.get("a")) # 1 — touches 'a', moves it to front. Order: a, c, b
cache.put("d", 4) # capacity full; evict LRU which is 'b'
print(cache.get("b")) # -1 (evicted)
print(cache.get("d")) # 4key AND value. When we evict the LRU node, we need to remove its entry from the cache dict too. The dict maps key → node, but eviction starts from the node side (the tail). Without node.key, we'd have to scan the entire dict to find which key owns this node — O(n) eviction instead of O(1). Storing the key on the node closes the loop.tail.next = head; "next song" always worksprev, forward button follows nextTests · assert cache.get(3) == 300; assert cache.get(2) == -1
if head is None branchingYou have a doubly linked list and you hold a direct reference to node C (in the middle). What is the time complexity of removing C from the list?