Algorithms and Data Structures

By the end of this lesson you'll be able to:

• Explain and implement a stack (LIFO) and a queue (FIFO)
• Represent a graph as an adjacency list and traverse it with BFS and DFS
• Implement bubble sort, selection sort, and binary search
• Describe Big-O notation and explain the time complexity of common operations

This chapter introduces the computer science fundamentals that power everything from search engines to game AI.

Welcome to Chapter 30!

Data structures and algorithms are the heart of computer science. Every search, every recommendation, every route-planning app uses the ideas in this chapter. Let's unlock them! Let's code it together!

Abstract Data Types

An Abstract Data Type (ADT) describes what a data structure does, not how it does it internally. A stack, queue, and graph are ADTs — each defines operations like push, pop, enqueue, and dequeue.

Stacks — LIFO

A stack is a Last In, First Out (LIFO) collection. Think of a stack of plates — you can only add or remove from the top.

Two operations: - Push — add to the top - Pop — remove from the top

Python lists work perfectly as stacks:

stack = []
stack.append("first")    # push
stack.append("second")   # push
stack.append("third")    # push
print(stack.pop())       # "third" — last in, first out
print(stack.pop())       # "second"

What Do You Think Will Happen?

The code below uses a stack to reverse a string. After pushing all characters and popping them, what order will they appear? Make your guess — then run it!

▶ Run ↻ Reset

Queues — FIFO

A queue is a First In, First Out (FIFO) collection. Think of a line at a lunch counter — the first person in line is the first to be served.

Two operations: - Enqueue — add to the back - Dequeue — remove from the front

Python's collections.deque is more efficient than a list for queues:

▶ Run ↻ Reset

Graphs — Nodes and Edges

A graph is a set of nodes (also called vertices) connected by edges. Graphs model social networks, road maps, the internet, and many more real-world systems.

An adjacency list represents a graph as a dictionary where each key is a node and the value is a list of its neighbors.

graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"]
}

Breadth-First Search (BFS)

BFS explores a graph level by level — all nodes at distance 1 first, then distance 2, and so on. It uses a queue to keep track of which node to visit next.

BFS finds the shortest path in an unweighted graph.

Before the code, the key steps are: 1. Start at the source node; mark it as visited; enqueue it 2. While the queue is not empty: dequeue a node, process it, enqueue all unvisited neighbors

▶ Run ↻ Reset

Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking. It uses a stack (or recursion) to keep track of the path.

DFS does not guarantee the shortest path, but uses less memory than BFS for deep graphs.

▶ Run ↻ Reset

	BFS	DFS
Data structure	Queue	Stack / recursion
Shortest path?	Yes (unweighted)	Not guaranteed
Memory	More (stores whole frontier)	Less (stores one path)
Best for	Shortest path, social networks	Exploring all paths, cycles

See It: The Queue and the Stack Drive Everything

The only difference between BFS and DFS is the row in that table's first line — which waiting node gets visited next. The explorer below shows the queue or stack live beside the graph while you step. Before you click, predict: starting at A, which node does BFS visit third? Does DFS agree?

Explore the Graph Traversal Explorer MicroSim

Step all the way through BFS and watch the ripple move level by level — then the final step reveals the payoff: following the parents backward gives the shortest path from A to the goal. Switch to DFS and step again: same graph, same start, completely different order, because the stack always grabs the newest discovery.

Applying BFS: Finding a Path Through a Maze

A maze is just a graph — junctions and rooms are nodes, corridors are edges. BFS's queue already explores level by level, which means it can find the shortest path, not just answer "can I get there?" The trick is remembering where you came from at each step, so you can retrace your route once you reach the goal.

What Do You Think Will Happen?

The maze below has two possible routes from "Start" to "Goal". Which rooms do you think the path will pass through — "A"/"C" or "B"/"D"? Make your guess — then run it!

▶ Run ↻ Reset

Were you right? BFS discovers "A" and "B" at the same time, but "A" is listed first in maze["Start"], so it's discovered first — the path goes through "A" and "C".

DFS could solve the same maze by following one corridor all the way before backtracking, but as the table above shows, it wouldn't guarantee the shortest route.

Sorting Algorithms

Bubble Sort

Bubble sort compares adjacent items and swaps them if they're in the wrong order. Each pass "bubbles" the largest unsorted item to its correct position. Time complexity: O(n²) — slow for large lists.

