Memory, values and references (Fundamentals)

Several earlier lessons ended with a warning that b = a does not always copy. This lesson explains why. The answer lies in how a program uses memory, and once you see it, a whole family of confusing bugs becomes predictable.

Where data lives

Your program’s memory is, roughly, one very long row of numbered boxes. Two regions matter most:

The stack holds the local variables of each running function, in the frames you traced in the recursion lesson. Space is claimed when a function is called and released automatically when it returns. It is fast and tidy, but each item must be small and have a known size.
The heap is a large pool for data whose size is not known in advance, or that must outlive the function that created it: lists, strings that grow, objects. Space is requested while the program runs, and something must decide when it is no longer needed.

A typical picture, for a function holding a number and a list:

 stack (this function's frame)            heap
 +---------------------+          +-------------------+
 | count  = 3          |          |  [10, 20, 30]     |
 | scores = ---------------------->|                   |
 +---------------------+          +-------------------+

The number 3 sits directly in the variable. The variable scores holds an address, a reference to where the list lives on the heap. This is the single most important picture in the lesson. (How literally a language follows it varies. Python, for instance, treats even numbers as heap objects, but it behaves as though small immutable values were stored directly, which is all you need to reason about.)

Value semantics and reference semantics

When you assign one variable to another, there are two possibilities:

Value semantics: the contents are copied. Afterwards there are two independent values. Numbers, booleans and (in C) structs and arrays-inside-structs behave this way.
Reference semantics: only the address is copied. Afterwards there are two names for one thing on the heap. Lists, dictionaries and objects in Python, JavaScript and Java behave this way. This is called aliasing.

value semantics:      y = x           reference semantics:   b = a

x [ 5 ]                               a ----+
y [ 5 ]   two boxes                          +--> [1, 2, 3]   one list, two names
                                      b ----+

Changing the thing through one alias is visible through every other.

Python

x = 5
y = x            # numbers: a copy of the value
y = 6
print("x:", x, "y:", y)

a = [1, 2, 3]
b = a            # lists: a copy of the reference, one list
b[2] = 99
print("a after changing b:", a)

c = a.copy()     # a real copy: a second list
c[0] = 0
print("a after changing c:", a)
print("c:", c)

JavaScript

let x = 5;
let y = x;       // numbers: a copy of the value
y = 6;
console.log("x:", x, "y:", y);

const a = [1, 2, 3];
const b = a;     // arrays: a copy of the reference, one array
b[2] = 99;
console.log("a after changing b:", `[${a.join(", ")}]`);

const c = [...a]; // a real copy: a second array
c[0] = 0;
console.log("a after changing c:", `[${a.join(", ")}]`);
console.log("c:", `[${c.join(", ")}]`);

Java

import java.util.Arrays;

public class AliasDemo {
    public static void main(String[] args) {
        int x = 5;
        int y = x;                       // primitives: a copy of the value
        y = 6;
        System.out.println("x: " + x + " y: " + y);

        int[] a = {1, 2, 3};
        int[] b = a;                     // arrays: a copy of the reference, one array
        b[2] = 99;
        System.out.println("a after changing b: " + Arrays.toString(a));

        int[] c = Arrays.copyOf(a, a.length);   // a real copy: a second array
        c[0] = 0;
        System.out.println("a after changing c: " + Arrays.toString(a));
        System.out.println("c: " + Arrays.toString(c));
    }
}

#include <stdio.h>
#include <string.h>

static void show(const char *label, const int *arr, int n) {
    printf("%s [", label);
    for (int i = 0; i < n; i++) {
        printf("%s%d", i > 0 ? ", " : "", arr[i]);
    }
    printf("]\n");
}

int main(void) {
    int x = 5;
    int y = x;                 /* a copy of the value */
    y = 6;
    printf("x: %d y: %d\n", x, y);

    int a[3] = {1, 2, 3};
    int *b = a;                /* a pointer: another name for the same memory */
    b[2] = 99;
    show("a after changing b:", a, 3);

    int c[3];
    memcpy(c, a, sizeof a);    /* a real copy: new memory, same contents */
    c[0] = 0;
    show("a after changing c:", a, 3);
    show("c:", c, 3);
    return 0;
}

All four print:

x: 5 y: 6
a after changing b: [1, 2, 99]
a after changing c: [1, 2, 99]
c: [0, 2, 99]

y = x copied the number, so changing y left x alone. b = a copied only the reference, so the change made through b showed up in a. Only an explicit copy (copy(), [...a], Arrays.copyOf, memcpy) produced an independent list; the later change to c never touched a.

In C the pointer b is spelled out: you can see it is not an array but the address of one. The other languages hide the address behind the name, which is safer and exactly as real.

Aliasing through functions

When you pass a list to a function, the parameter receives a copy of the reference, so the function and the caller share one list. A function that changes the list in place changes the caller’s data. A function that merely re-points its parameter at a new list has no effect on the caller.

Python

def add_item(items):
    items.append("new")            # changes the caller's list


def replace_all(items):
    items = ["replaced"]           # re-points the local name only
    return items


basket = ["apple"]
add_item(basket)
print("[" + ", ".join(basket) + "]")
replace_all(basket)
print("[" + ", ".join(basket) + "]")

JavaScript

function addItem(items) {
  items.push("new");               // changes the caller's array
}

function replaceAll(items) {
  items = ["replaced"];            // re-points the local name only
  return items;
}

const basket = ["apple"];
addItem(basket);
console.log("[" + basket.join(", ") + "]");
replaceAll(basket);
console.log("[" + basket.join(", ") + "]");

Java

import java.util.ArrayList;
import java.util.List;

public class AliasFunction {
    static void addItem(List<String> items) {
        items.add("new");                          // changes the caller's list
    }

    static List<String> replaceAll(List<String> items) {
        items = new ArrayList<>(List.of("replaced"));   // re-points the local name only
        return items;
    }

    public static void main(String[] args) {
        List<String> basket = new ArrayList<>(List.of("apple"));
        addItem(basket);
        System.out.println(basket);
        replaceAll(basket);
        System.out.println(basket);
    }
}

#include <stdio.h>

static void add_item(const char **items, int *count) {
    items[*count] = "new";             /* changes the caller's array */
    (*count)++;
}

static const char **replace_all(const char **items) {
    static const char *replacement[1] = {"replaced"};
    items = replacement;               /* re-points the local pointer only */
    return items;
}

static void print_basket(const char **items, int count) {
    printf("[");
    for (int i = 0; i < count; i++) {
        printf("%s%s", i > 0 ? ", " : "", items[i]);
    }
    printf("]\n");
}

int main(void) {
    const char *basket[4] = {"apple"};
    int count = 1;
    add_item(basket, &count);
    print_basket(basket, count);
    replace_all(basket);
    print_basket(basket, count);
    return 0;
}

All four print:

[apple, new]
[apple, new]

add_item changed basket because both names point at one list. replace_all did not, because assigning to the parameter only moves the local name.

Shallow and deep copies

A shallow copy makes a new outer list, but the inner lists are still shared. A deep copy duplicates everything all the way down. Here a team is a list of two groups, [[1, 2], [3]]. Both copies are taken, then a 9 is added to the first group of the original.

Python

import copy

team = [[1, 2], [3]]
shallow = team.copy()
deep = copy.deepcopy(team)

team[0].append(9)
print("team:   ", team)
print("shallow:", shallow)
print("deep:   ", deep)

JavaScript

const show = (rows) => "[" + rows.map((r) => "[" + r.join(", ") + "]").join(", ") + "]";

const team = [[1, 2], [3]];
const shallow = [...team];
const deep = structuredClone(team);

team[0].push(9);
console.log("team:   ", show(team));
console.log("shallow:", show(shallow));
console.log("deep:   ", show(deep));

Java

import java.util.ArrayList;
import java.util.List;

public class ShallowDeep {
    public static void main(String[] args) {
        List<List<Integer>> team = new ArrayList<>();
        team.add(new ArrayList<>(List.of(1, 2)));
        team.add(new ArrayList<>(List.of(3)));

        List<List<Integer>> shallow = new ArrayList<>(team);   // new outer list, same inner lists
        List<List<Integer>> deep = new ArrayList<>();
        for (List<Integer> row : team) {
            deep.add(new ArrayList<>(row));                    // copy each level by hand
        }

        team.get(0).add(9);
        System.out.println("team:    " + team);
        System.out.println("shallow: " + shallow);
        System.out.println("deep:    " + deep);
    }
}

#include <stdio.h>
#include <string.h>

typedef struct {
    int items[4];
    int count;
} Row;

static void show(const char *label, Row *const rows[2]) {
    printf("%s [", label);
    for (int r = 0; r < 2; r++) {
        printf("%s[", r > 0 ? ", " : "");
        for (int i = 0; i < rows[r]->count; i++) {
            printf("%s%d", i > 0 ? ", " : "", rows[r]->items[i]);
        }
        printf("]");
    }
    printf("]\n");
}

int main(void) {
    Row first = {{1, 2}, 2};
    Row second = {{3}, 1};
    Row *team[2] = {&first, &second};

    Row *shallow[2];
    memcpy(shallow, team, sizeof team);        /* copies the two pointers: the rows are shared */

    Row first_copy = first;                    /* copies the rows themselves */
    Row second_copy = second;
    Row *deep[2] = {&first_copy, &second_copy};

    team[0]->items[team[0]->count++] = 9;
    show("team:   ", team);
    show("shallow:", shallow);
    show("deep:   ", deep);
    return 0;
}

All four show the same three lists:

team:    [[1, 2, 9], [3]]
shallow: [[1, 2, 9], [3]]
deep:    [[1, 2], [3]]

Appending to the first group of team showed up in shallow, because the inner list is the same one. deep is unaffected. JavaScript offers structuredClone(value) for a deep copy; Java has no built-in one, so you copy each level yourself or use a library; in C you copy each struct yourself.

A trap with default values

In Python, a default value such as bucket=[] is created once, when the function is defined, then shared by every call that omits the argument. Other languages avoid the trap in different ways.

Python

def collect(item, bucket=[]):
    bucket.append(item)
    return bucket


print(collect("a"))
print(collect("b"))


# The safe form: use None and make a fresh list inside.
def collect_safe(item, bucket=None):
    if bucket is None:
        bucket = []
    bucket.append(item)
    return bucket


print(collect_safe("a"))
print(collect_safe("b"))

Output

['a']
['a', 'b']
['a']
['b']

The second call returns both items: the “empty” default list was shared and kept growing. The None form builds a fresh list on every call.

JavaScript

function collect(item, bucket = []) {
  bucket.push(item);
  return bucket;
}

console.log(collect("a"));
console.log(collect("b"));

Output

[ 'a' ]
[ 'b' ]

JavaScript evaluates a default value again on every call, so a fresh array is made each time and there is no trap.

Java

Java has no default arguments, so this trap cannot occur. A method that wants an optional list is written twice (an overload), and the version without a list builds a new one itself.

C has no default arguments either. The nearest relative of this bug is a function that returns a pointer to a static buffer: every call hands back the same memory, so the second call overwrites the first call’s result.

Repeating a nested list

The same sharing appears when you build a grid by repeating one row.

Python

grid = [[0] * 2] * 2          # two references to the SAME row
grid[0][0] = 1
print(grid)

grid = [[0] * 2 for _ in range(2)]   # a fresh row each time
grid[0][0] = 1
print(grid)

JavaScript

const show = (rows) => "[" + rows.map((r) => "[" + r.join(", ") + "]").join(", ") + "]";

let grid = new Array(2).fill([0, 0]);          // two references to the SAME row
grid[0][0] = 1;
console.log(show(grid));

grid = Array.from({ length: 2 }, () => [0, 0]);   // a fresh row each time
grid[0][0] = 1;
console.log(show(grid));

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class GridRows {
    public static void main(String[] args) {
        // nCopies repeats ONE row object, so both entries are the same list.
        List<List<Integer>> grid = new ArrayList<>(Collections.nCopies(2, new ArrayList<>(List.of(0, 0))));
        grid.get(0).set(0, 1);
        System.out.println(grid);

        grid = new ArrayList<>();
        for (int i = 0; i < 2; i++) {
            grid.add(new ArrayList<>(List.of(0, 0)));   // a fresh row each time
        }
        grid.get(0).set(0, 1);
        System.out.println(grid);
    }
}

#include <stdio.h>

int main(void) {
    int row[2] = {0, 0};
    int *shared[2] = {row, row};            /* two pointers to the SAME row */
    shared[0][0] = 1;
    printf("[[%d, %d], [%d, %d]]\n", shared[0][0], shared[0][1], shared[1][0], shared[1][1]);

    int grid[2][2] = {{0, 0}, {0, 0}};      /* a real 2-D array: each row is its own memory */
    grid[0][0] = 1;
    printf("[[%d, %d], [%d, %d]]\n", grid[0][0], grid[0][1], grid[1][0], grid[1][1]);
    return 0;
}

All four print:

[[1, 0], [1, 0]]
[[1, 0], [0, 0]]

The first grid holds the same row twice, so a change to one row appears in both. The second builds each row separately.

Giving memory back

Heap memory is finite, so something must free what is no longer used. Languages take two approaches:

Automatic (garbage collection). The runtime finds heap data that nothing can reach any more and reclaims it. Python tracks how many references each object has and frees it at zero (with an extra pass for cycles); Java and JavaScript periodically trace what is reachable from the live variables. You never free anything, but you do not control exactly when it happens, and a collector costs some time.
Manual. In C you request memory with malloc and must return it with free. This gives you total control and no collector pauses, but all the responsibility.

Each program below puts three numbers on the heap and prints them. Only one of them has to give the memory back.

Python

values = [10, 20, 30]      # the list lives on the heap
print("heap:", *values)
# No cleanup: when nothing refers to the list any more, Python frees it.

JavaScript

const values = [10, 20, 30];   // the array lives on the heap
console.log("heap:", ...values);
// No cleanup: the garbage collector frees it once nothing can reach it.

Java

public class HeapDemo {
    public static void main(String[] args) {
        int[] values = {10, 20, 30};   // the array lives on the heap
        System.out.println("heap: " + values[0] + " " + values[1] + " " + values[2]);
        // No cleanup: the garbage collector frees it once nothing can reach it.
    }
}

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    int *values = malloc(3 * sizeof *values);   /* ask the heap for room for 3 ints */
    if (values == NULL) {
        return 1;                               /* the request can fail */
    }
    for (int i = 0; i < 3; i++) {
        values[i] = (i + 1) * 10;
    }
    printf("heap: %d %d %d\n", values[0], values[1], values[2]);

    free(values);                               /* give it back exactly once */
    values = NULL;                              /* and drop the stale address */
    return 0;
}

