Array Basics

The Idea

An array stores items back to back in memory, so the computer can compute any slot's address with simple arithmetic. Reading or writing by index is O(1). Inserting in the middle is not, because everything after it has to shift.

Real-World Example

A parking garage numbers every space. You drive straight to space 47 without passing the other 46. But squeezing a brand new space into the middle of a row means renumbering every space after it.

The Code

prices = [12, 7, 30, 5]

print(prices[2])        # 30 -> O(1) direct access
prices[0] = 99          # O(1) overwrite
print(len(prices))      # 4  -> O(1), length is stored

prices.append(8)        # O(1) amortized, lands at the end
prices.insert(1, 42)    # O(n), shifts everything right
print(prices)           # [99, 42, 7, 30, 5, 8]

letters = ["a", "b", "c", "d"]
# print the third element
print(letters[___])