Dynamic Array

Remember how a static array is like an egg carton with a fixed number of slots? A dynamic array solves this problem. It's essentially a smart static array that knows how to buy a bigger egg carton when the current one gets full.

Under the hood, it's still just a regular static array. But the dynamic array keeps track of two things:

Capacity: How many total slots the underlying static array has.
Size (or Length): How many slots you are actually using right now.

When the Size equals the Capacity, the array is full. If you try to add another item, the dynamic array performs a magical trick called a resize.

Dynamic Array: Append & Resize

# Python's list is a dynamic array
arr = []
for i in range(5):
    arr.append(i)       # O(1) amortized
    print(f"len={len(arr)} item={arr[-1]}")

arr.insert(2, 99)       # O(n) — shifts elements
print(arr)              # [0, 1, 99, 2, 3, 4]
print(arr.pop())        # 4   O(1) from end
print(arr.pop(0))       # 0   O(n) from front

Output

len=1 item=0
len=2 item=1
len=3 item=2
len=4 item=3
len=5 item=4
[0, 1, 99, 2, 3, 4]
4
0

The Resizing Trick

When the array fills up, it can't just securely claim the memory slot right next to it — that space might be used by another program. Instead, it has to move everything to a new, bigger location. Here is the process:

Create a brand-new static array that is twice as big as the old one.
Copy every single item from the old array into the new array, one by one.
Add the new item you wanted to insert into the first empty slot.
Delete the old, smaller array so the computer can reuse that memory.

Copying all those items takes \(O(n)\) time. It's an expensive operation!

Amortized Time (The "Almost Always Fast" Rule)

You might think appending to a dynamic array is slow because of the resizing. But because we double the capacity every time we resize, it happens very rarely.

If you add 8 items, you resize when adding the 1st, 2nd, 3rd, 5th, and 9th items. As the array gets huge (say, 1 million items), you have to add another million items before it resizes again! Most of the time, adding an item is an instant \(O(1)\) operation. We call this \(O(1)\) amortized time — which means "it's \(O(1)\) on average over a long period of time."

Complexity

Grab by indexUses the underlying static array

Instant\(O(1)\)

Add to the end (usually)When there is spare capacity

Instant\(O(1)\)

Add to the end (when full)Requires resizing and copying

Slow\(O(n)\)

Add to the end (Amortized)The average time over many insertions

Instant\(O(1)\)

Insert/Delete in the middleMust shift elements over

Slow\(O(n)\)

Custom Dynamic Array with Doubling

class DynamicArray:
    def __init__(self):
        self.data = [None] * 1
        self.size = 0
        self.capacity = 1

    def append(self, val):
        if self.size == self.capacity:
            self._resize()
        self.data[self.size] = val
        self.size += 1

    def _resize(self):
        self.capacity *= 2
        new = [None] * self.capacity
        for i in range(self.size): new[i] = self.data[i]
        self.data = new
        print(f"  Resized to capacity {self.capacity}")

    def get(self, i): return self.data[i]
    def __len__(self): return self.size

da = DynamicArray()
for v in [1, 2, 3, 4, 5]:
    da.append(v)
print([da.get(i) for i in range(len(da))])

Output

  Resized to capacity 2
  Resized to capacity 4
  Resized to capacity 8
[1, 2, 3, 4, 5]

Dynamic Array: Append & Resize

The Resizing Trick

Amortized Time (The "Almost Always Fast" Rule)

Complexity

Custom Dynamic Array with Doubling

Quick check