How Arrays Are Stored in Memory - Array Memory Model & Contiguous Storage | OneNoughtOne

0/364

Data Structures & AlgorithmsArray Memory Model & Contiguous Storage

Array Memory Model & Contiguous Storage

LevelBeginner

Duration55 mins

TopicArray Memory Model & Contiguous Storage

1 / 4

How Arrays Are Stored in Memory

The Foundation of Array Performance

Every programmer uses arrays daily. They're so fundamental that we often take them for granted—just another tool in the language's standard library. But beneath the surface of arr[5] lies a profound design decision that shapes nearly everything about how computers process collections of data.

The central question: When you write array[42], how does the computer find the 43rd element instantly, without examining the first 42? The answer isn't magic—it's a deliberate memory layout that transforms a mathematical index into a direct memory address. Understanding this mechanism unlocks deep insight into not just arrays, but memory management, CPU cache behavior, and performance optimization across all of software engineering.

What You Will Learn

By the end of this page, you will understand exactly how array elements are physically arranged in computer memory, why this arrangement is the key to array performance, and how this foundational knowledge applies to virtually every data structure you'll encounter in your career.

The Core Insight: Arrays Live in Contiguous Memory

At the most fundamental level, an array is a contiguous block of memory where each element occupies a known, fixed amount of space, and elements are placed immediately adjacent to one another with no gaps.

This single design decision—contiguity—is the source of virtually all array properties:

Fast random access — Because we know where the first element lives and how much space each takes, we can calculate any element's location instantly.
Predictable memory usage — An array of n elements always uses exactly n × (element size) bytes, plus minimal overhead.
Cache-friendly traversal — Modern CPUs load memory in chunks called "cache lines." Contiguous data means sequential access benefits from prefetching.
Fixed size (in static arrays) — The block must be allocated upfront, so you can't grow it without copying to a larger block.

Let's visualize this fundamental layout.

The Contiguity Principle

Think of an array like a row of mailboxes in an apartment building. Each mailbox is the same size, they're numbered sequentially, and they're physically placed side by side. If you know the address of mailbox #0 and the size of each mailbox, you can walk directly to any mailbox without checking the others.

Memory as a Linear Address Space

Before diving deeper into arrays, we need to understand how computer memory is organized. Modern computers present memory to programs as a linear address space—a conceptual model where memory is treated as a vast sequence of numbered locations.

Key properties of the address space:

Each byte has a unique address — Think of addresses like street numbers. Address 0 is the "first" byte, address 1000 is the 1001st byte, and so on.
Addresses are just integers — On a 64-bit system, addresses range from 0 to approximately 18.4 quintillion (2⁶⁴ - 1), though practical systems use far less.
Programs see virtual addresses — The operating system provides each program its own virtual address space, mapped to physical RAM by the hardware. This abstraction protects programs from each other.
Memory access is by address — When your program reads or writes data, it specifies an address (or a range of addresses), and the memory system retrieves or stores bytes at those locations.

Simplified Memory Address Visualization
Address	Contents	Interpretation
0x1000	0x48	Character 'H' (ASCII code 72)
0x1001	0x65	Character 'e' (ASCII code 101)
0x1002	0x6C	Character 'l' (ASCII code 108)
0x1003	0x6C	Character 'l' (ASCII code 108)
0x1004	0x6F	Character 'o' (ASCII code 111)
0x1005	0x00	Null terminator (end of string)

The table above shows how the string "Hello" might appear in memory. Each byte has a unique address (shown in hexadecimal), and the bytes are stored sequentially. This is exactly how arrays work—except array elements might be larger than a single byte.

The critical point: Memory addresses are numbers, and arithmetic operations on numbers are trivially fast for CPUs. This fact enables the efficient index-to-address conversion that makes arrays powerful.

Virtual vs Physical Memory

While programs see a clean, linear virtual address space, physical RAM may be fragmented across many locations. The Memory Management Unit (MMU) handles translation transparently. For our purposes, the linear model is accurate—arrays appear contiguous in the program's view of memory, which is what matters for understanding array algorithms.

