Memory, References, and Pointers
Stack versus heap, what a pointer or reference really is, how garbage collection reclaims memory, and how aliasing works in Python and JavaScript.
beginner40 min#memory#references#pointers#heap#stack#garbage-collection#aliasing
Prerequisites: How Computers Run Programs
Why it matters
Linked lists, trees, graphs, and hash tables are all built from objects that point at other objects. Bugs like "I changed one list and another changed too", "my default argument remembers old data", or "memory keeps growing" are all questions about references. Once you see memory as a set of boxes and arrows, those bugs become easy to predict.
Intuition
Memory is a very long street of numbered mailboxes. Each mailbox holds a small value (one byte). A pointer is just a number: the address of a mailbox. A reference is a pointer with safety rails; you cannot do arithmetic on it or aim it at random places.
Think of a house and its street address. A friend with the address can visit the house and repaint it. If you give a second friend the same address, they both reach the same house, and repainting it by one is visible to the other. Writing down the address on another slip of paper does not build a second house. Building a second house is a copy.
variables heap (objects)
a ----+
+---> [ 1, 2, 3 ]
b ----+
c -------> [ 1, 2, 3 ] (a copy: separate object, equal contents)
Here a and b are aliases for one list. c equals them but is a different object.
How it works
Stack versus heap
- Stack: memory for function calls. Local variables live in a frame that is created on call and destroyed on return. Allocation is just moving a pointer, so it is extremely fast, but sizes must be known and lifetimes end with the function.
- Heap: memory for objects that must outlive the call or whose size is only known at run time. Allocation needs bookkeeping to find free space, and something must decide when it is no longer needed.
In C, you choose: a local int x goes on the stack; malloc(100) returns heap memory that you must free yourself. Forget to free and you leak; free twice or use after freeing and you get undefined behavior, one of the main sources of security bugs.
In Python and JavaScript, you never choose. Every object (lists, dicts, class instances, functions, even integers conceptually) lives on the heap, and variables hold references to them. The stack holds only the frames and those references.
Garbage collection
Managed languages free memory for you. Two main strategies:
- Reference counting: each object tracks how many references point to it, and it is freed when the count reaches zero. CPython does this. It frees memory immediately but cannot reclaim cycles (two objects pointing at each other), so Python adds a backup cycle collector.
- Tracing (mark and sweep): start from roots (global variables, the current stack) and mark everything reachable. Anything unmarked is garbage and is swept away. V8, the JVM, and Go use variants of this, often generational: most objects die young, so new objects are checked more often than old ones.
The practical rule: an object stays alive as long as something reachable still references it. A "memory leak" in a managed language is usually a forgotten reference, such as an ever-growing cache or global list.
Identity, equality, and mutation
Two questions are easy to confuse.
- Equality: do two objects have the same contents? (
==in Python, loose and strict equality for primitives in JavaScript) - Identity: are they the very same object? (
isandid()in Python;===on objects in JavaScript)
Python's id(x) returns an integer that is unique for the object while it lives (in CPython it is its memory address). a is b compares those ids. JavaScript has no id(), but === on two objects checks whether they are the same reference. For primitives (numbers, strings, booleans), compare by value.
Another key idea is mutability. Lists, dicts, and sets (Python) and arrays and objects (JavaScript) can be changed in place, so aliases see the change. Python's ints, strings, and tuples, and JavaScript's primitives, cannot be changed in place; "modifying" them rebinds the name to a new value, so aliasing is harmless.
Arguments follow the same rule. Python and JavaScript both pass the reference by value: the function gets its own name pointing at the same object. Mutate the object and the caller sees it; rebind the name and the caller does not.
| Operation | Time | Notes |
|---|---|---|
| Assign a reference (b = a) | O(1) | Copies an address, not the object |
| Shallow copy of list of n items | O(n) | New outer list, same inner objects |
| Deep copy | O(total size) | Copies everything reachable |
| Stack allocation | O(1) | Move the stack pointer |
| Mark and sweep collection | O(live objects) | Tracing cost depends on what survives |
Code: aliasing, copies, and the default argument trap
This program shows an alias, a shallow copy, the shared inner list inside a shallow copy, and a safe replacement for a mutable default argument. To print the same text in both languages we compare by JSON.
import json
def show(*vals):
print(" ".join(json.dumps(v, separators=(",", ":")) for v in vals))
a = [1, 2]
b = a # second name, same list
b.append(3)
show(a, a is b)
c = list(a) # shallow copy: new outer list
show(c == a, c is a)
nested = [[0], [0]]
shallow = list(nested)
shallow[0].append(9)
show(nested, nested[0] is shallow[0])
def add_item(item, bucket=None):
if bucket is None:
bucket = []
bucket.append(item)
return bucket
x = add_item(1)
y = add_item(2)
show(x, y, x is y)const show = (...vals) => console.log(vals.map((v) => JSON.stringify(v)).join(" "));
const a = [1, 2];
const b = a; // second name, same array
b.push(3);
show(a, a === b);
const c = [...a]; // shallow copy: new outer array
show(JSON.stringify(c) === JSON.stringify(a), c === a);
const nested = [[0], [0]];
const shallow = [...nested];
shallow[0].push(9);
show(nested, nested[0] === shallow[0]);
function addItem(item, bucket = []) {
bucket.push(item);
return bucket;
}
const x = addItem(1);
const y = addItem(2);
show(x, y, x === y);Both versions print:
[1,2,3] true
true false
[[0,9],[0]] true
[1] [2] false
Line 1: appending through b changed what a sees. Line 2: the copy is equal but not identical. Line 3: the shallow copy duplicated only the outer list, so the first inner list is shared and the change leaked into nested. Line 4: each call got a fresh bucket, so the results are independent.
Here is lines 1 and 2 of that program, one statement at a time.
b = a copies only the arrow. The append changes the single shared object, so a sees it. list(a) is the step that builds a second object.
Common pitfalls
- Assuming assignment copies:
b = acreates an alias. Uselist(a),a[:],copy.deepcopy, or[...a],structuredClone(a)when you need a copy. - Shallow copy surprises: copying a list of lists shares the inner lists. Use a deep copy, or build each row separately. The classic bug is
[[0] * 3] * 3, which makes three references to one row. - Using
isfor value comparison:ischecks identity. Small ints and interned strings may appear to work by accident in CPython, which hides the bug. Use==for values andisforNone. - Memory leaks via forgotten references: caches, event listeners, and global lists keep objects alive. Remove or bound them.
- Mutating arguments by accident: a function that sorts its input in place changes the caller's data. Copy first or document it.
Practice
Predict the output easy
Hint
Draw the boxes and arrows before running it.
Show solution
a = [1]; b = a; b = b + [2]; print(a). The expression b + [2] builds a new list and rebinds b to it, so a is still [1]. Compare with b.append(2) (or b += [2], which extends in place for lists), where a would change. Rebinding versus mutating is the whole story.
Fix the grid medium
Hint
How many different row objects does the multiplication create?
Show solution
grid = [[0] * 3] * 3; grid[0][0] = 1 sets the first cell of every row because all three rows are one object. Build it with a comprehension: grid = [[0] * 3 for _ in range(3)], which runs the inner expression once per row and yields three separate lists. In JavaScript use Array.from({ length: 3 }, () => [0, 0, 0]).
Detect a cycle in a linked list medium
Hint
Two references moving at different speeds will meet if there is a loop.
Show solution
Use Floyd's tortoise and hare: slow advances one node, fast advances two. If fast reaches the end there is no cycle; if fast and slow become the same object (identity!) there is one. O(n) time, O(1) space, versus O(n) space for a set of visited nodes. This also shows why reference counting struggles with cycles.
Implement deep copy for nested lists hard
Hint
Recursion: copy lists recursively, return other values as they are. What about a list that contains itself?
Show solution
Write deep(x): if x is a list, return [deep(i) for i in x], else return x. It is O(total size) time and space. A self-referencing list would recurse forever, so production implementations keep a dictionary from id(original) to its copy and reuse the copy when they meet the same object again. That memo table is how copy.deepcopy preserves shared structure and cycles.
Interview questions
- What is the difference between stack and heap memory? The stack holds call frames with automatic, last-in first-out lifetime and very fast allocation. The heap holds objects with flexible lifetime that something must free or collect.
- Is Python pass by value or pass by reference? Neither exactly: it passes object references by value. A function can mutate a shared object but cannot rebind the caller's variable.
- How does garbage collection work? Reference counting frees at zero count; tracing collectors mark from roots and sweep the rest. Cycles need a tracing pass.
- Shallow versus deep copy? Shallow copies the container only; deep copies everything reachable.
Interviewers look for: drawing the picture with arrows, naming aliasing as the source of the bug, and knowing when to copy.
Quick check
In Python, after `a = [[1], [2]]` and `b = list(a)`, you run `b[0].append(5)`. What is true?
Finished this lesson?
Further resources
- Reference (computer science) (Wikipedia) (article)
- Garbage collection (Wikipedia) (article)
- Python data model: objects, values and types (docs)
- MDN: Memory management (docs)