Class 25 - Mutable Data Structures and the Heap

Date: November 12, 2026

⚠️Homework

Homework 9 due November 15, 2026

Skills: 9

Notes (review before class)

Mutable Data

The fields of a dataclass can be changed, by putting a field access on the left of an =:

from dataclasses import dataclass

@dataclass
class Account:
    id: int
    balance: float

acct1 = Account(8404, 500)
acct1.balance = acct1.balance + 200

Mutable data can be changed; immutable data, all we've used until now, cannot.
The last line changes the existing account: acct1.balance is now 700. Account(acct1.id, acct1.balance + 200) would make a new account instead.
Every dataclass field can be changed, so it's up to you not to change one that shouldn't (like the id).
Setting a name and setting a field both use =, but they mean very different things (compare rules 2 and 3 in The Heap, below).

State

A test written right after making the account fails, because PLL runs the whole file first, and only then calls the test functions:

acct1 = Account(8404, 500)

def test_balance():
    assert acct1.balance == 500

acct1.balance = acct1.balance + 200

The test passes if it expects 700, but then fails if the update is removed: it is only sometimes true.
State: the values of the defined names at some point as the program runs. There is a state in which acct1.balance is 500, and a later one in which it is 700.
Not just tests: from now on, every instruction runs in some state, and the same code can give different answers in different states.

Testing Functions that Mutate

A function that mutates its input often returns nothing (None), so its test checks the effect of calling it:

def deposit(ac: Account, amt: float) -> None:
    """adds amt to the account's balance"""
    ac.balance = ac.balance + amt

def test_deposit():
    # Setup
    acct = Account(8200, 150)

    # Call
    deposit(acct, 100)

    # Check
    assert acct.balance == 250

A test for a function that uses mutation has three or four parts:

Setup: set up the values to give the function.
Call: call the function.
Check: check that the call had the desired effect.
Teardown: restore data to their expected state.

test_deposit needs no Teardown, since it made its own data; a test that changes data used elsewhere must undo its changes.
Setup may also need to reset existing data (which other code may have mutated) to the values the test expects.
Try: write a test for this function (remember pytest.approx):

def add_interest(ac: Account) -> None:
    """increases the account's balance by 2 percent"""
    ac.balance = ac.balance * 1.02

Aliasing

Continuing the program, acct1 (with a balance of 700) is shared by two customers, and Elena deposits 150 into it:

@dataclass
class Customer:
    name: str
    acct: Account

acct2 = Account(8405, 350)
elena = Customer("Elena", acct1)
jorge = Customer("Jorge", acct1)

elena.acct.balance = elena.acct.balance + 150

elena.acct.balance is now 850, and so is jorge.acct.balance, even though the update was made through elena.acct, not jorge.acct.
Aliases: different names for the exact same datum. Here acct1, elena.acct, and jorge.acct are aliases.
Without mutation, sharing didn't matter. With it, a change through one alias is seen through all of them ("spooky action at a distance"), so always be on the alert for aliases.

Why the Directory Isn't Enough

Values in the directory can't contain names (Python replaces names with their values when it evaluates expressions), so after Elena's deposit the directory would be:

acct1  Account(8404, 850)
acct2  Account(8405, 350)
elena  Customer("Elena", Account(8404, 850))
jorge  Customer("Jorge", Account(8404, 850))

Nothing here says why the deposit changed three balances but not acct2's. With mutation and aliasing, mapping names to values breaks down: it doesn't capture the aliases.
Customer("Elena", acct1) would show the sharing. Names can't go in values, but one term, reused wherever a value is shared, is the right idea: it's what the computer does.

The Heap

The computer's memory is a large number of slots, each labeled with an address, the way a street address picks out one building. Python stores its data in a portion of memory called the heap.
A constructor puts the new data in a slot in the heap, and the directory gets the address of that slot, not the value.
We write addresses as @ and four digits. The first (@1001) is arbitrary; later data get the next addresses, in order.
Customer("Elena", acct1) looks up acct1 and gets an address, @1001, so the Customer in the heap contains that address.

The same program, after Elena's deposit, as a directory and heap:

Directory       Heap
acct1  @1001    @1001  Account(8404, 850)
acct2  @1002    @1002  Account(8405, 350)
elena  @1003    @1003  Customer("Elena", @1001)
jorge  @1004    @1004  Customer("Jorge", @1001)

acct1, elena.acct, and jorge.acct all lead to @1001: that makes them aliases. acct2's address appears nowhere else.

Three rules for how running a program changes the directory and the heap:

Constructing a new piece of structured data puts it at the next address in the heap.
Associating a name with a piece of structured data maps the name, in the directory, to the address of that data.
Modifying a field of structured data modifies the data in the heap.

Elena's deposit (rule 3) changed only the Account at @1001, which all three names lead to.
acct3 = acct1 doesn't change the heap at all (rule 2): it maps acct3 to @1001, making it one more alias.
Try: write three expressions, each using a different name from the directory, that produce the balance at @1001. Would elena.acct.balance = jorge.acct.balance - 50 update Elena and Jorge's shared account? Is it a good way to write it?

Basic Data and the Heap

Basic data (numbers, strings, ...) don't go in the heap. Continuing the program:

