Arrays
An array is a contiguous block of memory where each element is the same size. This means you can jump directly to any element by index in O(1) time — just compute base_address + index * element_size.
Why It Matters
Arrays are the most fundamental data structure. Hash tables, heaps, and many sorting algorithms are built on top of arrays. Understanding their tradeoffs is essential.
Operations
| Operation | Time | Notes |
|---|---|---|
| Access by index | O(1) | Direct memory offset |
| Search (unsorted) | O(n) | Must scan every element |
| Search (sorted) | O(log n) | Binary Search |
| Insert at end | O(1) amortized | May need to resize |
| Insert at middle | O(n) | Must shift elements right |
| Delete at middle | O(n) | Must shift elements left |
Static vs Dynamic
- Static array (C, Go): fixed size, declared at creation
- Dynamic array (Python
list, JavaArrayList): grows automatically by doubling capacity when full
The doubling strategy gives O(1) amortized append — you rarely resize, and when you do, you copy everything (O(n)), but that cost is spread over n appends.
Code Example
# Python lists are dynamic arrays
nums = [10, 20, 30, 40, 50]
# O(1) access
print(nums[2]) # 30
# O(1) amortized append
nums.append(60) # [10, 20, 30, 40, 50, 60]
# O(n) insert at index (shifts elements)
nums.insert(0, 5) # [5, 10, 20, 30, 40, 50, 60]
# O(n) delete by value (shifts elements)
nums.remove(30) # [5, 10, 20, 40, 50, 60]
# Slicing creates a new array — O(k) where k = slice size
first_three = nums[:3] # [5, 10, 20]
# Common patterns
squares = [x**2 for x in range(10)] # list comprehension
matrix = [[0]*3 for _ in range(3)] # 2D array (3x3)Memory Layout
Arrays are cache-friendly because elements sit next to each other in memory. When the CPU loads one element, neighboring elements come into cache too. This is why array iteration is much faster than linked list iteration in practice, even when both are O(n).
Gotcha: Python Lists vs Real Arrays
Python list holds pointers to objects, not raw values. For numeric work, use array.array or numpy.ndarray for true contiguous storage.
from array import array
ints = array('i', [1, 2, 3, 4]) # actual C int arrayRelated
- Big O Notation — array operations complexity
- Bits Bytes and Memory — contiguous memory layout
- Hash Tables — built on arrays
- Sorting Algorithms — operate on arrays
- Two Pointers — common array technique