Array (data structure)

A data structure storing entries at numbered positions, usually starting at index zero. The fixed-capacity representation considered here puts equal-sized slots consecutively in computer memory. The number $n$ of occupied slots can be smaller than the capacity; unused slots provide room for later entries. An array of references stores consecutive references, while the objects they identify can be elsewhere. ^[ref]

Let the first slot have abstract address $b$ and each slot occupy $s$ address units. Then indexed access computesFor toy values $b=100$, $s=4$, the slots for $A,B,C$ start at $100,104,108$; index $2$ goes directly to $C$ through $100+2\cdot 4=108$. These are illustrative slot addresses, not observed allocation addresses. Under the word-RAM (random-access machine) model for time complexity, word-sized arithmetic operations and any addressed computer memory access have constant cost, and the addresses and entries fit in words. Thus one array access takes $O(1)$ time in Big O notation, independently of the index. This is the access assumption needed by binary search. ^[ref]

Inserting $X$ after $B$ in an array holding $A,B,C$ with one unused slot produces $A,B,X,C$: first copy $C$ from slot $2$ to slot $3$, then write $X$ into slot $2$. Writing $X$ first would lose $C$ unless it had been saved separately. More generally, insert at index $i$ by copying occupied slots from right to left, then fill the gap; with spare capacity this moves $n-i$ entries and takes $O(1+n-i)$ time in Big O notation, so insertion near the middle has $O(n)$ time complexity. Removing an entry closes the gap by shifting later entries left. ^[ref]

A fixed-capacity array cannot accept another entry when full. A resizable representation can allocate a larger array and copy the entries. Doubling capacity when full gives $O(1)$ append cost by amortized analysis over a sequence starting empty, but a single append that copies $n$ entries still has $O(n)$ worst-case time complexity. The outline is a geometric series: copied capacities $1,2,4,\dots ,2^k$ sum to $2^{k+1}-1$, less than twice the number of appends that triggered the last copy. Middle insertion still pays for its shifts. ^[ref]

Reverse the order of entries in an array segment by exchanging its outermost unprocessed pair and moving inward. This takes linear time and constant auxiliary space. Reversing two adjacent blocks separately and then reversing their union rotates the blocks while restoring each block's internal order.

A contiguous portion of an array, or a rectangular restriction to contiguous coordinate ranges for a multidimensional array.

A right array rotation by $k$ sends the entry originally at offset $j$ to offset $(j+k)\mathrm{mod}n$ for nonempty length $n$. Equivalently it changes adjacent blocks $AB$ into $BA$ when $|B|=k$. Identity rotations include $k=0$ and $k=n$.

Three reversals implement the operation: $AB\to A^{R}B\to A^R{B}^R\to BA$. Alternatively repeatedly use a block swap to put the smaller block in its final position and recurse on the remaining unresolved segment. Replacing that tail recursion by parameter updates gives constant auxiliary storage. If $S(a,b)$ counts swaps for blocks of lengths $a,b>0$, then $S(a,a)=a$ and $S(a,b)=\min (a,b)+S(\min (a,b),|a-b|)$ for unequal lengths. The Euclidean algorithm shows by induction that $S(a,b)=a+b-\gcd (a,b)$, so a right rotation uses $n-\gcd (n,k)$ element swaps for $0<k<n$.

Exchange two stored values while preserving all others. For an array, a temporary value implements x := a[i]; a[i] := a[j]; a[j] := x. For distinct indices this uses two element reads and two element writes. The operation is an involution, and its permutation is a transposition.

Exchange two equally long disjoint segments of an array, preserving the order within each segment. Applying one swap at each corresponding offset exchanges length-$n$ blocks in $n$ swaps and constant auxiliary storage. Disjointness ensures that an earlier swap does not overwrite an original value needed by a later pair.

Here a bitonic contiguous segment may be weakly increasing then weakly decreasing, or the reverse. Equivalently, remove zero signs from its adjacent differences: the remaining signs change at most once. This convention includes monotone and constant segments. A plateau can lie at the shared boundary between two directions, so maximal bitonic segments can overlap across that entire plateau.

A linear time scan can retain the earliest start of the current monotone suffix, the earliest start of the current bitonic suffix, the most recent nonzero direction and the endpoint of its most recent strict step. At a strict direction reversal, the new bitonic suffix begins at the old monotone start; the new monotone suffix begins at the old strict-step endpoint. Zero differences leave these boundaries unchanged. The suffix invariants show that no longer valid suffix is discarded, and recording the largest length gives a global optimum using constant auxiliary storage.

A contiguous segment whose elements all have the same value. Its longest suffix after scanning a new element extends the previous constant suffix when the adjacent values agree, and otherwise starts again with length one. Keeping the largest suffix length seen gives a linear time longest-segment scan.

An entry occurring strictly more than half the time in a finite array or sequence. At most one distinct value can satisfy this condition: two such occurrence counts would sum to more than the input length. A majority element need not be the smallest, largest or most recently observed entry.

For an array $a$, its difference array stores $d_0=a_0$ and $d_i=a_i-a_{i-1}$ for $i>0$. The original entries are prefix sums of $d$. Adding $v$ on indices $[l,r]$ requires only $d_l+=v$ and, when present, $d_{r+1}-=v$.

Storage of a multidimensional array with the last index varying fastest in consecutive positions. In a two-dimensional array, each row is contiguous. Row-major order is a layout convention; a program can traverse that array by rows or by columns. See the explicit address calculation in spatial locality.

Storage of a multidimensional array with the first index varying fastest in consecutive positions. In a two-dimensional array, each column is contiguous. Traversing a row-major array by columns does not change its storage into column-major order.

An array whose entries appear in nondecreasing order under a specified total order. The displayed inequalities allow repeated values.

For example, $(2,5,5,9)$ is a sorted array of integers. Inserting $7$ at index $3$ gives $(2,5,5,7,9)$: with spare capacity, first shift $9$ one slot right. Appending $7$ would violate the sorted array property. Updating an entry also requires preserving the total order, or removing and reinserting it in a suitable position.

The useful combination is order plus direct indexed access: binary search eliminates a whole interval of candidates at each comparison, giving $O(\log n)$ search time complexity under constant-cost comparisons and the array cost model. A sorted array is therefore attractive for many lookups between changes, while keeping it sorted can still require $O(n)$ shifting work per insertion. A sorted linked list has the ordering information but does not supply the same constant-cost access to a middle index.

An integer identifying a position in an array. With zero-based indexing and capacity $m$, valid array indices are $0,\dots ,m-1$. An array index identifies the slot rather than its stored value.

The permitted array indices for a length-$n$ array are $0,\dots ,n-1$ under zero-based indexing. A one-past-the-end index $n$ can describe an empty remaining segment but cannot be dereferenced. Proving bounds safety requires showing that every executed read and write uses a permitted index, including evaluations in a loop guard. A known target inside the array can sometimes supply a stronger loop invariant than an explicit bounds test.

A dynamic array is an array whose backing storage can grow as entries are appended. Dynamic array doubling is one growth policy with a deterministic amortized analysis.