Array Layout in Memory

Now let's see exactly how arrays occupy memory. When you declare an array, the runtime allocates a single contiguous block sized to hold all elements.

Example: An array of 5 integers (assuming 4 bytes per integer):

int arr[5] = {10, 20, 30, 40, 50};

In memory, this might appear as:

Memory Layout of int arr[5]
Index	Address Range	Bytes (hex)	Value
arr[0]	0x2000 - 0x2003	0A 00 00 00	10
arr[1]	0x2004 - 0x2007	14 00 00 00	20
arr[2]	0x2008 - 0x200B	1E 00 00 00	30
arr[3]	0x200C - 0x200F	28 00 00 00	40
arr[4]	0x2010 - 0x2013	32 00 00 00	50

Key observations from this layout:

Base address — The array starts at address 0x2000. This is the "base address" (often called arr or &arr[0]).
Element size — Each integer occupies exactly 4 bytes. Every element in the array uses the same amount of space—this uniformity is essential.
No gaps — There's no wasted space between elements. Address 0x2003 ends arr[0], and address 0x2004 immediately begins arr[1].
Predictable positions — arr[2] is at address 0x2008, which equals base (0x2000) + 2 × 4 (element size). This is not a coincidence—it's the fundamental formula.
Total size — The entire array occupies 20 bytes (5 elements × 4 bytes each). The allocation is exactly this size, no more, no less.

Little-Endian Byte Order

You might notice the bytes appear "backwards" (0A 00 00 00 for value 10). This is little-endian byte ordering, common on x86/x64 processors, where the least significant byte comes first. Big-endian systems store bytes in the opposite order. This detail matters for cross-platform development and binary file formats, but doesn't affect array indexing logic.

The "Base + Offset" Model

The contiguous layout enables a beautifully simple addressing scheme. Every array can be thought of as:

Base Address + (Index × Element Size) = Element Address

This is the fundamental formula that powers array access in virtually every programming language, CPU architecture, and runtime environment.

Let's trace a concrete example:

Given:

Base address of arr: 0x2000
Element size: 4 bytes
Target index: 3

Calculation:

address(arr[3]) = 0x2000 + (3 × 4)
                = 0x2000 + 12
                = 0x200C

Looking at our earlier table, arr[3] (value 40) does indeed start at address 0x200C. The formula works perfectly.

Why This Formula Is Revolutionary

•Constant-time operation — Multiplication and addition are single CPU instructions. No matter how large the array, the computation takes the same amount of time.
•No dependencies on other elements — Finding arr[1000000] doesn't require looking at arr[0] through arr[999999]. Each element stands alone.
•Hardware-optimal — CPUs are designed around arithmetic on integers. This formula maps directly to a few machine instructions.
•Predictable for compilers — Because the formula is fixed, compilers can generate highly optimized machine code for array access.

The Index Starts at Zero

Most languages start array indices at 0, not 1. This isn't arbitrary—it's mathematically natural. Index 0 means "0 elements away from the base," so address = base + 0 × size = base. The first element is at the base address with no offset. Zero-indexing directly reflects the underlying memory model.

Different Element Sizes

Arrays can store elements of any fixed size—1-byte characters, 2-byte shorts, 4-byte integers, 8-byte doubles, or even larger structures. The formula remains the same; only the size multiplier changes.

Example comparisons:

Address Calculation for Different Element Types
Type	Element Size	arr[0] Address	arr[5] Address (Base = 0x3000)
char	1 byte	0x3000	0x3000 + 5 × 1 = 0x3005
short	2 bytes	0x3000	0x3000 + 5 × 2 = 0x300A
int	4 bytes	0x3000	0x3000 + 5 × 4 = 0x3014
double	8 bytes	0x3000	0x3000 + 5 × 8 = 0x3028
struct (24 bytes)	24 bytes	0x3000	0x3000 + 5 × 24 = 0x3078