All four print:

heap: 10 20 30

Manual memory has three classic failure modes:

Leak: forgetting free, so the program slowly uses more and more memory.
Use after free: using a pointer after its memory was released. It might still appear to work, which is worse than crashing.
Double free: releasing the same block twice, which corrupts the allocator.

Setting a pointer to NULL after freeing it, as above, turns two of those into an obvious crash rather than silent damage. Newer languages such as Rust approach the problem differently, with rules checked at compile time, but that belongs to a language course.

Garbage-collected languages are not immune to memory trouble. A list that keeps growing, or a global cache that holds references forever, stays reachable, so the collector rightly keeps it. That is a memory leak of the logical kind.

Common pitfalls

Believing assignment copies a list or object. It copies the reference. Make a copy explicitly when you want independence.
Shallow copy of nested data. The inner structures are still shared. Use a deep copy, or copy each level.
Mutating an argument by accident. A function that sorts or appends to a parameter changes the caller’s data. Document it, or copy first.
Mutable default arguments in Python (def f(x, items=[])).
Repeating a nested list ([row] * n, fill(row), nCopies). Build each row separately.
In C, using memory after freeing it, or freeing it twice, or never freeing it.

ExercisePredict the aliasing

Without running them, say what each snippet prints. The five snippets are described in words; the code in the solution is in all four languages (C has no growable text, so it skips snippet 3).

