Arrays: How Data is Stored Contiguously

01 What is an Array?

Stated simply and formally:

Suppose we have five numbers: 10, 20, 30, 40, 50. We could hold them in five separate discrete variables:

When managing 10,000 numbers, creating 10,000 distinct variable names makes algorithmic iteration impossible. Instead, an Array aggregates them into an ordered sequence:

Now the entire collection is represented by a single identifier: numbers = [10, 20, 30, 40, 50]. The identifier numbers points directly to the entire array block.

02 The Fundamental Concept: The Index

Every element within an Array occupies an explicit position known as its Index. In virtually all contemporary systems and programming languages, array indexing starts at 0 (Zero):

Index:   0    1    2    3    4
         ↓    ↓    ↓    ↓    ↓
Data:   [10] [20] [30] [40] [50]
        

Notice that numbers[2] refers to the 3rd element because counting begins from zero.

03 Why Does Indexing Begin at 0? (Pointer Arithmetic)

To a newcomer, zero-based indexing seems unnatural. But it stems from an elegant piece of hardware mathematics.

Suppose our array's first item resides at physical memory address 1000 (called the Base Address), and each integer consumes 4 bytes:

The crucial insight: An index is not an ordinal count; it is an offset (distance)! How far is the first element from the beginning? Zero elements away! How far is the second element? Exactly one element away. Using 0-based indexing allows the CPU to compute addresses with a single multiply-add operation without subtracting 1 on every clock cycle.

04 Arrays and Contiguous Memory

The hallmark of a classic array is that its elements occupy an unbroken, contiguous sequence of hardware memory addresses:

Because elements are tightly packed side-by-side, if the CPU knows:

• Where the first element starts (Base Address)
• How many bytes each element consumes (Element Size)

To fetch index 3, the CPU does not step through 10, 20, or 30. It evaluates 1000 + (3 × 4) = 1012 and accesses slot 1012 in a single hardware cycle.

05 What Does "Random Access" Mean?

The word "Random" can be misleading. In computer science, Random Access does not mean arbitrary or accidental; it means:

Consequently, the asymptotic time complexity for indexed access in an Array is:

Reading slot 5 or slot 5,000,000 takes the exact same microsecond duration.

06 Visualizing an Array

Our spatial mental model for an Array can be visualized as:

        Array
┌──────┬──────┬──────┬──────┬──────┐
│  10  │  20  │  30  │  40  │  50  │
└──────┴──────┴──────┴──────┴──────┘
   0      1      2      3      4
        

07 Adding New Data to an Array

Suppose our array holds: [10, 20, 30, 40, 50]. We wish to append 60 at the end.

If unused pre-allocated capacity exists at the end of the array, appending is instantaneous:

However, a bottleneck occurs when available capacity is exhausted. If adjacent memory addresses are occupied by other variables or processes, the system cannot simply stretch the array boundary in place.

08 What is a Dynamic Array?

In modern high-level languages, we frequently work with arrays that automatically grow at runtime. These are known as Dynamic Arrays:

Under the hood, these collections manage fixed-size contiguous memory blocks. When capacity is exceeded, they allocate a new block (typically double the size) and migrate existing items.

09 Why Middle Insertions Can Be Computationally Expensive

Suppose we have: [10, 20, 30, 40, 50], and we need to insert 25 between 20 and 30:

To create space at index 2, every succeeding element must be shifted rightwards. In an array of 1,000,000 items, inserting near the front requires shifting nearly a million memory slots!

10 What Happens When Deleting from an Array?

Similarly, suppose we delete 30 from [10, 20, 30, 40, 50]:

To maintain contiguous indexing without empty holes, trailing items must be shifted leftwards ($O(n)$ operational cost).

11 Advantages of Arrays

Five core reasons why Arrays remain the most popular data structure:

12 Limitations of Arrays

Arrays are not universal panaceas. Key architectural constraints include:

13 Real-World Software Applications

Arrays underpin ubiquitous computer applications:

14 Multi-Dimensional Arrays (2D Arrays / Matrices)

Arrays are not limited to 1D linear sequences. Arrays can store other arrays, forming multi-dimensional structures such as a 3×3 matrix:

Accessing items requires coordinate indices: matrix[row][column]. For instance, matrix[1][2] fetches row 1, column 2 (value: 6). These multi-dimensional layouts drive:

• Linear algebra and matrix mathematics
• Spreadsheets and tabular calculations
• Chess, checkers, and grid-based game boards
• Image convolutions and scientific simulations

15 The Relationship Between Arrays and Strings

In many programming architectures, a String is internally represented as a sequential array of character bytes. For example, "HELLO" is conceptually: ['H', 'E', 'L', 'L', 'O'].

However, language semantics differ: strings are mutable in C/C++, while immutable in Python and Java. Rather than treating Strings as ordinary arrays, it is more accurate to understand them as specialized text representations with string-specific optimizations.

16 Array vs. Linked List: The Initial Encounter

This leads to one of the most famous dichotomies in software engineering:

“If array insertions and deletions in the middle are so costly, is there a data structure where elements explicitly link directly to one another?”

Yes! That structure is the Linked List:

17 Array Complexity Summary

A snapshot of operational costs in a standard Array:

18 5 Foundational Lessons from Arrays

Remember these 5 architectural principles above all syntax:

19 Visual Synthesis

One final mental synthesis of the physical hardware layout:

This simple mathematical elegance is one of the greatest inventions in the history of computation.

20 A New Architectural Question...

We now understand that Arrays store items contiguously, making reads blazingly fast.

But what if our application scenario requires:

• Frequent middle insertions and deletions
• Unpredictable, dynamic collection sizes where reallocations cause latency spikes
• Operating in fragmented memory where no large continuous block exists

We require a radically different architectural concept: Chaining data items via pointer references. And that brings us directly to our next data structure: Linked Lists.