Array

data-structures

Definition

Array

An array is a data structure consisting of a collection of elements (values or variables), each identified by at least one array index or key. An array is stored such that the position of each element can be computed from its index tuple by a mathematical formula.

In most low-level implementations, an array is a contiguous block of memory.

Memory Layout

The fundamental characteristic of an array is its contiguous allocation in memory. This allows for constant-time access to any element via its index.

The memory address of an element at index $i$ can be calculated as:

$$\text{address}(A[i])=\text{base\_address}+i\times \text{element\_size}$$

Complexity

The following table outlines the time complexity of standard array operations:

Operation	Static Array	Dynamic Array (Vector)
Random Access	$O(1)$	$O(1)$
Insertion (at end)	$N/A$	$O(1)$
Insertion (at start)	$O(n)$	$O(n)$
Deletion	$O(n)$	$O(n)$
Search (unsorted)	$O(n)$	$O(n)$