Chapter 20: Intro to Data Structures: Stacks, Queues, and Beyond

"Bad programmers worry about the code. Good programmers worry about data structures and their relationships." — Linus Torvalds

Chapter Overview

You already know lists, dictionaries, sets, and tuples. You can store data, look things up, iterate, and sort. So why does computer science have an entire subfield dedicated to data structures? Because general-purpose containers are like Swiss Army knives — useful everywhere, ideal nowhere. When a problem has a specific shape, a specialized data structure doesn't just make your code cleaner — it makes certain bugs structurally impossible and certain operations dramatically faster.

This chapter introduces two of the most important specialized data structures in computing: the stack and the queue. You'll build both from scratch, see how they solve real problems, and learn to recognize when a problem is secretly a stack problem or a queue problem. Along the way, you'll encounter one of the most important ideas in computer science — the abstract data type — which separates what a data structure does from how it does it.

We'll close with a conceptual tour of the data structures you'll meet in CS2: linked lists, trees, graphs, and hash tables. You won't implement them here, but understanding why they exist and what problems they solve will make the transition to more advanced courses far smoother.

In this chapter, you will learn to: - Implement a stack (LIFO) and use it for backtracking, undo, and bracket matching - Implement a queue (FIFO) and use it for task scheduling and processing pipelines - Think about data structures as abstract interfaces, not just concrete code - Describe when and why linked lists, trees, graphs, and hash tables are used - Choose the right data structure for a given problem by analyzing trade-offs

🏃 Fast Track: If you're comfortable with list operations and OOP from Chapters 8 and 14, skim 20.1 and dive into 20.2. Don't skip 20.6 (Abstract Data Types) — it's the threshold concept that changes how you think about all data structures.

🔬 Deep Dive: After this chapter, explore Python's queue module (queue.Queue, queue.LifoQueue, queue.PriorityQueue) for thread-safe implementations used in concurrent programming. The heapq module provides a priority queue via a binary heap — a data structure you'll study in depth in CS2.

20.1 Beyond Lists and Dicts

Think about the tools in a carpenter's workshop. A hammer works for dozens of tasks, but a carpenter also keeps specialized tools — a miter saw for precise angled cuts, a planer for flattening boards, a clamp for holding pieces in place while glue dries. You could substitute a hammer and brute force for most of these, but the specialized tool produces better results with less effort and fewer mistakes.

Data structures work the same way. Python's list is the hammer — versatile, powerful, your go-to for most problems. But some problems have constraints that a list doesn't enforce:

• An undo system needs to reverse the most recent action first. A list can do this (just pop() from the end), but nothing prevents you from accidentally removing an item from the middle. A stack makes "last in, first out" the only option.
• A print queue needs to process documents in the order they arrived. A list can do this too, but list.pop(0) is O(n), which gets slow fast. A queue enforces "first in, first out," and a well-built one (Section 20.4) removes from the front in O(1).
• A social network needs to represent who follows whom — relationships, not just items. No built-in Python type captures this naturally. A graph does.

The key insight is this: constraints are features, not limitations. When a data structure restricts what operations are allowed, it simultaneously prevents an entire category of bugs and communicates intent to anyone reading your code.

🔄 Spaced Review (Chapter 17): In Chapter 17, you learned that algorithm choice affects performance dramatically — O(n) vs. O(n log n) vs. O(n^2). Data structure choice has the same impact. The structure you choose determines which operations are fast, which are slow, and which are impossible. Keep Big-O thinking active as you read this chapter.

20.2 Stacks: Last In, First Out

A stack is a collection where the last item added is the first item removed. This pattern is called LIFO — Last In, First Out.

Think of a stack of plates in a cafeteria. You can only add a plate to the top, and you can only remove the plate on top. You can't pull a plate from the middle without toppling everything above it. That's exactly how a stack data structure works.

The Stack Interface

A stack supports exactly three core operations:

Two helper operations round out the interface: - is_empty() — returns True if the stack has no items - size() — returns the number of items

That's it. No indexing. No searching. No inserting in the middle. These restrictions are the whole point.

Implementing a Stack

Here's a complete stack implementation using a Python list as the internal storage. The end of the list is the top of the stack, so the list's append() and pop() methods (both O(1)) map directly to stack push and pop:

