Arrays
An array is a collection of elements stored in contiguous memory locations, all of the same data type, accessible using an integer index. Arrays are the si...
The Foundational Data Structure Behind Most Programs
An array is a collection of elements stored in contiguous memory locations, all of the same data type, accessible using an integer index. Arrays are the simplest and most widely used data structure in programming, and most other structures are built on top of them.
When you declare an array of size n, the operating system allocates a single block of n times the element size bytes. If each integer is four bytes and the array has ten elements, the OS allocates forty bytes of contiguous memory. To access element at index i, the CPU computes the address as base_address plus i times element_size. This arithmetic is done in a single CPU instruction, making array access O(1) regardless of array size.
Arrays are cache-friendly. When you access an element, the CPU loads not just that element but a surrounding cache line, typically sixty-four bytes. Subsequent accesses to nearby elements find them already in cache, making sequential traversal extremely fast. This spatial locality advantage is one reason arrays often outperform linked lists in practice even when theoretical complexity is the same.
The primary limitation of arrays is their fixed size and the cost of insertions and deletions. Inserting an element at position i requires shifting all elements from i onward one position to the right, which costs O(n) in the worst case when inserting at the beginning. Similarly, deleting from position i requires shifting subsequent elements left. Appending to the end, however, is O(1) if the array has unused capacity.
Many languages provide dynamic arrays that resize automatically. Java's ArrayList, Python's list, and C++'s vector all wrap a raw array and double its capacity whenever it fills up. The doubling strategy means that across n appends, the total number of copy operations is at most 2n, giving O(1) amortized cost per append. Individual appends that trigger a resize still cost O(n) in that single operation.
Multi-dimensional arrays extend this concept to grids, cubes, and higher dimensions. A two-dimensional array, or matrix, is commonly stored in row-major order where all elements of row 0 come first, then row 1, and so on. Accessing elements row by row is cache-friendly; column-by-column access is not.
Worked example: finding the second largest element in an array of n integers. A naive approach sorts the array in O(n log n) and reads the second-to-last element. A single-pass approach maintains two variables, largest and second_largest, and updates them as it scans, giving O(n) time and O(1) space.
Interview tip: when working with arrays, always check for edge cases: empty array, single-element array, and all elements equal. These are the inputs most likely to expose off-by-one errors.