An array is the most fundamental data structure in computing: a contiguous block of memory that stores a sequence of elements, each the same size, laid out one after another. Because the elements are equally sized and packed together, the location of element number i can be computed directly from the address of the first element plus i times the element size. This arithmetic is what gives an array its defining property: constant-time, or O(1), random access to any position regardless of how large the array is.
Arrays map almost directly onto how physical computer memory works. Memory is itself a long sequence of numbered cells, so an array is little more than a named, typed window onto a stretch of those cells. This closeness to the hardware is why arrays are fast in practice as well as in theory: reading consecutive array elements walks through memory in order, which suits the way processors and their caches fetch data.
Donald Knuth treats arrays among the foundational structures in Volume 1 of The Art of Computer Programming, titled “Fundamental Algorithms,” which develops the representation of information inside a machine from first principles (Knuth’s pages at Stanford, verified 2026-06-08). The classic, simplest array is fixed in size: you decide how many elements it holds when you create it, and that capacity does not change. Adding more elements than the array was sized for requires allocating a new, larger block, which is the problem that the dynamic array was designed to solve.
The trade-off of an array is that its strength in access is mirrored by weakness in insertion and deletion in the middle. Removing or inserting an element at an interior position requires shifting every following element by one place to keep the block contiguous, an operation that costs time proportional to the number of elements moved. Structures such as the linked list make the opposite trade, sacrificing fast indexing to gain cheap insertion and removal at a known position.