class Stack:
    """A Last-In, First-Out (LIFO) data structure."""

    def __init__(self):
        self._items: list = []

    def push(self, item) -> None:
        """Add an item to the top of the stack."""
        self._items.append(item)

    def pop(self):
        """Remove and return the top item. Raises IndexError if empty."""
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self._items.pop()

    def peek(self):
        """Return the top item without removing it."""
        if self.is_empty():
            raise IndexError("peek at empty stack")
        return self._items[-1]

    def is_empty(self) -> bool:
        """Return True if the stack contains no items."""
        return len(self._items) == 0

    def size(self) -> int:
        """Return the number of items in the stack."""
        return len(self._items)

    def __repr__(self) -> str:
        return f"Stack({self._items})"

Notice three design choices:

1. The internal list is named _items with a leading underscore. This is a Python convention from Chapter 14 — it signals "this is an implementation detail, not part of the public interface." Users of the stack should only use push, pop, peek, is_empty, and size.

2. pop() and peek() raise IndexError when the stack is empty. This is fail-fast design. If someone tries to pop from an empty stack, they made a logic error, and the error message tells them exactly what went wrong.

3. All operations are O(1). list.pop() without an index is O(1), and list.append() is amortized O(1): once in a while the list has to grow its storage, but averaged over many appends each one costs a constant amount. So our stack is efficient by default.

🔄 Spaced Review (Chapter 14): This is an example of encapsulation — hiding internal state behind a public interface. The Stack class wraps a list but only exposes stack operations. Users don't need to know (or care) that a list is used internally. They interact with a concept, not an implementation.

Using the Stack

s = Stack()
s.push("A")
s.push("B")
s.push("C")

print(s.peek())    # C  (top of stack, not removed)
print(s.pop())     # C  (removed)
print(s.pop())     # B  (removed)
print(s.size())    # 1  (only "A" remains)
print(s.pop())     # A  (removed)
print(s.is_empty())  # True

Visualizing the stack after each operation helps build intuition:

push("A"):  | A |          (bottom)
push("B"):  | A | B |
push("C"):  | A | B | C |  (top)
pop():      | A | B |       → returns "C"
pop():      | A |           → returns "B"
pop():      |   |           → returns "A"  (now empty)

The Text Adventure: Room Backtracking

In Crypts of Pythonia, the player explores rooms. When they enter a new room, we push the previous room onto a history stack. When they type "go back," we pop the most recent room. This naturally implements backtracking — the player always returns to the room they just left.

room_history = Stack()
current_room = "Entrance Hall"

def move_to(room_name: str) -> None:
    global current_room
    room_history.push(current_room)
    current_room = room_name
    print(f"You enter the {current_room}.")

def go_back() -> None:
    global current_room
    if room_history.is_empty():
        print("You're at the starting room. Nowhere to go back to.")
        return
    current_room = room_history.pop()
    print(f"You return to the {current_room}.")

# Simulate gameplay
move_to("Library")           # You enter the Library.
move_to("Secret Passage")    # You enter the Secret Passage.
move_to("Dragon's Lair")     # You enter the Dragon's Lair.

go_back()                    # You return to the Secret Passage.
go_back()                    # You return to the Library.
go_back()                    # You return to the Entrance Hall.
go_back()                    # You're at the starting room. Nowhere to go back to.

This is exactly how your web browser's "back" button works. Every page you visit is pushed onto a history stack. Clicking "back" pops the most recent page. The "forward" button uses a second stack — we'll build exactly this pattern in the undo/redo system below.

🔄 Check Your Understanding #1: If you push the values 1, 2, 3, 4 onto a stack and then pop twice, what value is on top? What is the stack's size?

Answer

After pushing 1, 2, 3, 4, the top is 4. Popping twice removes 4 then 3. The top is now 2, and the size is 2 (items 1 and 2 remain).

20.3 Stack Applications

Stacks show up everywhere in computing. Here are three important applications beyond the room backtracking example above.

Application 1: Matching Brackets