The pattern is universal: Regardless of what's stored, the address formula is simply base + index × size.

Implications for memory usage:

An array of 1,000,000 bytes occupies 1 MB.
An array of 1,000,000 32-bit integers occupies ~4 MB.
An array of 1,000,000 64-bit floating-point numbers occupies ~8 MB.
An array of 1,000,000 objects (each 256 bytes) occupies ~256 MB.

This predictability is both a strength (memory planning is straightforward) and a constraint (you must reserve all space upfront for static arrays).

Alignment Considerations

In practice, compilers often "pad" structures so elements align to memory boundaries (e.g., 4-byte or 8-byte boundaries). This affects the actual size used per element. A struct with a char and an int might occupy 8 bytes, not 5, due to padding. Array size calculations must use the actual stored size, not the sum of field sizes. This is handled automatically by sizeof() in C-family languages.

Visualizing Contiguous Memory

Let's build a stronger mental model through various visual representations.

The Linear View:

Imagine memory as a long tape divided into equal squares. Each square is one byte. An array occupies a consecutive section of this tape:

Memory tape:
... | | | |[arr[0]  ][arr[1]  ][arr[2]  ][arr[3]  ][arr[4]  ]| | | ...
         ↑                                                    ↑
      Base                                              End of array
      Address

For a 4-byte integer array, each "[arr[n]]" block spans 4 adjacent squares.

The Grid View:

We can also visualize larger arrays as a grid, though physically they're still linear:

Logical 2D view (for human understanding):
              Col 0    Col 1    Col 2    Col 3
Row 0:      [   0  ] [   1  ] [   2  ] [   3  ]
Row 1:      [   4  ] [   5  ] [   6  ] [   7  ]
Row 2:      [   8  ] [   9  ] [  10  ] [  11  ]

Physical 1D layout in memory:
[0][1][2][3][4][5][6][7][8][9][10][11]

This grid-to-linear mapping becomes crucial when we discuss multi-dimensional arrays.

The Ruler Analogy

Think of array memory like a ruler. The base address is the "0" mark. Each element occupies a fixed length on the ruler. To find element N, you measure N × (element length) from the zero mark. This is why we can jump directly to any element—we're doing arithmetic on a ruler, not walking step by step.

Physical vs. Logical Arrangement

It's important to distinguish between the logical view of an array (how programmers think about it) and the physical view (how it exists in memory).

Logical View:

An ordered sequence of elements
Indexed from 0 to n-1
Elements have a meaningful order (first, second, third...)
Operations like "get element at position 5" are natural

Physical View:

A contiguous block of bytes
Starts at a base address
Element boundaries occur at regular intervals
Access requires address calculation

The power of arrays comes from the tight correspondence between these views. The logical index directly maps to a physical offset, creating a data structure that matches how programmers think and how hardware operates.

Logical Properties

•Elements are numbered 0 to n-1
•The "first" element is at index 0
•Order is meaningful and preserved
•Size is the number of elements
•Access syntax: arr[i]

Physical Properties

•Block starts at base address
•First element at offset 0
•Bytes are adjacent with no gaps
•Size in bytes = n × element_size
•Access by: base + i × size

Why this alignment matters:

When logical operations ("get element 5") map directly to efficient physical operations ("read bytes at address base + 20"), there's no translation overhead. This is why arrays are often called a "hardware-native" data structure—they align perfectly with how CPUs access memory.

The Role of the Base Address

The base address is the starting point of the array—the memory location of the first element. This single value is the reference point for all array operations.

What the base address provides:

Identity — The base address uniquely identifies the array in memory. Two arrays with different base addresses are different arrays, even if they contain identical data.
Anchor for calculation — All index-to-address conversions reference the base. Without knowing the base, you cannot access any element.
Pointer representation — In C-family languages, the "name" of an array (e.g., arr) evaluates to its base address. This is why arrays and pointers are so closely related in C.
Memory management target — When an array is deallocated, it's the base address that's freed. The runtime uses this to return the entire block to available memory.

