The array is the most fundamental physical data structure in computer science. Every high-level collection (matrices, hash tables, dynamic lists, strings) is built upon arrays.
Memory Contiguity: How Arrays are Stored
An array is defined as a collection of elements of identical data type stored in contiguous (unbroken) memory locations.
Array elements: [ 42, 19, 88, 73 ]
Index: 0 1 2 3
Memory Address: 0x1000 0x1004 0x1008 0x100C (assuming 4-byte 32-bit Int)
Because every element is identical in byte size and located back-to-back, the CPU does not need to traverse nodes or follow pointers to locate an item.
The O(1) Address Translation Formula
To access an element at index i, the hardware computes the memory address with a single arithmetic equation:
Address(A[i]) = Base Address + (i × Element Size in Bytes)
Calculation Walkthrough
Suppose an array of 32-bit integers (size = 4 bytes) starts at base address 0x2000:
Address(A[0]) = 0x2000 + (0 * 4) = 0x2000Address(A[1]) = 0x2000 + (1 * 4) = 0x2004Address(A[3]) = 0x2000 + (3 * 4) = 0x200C
Because addition and multiplication take O(1) CPU clock cycles, array random access by index is strictly O(1) constant time.
Why are arrays 0-indexed? The index i is not an ordinal counting number; it is an offset (displacement) from the base memory address. The first element has an offset of 0!
Time Complexity of Array Operations
| Operation | Best Case | Average Case | Worst Case | Reason |
|---|---|---|---|---|
| Access by Index | O(1) | O(1) | O(1) | Direct address calculation |
| Search by Value | O(1) | O(n) | O(n) | Linear scan (unsorted) |
| Insertion at End | O(1) | O(1) | O(1) | If capacity available |
| Insertion at Index 0 | O(n) | O(n) | O(n) | Must shift all n items right |
| Deletion at End | O(1) | O(1) | O(1) | Decrement size pointer |
| Deletion at Index 0 | O(n) | O(n) | O(n) | Must shift all n items left |
Shifting During Insertion and Deletion
Inserting an element into the middle of an array requires shifting subsequent elements:
Initial: [ 10, 20, 30, 40, 50 ]
Insert 25 at index 2:
Step 1 (Shift): [ 10, 20, --, 30, 40, 50 ] (items 30, 40, 50 shifted right)
Step 2 (Write): [ 10, 20, 25, 30, 40, 50 ]
This linear shift cost (O(n)) is the primary disadvantage of arrays when frequent middle insertions or removals are needed.
Summary
- Arrays allocate a single contiguous block of physical memory for elements of uniform size.
- Direct mathematical indexing formula enables constant time
O(1)random access. - Inserting or deleting elements at arbitrary positions requires shifting elements, resulting in
O(n)time complexity.