Skip to main content
Be Bitwise

Arrays: Contiguous Memory

Arrays, Lists & Data Structures · Coding Fundamentals track

6 min read

In this module

Storing Collections of Data

A single variable holds a single value. Programs almost never deal with one piece of data, though. You might be juggling a list of student grades, a sequence of sensor readings, or a buffer of bytes pulled off a network socket. An array is the simplest and most fundamental way to store a collection of values.

An array is a contiguous block of memory carved into equally sized slots. Each slot holds one element, and each element is identified by its index — a number for its position, typically starting at 0.

text
grades = [92, 85, 78, 95, 88]
// [0] [1] [2] [3] [4]
print(grades[0]) // 92 (first element)
print(grades[3]) // 95 (fourth element)

Why Contiguous Memory Matters

Array elements sit shoulder-to-shoulder in memory with no gaps between them. If the array starts at address 1000 and each element is 4 bytes:

  • grades[0] is at address 1000
  • grades[1] is at address 1004
  • grades[2] is at address 1008
  • grades[n] is at address 1000 + (n * 4)

Step through the five grades below and watch the formula pick out each slot. The strip labels addresses in hex, so 1000 shows up as 0x3e8. Each grade is stored least significant byte first, the way x86-64 does it, which is why 92 appears as 5c 00 00 00.

grades[0..4], 4 bytes each, starting at address 1000

Starts at 0x3e8; small numbers under each byte are the last two hex digits of its address.

[0] = 0x3e8address = 1000 + 0 × 4 = 1000

Index 0 is the base address itself. 1000 in hex is 0x3e8.

Step 1 of 5

That arithmetic is why array access is O(1) — constant time. The CPU does one multiplication and one addition to land on element n. No searching, no traversal, no chasing pointers around.

Key Concept

Arrays store elements contiguously in memory. Accessing element n takes constant time because the address can be calculated directly: base + (n * element_size). This is called random access - you can jump to any element instantly.

Array Operations and Their Costs

Not every operation on an array is cheap. Here's the lay of the land:

Reading by index: O(1). One calculation and you're there.

Writing by index: O(1). Same calculation, then store the value.

Inserting at the end: O(1) if there's room. If the array is already full, you have to allocate a bigger one and copy everything across. That's O(n).

Inserting in the middle: O(n). Every subsequent element has to shuffle down to make space.

Deleting from the middle: O(n). Every subsequent element has to shuffle up to close the gap.

Searching for a value: O(n) for an unsorted array (you may have to check every element). O(log n) for a sorted array via binary search.

text
// Inserting 99 at index 2 requires shifting
Before: [92, 85, 78, 95, 88]
^-- shift everything from here right
After: [92, 85, 99, 78, 95, 88]

Static vs. Dynamic Arrays

A static array has a fixed size, locked in at creation time. You can't grow it. Declare an array of 10 elements and you get exactly 10 slots. No more.

A dynamic array (Python's list, Java's ArrayList, C++'s vector) grows as needed. Underneath, it maintains a backing array plus a count of how many slots are in use. When it runs out of room, it allocates a fresh, larger array (typically double the size), copies the old contents across, and frees the old one.

That doubling trick means individual insertions can occasionally be expensive (when the copy happens), but the amortized cost per insertion stays O(1). You pay a big cost rarely, and a tiny cost most of the time.

Count the writes yourself. The stepper pushes 1 to 9 into an array that starts with room for four and doubles when it fills, the policy libstdc++'s std::vector uses (other libraries grow by 1.5 times or less, which changes the constants but not the O(1) average). Keep an eye on the "writes per push" figure after the expensive pushes.

Pushing 1 to 9 onto a doubling array

backing array (capacity 4)
[0]
[1]
[2]
[3]
size = 0capacity = 4writes this push = 0total writes = 0writes per push = -
An empty dynamic array with capacity 4. Each push normally costs one write.
Step 1/12

Multi-Dimensional Arrays

Arrays can hold arrays. A two-dimensional array is like a grid:

text
grid = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
print(grid[1][2]) // 6 (row 1, column 2)

In memory, a 2D array is still a flat block of bytes. The 2D indexing translates into a single linear index: address = base + (row * num_columns + column) * element_size. This is row-major order, the layout C uses for its multi-dimensional arrays and NumPy uses by default. A few languages go the other way with column-major order, Fortran being the famous example. Python's list of lists is a different animal: each row is a separate list object, so the rows needn't sit next to each other in memory at all.

Here's grid laid out row-major as 4-byte ints, with a made-up base address of 2000 (0x7d0). Step through and check each address against the formula: row 1 starts right where row 0 ends.

grid[3][3] in row-major order, base address 2000

Starts at 0x7d0; small numbers under each byte are the last two hex digits of its address.

[0][0] = 0x7d0address = 2000 + (0 × 3 + 0) × 4 = 2000

Row 0, column 0 is the base address.

Step 1 of 4

Arrays and Cache Performance

Because array elements are stored contiguously, walking through an array in order is extremely cache-friendly. When the CPU loads one element from memory, the cache line drags in several neighbouring elements with it. The next access is already in cache, so it's a hit.

This is one of the most consequential practical facts about arrays. Linked lists and similar structures can match arrays in theoretical complexity for certain operations, yet arrays often win in practice purely on cache efficiency. Modern CPUs are tuned for sequential memory access, and arrays are the shape that fits.

Tying It Back to the Hardware

You already know memory is a linear sequence of bytes with addresses. An array is the most direct software shadow of that hardware: a named region of sequential bytes. Pointer arithmetic, which gets its own lesson later in the course, is exactly what the CPU does to index into one. Understand arrays and you understand how data actually sits in the machine.

When to Use Arrays

Arrays are the right pick when you know your collection's size up front (or can estimate it), when you need fast random access by index, and when you iterate through elements sequentially. They're the default data structure for a reason: simple, fast, hardware-friendly. The next lesson covers linked lists, which trade arrays' contiguous layout for the ability to insert and remove elements efficiently anywhere in the chain.