Two names for one list [1, 2]; add 3 through the second name; print the first.
Two names for one list [1, 2]; point the second name at a new list made by adding 3 to the old one; print the first.
Two names for the text "hi"; add "!" to the second name; print the first.
A list of two lists [[1], [2]]; make a shallow copy; add 9 to the first inner list through the copy; print the original.
A list of two lists [[1], [2]]; make a shallow copy; replace the copy’s first inner list with [9]; print the original.

Show solution

[1, 2, 3]. Adding to the list changes the one shared list.
[1, 2]. Building a new list and re-pointing the second name leaves the original untouched.
hi. Text is immutable, so += builds a new string and re-points the second name.
[[1, 9], [2]]. The copy is shallow, so the copy’s first inner list and the original’s are the same list.
[[1], [2]]. Replacing the copy’s first entry changes which list the outer copy holds, not the inner list the original still holds.

Checking them:

Python

a = [1, 2]
b = a
b.append(3)
print(a)

a = [1, 2]
b = a
b = b + [3]
print(a)

a = "hi"
b = a
b += "!"
print(a)

a = [[1], [2]]
b = a.copy()
b[0].append(9)
print(a)

a = [[1], [2]]
b = a.copy()
b[0] = [9]
print(a)

JavaScript

const show = (rows) => "[" + rows.map((r) => (Array.isArray(r) ? "[" + r.join(", ") + "]" : r)).join(", ") + "]";

