---
title: Arrays
source: 'https://academia.sh/en/courses/data-structures/arrays'
course: 'Data Structures'
language: en
updated: '2026-08-17T18:07:55+00:00'
license: 'CC BY-SA 4.0'
---

# Arrays

Contiguous memory layout, constant-time access through address arithmetic, the fixed-size constraint, and the language of cost.

In the Programming Fundamentals course, lists were used: elements were added,
traversed, filtered. What these operations correspond to in memory, and why some are
more expensive than others, was left open.

This course fills that gap. Its question is: depending on how data is arranged in
memory, which operation is cheap and which is expensive? The answer always comes from
the same two sources — the memory model established in the How Computers Work course,
and the structure's own layout.

## Contiguous Layout

An **array** is a structure that keeps elements of the same type **contiguous** in
memory. If the address of the first element is known, the addresses of the rest can be
computed:

$$
\text{address}(i) = \text{base} + i \times \text{element size}
$$

If an array of four-byte integers starts at address `1000`, the address of the third
element is $1000 + 3 \times 4 = 1012$. The calculation is a single multiplication and a
single addition; it is independent of the array's length.

This is the array's distinguishing property: **any element can be accessed directly,
given its index.** Reaching the fifth element does not require passing through the
previous four.

The layout's second consequence is that the array carries elements of a single type.
Address arithmetic relies on elements being of equal size; if elements of different
sizes were arranged contiguously, the location of the $i$-th element could not be
computed and would have to be searched for.

## The Language of Cost

Throughout this course, the cost of operations will be compared. Three expressions
suffice for the comparison; their formal definitions are given in the **Algorithms**
course.

- **Constant time**, $O(1)$: The duration of the work is independent of the data's
  size. Access to the array's $i$-th element is like this.
- **Linear time**, $O(n)$: The duration grows in proportion to the number of elements.
  Scanning an array from start to end is like this.
- **Logarithmic time**, $O(\log n)$: At each step, the search space shrinks by a fixed
  ratio. Binary search in a sorted array is like this.

The notation ignores constant factors and lower-order terms; what it measures is **the
rate at which** cost grows as data grows.

## The Cost of Array Operations

| Operation | Cost | Reason |
|---|---|---|
| Access to the $i$-th element | $O(1)$ | Address arithmetic |
| Search in an unsorted array | $O(n)$ | All elements in the worst case |
| Search in a sorted array | $O(\log n)$ | The range halves at each step |
| Insertion at the end (if room exists) | $O(1)$ | A single write |
| Insertion at the start or middle | $O(n)$ | Shifting the following elements |
| Deletion from the middle | $O(n)$ | Closing the gap |

Insertion and deletion being expensive is the direct cost of contiguous layout.
Inserting an element at the start of a five-element array requires moving each of the
existing five elements one position forward; the layout must stay contiguous, because
address arithmetic depends on it.

```python
def insert_at_start(array: list[int], value: int) -> int:
    """Shifts the array by one position to insert at the start; returns the count of elements shifted."""
    array.append(None)                      # open room at the end
    shifted = 0
    for i in range(len(array) - 1, 0, -1):  # shift from the end toward the start
        array[i] = array[i - 1]
        shifted += 1
    array[0] = value
    return shifted


measurements = [12, 18, 7, 25, 14]
print(insert_at_start(measurements, 30))    # 5     — five elements shifted
print(measurements)                         # [30, 12, 18, 7, 25, 14]
```

The number of shifts equals the length of the array; this is the $O(n)$ row from the
table shown as an actual count.

## The Fixed-Size Constraint

A classic array is a memory block whose size is fixed at the moment it is created.
Because the block is contiguous, growing it afterward is generally not possible: the
memory immediately following the array may already be in use by other data.

This constraint has two consequences. An array allocated larger than needed wastes
memory; one allocated too small becomes unusable once it fills up. If how many
elements the program will hold is not known in advance, a fixed-size array is not a
direct solution.

The next lesson's subject is exactly how this constraint is overcome.

## Bounds Checking

Address arithmetic assumes that the given index is valid. If the index is out of
range, the computed address points to a memory location outside the array.

Languages respond to this in two different ways. **Languages that check** compare the
index against the bound on every access and raise an error on overrun; the cost is a
few instructions per access. **Languages that do not check** apply the calculation
directly; access is at its fastest, but an out-of-range index leads to reading or
overwriting neighboring data.

The second behavior came up under the heading of undefined behavior in the How
Computers Work course. Its result is not only a wrong value: writing past the end of
an array can corrupt the return address in a stack frame. This is the best-known class
of memory safety vulnerabilities and is treated separately in the Cybersecurity
curriculum.

## Multidimensional Arrays

A two-dimensional array also sits one-dimensionally in memory; rows are placed one
after another. This is called **row-major order**, and the index calculation is:

$$
\text{position}(i, j) = i \times \text{column count} + j
$$

```python
COLUMNS = 4
flat = [0] * (3 * COLUMNS)        # a 3-row, 4-column table in a single array

def write(i: int, j: int, value: int) -> None:
    flat[i * COLUMNS + j] = value

def read(i: int, j: int) -> int:
    return flat[i * COLUMNS + j]

write(1, 2, 99)
print(read(1, 2), flat)           # 99 [0, 0, 0, 0, 0, 0, 99, 0, 0, 0, 0, 0]
```

The value `99` sitting at position six ($1 \times 4 + 2$) in the flat array shows how
two dimensions are reduced to one.

This layout's performance consequence was calculated in the cache lesson of the How
Computers Work course: traversing along a row reads consecutive addresses, while
traversing along a column skips a row's length at every step. For the same number of
additions, the amount of data moved differs by as much as the number of elements that
fit in a cache line.

## Why Arrays Are Common

Despite the array's high insertion and deletion costs, there are three reasons it is
the most commonly used structure in practice.

**Access cost is the lowest.** It is constant time and as cheap as a single address
calculation.

**Cache behavior is the best.** Contiguous layout is the arrangement that benefits
most from spatial locality; when one element is fetched, its neighbors enter the cache
too.

**It takes no extra space.** Unlike linked structures, no pointer is stored per
element.

For these three reasons, the default answer to the "which structure" question is the
array; another structure is chosen only when an operation the array is weak at
dominates. The rest of this course shows what those situations are and which
structure reduces which cost.

## Cost Table

Throughout the course, the table below will grow row by row. The first row is this
lesson's result:

| Structure | Access | Search | Insert at start | Insert at end | Delete from middle |
|---|---|---|---|---|---|
| Array (fixed size) | $O(1)$ | $O(n)$ | $O(n)$ | $O(1)$* | $O(n)$ |

\* As long as room remains; once the array is full, insertion is not possible.

## Summary

- An array keeps elements of the same type contiguous; the address of the $i$-th
  element is computed from the base address and the element size.
- Because this calculation is independent of the array's length, access is constant
  time.
- Insertion and deletion require shifting elements to preserve contiguity, and are
  linear time.
- The fixed-size constraint arises from the fact that a contiguous block cannot be
  grown afterward.
- Multidimensional arrays sit one-dimensionally in memory; row-major order causes the
  direction of traversal to determine cache behavior.
- Because of its access cost, cache compatibility, and lack of extra space, the array
  is the default choice.

## Next Step

The fixed-size constraint makes the array unusable in problems where the number of
elements is not known in advance. The next lesson will lift this constraint with a
solution based on moving the array, and show why that solution's cost is not as high
as it looks — through the concept of amortized cost.