Array

Indexed boxes in a row.

An array stores items back-to-back in memory, numbered from 0. Because the elements are the same size and laid out contiguously, you can jump straight to any position with its index — no searching required.

• Access by index is instant: a[3].
• Fixed size in low-level languages; a dynamic array (like Python's list or Java's ArrayList) grows as needed.
• Best for ordered collections you read a lot and mostly append to.

Complexity and memory.

The address of element i is base + i × elementSize, so indexing is O(1). Inserting or deleting in the middle is O(n) because elements must shift.

Access by index      O(1)
Search (unsorted)    O(n)
Insert/delete at end O(1) amortized (dynamic array)
Insert/delete middle O(n)

Contiguous layout gives excellent cache locality, so arrays are often faster in practice than pointer-based structures with the same asymptotic complexity.

Dynamic arrays and amortization.

• Amortized append — a dynamic array doubles capacity when full; copying is O(n) but happens rarely, so appends average O(1) amortized.
• Growth factor — doubling (or ~1.5×) balances wasted space vs copy frequency; it also affects memory fragmentation and reuse.
• Multidimensional — row-major vs column-major layout affects cache performance of nested loops.
• vs Linked List — arrays win on random access and locality; linked lists win on O(1) insertion/deletion given a node reference.