Moving to a bigger shelf

Dynamic Arrays

The analogy

🧸 ELI5⚙ Tech

Your shelf is full and another book arrives. You cannot stretch the shelf, so you buy one twice the size and carry every book across. It is a big effort — but you only do it occasionally, so averaged over many books it stays cheap.

Visualizer

Outgrowing the shelf

step 1 / 30

A shelf with room for 4 books, holding 0. Capacity and length are different numbers.

🎯 Predict modespeed1×

PythonJavaScriptHow devs thinkWhere it's used

# CPython list append, in essence:
def append(self, v):
    if self.length == self.capacity:
        self.capacity = self.capacity * 2   # O(n) copy
        self.buf = self.buf + [None] * self.capacity
    self.buf[self.length] = v               # O(1)
    self.length += 1

# amortised O(1) because capacity DOUBLES

Check yourself

Amortised cost of appending to a dynamic array?