How Memory Works
Understand RAM, addresses, contiguous vs non-contiguous storage, and why memory layout affects performance.
What Is It?
Before you can truly understand data structures, you need to understand where they live: memory.
Your computer's RAM (Random Access Memory) is a giant list of numbered storage slots. Each slot holds a small, fixed amount of data — one byte. Each slot has a unique address — a number that identifies its location, like a house number on a street.
When a program creates a data structure, it's really just claiming a group of these slots and writing values into them. The arrangement of those slots — whether they're side by side or scattered around — is what makes one data structure different from another.
Analogy
The Hotel Hallway
Imagine an infinitely long hotel hallway. Every room has a number on the door: Room 0, Room 1, Room 2, and so on. Each room is the exact same size and can hold exactly one small piece of information.
This hallway is your RAM. Each room is a memory slot. The room number is the address.
Now imagine you need to store a group of 5 friends:
- Contiguous storage (array): You book rooms 100, 101, 102, 103, 104 — five rooms in a row. If someone asks "where is friend #3?", you instantly know: Room 100 + 3 = Room 103. No searching required.
- Scattered storage (linked list): Your friends book whatever rooms they can find: Room 47, Room 203, Room 8, Room 991, Room 512. But each friend leaves a note on their door saying which room the next friend is in. To find friend #3, you start at Room 47, read the note ("go to 203"), go there, read the next note ("go to 8"), and arrive at Room 8.
Contiguous is faster for jumping to a specific position. Scattered is more flexible when you don't know how many rooms you'll need in advance.
How It Works
RAM: A Giant Numbered Array
Here's what RAM looks like at the hardware level:
Larger values span multiple cells — a 32-bit integer uses 4 consecutive bytes
Each slot holds one byte (values 0 to 255). Larger values span multiple slots. A standard integer uses 4 consecutive slots.
How the CPU Reads Memory
When your program says "read the integer at slot 1000", the CPU goes to slot 1000 and reads the bytes stored there. This takes a fixed amount of time regardless of which slot you ask for — that's the "Random Access" in RAM. Slot 0 and slot 1,000,000 take the same time to read.
Contiguous vs. Scattered Memory
To find element [3]: address = 200 + (3 × 4) = 212 — instant calculation
To find element [2]: start at location 200, follow pointer to location 520, follow pointer to location 108 — must walk the chain
Pointers and References
A pointer is just a number that represents where something is stored in memory. When a linked list node has a "next pointer" with the value 520, it means "the next node is stored at location 520." That's all a pointer is — a number that tells you where to go.
Pointers take up space too. Each pointer is typically 8 bytes. So every linked list node uses extra memory just to store the address of the next node.
Examples
Example 1: Storing an array of 4 integers
When you declare an array of four integers with values [5, 12, 8, 3]:
Each integer = 4 bytes. Address of element [i] = 400 + (i × 4)
Accessing array[2]: address = 400 + (2 × 4) = 408. Go to address 408, read 4 bytes — value is 8.
Example 2: How a pointer connects two nodes
Node A — address 300
- data: 42 (bytes 300–303)
- next: 700 (bytes 304–311)
- The pointer 700 is just a number — the address of Node B
points to Node B at address 700
Node B — address 700
- data: 99 (bytes 700–703)
- next: NULL (bytes 704–711)
- Pointer is 0 (null) — no next node
end of the chain
Node A doesn't directly "contain" Node B. It just stores the number 700. The program reads that number as an address and goes there to find Node B.
Common Mistakes
- Thinking some memory addresses are faster to reach than others. RAM access time is the same for every address — that's what "random access" means. Address 5 and address 5,000,000 take exactly the same time to read.
- Forgetting that pointers take up space. A linked list node storing a single 4-byte integer plus an 8-byte pointer is using twice as much memory for the pointer as for the actual data. For large collections of small values, this overhead adds up fast.
- Thinking scattered memory is always fine. Arrays and linked lists can both hold the same data, but reading through a linked list one node at a time is noticeably slower in practice because each node could be anywhere in memory.
Best Practices
- When you need fast access to any element by position, use contiguous storage (arrays)
- When you need to insert or remove elements frequently without shifting others around, linked structures are worth the pointer overhead
- Always think about where your data lives in memory — the layout directly affects how fast your code runs
- Keep pointer overhead in mind: a linked list of small values can use more memory for pointers than for actual data