An array is a data structure that stores a sequence of elements of the same type in one contiguous block of memory, so that any element can be reached directly through its numeric index. Among data structures in programming, the array is the most fundamental: many other structures, including stacks, queues, hash tables and heaps, are built on top of it.
Its defining strength is constant-time random access, written as O(1). Its defining weakness is the cost of changing its size or inserting in the middle, which may require shifting or copying many elements.
How an array locates its elements
An array finds any element with a single calculation: address = base address + index × element size. Because every element occupies the same number of bytes and the elements sit side by side, the processor needs no search and no pointer chasing. For an array of 4-byte integers starting at address 1000, the element at index 5 lies at 1000 + 5 × 4 = 1020.
This layout explains why most languages use zero-based indexing: the index is simply the offset from the start. It also explains why arrays are so fast on modern hardware. A typical 64-byte cache line holds sixteen 4-byte integers, so reading one element brings its neighbors into the cache, and sequential loops benefit from hardware prefetching.
The table below gives the time complexity of the main array operations.
| Operation | Static array | Dynamic array | Reason |
|---|---|---|---|
| Read or write by index | O(1) | O(1) | Direct address calculation |
| Search for a value, unsorted | O(n) | O(n) | Every element may need checking |
| Search for a value, sorted | O(log n) | O(log n) | Binary search halves the range |
| Append at the end | Not possible | O(1) amortized | Occasional resize copies all elements |
| Insert or delete in the middle | O(n) | O(n) | Later elements must shift |
Static and dynamic arrays
A static array has a size fixed when it is created, as with int a[10] in C. A dynamic array grows on demand: it keeps spare capacity beyond its current length, and when the capacity runs out it allocates a larger block, copies the elements and frees the old one.
The growth strategy is what makes appending cheap on average. If the capacity grows by a constant factor, such as 1.5 or 2, the total copying cost over n appends stays proportional to n, giving amortized O(1) appends. Growing by a fixed number of slots instead would make appends O(n) on average, which is a classic performance mistake.
| Language | Fixed-size form | Growable form | Notes |
|---|---|---|---|
| C | int a[10] | Manual realloc | No bounds checking |
| C++ | std::array | std::vector | Growth factor depends on the library, usually 1.5 or 2 |
| Java | int[] | ArrayList | Bounds checked; ArrayList grows by about 1.5 |
| Python | array module, NumPy ndarray | list | A list stores references, not raw values |
| JavaScript | Typed arrays such as Float64Array | Array | Engines optimize dense arrays internally |
A multidimensional array stores rows and columns in one block, either in row-major order, as in C and NumPy by default, or in column-major order, as in Fortran and MATLAB. Iterating in the same order as the memory layout can be several times faster on large matrices because of cache behavior.
Arrays compared with other data structures
Choosing an array over another structure is a trade between fast indexed access and cheap structural changes. The table compares the array with neighboring structures in the same topic.
| Structure | Access by position | Insert in the middle | Memory layout |
|---|---|---|---|
| Array | O(1) | O(n) | Contiguous, cache friendly |
| Linked list | O(n) | O(1) once the node is found | Scattered nodes with pointers |
| Hash table | Not ordered by position | O(1) average by key | Array of buckets |
| Balanced tree | O(log n) with size tracking | O(log n) | Nodes with child pointers |
In practice, arrays often win even where theory favors a linked list, because cache locality outweighs asymptotic advantages for small and medium sizes. A stack and a queue are usually implemented on an array or a circular buffer for the same reason.
Common mistakes when working with arrays
The most serious array error is accessing an index outside the valid range. Languages such as Java, Python and Rust check bounds and raise an error, while C and C++ do not, so an out-of-bounds write can silently corrupt memory. Buffer overflows of this kind remain one of the most exploited classes of security vulnerabilities.
| Symptom | Cause | Fix |
|---|---|---|
| Last element skipped or one extra read | Off-by-one error in loop bounds | Loop with i < length for zero-based arrays |
| Memory corruption or crash in C | Missing bounds check | Validate indexes; use checked containers |
| Slow appends in a loop | Growth by a fixed increment | Grow geometrically or reserve capacity |
| Elements skipped while removing | Modifying the array during iteration | Iterate backward or build a new array |
| Reference to stale data after append | Pointer invalidated by reallocation | Re-fetch references after growth |
The simple explanation
An array is like a row of numbered lockers of identical size. Because every locker is the same width and they stand side by side, you can walk straight to locker 37 without opening the first 36.
The catch is that the row is built in one piece. Adding a locker in the middle means moving every locker after it, and when the row is full, a longer row has to be built and everything carried over. Arrays are therefore ideal when you mostly read by position and rarely reshuffle.
How it is used in practice
A photo-editing application stores a 4000 × 3000 pixel image as one array of 12 million pixels, each with four 1-byte channels for red, green, blue and alpha. That is 48 million bytes, about 46 MiB, in a single contiguous block, with the pixel at row y and column x found at index y × 4000 + x.
When a brightness filter runs, it walks through the array row by row, matching the row-major memory layout. The processor streams memory sequentially, prefetches the next cache lines and can apply vector instructions to many pixels at once. A version that walked column by column performed the same arithmetic but ran several times slower because almost every access missed the cache.