What Is an Array? — The Fundamental Collection

If you were to strip away every complex data structure ever invented—linked lists, trees, hash tables, graphs—and ask yourself what single structure could rebuild them all, the answer would be the array.

Arrays are deceptively simple. At first glance, they're just numbered boxes holding values. But this simplicity is precisely what makes them powerful. Every database index, every image pixel buffer, every function call stack, every GPU shader—all ultimately rely on arrays. Understanding arrays isn't just learning one data structure; it's understanding the substrate upon which modern computing is built.

An array is a data structure consisting of a collection of elements, each identified by an index (or key), where:

1. All elements are of the same type (homogeneity)
2. Elements are stored in contiguous memory locations (contiguity)
3. The size is fixed at the time of creation (static size)
4. Elements are accessed by their position (ordered/indexed access)

This definition distinguishes arrays from other collection types. Lists may be resizable, dictionaries use keys instead of indices, and sets are unordered. Arrays commit to a specific set of constraints that unlock unique performance characteristics.

Mathematical notation:

Formally, an array A of size n can be denoted as:

$$A = [a_0, a_1, a_2, ..., a_{n-1}]$$

Where:

• $n$ is the fixed size of the array
• $a_i$ is the element at index $i$
• Indices range from $0$ to $n-1$ (in zero-indexed systems)
• Each $a_i$ belongs to the same type T

This notation captures the essence: an ordered sequence of n elements where position determines identity.

The most distinguishing property of a classical array is its fixed size. When you create an array, you must specify exactly how many elements it will hold, and that number cannot change throughout the array's lifetime.

This might seem like a limitation—and in some ways, it is—but it's a strategic limitation that enables critical optimizations.

The trade-off:

Fixed size means you must know (or estimate) how many elements you need before creating the array. If you underestimate, you can't fit all your data. If you overestimate, you waste memory.

This trade-off is fundamental to computer science: flexibility costs performance. Arrays sacrifice flexibility for speed. When you need dynamic sizing, you use different structures (dynamic arrays, linked lists) that introduce their own overhead.

Historical context:

In early computing, memory was precious and expensive. Arrays emerged as the natural fit because programmers did know their data sizes in advance (processing fixed-format punch cards, predefined sensor counts, etc.). The fixed-size constraint wasn't a limitation—it was a feature that matched the problem domain.

In an array, order matters. The element at index 0 is fundamentally different from the element at index 1, even if they hold the same value. Position is part of identity.

This ordered nature distinguishes arrays from sets (where only membership matters) and maps (where keys, not positions, identify elements).

Why order is computationally powerful:

Ordering enables positional reasoning. You can say "the element before X" or "the element after X" or "the elements between positions i and j." This positional vocabulary is essential for:

• Sorting algorithms — Reordering elements based on comparisons
• Binary search — Eliminating half the search space based on position
• Sliding window techniques — Processing contiguous subsequences
• Two-pointer algorithms — Processing from both ends simultaneously
• Sequential processing — Processing files, streams, or logs in order

Without ordering, none of these algorithms would work. The notion of "sorted" itself requires order. Arrays make order explicit and cheap to maintain.

In a true array, every element must be of the same type. An array of integers contains only integers. An array of characters contains only characters. You cannot mix types within a single array.

This constraint—called homogeneity—might seem limiting compared to languages that allow mixed-type lists. But homogeneity is what makes arrays fast.

The address calculation formula:

Given an array starting at memory address base with elements of size s bytes, the address of element at index i is:

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

This formula works only because element size is constant. If elements had different sizes, you'd need to sum the sizes of all preceding elements—an O(n) operation instead of O(1).

Example:

• Array of 32-bit integers starting at address 1000
• Element size = 4 bytes
• Element at index 5 = 1000 + (5 × 4) = 1020

This calculation happens in a single CPU cycle. It's the foundation of array efficiency.

The fourth defining property of arrays is contiguous storage: all elements are stored in adjacent memory locations with no gaps between them.

If your array starts at memory address 1000 and each element is 4 bytes, then:

• Element 0 is at 1000-1003
• Element 1 is at 1004-1007
• Element 2 is at 1008-1011
• And so on...

There's no wasted space, no pointers between elements, no indirection. Just data, one element after another.

Why contiguity is a superpower:

Contiguous storage transforms array access from a memory scavenger hunt into instant retrieval:

1. O(1) Random Access — Any element can be accessed in constant time using the address formula. No following chains of pointers.

2. Cache Locality — Modern CPUs don't fetch individual bytes; they fetch cache lines (typically 64 bytes). When you access element 0, elements 1-15 might already be in cache. Sequential array access achieves near-memory bandwidth.

3. Prefetching — CPUs detect sequential access patterns and prefetch upcoming elements before you request them. This hides memory latency.

4. Memory Efficiency — No metadata per element. A 100-element int array uses exactly 400 bytes (for 32-bit ints), not 800+ bytes like a linked list with pointers.

5. Vectorization — SIMD instructions can load multiple contiguous elements in a single operation and process them in parallel.

Each array property in isolation is useful, but together they create something greater than the sum of their parts. The four properties form a cohesive system where each enables and reinforces the others:

Remove any property and the system breaks:

• Remove fixed size → Can't pre-allocate contiguous memory; need dynamic reallocation
• Remove homogeneity → Can't calculate addresses; need per-element size metadata
• Remove contiguity → Can't use address arithmetic; need pointers or tables
• Remove ordering → Lose indexed access semantics; become a set or bag

This is why arrays are exactly what they are. They're not a compromise or a default—they're a carefully optimized sweet spot where constraints enable performance.

To fully understand what arrays are, it helps to clarify what they are not. Many structures get called "arrays" loosely, but they have fundamentally different properties:

Important distinctions:

1. Dynamic/Resizable Arrays — These grow as needed but internally use fixed-size arrays with periodic reallocation. They're arrays with a wrapper, not a fundamentally different structure.

2. Associative Arrays (Maps/Dictionaries) — The term "associative array" is misleading. These use keys (not indices) and have completely different implementations (hash tables, trees).

3. Language-Specific 'Arrays' — JavaScript's Array is highly dynamic and sparse-capable. PHP's arrays are really hash maps. Only languages like C, Rust, and low-level contexts provide true arrays.

4. Multi-Dimensional Arrays — These are arrays of arrays (or contiguous blocks indexed by multiple dimensions). The principles extend, but implementation details vary.

We've established the complete formal definition of an array. Let's consolidate:

What's next:

Now that we understand what arrays are, the next page explores why they're considered the most fundamental data structure. We'll see how nearly every other data structure—stacks, queues, heaps, hash tables, even graphs—can be (and often is) implemented using arrays as their foundation. Arrays aren't just a data structure; they're the data structure upon which computer science is built.