Arrays

An array is a data structure that stores a finite collection of elements, typically of the same type, in consecutive memory locations and accessible by a numeric index. In most implementations, indexing starts at 0 and the length of the array is the number of stored elements. Arrays offer constant-time access to any element, which makes them cache-friendly due to their contiguous layout.

Arrays come in static and dynamic forms. Static arrays have a fixed length determined at creation, so resizing requires allocating a new array and copying elements. Dynamic arrays, or resizable arrays, allocate additional capacity and grow when needed, resulting in amortized constant time for append operations. Multidimensional arrays are arrays of arrays and can model matrices; some languages enforce rectangular shapes, while others permit jagged arrays with rows of differing lengths.

Common operations include reading and writing by index, querying length, and iterating over elements. In many languages, additional operations such as copying, slicing, reversing, and sorting are provided by standard libraries or algorithms. Insertion or deletion at arbitrary positions typically incurs O(n) time because elements must be shifted. Copying arrays creates a new array and duplicates elements.

Memory considerations are important: elements are stored contiguously, which affects space efficiency and access patterns. Dynamic arrays separate the logical size from the allocated capacity, influencing when reallocations occur. Arrays underpin many data structures and are used to implement strings, buffers, matrices, and as the foundational sequence type in numerous programming languages.