Base Address Concepts
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdio.h>
 
int main() {
    int arr[5] = {10, 20, 30, 40, 50};
    
    // 'arr' evaluates to the base address
    printf("Base address (arr):     %p
", (void*)arr);
    
    // &arr[0] is also the base address
    printf("Address of arr[0]:      %p
", (void*)&arr[0]);
    
    // These are always identical
    printf("Are they equal? %s
", (arr == &arr[0]) ? "Yes" : "No");
    
    // Address of element 3
    printf("Address of arr[3]:      %p
", (void*)&arr[3]);
    
    // Pointer arithmetic: arr + 3 gives same result
    printf("arr + 3:                %p
", (void*)(arr + 3));
    
    return 0;
}
 
/* Possible output (addresses vary):
Base address (arr):     0x7ffd12345678
Address of arr[0]:      0x7ffd12345678
Are they equal? Yes
Address of arr[3]:      0x7ffd12345684
arr + 3:                0x7ffd12345684
*/

Arrays and Pointers in C

In C, arrays "decay" to pointers to their first element in most contexts. This design reflects the base-address model: an array is essentially described by where it starts. Other languages hide this detail, but the underlying mechanism is the same.

What Contiguity Prohibits

The contiguous memory model that makes arrays fast also imposes fundamental constraints. Understanding these limitations explains why other data structures exist and when arrays aren't the right choice.

Constraints imposed by contiguous storage:

What Arrays Cannot Do Efficiently

•Grow dynamically without moving — Adding to a full array requires allocating a larger block and copying all existing elements. You can't just "extend" the existing block because adjacent memory may be in use.
•Shrink to reclaim memory — Removing elements doesn't automatically return memory. The block remains its original size unless you explicitly reallocate.
•Insert in the middle efficiently — Inserting at position k requires shifting elements k+1 through n-1 to make room. This is O(n) work for O(1) insertion.
•Delete from the middle efficiently — Deleting from position k requires shifting elements k+1 through n-1 down. Again, O(n) work.
•Have variable-sized elements — Every element must be the same size for the address formula to work. Storing strings of different lengths requires indirection (storing pointers to strings).

These constraints aren't bugs—they're the necessary cost of O(1) random access. Every data structure makes tradeoffs. Arrays optimize for access speed at the cost of flexibility. Understanding this tradeoff is essential for choosing the right structure for each problem.

When Constraints Become Features

The "fixed size" constraint is an advantage when memory predictability matters, such as in embedded systems or real-time applications. Similarly, guaranteed contiguity enables memory-mapped I/O and efficient bulk transfers. Constraints define the use case, not just the limitations.

Summary: The Memory Model Foundation

We've established the foundational understanding of how arrays exist in memory. This isn't abstract theory—it's the concrete reality that explains every performance characteristic of arrays.

Key Takeaways

•Arrays are contiguous blocks — Elements are stored immediately adjacent to each other with no gaps, starting from a base address.
•Memory is a linear address space — Each byte has a unique numeric address, and arithmetic on addresses is trivially fast.
•The formula is everything — Address = Base + (Index × Element Size). This simple arithmetic enables O(1) access.
•Element size must be uniform — Every element occupies the same space, enabling the offset calculation to work.
•Contiguity has costs — Fixed size, expensive insertions/deletions, and inability to grow in place are the price of fast access.
•Base address is the anchor — All array operations reference this starting point; it uniquely identifies the array.

What's next:

Now that we understand the basic memory layout, we'll dive deeper into contiguous memory allocation—examining how memory is reserved for arrays, what happens in different allocation scenarios (stack vs. heap), and the full implications of the contiguity requirement for system design and performance.

Page Complete

You now understand the fundamental memory model that makes arrays one of the most efficient data structures in computing. This knowledge applies universally—every language, every platform, every system uses this same underlying model. Next, we'll explore contiguous memory allocation and its far-reaching implications.