The Static Array
An array is a collection of items stored in contiguous memory locations — meaning each element sits right next to the previous one in RAM, with no gaps. This physical layout is the source of both its greatest strength and its greatest weakness.
Imagine a row of numbered mailboxes in an apartment building. If you know the building's starting address and that each mailbox is exactly the same size, you can calculate the exact location of mailbox #500 without walking past mailboxes 1 through 499. You just do the math: start_address + (500 × item_size). This is random access, and it runs in O(1) — constant time regardless of array size.
The core operations and their complexities:
| Operation | Time Complexity | Why |
|---|---|---|
| Read by index | O(1) | Direct address calculation |
| Write by index | O(1) | Direct address calculation |
| Search (unsorted) | O(N) | Must check each element |
| Insert at end | O(1) | Just write to next slot |
| Insert at middle | O(N) | Must shift all elements right |
| Delete at middle | O(N) | Must shift all elements left |
The weakness is fixed size. When you declare int arr[10], the operating system reserves exactly 10 contiguous slots. If you need an 11th slot, those adjacent memory addresses may already be occupied by other data. You cannot simply extend the array in place.
Interviewers frequently ask: "What is the time complexity of inserting an element at the beginning of an array?" The answer is O(N) — every existing element must shift one position to the right to make room. This surprises candidates who assume all array operations are O(1). Contrast this with a Linked List, where prepending is O(1) because you only update a pointer.