let a = [1, 2];
let b = a;
b.push(3);
console.log(show(a));

a = [1, 2];
b = a;
b = [...b, 3];
console.log(show(a));

let s = "hi";
let t = s;
t += "!";
console.log(s);

a = [[1], [2]];
b = [...a];
b[0].push(9);
console.log(show(a));

a = [[1], [2]];
b = [...a];
b[0] = [9];
console.log(show(a));

Java

import java.util.ArrayList;
import java.util.List;

public class AliasingPuzzles {
    public static void main(String[] args) {
        List<Integer> a = new ArrayList<>(List.of(1, 2));
        List<Integer> b = a;
        b.add(3);
        System.out.println(a);

        a = new ArrayList<>(List.of(1, 2));
        b = a;
        b = new ArrayList<>(b);
        b.add(3);
        System.out.println(a);

        String s = "hi";
        String t = s;
        t += "!";
        System.out.println(s);

        List<List<Integer>> outer = new ArrayList<>();
        outer.add(new ArrayList<>(List.of(1)));
        outer.add(new ArrayList<>(List.of(2)));
        List<List<Integer>> copy = new ArrayList<>(outer);
        copy.get(0).add(9);
        System.out.println(outer);

        outer = new ArrayList<>();
        outer.add(new ArrayList<>(List.of(1)));
        outer.add(new ArrayList<>(List.of(2)));
        copy = new ArrayList<>(outer);
        copy.set(0, new ArrayList<>(List.of(9)));
        System.out.println(outer);
    }
}

