What is an Array?
Arrays are one of the most fundamental data structures in programming. An array is a collection of elements stored in contiguous memory locations—meaning they sit side-by-side in the computer's memory.
This simple property makes arrays extremely fast for certain operations!
Sequential Storage in Memory
When you create an array, the computer allocates a continuous block of memory to store all elements together:
Each element occupies a fixed amount of space (e.g., 4 bytes for a 32-bit integer), and they're placed one after another without gaps. This is fundamentally different from scattered data structures like linked lists.
Key insight: Because elements are side-by-side, the computer can calculate exactly where any element is using simple arithmetic—no searching required!
Zero-based Indexing
Arrays use zero-based indexing, meaning the first element is at index 0, not 1:
Why zero-based? It simplifies the address calculation formula: address = base + (index × element_size). With zero-based indexing, the first element requires zero offset from the base address.
- Index 0: First element (1st position)
- Index 1: Second element (2nd position)
- Index 2: Third element (3rd position)
- Index n-1: Last element (nth position)
Direct Access via Index
The most powerful feature of arrays is O(1) direct access—you can jump to any element instantly using its index:
The formula:
element_address = base_address + (index × element_size)
This simple calculation gives the exact memory location of any element. No loops, no searching—just arithmetic!
Why Arrays are Fast
Arrays have several advantages that make them one of the fastest data structures:
1. Direct access (O(1)): Simple address calculation, no pointer chasing
2. CPU cache friendly: Contiguous memory means nearby elements are loaded into CPU cache together
3. Predictable memory layout: CPU can prefetch data and optimize access patterns