@dataclass
class Office:
    name: str
    room: int

x = 4
prof = "Dr. Kumar"
office1 = Office("Dr. Lakshmi", 311)
office2 = Office(prof, 310 + x)

Directory              Heap
x        4             @1005  Office("Dr. Lakshmi", 311)
prof     "Dr. Kumar"   @1006  Office("Dr. Kumar", 314)
office1  @1005
office2  @1006

The heap is there so that a change to a field is seen through every alias. Basic data have no fields, so (though real implementations vary) think of them as living right in the directory.
Structured data have an identity (an address) and parts; basic data can't be broken down.
Strings do have characters, but nothing in Python changes the characters of a string (+ and the like make new strings), so we treat them as basic data.

Equality

In a new file (after the dataclasses), with two checkpoints:

a1 = Account(8603, 500)
a2 = Account(8603, 500)
a3 = Account(8603, 250)
a4 = a2
# checkpoint 1
a2.balance = 800
# checkpoint 2

At checkpoint 1:

Directory     Heap
a1  @1001     @1001  Account(8603, 500)
a2  @1002     @1002  Account(8603, 500)
a3  @1003     @1003  Account(8603, 250)
a4  @1002

a3 has a different balance: it isn't equal to the others.
a1 and a2 have the same contents, but different addresses. At checkpoint 2, @1002 holds Account(8603, 800), so their contents differ.
a2 and a4 are aliases, so they change in lockstep: both now show 800.

There are two kinds of equality, with an operator for each:

Structural equality, ==: do the values have the same contents (do they look the same when displayed)?
Reference equality, is: are they at the same address (are the names aliases, for what is really only one value)?

a1 == a2  # True at checkpoint 1, but False at checkpoint 2
a2 == a4  # True at both
a1 is a2  # False at both
a2 is a4  # True at both

Mutation is why a1 == a2 stopped being true, which seems to break a basic idea of "equality": values that are == now may not be later.
== is more accepting, so it is usually the right default. Use is when you need to know whether two expressions evaluate to the same address.

Recap (15 mins)

A library program keeps track of how many copies of each book are on its shelves, and which book each display features. Read through the program:

from dataclasses import dataclass

@dataclass
class LibraryBook:
    id: int
    title: str
    copies: int

@dataclass
class Display:
    theme: str
    book: LibraryBook

def check_out(b: LibraryBook) -> None:
    """records that one copy of b has been checked out"""
    b.copies = b.copies - 1

def test_check_out():
    # Setup
    kindred = LibraryBook(205, "Kindred", 3)
    # Call
    check_out(kindred)
    # Check
    assert kindred.copies == 2

book1 = LibraryBook(101, "The Curious Incident", 5)
book2 = book1
book3 = LibraryBook(101, "The Curious Incident", 5)
staff_picks = Display("Staff Picks", book3)

check_out(book2)
check_out(staff_picks.book)

After the last line, what are book1.copies, book2.copies, and book3.copies? Draw the directory and heap to check your answers.
What are book1 == book3, book1 is book2, and staff_picks.book is book3? Which of them would change if we deleted the last line?
Why does test_check_out make its own LibraryBook, rather than checking that check_out(book1) takes book1.copies from 5 to 4?

Class Exercises (40 mins)

Analyze this Python code. What gets printed and why?

list1 = [1, 2, 3]
list2 = list1
list1.append(4)
print(list2)

Draw the program directory and heap for this scenario in Python:

@dataclass
class Student:
   name: str
   age: int
obj1 = Student("Alice", 25)
obj2 = Student("Alice", 25)
obj3 = obj1
obj1.age = 26

Show which variables are affected and why.

Analyze this Python code. What do the comparisons return?

list1 = [1, 2, 3]
list2 = [1, 2, 3]
list3 = list1
print(list1 == list2)
print(list1 is list2)
print(list1 is list3)

Trace through this Python function. What happens after each call?

def add_item(my_list, item):
    my_list.append(item)
    return my_list

original = [1, 2]
result1 = add_item(original, 3)
result2 = add_item(original, 4)
print(original)
print(result1)
print(result2)

Analyze this Python code. What gets printed?

list1 = [10, 20, 30]
list2 = list1
list1[1] = 99
print(list1)
print(list2)

Trace this Python function through multiple calls:

def make_list():
    new_list = [1, 2, 3]
    new_list.append(4)
    return new_list

result1 = make_list()
result2 = make_list()
print(result1 is result2)

Trace this Python function through multiple calls:

def make_counter():
    count = 0
    count = count + 1
    return count

result1 = make_counter()
result2 = make_counter()
print(result1 == result2)

Wrap-up (5 mins)

In Python, mutable data structures live in the heap and can be aliased.
Mutating through one alias affects all.
Structural equality checks contents; reference equality checks identity.
Understanding these concepts is key to writing correct code and avoiding bugs related to aliasing and mutation.

Skills: 9​

Notes (review before class)​

Mutable Data​

State​

Testing Functions that Mutate​

Aliasing​

Why the Directory Isn't Enough​

The Heap​

Basic Data and the Heap​

Equality​

Recap (15 mins)​

Class Exercises (40 mins)​

Wrap-up (5 mins)​