Arrays

The idea

An array is a data structure that stores a fixed number of elements next to each other in memory (contiguously), and lets you refer to each element using an integer index.

If we name an array A, then:

• •A[0] is the first element (in many languages)
• •A[1] is the second element
• •…
• •A[i] is the element at position i

That simple indexing idea—A[i]—is the signature move of arrays.

Why we care (before details)

Arrays are foundational because they give you something incredibly powerful:

• •Direct (random) access: “Go to element 120 right now.”

Many other data structures either build on arrays (stacks, heaps) or are compared against arrays (linked lists, hash tables).

A concrete mental model: numbered lockers

Imagine a hallway of lockers, each locker the same size, in a single line. Locker #0, #1, #2, … Each locker holds exactly one value.

If you want locker #120, you don’t start at #0 and walk 120 steps checking each locker. You go straight there because the lockers are in order.

That is the feeling arrays provide: jumping directly to a position.

What “contiguous memory” really means

“Contiguous” means the elements are stored back-to-back in memory addresses:

• •A[0] at address base
• •A[1] at address base + elementSize
• •A[2] at address base + 2*elementSize

This layout is the entire reason arrays can do O(1) indexing.

Indices and bounds

Indices are integers. Common conventions:

• •0-based indexing (C, Java, Python lists behave like 0-based arrays)
• •1-based indexing (MATLAB, some math notation)

Important: indices must be in range.

If the array length is n, valid indices are typically 0…n−1.

Accessing outside that range is called out-of-bounds. Some languages catch it with an error; lower-level languages might do something worse (like reading random memory).

Arrays vs “array-like”

In everyday programming, you’ll see:

• •Static arrays: fixed size (common in low-level languages)
• •Dynamic arrays: grow as needed (e.g., Python’s list, Java’s ArrayList). These still store elements contiguously most of the time, but may occasionally resize and move.

In this lesson, the core mechanics are the same: contiguous storage + integer index.

Why indexing can be constant time

When you write A[i], the computer doesn’t “look for” the i-th element.

Instead, it computes the memory address directly.

Address formula

Let:

• •base(A) be the memory address where A[0] starts
• •s be the size (in bytes) of one element (e.g., 4 bytes for a 32-bit integer)
• •i be the index

Then the address of A[i] is:

That’s just multiplication and addition—constant-time arithmetic—so indexing is O(1).

Why equal-sized elements matter

This formula relies on each element having the same size.

• •If every locker is the same width, you can compute “locker #i” easily.
• •If lockers had random widths, you’d need to sum widths to find the start of locker #i, which could take O(n).

That’s why classic arrays store uniform element sizes.

Read and write are both O(1)

Once the address is computed:

• •Reading A[i] is O(1)
• •Writing A[i] = value is O(1)

So arrays are excellent for:

• •pixel buffers (image editing)
• •audio samples
• •game grids / tile maps
• •lookup tables
• •any workload that frequently accesses “the i-th thing”

A 2D example: grids (still arrays underneath)

Suppose you have a 2D grid with rows and cols. Many systems store it as a 1D array in row-major order.

Let grid[y][x] be the cell at row y, column x.

Then the 1D index is:

So:

• •grid[0][0] → i = 0
• •grid[0][1] → i = 1
• •grid[1][0] → i = cols

This is the same O(1) indexing idea, just with an extra step to compute i.

A note on caching (a hidden superpower)

Because arrays are contiguous, iterating through them tends to be fast in practice.

Modern CPUs fetch memory in chunks (cache lines). If you access A[0], A[1], A[2], … sequentially, the CPU often already has the next values nearby.

So arrays are not just theoretically efficient—they’re often practically fast.

Arrays are fast at one thing: index-based access.

But many tasks aren’t “give me A[i]”. They’re:

• •“Find the value 42.”
• •“Insert a new element at the beginning.”
• •“Delete the element in the middle.”

This is where the tradeoffs show up.

Searching: why it’s often O(n)

If the array is unsorted and you want to find a particular value x, you usually must scan:

• •check A[0]
• •check A[1]
• •…
• •check A[n−1]

In the worst case, x is at the end or not present, so you check n elements.

That’s O(n).

Sorted arrays change the story

If the array is sorted, you can use binary search, which is O(log n).

But sorting has its own costs (and maintaining sorted order makes insertions harder). This lesson’s baseline claim “O(n) search” assumes no additional structure.

Inserting: the curiosity challenge

Recall the question: Why is inserting at the front slow?

Consider inserting a new element at index 0.

If you need to keep the existing order, everything must shift right:

• •old A[0] moves to A[1]
• •old A[1] moves to A[2]
• •…

That’s potentially moving n elements, so insertion at the front is O(n).

Inserting in the middle is also O(n)

If you insert at index k, then elements k…n−1 shift right.

Worst case k=0 → shift all n.

So insertion is O(n) in the worst case.

Appending can be O(1) (sometimes)

If you insert at the end (append), you might not need to shift anything.

• •Static array: can’t append if it’s full.
• •Dynamic array: can append in amortized O(1), but occasionally it resizes.

We’ll keep the basic mental model: order-preserving insertions generally require shifting → O(n).

Deleting: also involves shifting

Deleting A[k] while preserving order means:

• •A[k+1] shifts left to fill the gap
• •…

Worst case: delete near the front → shift almost all elements.

So deletion is typically O(n).

Summary table: typical time costs

Space: compact and predictable

Arrays store elements with little overhead:

• •no extra “next pointer” fields
• •no per-element object metadata (in low-level representations)

This compactness is why arrays are often used as the underlying storage for many other structures.

Arrays show up everywhere because they provide:

1) fast indexing

2) cache-friendly iteration

3) simple memory layout

Here are key connections to what you’ll learn next.

Stacks and queues

A stack (LIFO) often uses a dynamic array underneath:

• •push: write to the next free index
• •pop: decrease size counter

Most operations become O(1) because you only modify the end.

A queue (FIFO) can also be built on an array using a circular buffer:

• •head and tail indices wrap around
• •avoids shifting on dequeue

This is an important trick: arrays are bad at removing from the front if you shift, but great if you redesign the indexing.

Heaps (priority queues)

A binary heap is typically stored in an array.

For 0-based indexing:

• •parent(i) = ⌊(i−1)/2⌋
• •left(i) = 2i + 1
• •right(i) = 2i + 2

This is a beautiful example of arrays enabling a tree-like structure without pointers.

Hash tables

Many hash table designs use arrays internally:

• •an array of buckets
• •or an array of entries

The hash function maps a key to an integer index.

That index is used to jump to a location quickly (again, array indexing).

Graph representations

Graphs can be represented with an adjacency matrix, which is basically a 2D array:

• •matrix[u][v] tells whether there is an edge u→v
• •O(1) edge query
• •but space is O(n²)

Arrays make that matrix representation possible and efficient to access.

When arrays are the wrong tool

Arrays struggle when you need lots of:

• •insertions/deletions in the middle
• •growth without occasional resizing costs (for dynamic arrays)

In those cases, other structures (linked lists, balanced trees) can help—at the cost of losing O(1) random access.

Arrays are not “best.” They are specific.

And that specificity—fast direct access—makes them the foundation for much of practical computing.