Arrays: fixed-size and indexing

An array is the simplest data structure: a fixed number of elements of the same type, stored in one contiguous block of memory. Every other data structure in this series either builds on arrays (dynamic arrays, heaps, hash tables) or exists specifically to work around their limitations (linked lists, trees). Understanding arrays deeply pays off for the rest of the series.

Arrays are just memory, indexed

You already saw the core formula in the memory post: address = base + index × element_size. An array is nothing more than a promise from the language/OS that element_size × count contiguous bytes are reserved for you, starting at base.

Because every element is the same size, the CPU never has to search — it computes the exact address and jumps straight there. This is why array indexing is O(1): one multiplication, one addition, one memory read, regardless of whether the array has 10 elements or 10 million.

Fixed-size arrays vs what most languages give you

Low-level languages (C, C++, Java’s primitive arrays) expose true fixed-size arrays: you declare the size up front, and it never changes.

int scores[6] = {42, 17, 89, 53, 71, 35};
// scores occupies exactly 6 * sizeof(int) = 24 contiguous bytes.
// scores[6] would read past the end — undefined behavior, no safety net.
printf("%d\n", scores[2]);  // 89, computed as base + 2*4

int[] scores = {42, 17, 89, 53, 71, 35};
// Java arrays are fixed-size but DO bounds-check at runtime:
System.out.println(scores[2]);      // 89
System.out.println(scores[6]);      // throws ArrayIndexOutOfBoundsException

Python’s list, JavaScript’s Array, and Java’s ArrayList are not fixed-size arrays under the hood — they’re dynamic arrays (covered next) that happen to look like arrays at the language level. The fixed-size array is still there underneath, but the language automatically reallocates it when you outgrow it.

Bounds checking: why it exists and what it costs

Reading or writing past the end of an array’s allocated memory is one of the most common sources of security bugs (buffer overflows) and crashes. Languages handle this differently:

scores = [42, 17, 89, 53, 71, 35]
print(scores[10])   # IndexError: list index out of range
print(scores[-1])   # 35 — negative indexing is a Python convenience,
                     # NOT how the memory address is computed; Python
                     # translates -1 to len(scores)-1 = 5 before indexing

Iterating through an array

The most fundamental operation on an array is visiting every element, one by one, using a for loop. Step through the visualization below to see exactly how the index variable i changes and which element gets accessed at each step:

You can also iterate in reverse — useful when you need to process elements from the end, or when deleting elements without skipping:

Or skip elements with a step size — e.g., visiting only even-indexed elements:

These patterns are the building blocks for every array algorithm you’ll encounter later.

What’s O(1) and what isn’t

This is the single most important table for arrays — memorize which operations are cheap and which aren’t, and why:

arr = [10, 20, 30, 40, 50]

arr.append(60)          # O(1): [10, 20, 30, 40, 50, 60]

arr.insert(0, 5)         # O(n): every element shifts right
                         # [5, 10, 20, 30, 40, 50, 60]

arr.pop()                # O(1): removes from the end
                         # [5, 10, 20, 30, 40, 50]

arr.pop(0)                # O(n): every remaining element shifts left
                         # [10, 20, 30, 40, 50]

The insight that trips up beginners: it feels like insert(0, x) should be as fast as append(x) since both “just add one element” — but appending writes to an already-free slot, while inserting at the front requires physically moving every other element over in memory to open up that slot.

Cache locality: why arrays are faster than the theory suggests

From the memory post, recall that the CPU pulls memory into cache in chunks (cache lines), not one byte at a time. Because array elements sit next to each other, reading arr[0] often pulls arr[1], arr[2], arr[3]… into cache for free.

import time

n = 10_000_000
arr = list(range(n))

# Sequential access — cache-friendly
start = time.time()
total = 0
for x in arr:
    total += x
print("sequential:", time.time() - start)

# Same number of operations, but scattered access pattern
# (e.g. via a shuffled index list) is measurably slower in
# languages/data structures where this matters more than Python's
# interpreter overhead masks it (try this comparison in C for a
# dramatic difference)

This is why a linked list with the same Big-O for traversal (O(n)) is often noticeably slower in practice than an array — its nodes are scattered across memory, causing cache misses on every step. Big-O tells you how cost scales; it doesn’t tell you the constant factor, and cache behavior is a huge part of that constant factor.

Multi-dimensional and variable-length data

Real arrays are only ever truly one-dimensional in memory — “2D arrays” (matrices) and resizable arrays are built on top of this foundation. Both get dedicated posts:

• 2D arrays and matrices (coming soon) — how a grid is flattened into the same 1D memory layout
• Dynamic arrays — how append stays O(1) amortized even though the underlying array is fixed-size

Key takeaways

1. Arrays are contiguous memory — same element size, one base address, index-based addressing.
2. Random access is O(1); insertion/deletion at the front or middle is O(n) because of shifting.
3. Bounds checking trades a tiny per-access cost for memory safety — nearly every modern language does it.
4. Cache locality makes arrays faster in practice than their Big-O alone suggests, especially compared to pointer-chasing structures like linked lists.
5. What looks like “an array” in Python/JS/Java’s ArrayList is almost always a dynamic array underneath — the true fixed-size array is one layer down.

Practice problems

• Remove Duplicates from Sorted Array (Easy) — in-place O(1) space manipulation
• Rotate Array (Medium) — shifting elements without extra space
• Merge Sorted Array (Easy) — why merging from the back avoids O(n) shifting

What’s next

• Dynamic arrays — how languages give you “arrays that grow” while keeping append O(1) amortized
• 2D arrays and matrices — flattening grids into 1D memory (coming soon)