Arrays

Overview

An array stores elements in a contiguous block of memory, so each element is reachable by its index in O(1) time. Reading or updating by index is fast, but inserting or removing in the middle is O(n) because later elements must shift. In Python the built-in list is a dynamic array that grows automatically, giving amortized O(1) appends.

Syntax / Usage

Create a list, index into it, and use the common operations.

scores = [90, 85, 72]

print(scores[0])      # O(1) read -> 90
scores[1] = 88        # O(1) update

scores.append(60)     # amortized O(1) add to end
scores.insert(0, 100) # O(n) shift everything right
scores.pop()          # O(1) remove from end
scores.pop(0)         # O(n) shift everything left

print(len(scores))    # O(1)
print(72 in scores)   # O(n) linear search

Examples

Summing values with a simple loop:

temps = [21, 19, 24, 30]
total = 0
for t in temps:       # O(n) traversal
    total += t
print(total / len(temps))  # average -> 23.5

Filtering into a new array with a comprehension:

nums = [4, 7, 10, 3, 8]
evens = [n for n in nums if n % 2 == 0]  # O(n)
print(evens)  # [4, 10, 8]

Common Mistakes

• Assuming middle inserts/removes are cheap — they are O(n) due to shifting
• Using x in list inside a loop, turning an algorithm into O(n^2)
• Off-by-one errors accessing arr[len(arr)], which is out of range
• Mutating a list while iterating over it, skipping elements
• Confusing a shallow copy (b = a) with a real copy (b = a[:])

See Also

data-structures-linked-lists data-structures-stacks data-structures-hash-tables