Every programmer has met Python's bracket complaints: SyntaxError: '(' was never closed, unmatched ')', or closing parenthesis '}' does not match opening parenthesis '['. Python's parser and your code editor catch these with the same tool you're about to build: a stack.

The algorithm: 1. Scan the string left to right. 2. When you see an opening bracket ((, [, {), push it onto the stack. 3. When you see a closing bracket (), ], }), pop the stack and check that it matches. If the stack is empty or the brackets don't match, the input is invalid. 4. After scanning the entire string, the stack should be empty. If it's not, there are unmatched opening brackets.

def check_brackets(text: str) -> tuple[bool, str]:
    """Check whether brackets in text are properly matched."""
    MATCH = {")": "(", "]": "[", "}": "{"}
    stack = Stack()

    for i, ch in enumerate(text):
        if ch in "([{":
            stack.push((ch, i))
        elif ch in ")]}":
            if stack.is_empty():
                return False, f"Unmatched '{ch}' at position {i}"
            top_char, top_pos = stack.pop()
            if top_char != MATCH[ch]:
                return False, (f"Mismatched '{top_char}' at position "
                               f"{top_pos} with '{ch}' at position {i}")

    if not stack.is_empty():
        top_char, top_pos = stack.pop()
        return False, f"Unmatched '{top_char}' at position {top_pos}"

    return True, "All brackets matched!"

# Test cases
print(check_brackets("{[()]}"))        # (True, 'All brackets matched!')
print(check_brackets("print('hi')"))   # (True, 'All brackets matched!')
print(check_brackets("data = [1, 2}")) # (False, "Mismatched '[' at position 7 with '}' at position 12")
print(check_brackets("((())"))         # (False, "Unmatched '(' at position 0")

Why a stack? Because brackets nest. The most recently opened bracket must be the first one closed. That's LIFO.

Here's the stack at each bracket for "{[(])}", which fails partway through:

'{'  push  → [ '{' ]
'['  push  → [ '{', '[' ]
'('  push  → [ '{', '[', '(' ]
']'  pop '(' — but ']' needs '['  → mismatch, stop

Notice that we push (character, position) tuples rather than bare characters. That extra bit of context is what lets the error message say where the problem is.

Application 2: Undo/Redo

An undo system uses two stacks: - Undo stack: Every time you perform an action, push a record of it onto the undo stack. - Redo stack: When you undo, move that record to the redo stack. - Critical rule: Any new action clears the redo stack. You've branched into a new timeline.

class TextEditor:
    """A minimal text editor with undo/redo."""

    def __init__(self):
        self.text: str = ""
        self._undo_stack = Stack()
        self._redo_stack = Stack()

    def type_text(self, new_text: str) -> None:
        self._undo_stack.push(self.text)   # save current state
        self._redo_stack = Stack()          # new action kills redo
        self.text += new_text

    def undo(self) -> None:
        if self._undo_stack.is_empty():
            print("Nothing to undo.")
            return
        self._redo_stack.push(self.text)
        self.text = self._undo_stack.pop()

    def redo(self) -> None:
        if self._redo_stack.is_empty():
            print("Nothing to redo.")
            return
        self._undo_stack.push(self.text)
        self.text = self._redo_stack.pop()

editor = TextEditor()
editor.type_text("Hello")
editor.type_text(", World")
print(editor.text)    # Hello, World

editor.undo()
print(editor.text)    # Hello

editor.undo()
print(editor.text)    # (empty string)

editor.redo()
print(editor.text)    # Hello

This is how Ctrl+Z works in virtually every application you use. The fact that it feels natural — always undoing the most recent thing — is because the underlying data structure is a stack.

Application 3: Expression Evaluation

When Python evaluates 2 + 3 * 4, it doesn't just go left to right. It respects operator precedence: multiplication before addition. Compilers, interpreters, and calculators use stacks to manage this. One classic trick is to rewrite the expression in postfix form, where each operator comes after its two operands: 2 3 4 * +. Evaluating postfix needs nothing but a stack. Push each number; when you hit an operator, pop two numbers, apply the operator, and push the result:

token   stack
2       [2]
3       [2, 3]
4       [2, 3, 4]
*       [2, 12]     ← popped 3 and 4, pushed 3 * 4
+       [14]        ← popped 2 and 12, pushed 2 + 12

You'll build this evaluator yourself in Exercise C.3. A full expression parser is beyond this course, but there's an even bigger stack hiding in plain sight: the call stack you met in Chapter 6. When function a calls function b, which calls function c, Python pushes a frame for each call (holding its local variables and where to resume). When c finishes, Python pops its frame and picks up in b. When b finishes, it pops again and returns to a. Python caps how deep that stack can grow (about 1,000 frames by default), which is why runaway recursion ends in RecursionError: maximum recursion depth exceeded (Chapter 18).

🧩 Productive Struggle: Design an undo system for a text editor. What data structure would you use? Think about: what happens when you type, delete, undo, redo, then type something new? Write pseudocode before looking at the solution above. The insight that a new action clears the redo stack is the hardest part — and the most important.

20.4 Queues: First In, First Out

A queue is a collection where the first item added is the first item removed. This pattern is called FIFO — First In, First Out.

Think of a line at a coffee shop. The person who arrived first gets served first. New customers join at the back of the line. Nobody cuts in front (in a fair queue, at least). That's exactly how a queue data structure works.

The Queue Interface

Plus the usual is_empty() and size() helpers.

Why Not Just Use a List?

You can implement a queue with a list — append() to add at the back, pop(0) to remove from the front. But pop(0) is O(n) because Python has to shift every remaining element forward by one position. The first dequeue from a 100,000-item list shifts 99,999 elements, the next shifts 99,998, and so on. Draining the whole queue that way is O(n²).

Python's collections.deque (pronounced "deck," short for "double-ended queue") solves this. Internally it's a chain of fixed-size blocks linked together, so removing from the front just moves a marker instead of shifting everything. It provides O(1) append() and O(1) popleft():

from collections import deque

class Queue:
    """A First-In, First-Out (FIFO) data structure."""

    def __init__(self):
        self._items: deque = deque()

    def enqueue(self, item) -> None:
        """Add an item to the back of the queue."""
        self._items.append(item)

    def dequeue(self):
        """Remove and return the front item."""
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        return self._items.popleft()

    def front(self):
        """Return the front item without removing it."""
        if self.is_empty():
            raise IndexError("front of empty queue")
        return self._items[0]

    def is_empty(self) -> bool:
        return len(self._items) == 0

    def size(self) -> int:
        return len(self._items)

    def __repr__(self) -> str:
        return f"Queue({list(self._items)})"

The performance difference is dramatic:

import time
from collections import deque

# list.pop(0) — O(n) per operation, O(n^2) total
test_list = list(range(100_000))
start = time.perf_counter()
while test_list:
    test_list.pop(0)
list_time = time.perf_counter() - start

# deque.popleft() — O(1) per operation, O(n) total
test_deque = deque(range(100_000))
start = time.perf_counter()
while test_deque:
    test_deque.popleft()
deque_time = time.perf_counter() - start

print(f"list:  {list_time:.3f}s")   # e.g. 0.440s (machine-dependent)
print(f"deque: {deque_time:.3f}s")  # e.g. 0.003s (machine-dependent)

Your exact numbers will differ (on a slower machine the list version can take several seconds), but the deque wins by a factor of a hundred or more. And the gap keeps growing: double the number of items and the list version takes roughly four times as long, the signature of O(n²).

⚠️ Pitfall: If you see some_list.pop(0) in a loop, that's a code smell. It means "I need a queue but I'm using a list." Replace the list with a deque and use popleft().

Using the Queue

q = Queue()
q.enqueue("Alice")
q.enqueue("Bob")
q.enqueue("Charlie")

print(q.front())     # Alice  (first in line, not removed)
print(q.dequeue())   # Alice  (served, removed)
print(q.dequeue())   # Bob    (served, removed)
print(q.size())      # 1      (only Charlie remains)

Visualizing the queue:

enqueue("Alice"):   [Alice]           front →  ← back
enqueue("Bob"):     [Alice, Bob]
enqueue("Charlie"): [Alice, Bob, Charlie]
dequeue():          [Bob, Charlie]     → returns "Alice"
dequeue():          [Charlie]          → returns "Bob"

🔄 Check Your Understanding #2: If you enqueue the values "X", "Y", "Z" and then dequeue once, what is at the front of the queue? What would happen if you dequeued three more times?

Answer

After enqueueing X, Y, Z and dequeuing once (removes X), the front is "Y". Of the three extra dequeues, the first returns Y, the second returns Z (the queue is now empty), and the third raises IndexError: dequeue from empty queue.

20.5 Queue Applications

Application 1: Elena's Report Processing Pipeline

Elena Vasquez, our nonprofit data analyst, receives reports from multiple departments throughout the week. Each report needs to be processed in the order it arrives — a natural FIFO scenario:

report_queue = Queue()

# Reports arrive throughout the day
report_queue.enqueue("Q1 Donations Summary")
report_queue.enqueue("Volunteer Hours Log")
report_queue.enqueue("Grant Application Status")
report_queue.enqueue("Monthly Budget Reconciliation")

# Elena processes them in order
while not report_queue.is_empty():
    report = report_queue.dequeue()
    print(f"Processing: {report}")

# Output (always in arrival order):
# Processing: Q1 Donations Summary
# Processing: Volunteer Hours Log
# Processing: Grant Application Status
# Processing: Monthly Budget Reconciliation

Application 2: Task Scheduling

Operating systems use queues to schedule which process runs next. A simplified version: tasks arrive with different processing times, and the system works through them in order.

from collections import deque

task_queue: deque = deque()

# Tasks arrive
tasks = [
    {"name": "Download update", "time_ms": 3000},
    {"name": "Save document", "time_ms": 500},
    {"name": "Send email", "time_ms": 1200},
]

for task in tasks:
    task_queue.append(task)

# Process in FIFO order
clock_ms = 0                    # time elapsed since the first task started
while task_queue:
    task = task_queue.popleft()
    clock_ms += task["time_ms"]
    print(f"Running '{task['name']}' — "
          f"completes at {clock_ms}ms")

# Output:
# Running 'Download update' — completes at 3000ms
# Running 'Save document' — completes at 3500ms
# Running 'Send email' — completes at 4700ms

Application 3: Breadth-First Search Preview

In Chapter 18, Dr. Patel's recursive directory search went as deep as it could down one branch before backing up to try the next. That's depth-first exploration, and it runs on a stack (the call stack). Queues enable a fundamentally different traversal pattern: breadth-first search (BFS). Imagine you're exploring a maze. Instead of diving down one corridor, BFS explores every square one step away, then every square two steps away, then three. Picture ripples spreading out from a stone dropped in a pond. When every step costs the same, as in a grid maze, the first time a ripple touches the goal is guaranteed to be via a shortest path.

Here's a taste — a BFS that finds the shortest path in a simple grid:

def bfs_shortest_path(grid: list[list[str]], start: tuple[int, int],
                      goal: tuple[int, int]) -> int | None:
    """Find shortest path length in a grid using BFS. '#' = wall."""
    rows, cols = len(grid), len(grid[0])
    queue: deque = deque()
    queue.append((start[0], start[1], 0))  # row, col, distance
    visited: set = {start}                 # mark cells when we queue them

    while queue:
        row, col, dist = queue.popleft()
        if (row, col) == goal:
            return dist
        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nr, nc = row + dr, col + dc
            if (0 <= nr < rows and 0 <= nc < cols
                    and grid[nr][nc] != "#" and (nr, nc) not in visited):
                visited.add((nr, nc))
                queue.append((nr, nc, dist + 1))

    return None  # no path found

maze = [
    [".", ".", "#", "."],
    ["#", ".", "#", "."],
    [".", ".", ".", "."],
    [".", "#", "#", "."],
]

result = bfs_shortest_path(maze, (0, 0), (3, 3))
print(f"Shortest path length: {result}")  # Shortest path length: 6

The queue ensures we explore closer cells before farther ones — that's what guarantees shortest-path correctness. If we used a stack instead, we'd get depth-first search, which might find a path but not necessarily the shortest.

One detail worth copying into your own BFS code: a cell goes into visited the moment it's queued, not when it's dequeued. If you wait until dequeue, two neighbors can both queue the same cell before either is processed, and the queue fills with duplicates.

🔄 Check Your Understanding #3: A stack uses LIFO and enables depth-first exploration. A queue uses FIFO and enables breadth-first exploration. If you replaced the queue in BFS with a stack, what change in behavior would you observe?

Answer

The algorithm would become depth-first search (DFS). It would still find a path (if one exists), but it would explore one branch deeply before trying others. It would not guarantee finding the shortest path. DFS might return a path of length 20 even if a path of length 6 exists.

20.6 Abstract Data Types

This is the threshold concept of the chapter. Take your time with it.

🚪 Threshold Concept: Abstract Data Types

Before: "A stack is a list with restrictions."

After: "A stack is a concept (LIFO behavior) that can be implemented in many ways."

An abstract data type (ADT) is a specification of what a data structure does — its operations and their behavior — without specifying how it does it internally. It's the difference between a blueprint and a building.

Consider the stack ADT. The specification says: - push(item) adds an item to the top - pop() removes and returns the top item - peek() returns the top item without removing it - is_empty() reports whether the stack is empty

That's the entire ADT. It says nothing about lists, arrays, linked lists, or any other implementation technology. Any code that provides these operations with LIFO behavior is a stack, regardless of how it works internally.

Why Does This Matter?

Because it means you can swap implementations without changing any code that uses the data structure. This is the same principle you encountered with polymorphism in Chapter 15 — code against the interface, not the implementation.

Here's a concrete example. We implemented our stack using a Python list:

class ListStack:
    """Stack implemented with a Python list."""

    def __init__(self):
        self._items: list = []

    def push(self, item) -> None:
        self._items.append(item)

    def pop(self):
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self._items.pop()

    def peek(self):
        if self.is_empty():
            raise IndexError("peek at empty stack")
        return self._items[-1]

    def is_empty(self) -> bool:
        return len(self._items) == 0

    def size(self) -> int:
        return len(self._items)

But we could also implement the same ADT using a collections.deque:

from collections import deque

class DequeStack:
    """Stack implemented with a deque."""

    def __init__(self):
        self._items: deque = deque()

    def push(self, item) -> None:
        self._items.append(item)

    def pop(self):
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self._items.pop()

    def peek(self):
        if self.is_empty():
            raise IndexError("peek at empty stack")
        return self._items[-1]

    def is_empty(self) -> bool:
        return len(self._items) == 0

    def size(self) -> int:
        return len(self._items)

Both classes implement the same ADT. Any code that uses push, pop, peek, and is_empty works identically with either one. The user never knows — or needs to know — which implementation is underneath. Try it: in check_brackets from Section 20.3, change stack = Stack() to stack = DequeStack(). That one line is the only edit, and every test case prints exactly what it did before.

This separation of interface from implementation is one of the most powerful ideas in computing:

In CS2, you'll learn that the same ADT (like "priority queue") can have dramatically different performance depending on the implementation (unsorted list vs. sorted list vs. binary heap). The ADT stays the same; the trade-offs change. Learning to separate these two concerns is what makes you a computer scientist, not just a programmer.

💡 Intuition: Think of a vending machine. The ADT is the interface: insert money, press a button, get a snack. The implementation is whatever mechanism is inside — gears, springs, a robotic arm. As a customer, you don't care how it works. You care that it works. If the manufacturer swaps the internal mechanism, your experience doesn't change — as long as the interface stays the same.

20.7 Linked Lists Conceptually

Python's lists, tuples, and strings all store their elements in contiguous memory: one right after another, like books on a shelf. (Strictly, a list stores a contiguous row of references to its items, but the effect is the same.) This is great for random access (my_list[42] is O(1)) but expensive for insertions near the front or middle (every element after the insertion point has to shift over).

A linked list takes a fundamentally different approach. Instead of storing elements side by side, each element is a node that contains two things: 1. The data (the actual value) 2. A reference (or pointer) to the next node

The nodes can be scattered anywhere in memory. The references stitch them together into a sequence.

Node("A")      Node("B")      Node("C")
┌──────┬───┐   ┌──────┬───┐   ┌──────┬───┐
│ "A"  │ ──┼──→│ "B"  │ ──┼──→│ "C"  │ / │
└──────┴───┘   └──────┴───┘   └──────┴───┘
  data  next     data  next     data  next
                                      (None = end)

In Python, a node might look like this:

class Node:
    """A single node in a linked list."""

    def __init__(self, data, next_node=None):
        self.data = data
        self.next = next_node

# Build a tiny linked list: A → B → C
c = Node("C")
b = Node("B", c)
a = Node("A", b)

# Traverse it
current = a
while current is not None:
    print(current.data, end=" → ")
    current = current.next
print("None")
# Output: A → B → C → None

Why Linked Lists Exist

Linked lists aren't better than Python lists for most tasks. Their power shows up in specific scenarios:

The trade-off is clear: linked lists sacrifice random access for fast insertions and deletions at positions you've already reached. (Getting to a position still means walking the chain, which is O(n).) In CS2, you'll implement linked lists fully and discover that many advanced data structures (trees, graphs, hash table chains) use linked-list-like node-and-reference patterns internally.

⚠️ Important: You don't need to implement a full linked list for this course. The goal here is to understand the concept — nodes connected by references — because it appears everywhere in advanced data structures.

20.8 Preview: Trees, Graphs, and Hash Tables

This section is a roadmap, not a tutorial. You won't implement these structures here, but knowing they exist — and what problems they solve — gives you a framework for the data structures courses ahead.

Trees

A tree is a hierarchical data structure where each node has a value and zero or more children. The topmost node is the root. Nodes with no children are leaves.

        CEO
       /    \
     CTO    CFO
    /   \      \
  Dev1  Dev2  Accountant

Trees model anything hierarchical: file systems (folders contain subfolders), HTML documents (tags contain other tags), organizational charts, decision trees, and more. A binary tree — where each node has at most two children — is the foundation of binary search trees (BSTs), which provide O(log n) search, insert, and delete as long as the tree stays balanced.

Graphs

A graph is a set of nodes (also called vertices) connected by edges. Unlike trees, graphs can have cycles (A connects to B connects to C connects back to A), and edges can be one-directional or two-directional.

    Alice ←→ Bob
      ↕       ↕
    Carol ←→ Dave

Graphs model relationships: social networks (who follows whom), maps (cities connected by roads), dependency systems (which tasks must finish before others can start), and the internet itself (web pages linked by hyperlinks). Graph algorithms like BFS, DFS, Dijkstra's shortest path, and minimum spanning trees are among the most important algorithms in computer science.

Hash Tables

A hash table maps keys to values using a hash function — a function that turns a key into a number, which then picks a slot in an internal array. This is exactly how Python's dict works behind the scenes.

# When you write:
phonebook = {"Alice": "555-0101", "Bob": "555-0102"}

# Python internally computes hash("Alice") to find WHERE to store the value.
# That's why dict lookup is O(1) on average — it jumps directly to the slot.

In Chapter 9, you learned to use dictionaries. In CS2, you'll learn how they work: hash functions, collision resolution, load factors, and resizing. Understanding the implementation explains why dictionary keys must be hashable (in practice, immutable types like str, int, and tuple) and why, before Python 3.7, dictionaries didn't promise to keep keys in insertion order.

The Big Picture

These six data structures (plus arrays, which you already know as Python lists) cover the vast majority of data structure needs in practice. Everything else — heaps, tries, B-trees, skip lists, Bloom filters — builds on these fundamentals.

20.9 Choosing the Right Data Structure

One of the most important skills in programming is choosing the right data structure for the job. Here's a comprehensive decision guide comparing the structures you know:

Decision Flowchart (Mental Model)

Ask yourself these questions in order:

1. Do I need key-value pairs? → Use a dict.
2. Do I need to enforce uniqueness? → Use a set.
3. Do I need LIFO (last in, first out)? → Use a stack.
4. Do I need FIFO (first in, first out)? → Use a queue.
5. Do I need an ordered sequence? → Use a list (or tuple if it shouldn't change).
6. Am I modeling relationships? → You need a graph (CS2 territory).
7. Am I modeling hierarchy? → You need a tree (CS2 territory).

💡 Intuition: The right data structure makes the code obvious. If you find yourself writing complicated workarounds — checking if a list is empty before popping, shifting elements manually, using a list as a makeshift queue — you're probably using the wrong data structure. Step back and ask: "What shape does this problem have?"

🐛 Debugging Walkthrough: Empty Stack and Queue Errors

The most common bug with stacks and queues is trying to access an element when the container is empty. Let's trace through a typical scenario:

# Bug: processing without checking for empty
task_stack = Stack()
task_stack.push("Task A")
task_stack.push("Task B")

# Process all tasks... but one too many pops
task_stack.pop()    # Returns "Task B" — fine
task_stack.pop()    # Returns "Task A" — fine
task_stack.pop()    # IndexError: pop from empty stack

The fix: Always guard with is_empty() before pop() or dequeue():

# Correct pattern: check before popping
while not task_stack.is_empty():
    task = task_stack.pop()
    print(f"Processing: {task}")

A similar bug occurs with queues:

q = Queue()
q.enqueue("first")

# Bug: processing assumes more items than exist
for _ in range(5):
    item = q.dequeue()  # Crashes on second iteration

The fix: Same pattern — use is_empty() or size() as a guard:

while not q.is_empty():
    item = q.dequeue()
    print(f"Processed: {item}")

Rule of thumb: Before you call pop(), peek(), dequeue(), or front(), know what happens if the container is empty. Either check is_empty() first (the natural choice for a "process until empty" loop, where running out is the expected way to stop), or, if an empty container would be genuinely unusual, wrap the call in try/except IndexError in the EAFP style from Chapter 11. The same applies to Python's built-in collections: list.pop() on an empty list raises IndexError, and deque.popleft() on an empty deque does the same.

20.10 Project Checkpoint: TaskFlow v1.9

It's time to add undo/redo and a task execution queue to TaskFlow.

What's New in v1.9

1. Undo stack: Every add_task and delete_task operation pushes a record onto an undo stack. The undo command reverses the most recent operation.
2. Redo stack: Undone operations can be redone. A new add or delete clears the redo stack (you've branched into a new timeline).
3. Task queue: Tasks can be scheduled for sequential execution. The process_next command completes the next queued task in FIFO order.

Implementation Overview

We need three new components:

1. Stack and Queue classes — the ones you built in this chapter.
2. UndoableAction class — a record that stores what was done (add or delete), which task was affected, and where it was in the list (for accurate restoration).
3. New methods on TaskList: undo(), redo(), schedule_task(), process_next().

Tasks are still v1.5's Task dataclass, with one new field: an id. Undo puts a deleted task back where it was, so list positions shift around; a number that never changes is a safer way to name a task. TaskList hands out the ids as tasks are added, which is why its methods take a task id rather than a position. To keep the new code easy to see, the checkpoint's TaskList leaves out the observers (v1.5), the keyword index (v1.6), and the sorting and searching functions (v1.8).

Key Code

The full implementation is in code/project-checkpoint.py. Here are the critical pieces:

Recording an action:

class UndoableAction:
    """Records an action so it can be undone or redone."""

    def __init__(self, action_type: str, task: Task,
                 position: int | None = None):
        self.action_type: str = action_type   # "add" or "delete"
        self.task: Task = task
        self.position: int | None = position  # where it was (for delete)
        self.timestamp: str = datetime.now().strftime("%Y-%m-%d %H:%M:%S")

    def __repr__(self) -> str:
        return f"UndoableAction({self.action_type}, '{self.task.title}')"

Undoing an action (reverse whatever was done):

def undo(self) -> bool:
    """Undo the last add or delete operation."""
    if self._undo_stack.is_empty():
        print("  Nothing to undo.")
        return False

    action = self._undo_stack.pop()

    if action.action_type == "add":
        # Undo an add → remove the task
        self.tasks = [t for t in self.tasks if t.id != action.task.id]
        print(f"  Undid add: removed '{action.task.title}'")

    elif action.action_type == "delete":
        # Undo a delete → re-insert at original position
        pos = action.position if action.position is not None else len(self.tasks)
        self.tasks.insert(pos, action.task)
        print(f"  Undid delete: restored '{action.task.title}'")

    self._redo_stack.push(action)
    return True

Watch that is not None check. A task deleted from the front of the list has position == 0, and 0 is falsy, so the tempting shortcut action.position or len(self.tasks) would quietly restore it at the end of the list instead of the front. Undo would "work" and still be wrong.

Scheduling and processing tasks:

def schedule_task(self, task_id: int) -> bool:
    """Add a task to the execution queue."""
    for task in self.tasks:
        if task.id == task_id:
            self._execution_queue.enqueue(task)
            print(f"  Scheduled: {task}")
            return True
    print(f"  Task #{task_id} not found.")
    return False

def process_next(self) -> Task | None:
    """Process (complete) the next task in the queue."""
    if self._execution_queue.is_empty():
        print("  No tasks in the execution queue.")
        return None
    task = self._execution_queue.dequeue()
    task.complete()
    print(f"  Processed: {task}")
    return task

Testing Your Implementation

task_list = TaskList()
task_list.add_task("Write notes", "high", "school")      # gets id 1
task_list.add_task("Buy groceries", "medium", "personal") # gets id 2
task_list.add_task("Review PR", "high", "work")           # gets id 3

# Delete and undo
task_list.delete_task(2)   # Removes "Buy groceries"
task_list.undo()           # Restores "Buy groceries" at its old position

# Schedule and process
task_list.schedule_task(1) # Queue: [Task #1]
task_list.schedule_task(3) # Queue: [Task #1, Task #3]
task_list.process_next()   # Completes Task #1 (FIFO)
task_list.process_next()   # Completes Task #3

Run code/project-checkpoint.py for a complete demo with expected output for every operation.

🔄 Spaced Review (Chapter 19): In v1.8, you added custom sorting and binary search. In your own TaskFlow, those features keep working — undo/redo is a layer on top of the existing task management. (The checkpoint file leaves them out, along with v1.5's observers and v1.6's keyword index, so the new code is easier to see.) Notice how each new feature composes with the existing code rather than replacing it. Good design is additive.

Chapter Summary

This chapter introduced stacks (LIFO), queues (FIFO), and the critical idea of abstract data types — separating what a data structure does from how it's implemented.

Key ideas:

• A stack supports push, pop, and peek. It's used for undo systems, bracket matching, backtracking, and expression evaluation. Implement it with a Python list using append() and pop() for O(1) operations.
• A queue supports enqueue, dequeue, and front. It's used for task scheduling, processing pipelines, and breadth-first search. Implement it with collections.deque using append() and popleft() for O(1) operations.
• An abstract data type defines what operations a data structure supports, not how it implements them. The same ADT can have multiple implementations with different performance characteristics.
• Linked lists store elements in nodes connected by references, trading random access for fast insertions and deletions at a node you've already reached.
• Trees, graphs, and hash tables are fundamental data structures you'll study in CS2, each optimized for a different class of problems.
• Choosing the right data structure is one of the most impactful design decisions you'll make. Match the structure to the problem's shape.

Looking ahead: In Chapter 21, you'll move from data structures to data sources. You'll go deeper into the CSV and JSON you first met in Chapter 10 and learn to pull live data from web APIs — connecting your programs to the outside world. The queue pattern from this chapter will reappear when you process records from a file in the order they arrive.

"I will, in fact, claim that the difference between a bad programmer and a good one is whether he considers his code or his data structures more important." — Linus Torvalds