Memory

Why we need to talk about memory

This is the chapter that makes the previous seven click into place. It is also the reason you can understand why an array is fast, instead of memorising that it is.

Bits, bytes, and where types come from

Now go back to data types. An integer overflows because it only got 4 lockers, and 4 lockers can only count so high. A double is more precise than a float because it was given twice the space.

A data type is really just a decision about how many lockers to reserve and how to read what is inside them.

Two areas that behave differently

Your program does not treat memory as one big pile. It splits it in two.

The stack is small, fast and completely automatic. It holds local variables and the record of which functions are currently running. Call a function and a frame is pushed on top holding that function's locals; the function finishes and its frame is popped off, and everything inside it disappears instantly.

That is why local variables vanish when a function ends. It is not a rule somebody invented. It is what happens when the frame is popped.

The heap is large, flexible and slower. It holds things whose size is not known in advance, or that need to outlive the function that created them: lists, objects, strings.

The mystery from the variables chapter

Here is that confusing example again, and now you have the tools for it.

x = [1, 2, 3]y = xx.append(4)print(y)      # [1, 2, 3, 4]

The list itself lives on the heap. The variable x does not hold the list - it holds the list's address, and that address sits on the stack. So y = x copied the address. Two name tags, one box.

A plain number is small and fixed in size, so it sits directly on the stack and b = a copies the actual value. Two separate boxes, no connection.

One sentence: small values are copied, big things are shared by address. When you genuinely want a separate copy of a list you have to ask for one, with y = x.copy() or the equivalent.

Why an array is fast

This is the payoff. Everything above was building to it.

An array's items sit in one continuous run of lockers, back to back with no gaps. Each int takes 4 bytes, so each item is exactly 4 addresses further along. Which means when you ask for arr[3] the computer does not go looking for it. It calculates:

address = start + (index x size)address = 1000 + (3 x 4)address = 1012

One multiplication, one addition, done. It takes the same time to reach item 3 as item 3,000,000.

That is what O(1) access means. Not that the computer is clever. Just arithmetic on an address.

A linked list's nodes are scattered anywhere on the heap, joined by addresses. There is no formula, because the nodes are not evenly spaced, so to reach the fourth node you start at the head and follow three links. That is O(n), and it is O(n) because of physical layout rather than a rule in a textbook.

Cleaning up

Stack memory handles itself. Heap memory has to be released, and languages take two approaches.

Manual (C, C++): you allocate, you free. Full control and full responsibility.

Automatic (Java, Python, JavaScript, Go): a garbage collector runs in the background, finds heap objects nothing points to any more, and reclaims them. Easier and safer, at the cost of a small occasional pause.

Two problems worth knowing by name. A memory leak is heap memory you allocated, never released, and no longer have a reference to - occupied but unreachable. A dangling pointer is memory you freed but kept using the address of; the locker belongs to something else now.

Why this chapter matters for everything next

Every claim in a data structures course rests on this page.

• Arrays give O(1) access because items sit in a continuous block and the address is a calculation
• Linked lists are O(n) to search because nodes are scattered and you must follow addresses one at a time
• Inserting into an array is O(n) because continuous memory means everything after the gap has to physically shift
• Inserting into a linked list is cheap because nothing moves, you just rewrite two addresses
• Recursion crashes with stack overflow because the stack is small and every call pushes a frame

None of those are facts to memorise. They all fall out of how memory is physically arranged.

Mistakes to watch for

Quick recap

• Memory is a long line of numbered, byte-sized lockers
• A data type decides how many to reserve and how to read them
• The stack is small, fast and automatic. It holds locals and function frames
• The heap is large and flexible. It holds objects and lists
• Small values are copied. Big things are shared through their address
• Arrays are fast because their items are continuous and the address is a calculation