def bubble_sort(lst):
    n = len(lst)
    for i in range(n):
        for j in range(n - i - 1):
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]
    return lst

Selection Sort

Selection sort finds the smallest item and moves it to the front, then repeats for the remaining items. Also O(n²) but makes fewer swaps than bubble sort.

Insertion Sort

Insertion sort builds the sorted list one item at a time — like sorting playing cards in your hand. O(n²) worst case but O(n) for nearly-sorted lists, making it fast in practice for small or nearly-sorted inputs.

▶ Run ↻ Reset

See It: Sorting in Slow Motion

The code above shows what each sort computes; the comparer below shows how they move. Every sort is just compares and swaps in a different choreography. Before you click Step, predict: for 10 reversed values, roughly how many comparisons will bubble sort need?

Explore the Sorting Algorithm Comparer MicroSim

Step through each algorithm and watch its signature move: bubble sort's big values float right, selection sort hunts for the minimum, insertion sort slides each new value into place. Then pick Race — Bubble vs Insertion, switch the data to nearly sorted, and Auto-play: insertion sort demolishes bubble sort — the answer to "which sort is best?" is always it depends on the data.

Binary Search

Binary search finds an item in a sorted list in O(log n) time — far faster than linear search.

The idea: repeatedly cut the search range in half. 1. Look at the middle item 2. If it matches — done! 3. If the target is smaller — search the left half 4. If the target is larger — search the right half

def binary_search(sorted_list, target):
    lo, hi = 0, len(sorted_list) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if sorted_list[mid] == target:
            return mid
        elif sorted_list[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1   # not found

See It: Linear vs Binary, Head to Head

The race below runs both searches on the same shelf of 31 boxes. Before you click Step, predict: how many checks will each search need to find 24? (Linear starts at the left; binary starts in the middle.)

Explore the Search Race MicroSim

Watch binary search throw away half the shelf with every check: 31 → 15 → 7 → 3 → 1. Then switch to the shuffled shelf (trap!) and search again — binary search can report NOT FOUND even when the target is sitting right there. Cutting the problem in half only works when the shelf is sorted, which is exactly why the function above is named binary_search(sorted_list, ...).

Big-O Notation — Time and Space Complexity

Big-O notation describes how an algorithm's running time grows with input size.

Big-O	Name	Example
O(1)	Constant	Dictionary lookup
O(log n)	Logarithmic	Binary search
O(n)	Linear	Linear search, single loop
O(n log n)	Log-linear	Python's built-in sorted()
O(n²)	Quadratic	Bubble sort, nested loops
O(2ⁿ)	Exponential	Brute-force subset enumeration

Space complexity describes how much memory an algorithm uses. BFS uses O(n) memory because the queue can grow to hold all nodes. DFS uses O(depth) memory — just the current path.

Why Big-O Matters

With 1,000 items: O(n²) = 1,000,000 operations; O(n log n) = ~10,000. That's 100× faster! For 1,000,000 items, the gap becomes 1,000,000× faster. Choosing the right algorithm is often more important than buying faster hardware.

Learning Check

Your Turn — Implement Binary Search

The code below calls binary_search but the function body is missing! Implement it using the algorithm described above — repeatedly halve the search range.

▶ Run ↻ Reset

Experiments

Try these changes. Predict what will happen first, then run it to check!

1. Modify the BFS function to also return the distance (number of hops) from the start to each node. You'll know it worked when each node is paired with its distance from "A".

2. Add a new node "G" to the graph connected to "D". Run BFS again and check that G appears. You'll know it worked when "G" is included in the BFS output.

3. Compare BFS and DFS starting from "C" instead of "A". Notice how the visit orders differ. You'll know it worked when both start at "C" and explore in clearly different patterns.

4. Implement selection sort: find the minimum in the unsorted portion and swap it to the front. You'll know it worked when selection_sort([5, 3, 8, 1]) returns [1, 3, 5, 8].

5. Test binary search on a list of 1,000,000 items. How many comparisons does it need? Add a counter inside the loop and print it. You'll know it worked when you see it takes at most 20 comparisons — O(log 1,000,000) ≈ 20!

Computer Scientist!

You've learned data structures and algorithms — the foundation of all efficient software! Stacks, queues, graphs, BFS, DFS, sorting, and Big-O are the tools professional developers think about every day. You're now thinking like a computer scientist. Let's keep coding!

Take the Chapter Review Quiz

See Annotated References