Array Subscripting Operations

Data Structures and Algorithms with Object-Oriented Design Patterns in Java

Array Subscripting Operations

We now address the question of accessing the elements of an array of data. In general, the elements of a one-dimensional array are stored in consecutive memory locations. Therefore, given the address of the first element of the array, a simple addition suffices to determine the address of an arbitrary element of the array:

Axiom The time required for the address calculation implied by an array subscripting operation, e.g., a[i], is a constant, . This time does not include the time to compute the subscript expression, nor does it include the time to access (i.e., fetch or store) the array element.

By applying Axiom , we can determine that the running time for the statement

y = a [i];

. Three operand fetches are required: the first to fetch a, the base address of the array; the second to fetch i, the index into the array; and, the third to fetch array element a[i].