Arrays — Introduction
Learn what arrays are, how they work in memory, and the key operations that make them the most fundamental data structure.
Arrays
An array is a collection of elements stored in contiguous memory locations, where each element is accessible directly by its index. It is the most fundamental data structure in computer science — almost every other structure is built on top of it or compared against it.
Think of an array like a row of numbered lockers in a school hallway. Each locker has a number (the index) and holds something inside (the value). To get to locker 5, you go directly to locker 5 — you do not open lockers 1, 2, 3, 4 first.
How arrays work in memory
When you create an array, the computer reserves a contiguous block of memory — slots sitting right next to each other. Because each slot is the same size, the computer can calculate the exact memory address of any element instantly:
address of element[i] = base_address + (i × element_size)This is why accessing any element by index is O(1) — constant time, regardless of array size.
Key operations and their complexity
| Operation | Time | Why |
|---|---|---|
| Access by index | O(1) | Direct memory calculation |
| Search (unsorted) | O(n) | Must check each element |
| Search (sorted) | O(log n) | Binary search |
| Insert at end | O(1) amortized | Just append |
| Insert at position | O(n) | Must shift elements right |
| Delete at position | O(n) | Must shift elements left |
| Delete at end | O(1) | Just remove last |
Arrays in Python
Python's list is a dynamic array — it grows automatically when needed:
# create
arr = [10, 20, 30, 40, 50]
# access — O(1)
print(arr[0]) # 10
print(arr[-1]) # 50
# insert at end — O(1) amortized
arr.append(60)
# insert at position — O(n)
arr.insert(2, 99)
# delete at position — O(n)
arr.pop(2)
# delete at end — O(1)
arr.pop()
# search — O(n)
print(30 in arr)
print(arr.index(30))Static vs dynamic arrays
Static array — fixed size, set at creation. Fast, predictable memory. Used in C, Java.
Dynamic array — grows automatically. Python's list is a dynamic array. When it runs out of space, it allocates a new block (usually 2x the size) and copies everything over. This copy is O(n) — but it happens rarely enough that the average cost stays O(1).
Python lists are dynamic arrays under the hood. When you call append(), Python occasionally needs to resize and copy the whole array. But this happens so infrequently that the amortized (averaged) cost per append is still O(1).
When to use an array
| Situation | Use array? |
|---|---|
| Need fast access by index | Yes |
| Data is ordered and accessed sequentially | Yes |
| Frequent insert/delete at end | Yes |
| Frequent insert/delete in the middle | No — use linked list |
| Need fast search in unsorted data | No — use hash map |
| Need fast search in sorted data | Yes — with binary search |
What is coming in this section
Sliding window — a technique for finding subarrays or substrings that satisfy a condition. One of the most common interview patterns.
Two pointers — two indices moving through an array simultaneously. Solves many problems in O(n) that would otherwise require O(n²).
Prefix sum — precompute cumulative sums to answer range queries in O(1) instead of O(n).