#include <stdio.h>
#include <string.h>

int main(void) {
    /* 1: a pointer is a second name for the same array */
    int a1[3] = {1, 2, 0};
    int *b1 = a1;
    b1[2] = 3;
    printf("[%d, %d, %d]\n", a1[0], a1[1], a1[2]);

    /* 2: pointing the second name somewhere new leaves the original alone */
    int a2[3] = {1, 2, 0};
    int new_list[3] = {1, 2, 3};
    int *b2 = a2;
    b2 = new_list;
    (void)b2;
    printf("[%d, %d]\n", a2[0], a2[1]);

    /* 4: copying an array of pointers shares the rows they point at */
    int row_a[2] = {1, 0};
    int row_b[2] = {2, 0};
    int *outer4[2] = {row_a, row_b};
    int *copy4[2];
    memcpy(copy4, outer4, sizeof outer4);
    copy4[0][1] = 9;
    printf("[[%d, %d], [%d]]\n", outer4[0][0], outer4[0][1], outer4[1][0]);

    /* 5: replacing the copy's pointer changes only the copy */
    int row_c[2] = {1, 0};
    int row_d[2] = {2, 0};
    int replacement[2] = {9, 0};
    int *outer5[2] = {row_c, row_d};
    int *copy5[2];
    memcpy(copy5, outer5, sizeof outer5);
    copy5[0] = replacement;
    printf("[[%d], [%d]]\n", outer5[0][0], outer5[1][0]);
    return 0;
}

