Array
Arrays place elements in a contiguous logical sequence, making indexed access predictable and iteration cache-friendly. Dynamic arrays add growth while preserving that model.
One Block, One Multiplication
An array stores its elements in a single contiguous block of memory, one immediately after another, with every element occupying the same fixed number of bytes. Those two conditions — contiguous and uniform width — are the entire basis of the structure's behaviour.
Together they mean the address of element i can be computed: address = base + i × width. The machine does not search, compare, or follow anything; it performs one multiplication and one addition. That is why access by index is O(1), and why it is O(1) for element 0 and element 999,999 alike.
This also explains why indices start at zero. The index is an offset from the base address, so element 0 sits at base + 0, exactly at the start. One-based indexing would require subtracting one on every single access, which is why the languages that use it pay a small tax that C-derived languages do not.
The uniform-width requirement is why arrays hold a single type. An array of 32-bit integers has width 4 and the arithmetic works; a hypothetical array of mixed-size values would break it. Languages that appear to store mixed types in arrays — Python's list, Java's Object[] — actually store uniform-width pointers to values that live elsewhere, which preserves the arithmetic and quietly reintroduces the pointer-chasing that arrays are meant to avoid.
Valid indices run from 0 to length − 1. Reading past that in C or C++ is undefined behaviour and returns whatever memory happens to be adjacent, which is the mechanism behind buffer-overflow vulnerabilities; managed languages check the bound and throw instead, trading a comparison per access for safety.
- Contiguous storage plus fixed width makes
base + i × widthwork - Access is O(1) regardless of position or array size
- Zero-based indexing means the index is an offset, not a count
- Valid indices are 0 to length − 1 — unchecked in C, checked elsewhere
Length, Capacity, and Growth
A static array has its size fixed when it is created and cannot change. A dynamic array — vector in C++, ArrayList in Java, list in Python — presents itself as growable, and the mechanism behind that is worth knowing because it explains an entire class of performance surprises.
Two numbers are tracked, and confusing them is a common error. The length is how many elements are actually stored. The capacity is how many the currently allocated block could hold. Capacity is always at least the length and usually more; the difference is unused space held in reserve, invisible to the user of the structure.
Appending when capacity remains is trivial: write at index length and increment. Appending when the block is full cannot extend it in place, because the adjacent memory belongs to something else. Instead a larger block is allocated, every existing element is copied into it, and the old block is freed. That copy is O(n).
The saving grace is the growth policy. Implementations do not add a fixed number of slots — they multiply, typically doubling. Because each resize costs proportionally more but happens proportionally less often, the total copying across n appends stays O(n), so the average cost per append is constant. Append is amortised O(1).
Amortised is not the same as guaranteed, and the difference has consequences. Most appends are instant; one occasionally copies the entire array. For a real-time system with a latency deadline, that unpredictable stall is a genuine problem, and the fix is to reserve the expected capacity up front so no resize occurs mid-operation. Growing an array to a million elements without reserving performs about twenty reallocations and copies roughly two million elements in total.
Shrinking is generally not automatic. Removing elements lowers the length but usually leaves the capacity alone, so an array that was briefly large keeps holding that memory — which is why C++ has shrink_to_fit and why memory profiles sometimes show a collection retaining far more than its contents justify.
| Operation | Cost | Why |
|---|---|---|
| Access or update by index | O(1) | One address computation |
| Append with spare capacity | O(1) | Write and increment the length |
| Append triggering a resize | O(n) | Allocate a bigger block and copy everything |
| Append, averaged | Amortised O(1) | Doubling makes resizes exponentially rare |
| Insert or delete in the middle | O(n) | Every later element shifts one slot |
| Search an unsorted array | O(n) | Every element may need checking |
| Search a sorted array | O(log n) | Binary search halves the range |
- Length is what exists; capacity is what fits
- A full append allocates a bigger block and copies — O(n)
- Doubling makes append amortised O(1), not worst-case O(1)
- Reserve capacity up front when a latency spike is unacceptable
Insertion, Deletion, and Order
Inserting into the middle of an array is expensive for the same reason access is cheap. Contiguity leaves no gap to insert into, so room must be made: every element from the insertion point onwards shifts one slot to the right. Inserting at the front shifts all n elements, making it the worst case at O(n).
Deletion is the mirror image. Removing an element leaves a hole that must be closed by shifting everything after it one slot left, again O(n). The cost is proportional to how many elements sit after the position, so removing from the end is O(1) and removing from the front is O(n).
There is a faster deletion when order does not matter: overwrite the doomed element with the last element and decrease the length. This 'swap and pop' is O(1) and does no shifting at all. It is the right move for an unordered collection and completely wrong for one where position carries meaning — worth naming explicitly, since the trade is exactly order for speed.
When many removals are needed, doing them one at a time is O(n) each and O(n²) overall. The better approach is a single pass with two pointers: a read index scanning every element and a write index marking where the next keeper goes. Copy forward only the elements that survive, then truncate. One pass, O(n) total, and it is the standard shape for remove-duplicates and remove-by-value problems.
A related distinction worth carrying into sorting: an algorithm is stable if elements comparing equal keep their original relative order. That matters whenever data is sorted by one key and then another, since a stable second sort preserves the first ordering within ties.
- Insertion and deletion shift every element after the position
- Cost depends on distance from the end — the front is worst
- Swap-with-last deletes in O(1) when order is irrelevant
- Batch removals with a read and a write pointer in one O(n) pass
Terms, operations, and practical uses
Memory model
- Base addressThe location of the first slot in the contiguous block.
- IndexA zero-based offset used in
base + index × element width. - LengthThe number of logical elements currently stored.
- CapacityThe number of slots available before another allocation is required.
Costs that matter
- Indexed readConstant time because address arithmetic jumps directly to a slot.
- Middle insertionLinear time when the suffix must shift right to preserve order.
- Dynamic appendAmortized constant time; an occasional resize copies the existing prefix.
Common uses
- Prefix summaryStore information about everything before an index to answer later range questions quickly.
- Sliding windowTrack one contiguous region while its left and right boundaries move.
- Binary searchDiscard half of an ordered search interval after each comparison.
Insert into a full dynamic array (grow, then shift)
# What list.insert() does underneath: grow if full, then shift.
data = [10, 20, 30, 40] # length 4, capacity 4
capacity = 4
length = 4
def insert(index, value):
global data, capacity, length
if length == capacity:
# no room: grow first
capacity *= 2 # geometric growth keeps append O(1) amortised
bigger = [None] * capacity
for k in range(length):
# O(n) copy into the new block
bigger[k] = data[k]
data = bigger
for k in range(length, index, -1):
# walk backwards so nothing is overwritten
data[k] = data[k - 1]
data[index] = value
length += 1
insert(2, 25)
print(f"{data[:length]} capacity {capacity}")#include <iostream>
using namespace std;
int* data_ = new int[4]{10, 20, 30, 40};
int capacity = 4, length = 4;
void insert(int index, int value) {
if (length == capacity) { // no room: grow first
capacity *= 2; // geometric growth
int* bigger = new int[capacity];
for (int k = 0; k < length; k++) { // O(n) copy
bigger[k] = data_[k];
}
delete[] data_; // old pointers are now dangling
data_ = bigger;
}
for (int k = length; k > index; k--) { // shift backwards
data_[k] = data_[k - 1];
}
data_[index] = value;
length++;
}
int main() {
insert(2, 25);
cout << '[';
for(int k = 0; k < length; k++) {
if (k) cout << ", ";
cout << data_[k];
}
cout << "] capacity " << capacity << '\n';
}public class Main {
static int[] data = {10, 20, 30, 40};
static int capacity = 4, length = 4;
static void insert(int index, int value) {
if (length == capacity) { // no room: grow first
capacity *= 2; // geometric growth
int[] bigger = new int[capacity];
for (int k = 0; k < length; k++) { // O(n) copy
bigger[k] = data[k];
}
data = bigger;
}
for (int k = length; k > index; k--) { // shift backwards
data[k] = data[k - 1];
}
data[index] = value;
length++;
}
public static void main(String[] args) {
insert(2, 25);
for (int k = 0; k < length; k++) {
System.out.print(data[k] + " ");
}
System.out.println("capacity " + capacity);
}
}Step through it
Running on [10, 20, 30, 40] at capacity 4, insert 25 at index 2
Read all 11 Steps
- A full array The array holds 4 values in a block of capacity 4. Length equals capacity, so there is no free slot at the end. The addresses run 1000, 1004, 1008, 1012 — four bytes apart, which is what makes indexing arithmetic.
- Request: insert 25 at index 2 We want 25 to sit between 20 and 30. Two problems: there is no spare slot, and the values at index 2 and 3 must not be overwritten.
- Capacity check fails length (4) equals capacity (4). Before anything can be inserted, the array must grow. This is the branch a fixed-size array cannot take at all.
- Allocate double the capacity Request a fresh block of 8 slots at a new address. Growth is geometric — doubling, not adding one — which is what keeps appends O(1) amortised instead of O(n).
- Copy the old elements Every existing value is copied into the new block. This copy is O(n), and it is the cost that geometric growth spreads thinly across many cheap appends.
- Free the old block The original block is released. In C or C++ every pointer into it is now dangling, and in higher-level languages any saved reference to the old storage is stale. This is why a resize invalidates iterators.
- Shift: copy 40 right Now the insertion itself. Start at the last element and work backwards, so nothing is overwritten before it has been moved. 40 goes from index 3 to index 4.
- Shift: copy 30 right Move one position left and repeat. 30 goes from index 2 to index 3. Index 2 is now safe to overwrite.
- Write 25 at index 2 The hole is open, so the new value is written. Only now does the array hold the intended order.
- Update length Length becomes 5, capacity stays 8. The three unused slots are the price paid for the next three appends being free.
- What this cost Two O(n) passes ran: one to copy into the larger block, one to shift for the insertion. Appending at the end would have skipped the shift entirely — which is why appending is the operation arrays are good at, and inserting in the middle is not.
The Patterns Arrays Are Built For
Most array algorithms are one of a few recurring shapes, and recognising the shape is most of solving the problem.
Two pointers run indices from opposite ends inward, or both forward at different rates. It applies when the array is sorted or when a relationship between two positions is being sought — pair sums, reversal, palindrome checks, partitioning. It replaces a nested loop with a single pass, taking O(n²) down to O(n).
Sliding window maintains a contiguous range and moves its boundaries rather than rebuilding it. When the range grows or shrinks by one, the summary of its contents — a sum, a count, a frequency map — can be updated incrementally instead of recomputed. This is the shape for 'longest or shortest subarray satisfying a condition'.
Prefix sums precompute cumulative totals so any range sum becomes one subtraction, trading O(n) space for O(1) queries. Binary search halves the search range each step on sorted data, and generalises to searching an answer space rather than an array.
Hashing trades memory for lookup: a set or map built from one pass over the array answers 'have I seen this value' in O(1), turning many nested-loop problems into single passes. Two-sum is the archetype.
Underneath all of them sits an advantage the notation cannot show. Array elements are adjacent in memory, so the CPU loads them in cache lines and prefetches ahead of a sequential scan. A linked structure with identical big-O can run several times slower because each hop risks a cache miss costing hundreds of cycles. When two approaches tie asymptotically, the array-based one usually wins in practice — and it is why iterating in memory order, rather than by stride, can change the runtime of the same loop by an order of magnitude.
- Two pointers replace nested loops on sorted or paired data
- Sliding window updates a range summary incrementally
- Prefix sums buy O(1) range queries with O(n) space
- Sequential access is prefetched — locality often decides real speed