Arrays & Dynamic Arrays

What is an Array?

An array is a collection of elements, all of the same fixed size, stored in one contiguous block of memory. Because every element takes up the same number of bytes, the computer can calculate the exact memory address of any element instantly, without searching for it.

def get_price(prices: list[float], index: int) -> float:
    # Direct memory address calculation: O(1), regardless of list size
    return prices[index]

prices: list[float] = [19.99, 24.99, 9.99, 49.99]
print(get_price(prices, 2))

Here is that idea laid out in memory. Each cell is one 8-byte float, and the small offset under each is how many bytes past the start it begins:

Static vs Dynamic Arrays

How Dynamic Arrays Grow (Amortized Analysis)

A dynamic array starts with a small backing array. When it fills up, appending one more element requires: allocating a new, larger backing array (commonly double the size), copying every existing element into it, an O(n) operation, and only then placing the new element. CPython's actual list growth pattern isn't a clean doubling, but you can watch it grow in real time with sys.getsizeof:

import sys

items: list[int] = []
previous_capacity = 0

for i in range(12):
    items.append(i)
    capacity = sys.getsizeof(items)
    if capacity != previous_capacity:
        print(f"len={len(items)} bytes={capacity}")
        previous_capacity = capacity

len=1 bytes=88
len=5 bytes=120
len=9 bytes=184

Notice the list doesn't resize on every single append, it resizes in occasional bursts and over-allocates room for future growth. That over-allocation is exactly what makes append fast most of the time.

Building the Idea from Scratch

Here's a simplified dynamic array that doubles its capacity whenever it fills up, the same core idea behind Python's list:

class DynamicArray:
    def __init__(self) -> None:
        self._capacity: int = 4
        self._size: int = 0
        self._data: list[int | None] = [None] * self._capacity

    def append(self, value: int) -> None:
        if self._size == self._capacity:
            self._resize(self._capacity * 2)   # grow before the array is full
        self._data[self._size] = value
        self._size += 1

    def _resize(self, new_capacity: int) -> None:
        new_data: list[int | None] = [None] * new_capacity
        for i in range(self._size):
            new_data[i] = self._data[i]        # copy every existing element: O(n)
        self._data = new_data
        self._capacity = new_capacity

    def __getitem__(self, index: int) -> int:
        if index >= self._size:
            raise IndexError("index out of range")
        return self._data[index]

    def __len__(self) -> int:
        return self._size

arr = DynamicArray()
for i in range(10):
    arr.append(i)

print(len(arr), arr[9])

10 9

Time Complexity of Common Operations

Not every array operation costs the same. Adding or removing at the end is cheap, doing it anywhere else forces every following element to shift.

def insert_at_front(items: list[int], value: int) -> list[int]:
    # Every existing element must shift right by one position: O(n)
    items.insert(0, value)
    return items

def append_at_end(items: list[int], value: int) -> list[int]:
    # No shifting needed, the new slot is already reserved: O(1) amortized
    items.append(value)
    return items

The O(n²) Trap: Repeated Front Insertion

A single insert(0, x) is O(n). Calling it inside a loop that runs n times turns an innocent-looking function into an O(n²) one, exactly the kind of hidden cost Lesson 1 warned you to watch for.

def build_list_badly(n: int) -> list[int]:
    items: list[int] = []
    for i in range(n):
        items.insert(0, i)   # O(n) shift, repeated n times -> O(n^2) total
    return items

def build_list_efficiently(n: int) -> list[int]:
    items: list[int] = [i for i in range(n)]
    items.reverse()          # a single O(n) pass instead of n separate shifts
    return items

from collections import deque

def build_deque_efficiently(n: int) -> deque[int]:
    items: deque[int] = deque()
    for i in range(n):
        items.appendleft(i)  # O(1) per call, deque is backed by a doubly linked list of blocks
    return items