Array (data structure)

In computer science, an array is a fundamental linear data structure consisting of a collection of elements, typically of the same data type, stored in contiguous memory locations and individually identified by at least one index or key.

Overview

An array is designed to store a fixed-size or dynamically resizable sequential collection of elements. Because the elements are stored in contiguous memory, the position of each element can be computed mathematically from its index tuple using a specific formula. This allows for constant-time access to any element, making arrays highly efficient for data retrieval. Arrays serve as the foundational building blocks for many other complex data structures, including heaps, hash tables, queues, and stacks.

Types of Arrays

Arrays can be categorized based on their dimensions and resizing capabilities:

• One-dimensional arrays: Often referred to as vectors or linear arrays, these represent a simple list of elements. A single index is required to access an element.
• Multidimensional arrays: These are arrays of arrays. A two-dimensional array is commonly known as a matrix, requiring two indices (row and column) to access an element. Higher-dimensional arrays (tensors) require correspondingly more indices.
• Static arrays: The size of a static array is determined at the time of creation and cannot be changed during the execution of the program. Memory is allocated once and remains fixed.
• Dynamic arrays: Also known as resizable arrays, these allow elements to be added or removed, automatically adjusting their capacity. Under the hood, dynamic arrays typically allocate a larger contiguous block of memory and copy existing elements when the current capacity is exceeded (e.g., std::vector in C++ or ArrayList in Java).

Memory Layout and Addressing

The defining characteristic of an array is its contiguous memory allocation. When an array is created, a single block of memory large enough to hold all its elements is reserved.

The memory address of a specific element can be calculated using the base address of the array (the address of the first element) and the size of each element. For a one-dimensional array, the address of the element at index $i$ is calculated as:
Address = Base_Address + (i × Element_Size)

For multidimensional arrays, the linear memory must map to a multi-index structure. There are two primary conventions for this mapping:

• Row-major order: Elements of each row are stored in contiguous memory locations. This is the default in languages like C, C++, and Python.
• Column-major order: Elements of each column are stored contiguously. This is the default in languages like Fortran, MATLAB, and R.

Operations and Time Complexity

The performance of array operations is generally measured using Big O notation:

• Access (Read/Write): $O(1)$. Because the memory address is calculated directly via an arithmetic formula, accessing or modifying an element by its index takes constant time.
• Search: $O(n)$ for unsorted arrays, as a linear search may be required. For sorted arrays, binary search can be applied, reducing the time complexity to $O(\log n)$.
• Insertion: $O(n)$ in the worst case. Inserting an element at the beginning or middle of a static array requires shifting all subsequent elements to make room. Inserting at the end is $O(1)$ if there is available capacity. In dynamic arrays, appending is amortized $O(1)$, but occasional resizing operations take $O(n)$.
• Deletion: $O(n)$. Similar to insertion, removing an element from the middle requires shifting all subsequent elements to fill the gap.

Advantages and Disadvantages

Advantages:

• Fast Access: Constant-time $O(1)$ retrieval and modification of elements via indexing.
• Cache Locality: Because elements are stored contiguously, arrays exhibit excellent spatial locality. When one element is loaded into the CPU cache, adjacent elements are likely loaded as well, significantly speeding up sequential processing.
• Memory Efficiency: Arrays do not require extra memory for pointers or structural metadata (unlike linked lists), storing only the raw data.

Disadvantages:

• Fixed Size (Static Arrays): The size must be known in advance. Over-allocating wastes memory, while under-allocating requires creating a new array and copying data.
• Costly Insertions and Deletions: Modifying the array structure in the middle requires shifting elements, which is computationally expensive for large datasets.
• Homogeneity: In many low-level languages, arrays can only store elements of a single data type, limiting flexibility without the use of complex structures or object references.

Applications

Arrays are ubiquitous in computer science and software engineering. Common applications include:

• Implementation of other data structures: Arrays are used to implement heaps, hash tables, deques, queues, and stacks.
• Mathematical computations: Multidimensional arrays are the standard representation for matrices and tensors in linear algebra, machine learning, and scientific computing.
• Lookup tables: Arrays are used to store precomputed results or mappings for rapid retrieval.
• Database records: Arrays can represent rows or columns in database management systems.
• Image and Audio processing: Digital images are typically represented as 2D or 3D arrays of pixel values, while audio signals are processed as 1D arrays of amplitude samples.

Implementation in Programming Languages

Different programming languages handle arrays with varying levels of abstraction:

• C and C++: Provide raw, static arrays that are essentially pointers to contiguous memory blocks. C++ also offers std::array for bounds-checked static arrays and std::vector for dynamic arrays.
• Java: Features built-in static arrays with strict bounds checking. For dynamic sizing, the java.util.ArrayList class is used.
• Python: Does not have a built-in static array type in its core syntax; instead, it uses list, which is a highly optimized dynamic array of pointers to objects. The array module provides C-style typed arrays.
• JavaScript: Arrays are dynamic, heterogeneous objects that can grow and shrink automatically and hold elements of mixed data types.