Arrays

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.

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$$

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.