Internal mechanics of arrays
So far, we learned what an array is and how it solves problems where we need to store and manipulate large-scale data easily. We can now look at how the array data structure works under the hood and what makes it so fast and easy to use.
Memory addresses
Array elements are accessed using indices because arrays are stored contiguously in memory. To better understand the relationship between array elements and indices, let us revisit the memory model we learned earlier.
Memory is logically organized as a linear sequence of blocks.
Memory is logically organized in RAM as a sequence of blocks, each 1 byte (8 bits) long. Every block has a unique identifier that can be used to locate it in memory, called its address. The address is nothing but a number that is the relative position of the block from the start (starting from 0).
Layout in memory
An array is just a contiguous segment of memory that stores data of a single type. Each data item in the array has a fixed size equal to the size of its data type, so the total size of an array is the sum of the size of all data items.
The address of the block of memory where an array starts is also called the array's base address. The base address, along with the index, is used to access data items in an array.
In the drawing below, an array of 5 integers is mapped into a memory of byte-sized blocks starting at base address 2. Each integer takes 4 bytes, so every element (value1 to value5) spans 4 consecutive blocks. We will reuse this exact setup in the working example lesson at the end of this module.
Structure of an array in memory
Accessing data items
Now that we know how an array is mapped into contiguous memory, it is easy to figure out a mathematical formula to calculate the address of a data item at a given index if we know the base address (where the array starts in memory) and the size of each data item.
The address of the data item at index is base_address + index * size_of_datatype.
index by the size of each item?To reach the item at
index, we must skip over every item placed before it. There are exactly index items before it (this is what a 0-based index counts), and each one occupies size_of_datatype bytes, so we skip index * size_of_datatype bytes from the base address.Calculating the address of a data item stored at a given index in an array
An array's index is not a count but an offset from the base address. To locate the item, the machine computes
base address + (size of datatype * index). The first element sits exactly at the base address, so its index (offset) is 0.