Array

An array is a data structure that stores a collection of elements, each identified by a numeric index. In many languages, elements are stored in contiguous memory, which allows efficient random access to a specific element by computing its offset from the start. Arrays are typically homogeneous, meaning all elements have the same data type, and they often have a fixed length determined when the array is created.

Elements are referenced by a zero-based index in most languages, though some use one-based indexing. The memory layout of multi-dimensional arrays can be organized as row-major or column-major, which affects how multi-dimensional indices map to a linear memory address. In addition to one-dimensional arrays, many languages support multi-dimensional arrays or arrays of arrays (jagged arrays), with different performance and storage characteristics.

Variations across languages include static arrays, which have a fixed size and simple semantics as in C, and arrays as first-class objects with length information, as in Java. Dynamic arrays grow or shrink as needed, typically by allocating a larger underlying storage and copying elements, as seen in C++ vectors, Java array lists, and Python lists. In Python, lists are dynamically sized and can hold heterogeneous elements, while NumPy provides fixed-size, homogeneous arrays suitable for numerical computing and performance-critical tasks.

Basic operations include reading and updating elements by index, iterating over elements, and searching for values. In general, random access is O(1), while searching is O(n). In fixed-size arrays, insertion or deletion often requires shifting elements, yielding O(n) time in the worst case. Dynamic arrays achieve amortized O(1) append operations through resizing.

Arrays are a foundational concept in programming and are used for buffers, matrices, tables, and function parameters, among other purposes.