algo-viz course demos
Interactive demos for the data structures and algorithms course, in chapter order. Each one opens on its own page and can also be embedded in a chapter or linked from a slide.
-
Dynamic Array
An array that grows its own capacity as items are added, and shifts elements to close the gap when one is removed.
-
Linear Search
Scans a list left to right for a value, stopping at the first match or the end.
-
Selection Sort
Sorts a list by repeatedly finding the smallest remaining element and swapping it into place.
-
Bag (Urn) Data Structure
An unordered collection: add items, then remove one at random in O(1) by swapping in the last item.
-
Binary Search
Searches a sorted array by repeatedly halving the range until the target turns up or the range is empty.
-
Binary Search (Recursive)
The same binary search, done recursively, with a live call stack showing each recursive call.
-
Sorted Array
An array that stays sorted at all times, using binary search to find where to insert or remove a value.
-
Leaderboard
A fixed-size top-k list, highest score first: insert a score and the lowest one drops off once the list is full.
-
Singly Linked List
A chain of nodes, each pointing to the next: add, remove, and search without a backing array.
-
Doubly Linked List
A two-way chain of nodes with permanent head and tail sentinels, so insert and remove never need a special case for the first or last item.
-
SparseList
A third List implementation that only stores positions that differ from a default value, kept as a sorted chain of (index, value) nodes.
-
MaxArrayList
A MaxList backed by an elements array and a parallel maxes array: getMax(index) is one lookup, and set and remove call recomputeMaxesFrom to rebuild maxes after the change.
-
MaxLinkedList
A MaxList backed by a doubly linked list whose nodes keep a maxPointer: add and setMaxPointer are O(1), but getMax(index) still has to traverse to the node, and set and remove repair every later maxPointer.
-
ArrayStack
A stack stored in an array with its top at arr[size - 1]: push writes into the next free slot and grows the array when it is full, and pop clears the last used slot.
-
LinkedStack
A stack stored in a singly linked list with its top at head: push links a new node in front and pop moves head one node forward.
-
Valid Parentheses
isValid(s) reads a string of brackets once, pushing each opening bracket onto a stack and checking each closing bracket against the top of the stack.
-
Evaluate Reverse Polish Notation
evalRPN(tokens) evaluates a Reverse Polish Notation expression in one pass: numbers are pushed onto a stack, and each operator pops two numbers and pushes the result.
-
LinkedMinStack
A LinkedStack whose nodes each keep a minPointer to the smallest value at or below them, so getMin() follows one pointer and every operation is O(1).
-
ArrayMonotonicStack
An ArrayStack whose push first evicts every smaller value from the top, so the values stay in decreasing order from bottom to top and push is amortized O(1).
-
LinkedQueue
A queue stored in a singly linked list with head as the front and tail as the back: enqueue links a new node after the tail, and dequeue moves head one node forward.
-
ArrayQueue
A queue stored in a circular array with a front index and a size: enqueue writes into (front + size) % arr.length and grows the array in queue order when it is full, and dequeue advances front around the circle.
-
Round-Robin Scheduling
Round-robin scheduling simulated with a queue of task indices: each turn runs the front task for at most quantum units, records its completion time when remaining[taskIndex] reaches 0, and otherwise sends it to the back of the line.
-
Josephus Problem
The Josephus problem solved with a circularly linked list: current stands one node before the count, moves k - 1 times, and unlinks current.next, until one person is left.
-
Moving Average
A MovingAverage class that keeps the last k readings in a queue and a running sum in a field, so add enqueues the new reading, dequeues the oldest one when the window is too big, and returns sum / count in O(1).
-
Queue with Two Stacks
A StackQueue that implements Queue with an in stack and an out stack: enqueue pushes onto in, and dequeue and front pour in into out only when out is empty, which makes them amortized O(1).
-
LinkedDeque
A deque stored in a doubly linked list with a sentinel node at each end: every add splices a new node between two neighbors, and every remove unlinks one.
-
ArrayDeque
A deque stored in a circular array: addFirst moves front one slot backward, addLast writes after the last item, and grow copies the items in deque order.
-
MaxQueue
A MaxQueue built from two deques: items holds the queue, and candidates holds the items that could still be the maximum, largest first, so getMax reads the first candidate and every operation is amortized O(1).
-
Sliding Window Maximum
slidingMaximum(values, k) keeps a deque of candidate indices: expired indices leave from the first end, indices whose values are no larger than the new value leave from the last end, and the first index is each window's maximum, in O(n) time.
-
Selection Sort (Largest to the End)
selectionSort(arr) on an int array: each pass finds the largest remaining element and swaps it to the end, with a toggle for skipping the swap of an element with itself.
-
Bubble Sort
bubbleSort(arr) swaps adjacent out-of-order pairs, carrying the largest unsettled value to the end each pass, with a toggle for early termination.
-
Insertion Sort
insertionSort(arr) inserts each key into the sorted portion before it, with a toggle between swapping the key left and shifting larger elements right.
-
Insertion Sort with Binary Search
Insertion sort that finds each key's position with a binary search and then shifts the larger elements right: fewer comparisons, the same shifts.
-
Cocktail Shaker Sort
A bubble sort whose passes alternate direction, settling the largest remaining element at the end and the smallest at the front, with early termination.
-
Merge Two Sorted Arrays
merge(arr1, arr2) fills a new array one slot at a time, taking the smaller of the two front elements, in O(n + m) time.
-
In-Place Merge
merge(arr, mid) merges two sorted halves of one array without a second array, by shifting: O(1) auxiliary space, but O(n²) time in the worst case.
-
Merge Sort (Bottom-Up)
Bottom-up merge sort: merge adjacent sorted runs of width 1, 2, 4, and so on, one pass per width, in O(n log n) time.
-
Merge Sort (Recursive)
Recursive merge sort: split the range in half on the way down, and merge the sorted halves on the way up, depth-first.
-
Union of Two Sorted Arrays
union(arr1, arr2) is a merge that copies a shared value once and advances both pointers, then trims the result to its length.
-
Merge k Sorted Arrays
mergeAll(arrays) merges k sorted arrays in pairs, recursively, the way merge sort merges runs, in O(n log k) time.
-
Sorting Algorithms Compared
Every sort from the course side by side on the same inputs, counting comparisons and swaps, shifts, or copies.
-
Maze Search with Recursion
hasPath(maze) searches recursively from the start, marks each cell visited, and backtracks out of a dead end when a call returns false.
-
Maze Search with a Stack
hasPathWithStack(maze) keeps its own stack of cells to explore, pushes open neighbors in the order right, down, left, up, and marks each cell visited when it is pushed.
-
Maze Search with a Queue
hasPathWithQueue(maze) swaps the stack for a queue, so the search dequeues every cell one move from the start before any cell two moves out.
-
Maze Search: Stack and Queue
The stack search and the queue search run side by side on the same maze, so the order each explores cells in can be compared.
-
Reachable Cells
reachableCount(maze) counts the open cells reachable from the start with a stack or a queue, counting each cell when it is taken out.
-
Maze Distance
distanceToExit(maze) runs the queue search with a distance array and returns the number of moves the search takes from the start to the exit, or -1 if the exit cannot be reached.
-
Maze Path
pathToExit(maze) records cameFrom for each cell during the queue search, then follows the links back from the exit and reverses them with a stack to return the route the queue search takes.
-
LinkedSet
A set stored in a singly linked list: add checks for a duplicate and links a new node at the head, and remove tracks the previous node to unlink a match.
-
ArraySet
A set stored in an unsorted array: add checks for a duplicate and appends, and remove moves the last item into the gap because a set promises no order.
-
Move-to-Front Heuristic
LinkedSet's contains moves each found node to the head of the list, so items looked up often end up near the front.
-
Transpose Heuristic
ArraySet's contains swaps each found item with the one before it, so items looked up often move toward the front one slot per hit.
-
Set Search Heuristics Compared
The plain search, move-to-front, and transpose run the same sequence of contains calls side by side, counting comparisons.
-
Set Union
union on unsorted arrays adds each value of arr2 that a linear search does not find in arr1, O(m · n); on sorted arrays a merge copies a tie once, O(m + n).
-
Set Intersection
intersection on unsorted arrays searches arr2 for each value of arr1, O(m · n); on sorted arrays a merge copies only the ties, O(m + n).
-
Set Difference
difference keeps the values of arr1 that are not in arr2: a linear search per value on unsorted arrays, O(m · n), or a merge on sorted arrays, O(m + n).
-
Set Iterator
An iterator for ArraySet and LinkedSet: hasNext and next step a cursor through the array, or a current reference through the nodes, one element at a time.
-
Modifying While Iterating
Removing from a set inside its own for loop: the iterator skips or revisits elements with no error, unless it fails fast with a modCount.
-
SparseList Iterator
An iterator for SparseList that steps through every logical position, reading a stored node where there is one and the default value everywhere else.
-
LinkedMap
A map stored in a singly linked list of key–value nodes: put searches for the key and either replaces its value or links a new node at the head.
-
ArrayMap
A map stored in an unsorted array of entries: every operation searches with indexOf, put appends a new key or replaces a value, and remove moves the last entry into the gap.
-
SortedArrayMap
A map stored in two parallel sorted arrays, keys and values: binary search finds a key in O(log n), and put and remove shift each key and its value together.
-
Tree Size, Height, and Depth
size, height, and depth on a binary tree: each recursive call builds its answer from the answers its subtrees return, and depth passes -1 up unchanged from a subtree without the target.
-
Pre-order Traversal with Recursion
preOrder(root) adds each node's value to result before it calls itself on the left and right subtrees, so every node comes before its descendants.
-
In-order Traversal with Recursion
inOrder(root) adds each node's value to result between its calls on the left and right subtrees, so a node comes after its left subtree and before its right.
-
Post-order Traversal with Recursion
postOrder(root) adds each node's value to result after its calls on the left and right subtrees, so every node comes after its descendants.
-
Level-order Traversal
levelOrder(root) visits the tree one level at a time with a queue: dequeue a node, add its value to result, and enqueue its children at the back.
-
Iterative Pre-order Traversal
Pre-order without recursion: pop a node from a stack you manage, add its value to result, and push its right child before its left so the left comes off first.
-
Iterative In-order Traversal
In-order without recursion: follow the left spine and push every node on it, then pop, add the value to result, and move into the right subtree.
-
Iterative Post-order Traversal
Post-order without recursion: run pre-order with the push order swapped, push each popped node onto a second stack, then pop that stack into result.
-
Searching a Binary Search Tree
contains on a binary search tree: each comparison rules out one subtree, so the search follows one path from the root, with the recursive call stack or the iterative current reference.
-
Adding to a Binary Search Tree
add on a binary search tree: the search ends at a null child, the base case returns the new node, and only the assignment at its parent changes a link.
-
Removing from a Binary Search Tree
remove on a binary search tree: unlink a leaf, splice out a node with one child, and replace a node with two children by its in-order successor before removing the successor below.
-
Iterating over a Binary Search Tree
The binary search tree's iterator: a stack field holds the left spine, each call to next pops one node and pushes the left spine of its right child, and the values come out in sorted order.
-
Tree Height and Add Order
Add the same values in different orders and compare the heights: a perfect tree of about log n levels, or a degenerate tree of height n − 1 when the values arrive in sorted order.
-
Binary Search Tree Playground
A binary search tree to try add, remove, and contains on, one call at a time, with the path each call follows, the in-order values, and the height.
-
Validating a Binary Search Tree
Check whether a binary tree is a binary search tree by carrying an open range down the recursion, and see why checking each node only against its children is not enough.
-
The k-th Smallest Value
Find the k-th smallest value in a binary search tree by counting in-order visits and stopping at the k-th, so the nodes after it are never visited.
-
AVL Rotations
The four AVL rotations on the notes' shapes or any tree: each single rotation changes two links and keeps the in-order sequence, and a bend needs a double rotation.
-
The AVL Tree
Add, remove, and search an AVL tree by hand: balance factors on every node, the walk back up after each change, the case named, and each rotation animated.
-
TreeMap
TreeMap's put, get, containsKey, and remove traced through the code: the call stack, the cached heights, rebalance's choice, and each rotation's link changes.
-
Ordered Queries on a TreeMap
floorKey, ceilingKey, and keysBetween on a TreeMap: one descent that remembers the best candidate, and an in-order traversal that skips every subtree outside the range.
-
Order Statistics on a TreeMap
select and rank on a TreeMap whose nodes cache their subtree sizes: each query is one descent that reads the left subtree sizes on its way.
-
LinkedHeap
LinkedHeap's add, remove, and peek traced through the code: pathTo's binary path, the recursive add's call stack with one swim step per return, removeLast, and sink.
-
ArrayHeap
ArrayHeap's add, remove, and peek traced through the code: the tree and the backing array side by side, the index arithmetic for parent and children, and swim and sink as loops.