The simplest structure in computing — and still one of the most important.
What Is an Array?
An array is a collection of elements stored in contiguous (adjacent) memory locations, all of the same data type, accessible via an integer index.
Index: [0] [1] [2] [3] [4]
Values: [10] [20] [30] [40] [50]
Address: 100 104 108 112 116 (assuming 4 bytes per int)
Three key properties define an array:
- Fixed size — Declared at creation; cannot change (in most languages).
- Homogeneous — All elements are the same type.
- Random access — Any element can be accessed in O(1) by its index.
How Arrays Work in Memory
When you declare int arr[5], the system allocates 5 × 4 = 20 consecutive bytes in memory.
To access arr[i], the CPU computes:
address_of(arr[i]) = base_address + (i × size_of_element)
For example, if the base address is 100 and each int is 4 bytes:
-
arr[0]→ 100 -
arr[1]→ 104 -
arr[3]→ 112
This formula explains why array indexing is O(1) — it's simple arithmetic, no searching required.
Types of Arrays
1. One-Dimensional Array
The classic linear array: a single row of elements.
arr = [5, 10, 15, 20, 25]
2. Two-Dimensional Array (Matrix)
An array of arrays — rows and columns.
matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
# Access: matrix[row][col] → matrix[1][2] = 6
3. Multi-Dimensional Array
Arrays with 3 or more dimensions. Common in scientific computing, image processing (height × width × channels), and game development.
4. Dynamic Array
Languages like Python (list), Java (ArrayList), and C++ (vector) provide arrays that resize automatically. Under the hood, they allocate a larger chunk of memory when full and copy elements over. Amortized O(1) append.
Core Array Operations
1. Traversal — O(n)
Visit every element exactly once.
def traverse(arr):
for element in arr:
print(element)
Used for: printing, summing, searching, transforming.
2. Insertion
At the end (if space available): O(1)
arr[last_index + 1] = new_value
At a specific index: O(n) — all elements after the index must shift right.
def insert_at(arr, index, value):
# Shift elements right from the end
for i in range(len(arr) - 1, index, -1):
arr[i] = arr[i - 1]
arr[index] = value
Before: [10, 20, 30, 40, _] Insert 25 at index 2
Shift: [10, 20, 30, 30, 40]
After: [10, 20, 25, 30, 40]
Time complexity: O(n) worst case (inserting at index 0 shifts everything).
3. Deletion
From the end: O(1) — just decrement the size counter.
From a specific index: O(n) — elements after the deleted position must shift left.
def delete_at(arr, index, size):
for i in range(index, size - 1):
arr[i] = arr[i + 1]
arr[size - 1] = None # Clear the last slot
return size - 1
Before: [10, 20, 30, 40, 50] Delete at index 1 (value 20)
Shift: [10, 30, 40, 50, _]
Time complexity: O(n) worst case.
4. Search
Linear Search (unsorted array) — O(n)
def linear_search(arr, target):
for i, val in enumerate(arr):
if val == target:
return i
return -1
Binary Search (sorted array) — O(log n)
def binary_search(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
5. Update / Access — O(1)
arr[index] = new_value # Update
value = arr[index] # Access
Direct index access is the killer feature of arrays — no traversal needed.
6. Sorting
Arrays can be sorted in-place. Complexity depends on the algorithm:
| Algorithm | Best | Average | Worst | Space |
|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) |
Complexity Summary for Arrays
| Operation | Time Complexity |
|---|---|
| Access by index | O(1) |
| Update by index | O(1) |
| Search (unsorted) | O(n) |
| Search (sorted) | O(log n) |
| Insert at end | O(1) amortized |
| Insert at index | O(n) |
| Delete from end | O(1) |
| Delete from index | O(n) |
| Traverse | O(n) |
Arrays vs. Linked Lists: A Quick Comparison
| Property | Array | Linked List |
|---|---|---|
| Memory layout | Contiguous | Non-contiguous |
| Access by index | O(1) | O(n) |
| Insertion (middle) | O(n) — shifting | O(1) — pointer swap |
| Deletion (middle) | O(n) — shifting | O(1) — pointer swap |
| Memory overhead | Low (just data) | Higher (data + pointer per node) |
| Cache performance | Excellent | Poor (pointer chasing) |
| Size flexibility | Fixed (or amortized) | Truly dynamic |
Use arrays when: You need fast random access, know the size in advance, and rarely insert/delete in the middle.
Use linked lists when: You insert/delete frequently at arbitrary positions and don't need random access.
Common Array Patterns in Problem Solving
Two Pointers
# Reverse an array in-place
def reverse(arr):
left, right = 0, len(arr) - 1
while left < right:
arr[left], arr[right] = arr[right], arr[left]
left += 1
right -= 1
Sliding Window
# Maximum sum subarray of size k
def max_sum(arr, k):
window = sum(arr[:k])
max_sum = window
for i in range(k, len(arr)):
window += arr[i] - arr[i - k]
max_sum = max(max_sum, window)
return max_sum
Prefix Sum
# Precompute prefix sums for O(1) range queries
def build_prefix(arr):
prefix = [0] * (len(arr) + 1)
for i, val in enumerate(arr):
prefix[i + 1] = prefix[i] + val
return prefix
def range_sum(prefix, l, r):
return prefix[r + 1] - prefix[l] # O(1) query
Summary
- Arrays store elements contiguously in memory, enabling O(1) random access.
- Access and update are O(1); traversal is O(n); insertion and deletion in the middle are O(n) due to shifting.
- Types include 1D, 2D, multi-dimensional, and dynamic arrays.
- Binary search (O(log n)) only works on sorted arrays.
- Arrays excel at random access; linked lists excel at frequent middle insertions/deletions.
- Powerful algorithmic patterns built on arrays: two pointers, sliding window, prefix sums.
Next up: Linear Search vs. Binary Search — a detailed comparison of the two fundamental searching strategies.
Top comments (0)