Memory

Why Do We Need to Understand Memory?

When you write:

int score = 100;

it may look like the computer simply remembers that score is 100.

It does not.

The program needs somewhere to store that value while it is running. That place is memory.

Understanding memory helps explain many things that become important in DSA:

• Why different data types require different amounts of space
• Why arrays are stored differently from linked lists
• What a memory address is
• Why accessing some data is faster than other data
• Why recursion can eventually cause a stack overflow
• Why some data remains available after a function finishes

You do not need to understand the hardware in detail.

You only need a clear mental model of how your program uses memory.

What Is Computer Memory?

Think of RAM as a huge collection of small storage locations. When your program runs, it uses part of this memory to store the information it needs.

Bits and Bytes

Everything stored in computer memory is represented using bits.

A bit can have one of two values: 0 or 1. Eight bits make one byte, so 10110101 is one byte containing eight bits.

The byte is the unit that gets an address. Memory is byte-addressable: every single byte has its own number, not every bit and not every variable. That is why a 4-byte integer occupies four consecutive addresses rather than one, and it is what makes the address arithmetic later in this chapter work.

Memory is commonly described using larger units:

These units help us describe how much memory is available or how much space a program or piece of data requires.

Memory Has Addresses

If memory contains millions or billions of storage locations, how does the computer know where a particular value is stored?

Each addressable location has an address.

The number identifies where something is stored. The value is what is stored there.

Address → WhereValue   → What

Memory addresses are often displayed in hexadecimal notation, such as 0x1000 or 0x1001. You normally do not need to work with these addresses directly. The programming language handles most of this for you.

Variables and Memory

Consider:

int score = 100;

There are three important ideas here:

int       → typescore     → variable name100       → value

The program stores the value somewhere in memory. The variable gives your program a convenient way to refer to that stored value.

You do not need to remember the actual memory address. Instead of saying "read the value at address 0x7FFE...", you can simply write score.

That is one of the reasons variables make programming practical.

What Happens When a Variable Changes?

Suppose:

int score = 100;score = 50;

The program updates the value associated with score.

Before          After score           score  ↓               ↓[ 100 ]         [  50 ]

The exact behavior underneath depends on the language and its runtime, but the important idea is simple:

Assignment changes the value associated with a variable.

How Data Types Affect Memory

This connects directly to the Data Types chapter.

Different types can require different amounts of memory and use different representations. int, double, char and boolean do not necessarily use memory in the same way.

A simplified example:

int┌────┬────┬────┬────┐│    │    │    │    │└────┴────┴────┴────┘       4 bytes double┌────┬────┬────┬────┬────┬────┬────┬────┐│    │    │    │    │    │    │    │    │└────┴────┴────┴────┴────┴────┴────┴────┘                 8 bytes

The exact size depends on the language and type.

The type also determines how the stored bits should be interpreted. An integer and a floating-point value use different representations even though both ultimately consist of bits. This is why knowing the data type is important.

The Same Bits Can Mean Different Things

Memory itself does not contain labels saying "this is an integer" or "this is a character". It contains bits.

The program interprets those bits according to the type and representation being used. For example, 01000001 can represent the character 'A' under a character encoding such as ASCII.

The key idea is:

Bits are the representation; the type and encoding determine how those bits are interpreted.

You do not need to memorize binary representations at this stage.

Contiguous Memory

Some data is stored in contiguous memory, meaning the elements are placed next to one another. An array is the classic example.

[10] [20] [30] [40] ↑    ↑    ↑    ↑1000 1004 1008 1012

If each integer occupies 4 bytes, the next element sits at the next 4-byte position. That regularity is the whole trick, because it means an element's address can be calculated rather than searched for:

address = base + index × size numbers[2] → 1000 + 2 × 4 = 1008

Three numbers the program already has, one multiplication, one addition. It takes the same amount of work whether you ask for numbers[2] or numbers[2000000], which is exactly what O(1) access means.

It also explains the thing the next section is about. A linked list has no such formula: its nodes are wherever the allocator put them, so there is nothing to calculate and the only way to reach the hundredth node is to walk the ninety-nine in front of it.

We will explore this in detail when we study Arrays.

Non-Contiguous Memory

Other structures do not require their elements to sit next to each other. A linked list is a classic example: the nodes can exist at different memory locations while references connect them.

This gives linked lists different performance characteristics from arrays.

You do not need to understand the references yet. For now, remember:

Array       → typically contiguousLinked List → nodes can be non-contiguous

This difference becomes extremely important in DSA.

Why Memory Layout Matters

Two structures can store the same values but organize them differently in memory.

Both contain 10, 20, 30, 40, 50, but their memory layouts are different. That difference affects access time, insertion and deletion, memory usage, and cache performance.

This is one of the central ideas behind Data Structures:

Choosing a data structure means choosing how your data is organized and what operations you want to make efficient.

A Small Look at CPU Cache

There is one more reason memory layout matters.

The CPU is much faster than RAM. To reduce the time spent waiting for data, modern CPUs use small, fast memory called cache. When the CPU accesses some data, it may also load nearby data into the cache.

This works particularly well when data is stored close together.

[10][20][30][40][50][60] ↑CPU accesses 10 ↓Nearby values may already be available

This is called cache locality.

Because array elements are typically stored next to one another, sequential array access often makes good use of the CPU cache. Linked-list nodes can be scattered throughout memory, making sequential traversal less cache-friendly.

You do not need to memorize the hardware details. Just remember:

Data that is stored close together can often be accessed more efficiently by modern CPUs.

Memory Allocation

When a program needs memory, that memory has to be allocated. Allocation means reserving memory for data.

For example, when you create an array:

int[] numbers = new int[100];

the program needs enough memory to store 100 integers. The memory required depends on the type and the number of elements.

Memory can also be released when it is no longer needed. How allocation and release are handled depends heavily on the programming language.

We will study the different memory regions and their lifetimes in the next chapters.

Memory Is Limited

Memory is not infinite. A program that keeps allocating more and more memory will eventually run into a limit.

This is why memory usage matters when designing algorithms. Consider two solutions:

Solution A → O(n) extra spaceSolution B → O(1) extra space

If both solve the problem correctly, Solution B may use significantly less additional memory.

We will study this systematically in Space Complexity.

Memory and Data Structures

Now the connection to DSA becomes clear. Different data structures organize memory differently.

The layout influences the operations that are efficient. An array gives fast indexed access; a linked list gives efficient insertion and deletion at known positions when references are available.

There is no universally "best" data structure. The right choice depends on what operations your program needs to perform efficiently.

Common Misconceptions

Quick Check

Quick Recap

• RAM is temporary working memory used by running programs.
• Memory is built from bits, and 8 bits make one byte.
• Addressable memory locations have addresses that identify where data is stored.
• Variables provide a convenient way for programs to work with values without manually managing addresses in most cases.
• Data types influence how values are represented and how much memory they may require.
• Arrays typically use contiguous memory, while linked structures can use non-contiguous memory.
• Memory layout affects performance, including cache locality.
• Memory is limited, so efficient memory usage matters in DSA.
• Different data structures organize memory differently because they optimize for different operations.

Where This Leads

You now have the basic mental model:

Program   ↓Memory   ↓Values + Variables   ↓Memory Layout   ↓Data Structures

But there is an important question left:

Where does a variable live while a function is running, and what happens to it when the function finishes?

To answer that, we need to understand two important areas of memory: Stack and Heap.