Dynamic Arrays

Implementation Details

Let's look at how we might implement a dynamic array using only fixed-size arrays.

The Challenge: Resizing

The challenging case is when the underlying fixed-size array is full. We call this process resizing.

When a full dynamic array resizes, it usually creates a larger contiguous block elsewhere in memory, then copies the existing elements into it.

If we increased capacity by only 1 slot, nearly every append would trigger this $O(n)$ copy. That is too slow.

Doubling is the standard interview choice. More generally, any fixed multiplier greater than $1$ preserves amortized $O(1)$ append; production libraries may choose a different factor.

Code Structure

We track two key properties:

• size: The number of actual elements.
• capacity: The number of "slots" in the underlying fixed-size array.

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

    def append(self, x):
        if self.size == self.capacity:
            self._resize(self.capacity * 2)
        
        self.fixed_array[self.size] = x
        self.size += 1

    def _resize(self, new_capacity):
        new_fixed_array = [None] * new_capacity
        for i in range(self.size):
            new_fixed_array[i] = self.fixed_array[i]
        self.fixed_array = new_fixed_array
        self.capacity = new_capacity

Optional Shrinking

Removing the last element normally just decreases size, so pop_back() is $O(1)$. Some implementations optionally shrink the backing array to reclaim memory; others keep the capacity until an explicit trim.

If you implement automatic shrinking, leave a gap between the grow and shrink thresholds:

• Shrink at 50%? Bad idea. If we hover around 50%, we might constantly resize and shrink (thrashing).
• Shrink at 25%? Good idea. Halve the capacity when the array is 25% full. After shrinking, it is 50% full—enough room to avoid repeated resizing without wasting too much space.

With this gap, pop_back() remains $O(1)$ amortized, although the occasional shrink itself costs $O(n)$.

Amortized Time Analysis

What does "amortized" mean?

Appending to a dynamic array has poor worst-case performance (when resizing happens, it takes $O(n)$), but excellent amortized performance ($O(1)$).

Extra Operations

It's important to distinguish between operations at the end of the array vs. arbitrary indices.

1. pop(i): Removes element at index i.

   • Time: $O(n)$. We must shift all elements after i one slot to the left to close the gap.
   • Note: If you need to pop from both ends often, consider a Deque (Double-Ended Queue).

2. insert(i, x): Inserts x at index i.

   • Time: $O(n)$. We must shift all elements from i onwards one slot to the right.

3. contains(x): Checks if x exists.

   • Time: $O(n)$. In an unordered array, we must scan linearly.

When to Use It

Key Takeaways