The C program has no snippet 3, because plain C text cannot grow.

Python, JavaScript and Java print:

[1, 2, 3]
[1, 2]
hi
[[1, 9], [2]]
[[1], [2]]

The C program prints the same lines for snippets 1, 2, 4 and 5, with no hi line:

[1, 2, 3]
[1, 2]
[[1, 9], [2]]
[[1], [2]]

ExerciseFix the shared rows

This is meant to be a 3-by-3 board of zeros where setting one cell changes only that cell. The first attempt does not work. Why, and what is the fix? Expected result after setting row 1, column 1 to 5: [[0, 0, 0], [0, 5, 0], [0, 0, 0]].

Python

board = [[0] * 3] * 3
board[1][1] = 5
print(board)       # shows 5 in every row

JavaScript

const board = new Array(3).fill(new Array(3).fill(0));
board[1][1] = 5;
console.log(board);       // shows 5 in every row

Java and C arrays of arrays do not have this trap by default (new int[3][3] and int board[3][3] give three separate rows), so the fix below is the way to write it in all four languages.

Show solution

[[0] * 3] * 3 and fill(row) repeat the reference to a single inner list three times, so all three rows are the same list. Build each row separately:

Python

board = [[0] * 3 for _ in range(3)]
board[1][1] = 5
print(board)

JavaScript

const board = Array.from({ length: 3 }, () => new Array(3).fill(0));
board[1][1] = 5;
console.log("[" + board.map((row) => "[" + row.join(", ") + "]").join(", ") + "]");

Java

import java.util.Arrays;

public class BoardFixed {
    public static void main(String[] args) {
        int[][] board = new int[3][3];   // three separate rows
        board[1][1] = 5;
        System.out.println(Arrays.deepToString(board));
    }
}

#include <stdio.h>

int main(void) {
    int board[3][3] = {{0}};   /* three separate rows */
    board[1][1] = 5;
    printf("[");
    for (int r = 0; r < 3; r++) {
        printf("%s[%d, %d, %d]", r > 0 ? ", " : "", board[r][0], board[r][1], board[r][2]);
    }
    printf("]\n");
    return 0;
}

All four print:

[[0, 0, 0], [0, 5, 0], [0, 0, 0]]

ExerciseName the memory bug

In a C program, which of these is a leak, a use after free, or a double free? (a) free(p); printf("%d", *p); (b) p = malloc(100); p = malloc(200); with no free in between. (c) free(p); free(p); Expected: one label for each of the three.

Show solution

(a) Use after free: the pointer still holds the old address, but the memory is no longer yours. (b) A leak: the first block’s only address was overwritten, so it can never be freed. (c) Double free: the same block is released twice.

Summary

Local variables live on the stack and vanish when a function returns; larger, longer-lived data lives on the heap and is reached through a reference.
Assigning a number copies the value; assigning a list or object copies the reference, so both names share one thing until you make a real (deep, when nested) copy.
Garbage collectors free unreachable data for you; in C you call malloc and free yourself.

That completes the third module of the shared track. The next module turns to algorithms and how to reason about how fast they are, starting with Algorithmic thinking.