Implementing Dynamic Arrays

We have spent six sections using arrays. Now we build one. By the end of this section you will have written, line by line, both a Python DynamicArray backed by raw ctypes memory and a C++ Vector<T> with proper RAII and move semantics. These are not toys: the same ideas, often the same code shape, power CPython's list, libstdc++ std::vector, Java ArrayList, Go slices, Rust Vec, and JavaScript Array. Once you understand this section you understand all of them.

The thesis of this section. A dynamic array is just a fixed buffer plus two integers — size and capacity — managed by exactly two policies: geometric growth (double when full) and hysteretic shrink (halve when usage drops to a quarter). Get those two right and every operation is amortized O(1) or, where it can't be, optimal O(n − i).

The Contract: What a Dynamic Array Promises

Before we write a single line, we pin down the abstract data type — the public surface every reasonable dynamic array must expose, and the cost model the user can rely on:

Three private fields back this entire interface: a pointer to a contiguous buffer, a logical size $n$, and an allocated capacity $c$ with the perpetual invariant $0 \leq n \leq c$. Live elements occupy slots $A[0..n-1]$; slots $A[n..c-1]$ are reserved memory waiting to be used.

Memory Model: Going Below Python's list

There is a chicken-and-egg problem: Python's built-in list is itself a dynamic array, so if we build “our” dynamic array on top of it, we're really just renaming list operations. We need a real fixed-size primitive. The right tool is ctypes:

1import ctypes, sys
2
3cap = 4
4A = (ctypes.py_object * cap)()   # one allocation, 4 PyObject* slots
5print(sys.getsizeof(A))          # ~ 64 bytes on a 64-bit system
6A[0] = "hello"; A[1] = 42
7print(A[0], A[1])                # hello 42
8# A is FIXED-SIZE: there is no A.append, no A.extend.

The expression (ctypes.py_object * 4)() calls into the C allocator and reserves exactly$4 \cdot \textsf{sizeof}(\text{void*}) = 32$ bytes (plus a small header) for four object pointers, contiguous in memory. Crucially, that buffer cannot grow itself. To grow, we allocate a bigger one and copy.

Growth Strategy: Why Doubling Wins

When append finds the buffer full, it must allocate a new one of size $c'$ and copy $n$ elements over. The choice of $c'$ determines everything. Three strategies:

1. Constant additive growth: $c' = c + k$ for some constant $k$. Every $k$ appends triggers a resize, costing $\Theta(n)$ each time. Total cost of $n$ appends is $\Theta(n^2 / k)$. Catastrophic.
2. Geometric growth with factor $g > 1$: $c' = \lceil g \cdot c \rceil$. Resizes happen at sizes $g^0, g^1, g^2, \ldots$; total copy cost is $\sum_{k=0}^{\log_g n} g^k = \frac{g^{\log_g n + 1} - 1}{g - 1} \leq \frac{g}{g-1} n$. For $g = 2$: at most $2n$ total copies. Linear total work, O(1) amortized.
3. Doubling ($g = 2$): Simplest, cleanest, and what almost everyone uses. The newly-allocated unused space equals the previously used space, which makes the accounting argument fall out cleanly (next subsection).

Amortized Analysis: Two Proofs of O(1) append

Aggregate method

Consider $n$ appends starting from capacity 1 and doubling. The total cost is the cost of writing each element ($n$ writes, one each) plus the cost of all resizes. Resizes happen exactly when the buffer is full, at sizes $1, 2, 4, 8, \ldots, 2^{\lfloor \log_2 n \rfloor}$, copying that many elements each time:

$T(n) \;=\; \underbrace{n}_{\text{writes}} \;+\; \underbrace{\sum_{k=0}^{\lfloor \log_2 n \rfloor} 2^k}_{\text{resize copies}} \;\leq\; n + 2n \;=\; 3n.$

Dividing by $n$ gives an amortized cost of at most 3 per append — independent of $n$, hence $O(1)$.

Accounting (banker's) method

Charge each append a flat amortized cost of 3 dollars. Spend 1 dollar on the actual write, and store 2 dollars as “credit” on the new element. When the buffer fills at capacity $c$, every one of the $c$ live elements carries at least 2 dollars of credit (the latest-doubled half each carry 2; the older half carry even more, since they survived the previous resize too). The resize costs $c$ copies, payable from the $2c$ dollars in credit — with $c$ dollars to spare. The invariant holds for all time, so amortized cost ≤ 3.

Shrink Policy: The Hysteresis Trick

Symmetric reasoning suggests: when pop drops the size below half the capacity, halve the buffer to recover memory. This is wrong. Consider a sequence that alternates append and pop right at the boundary:

1. Suppose $n = c = 4$ (full, capacity 4).
2. append → grows to capacity 8, copies 4, now $n = 5, c = 8$.
3. pop → $n = 4$. With shrink-at-half: $4 \leq 8/2$ → halve to capacity 4, copies 4.
4. append → full again → grows to 8, copies 4. pop shrinks to 4, copies 4.Repeat forever.

Each operation now costs $\Theta(n)$. The amortized argument fails because we spend the credit immediately and have nothing left for the next resize.

Fix: shrink only when the size has dropped to a quarter of capacity, and when shrinking, halve to half of capacity. Now after a shrink we're at 50% utilization, and we need to either drop to 25% (requiring $c/4$ pops) or fill to 100% (requiring $c/2$ appends) before another resize. Every resize is matched by a long stretch of cheap operations — the credit fund stays solvent.

Insert and Delete: The O(n - i) Shifts

Random-position insert(i, v) and delete(i) are not amortized O(1). They require physically moving every element to the right of position $i$ by one slot — $n - i$ elements in the worst case. Inserting at the front is $\Theta(n)$; inserting at the end is $O(1)$ amortized.

Bounds Checks and the Iterator Protocol

Two more responsibilities round out the implementation:

1. Bounds checks on every read/write/delete. Negative indices should be normalized ($A[-1] = A[n-1]$) the way Python does. Out-of-range indices must raise IndexError — never write past the buffer end. Skipping this is the most common source of memory-corruption bugs in C-level dynamic arrays.
2. Iterator protocol. __iter__ yields A[0..n-1]. A subtle real-world bug: if the user mutates the array during iteration (e.g., append inside a for loop), a resize relocates the buffer; if your iterator captured the old pointer, it is now dangling. Python's built-in list reads self._A[k] on each step and tolerates appends-during-iteration (you may or may not see the new elements); insert/delete during iteration is undefined behavior even there. We follow the same rule.

Full Implementation: Python with ctypes

Here is the complete DynamicArray. Each line is annotated below — read the code, then click any line on the left to see why it does what it does.

1import ctypes
2
3
4class DynamicArray:
5    """A dynamic array built on a fixed-capacity ctypes buffer.
6
7    This is essentially what CPython's list does internally,
8    minus the per-element refcount bookkeeping in the C layer.
9    """
10
11    def __init__(self, initial_capacity: int = 4) -> None:
12        self._n: int = 0
13        self._capacity: int = max(1, initial_capacity)
14        self._A = self._make_array(self._capacity)
15
16    @staticmethod
17    def _make_array(capacity: int):
18        return (ctypes.py_object * capacity)()
19
20    def __len__(self) -> int:
21        return self._n
22
23    def _check_index(self, i: int) -> int:
24        if i < 0:
25            i += self._n
26        if not 0 <= i < self._n:
27            raise IndexError(f"index {i} out of range for size {self._n}")
28        return i
29
30    def __getitem__(self, i: int):
31        i = self._check_index(i)
32        return self._A[i]
33
34    def __setitem__(self, i: int, value) -> None:
35        i = self._check_index(i)
36        self._A[i] = value
37
38    def append(self, value) -> None:
39        if self._n == self._capacity:
40            self._resize(2 * self._capacity)
41        self._A[self._n] = value
42        self._n += 1
43
44    def pop(self):
45        if self._n == 0:
46            raise IndexError("pop from empty array")
47        self._n -= 1
48        value = self._A[self._n]
49        self._A[self._n] = None
50        if 0 < self._n <= self._capacity // 4 and self._capacity > 1:
51            self._resize(self._capacity // 2)
52        return value
53
54    def insert(self, i: int, value) -> None:
55        if not 0 <= i <= self._n:
56            raise IndexError(f"insert index {i} out of range")
57        if self._n == self._capacity:
58            self._resize(2 * self._capacity)
59        for k in range(self._n, i, -1):
60            self._A[k] = self._A[k - 1]
61        self._A[i] = value
62        self._n += 1
63
64    def delete(self, i: int) -> None:
65        i = self._check_index(i)
66        for k in range(i, self._n - 1):
67            self._A[k] = self._A[k + 1]
68        self._A[self._n - 1] = None
69        self._n -= 1
70        if 0 < self._n <= self._capacity // 4 and self._capacity > 1:
71            self._resize(self._capacity // 2)
72
73    def _resize(self, new_cap: int) -> None:
74        B = self._make_array(new_cap)
75        for k in range(self._n):
76            B[k] = self._A[k]
77        self._A = B
78        self._capacity = new_cap
79
80    def __iter__(self):
81        for k in range(self._n):
82            yield self._A[k]
83
84    def __repr__(self) -> str:
85        items = ", ".join(repr(self._A[k]) for k in range(self._n))
86        return f"DynamicArray([{items}], cap={self._capacity})"

Drive it with the canonical example:

1da = DynamicArray()             # n=0, cap=4
2for i in range(10):
3    da.append(i)
4    print(f"after append({i}): n={len(da)}, cap={da._capacity}")
5
6# Output:
7# after append(0): n=1, cap=4
8# after append(1): n=2, cap=4
9# after append(2): n=3, cap=4
10# after append(3): n=4, cap=4   # one slot left
11# after append(4): n=5, cap=8   # FULL → resize, then write
12# after append(5): n=6, cap=8
13# after append(6): n=7, cap=8
14# after append(7): n=8, cap=8
15# after append(8): n=9, cap=16  # FULL → resize again
16# after append(9): n=10, cap=16

Capacity follows the geometric sequence $4, 8, 16, 32, \ldots$, growing precisely at appends 5, 9, 17, 33, … Total copy cost up to $n = 10$ appends: $4 + 8 = 12$ copies plus $10$ writes = 22 ≤ 3 · 10. The bound holds.

Full Implementation: C++ with RAII and Move Semantics

The Python version is short because Python hides many costs. C++ forces us to confront them: separate allocation from construction, manage destructor calls explicitly, decide between move and copy on resize. The result is a Vector<T> close enough to std::vector that the same optimizations apply.

1#include <cstddef>
2#include <stdexcept>
3#include <utility>
4#include <new>
5
6template <typename T>
7class Vector {
8public:
9    Vector() : data_(nullptr), size_(0), cap_(0) {}
10
11    explicit Vector(std::size_t initial_cap)
12        : data_(static_cast<T*>(::operator new(initial_cap * sizeof(T)))),
13          size_(0), cap_(initial_cap) {}
14
15    ~Vector() {
16        for (std::size_t i = 0; i < size_; ++i) data_[i].~T();
17        ::operator delete(data_);
18    }
19
20    Vector(Vector&& other) noexcept
21        : data_(other.data_), size_(other.size_), cap_(other.cap_) {
22        other.data_ = nullptr; other.size_ = 0; other.cap_ = 0;
23    }
24
25    Vector& operator=(Vector&& other) noexcept {
26        if (this != &other) {
27            for (std::size_t i = 0; i < size_; ++i) data_[i].~T();
28            ::operator delete(data_);
29            data_ = other.data_; size_ = other.size_; cap_ = other.cap_;
30            other.data_ = nullptr; other.size_ = 0; other.cap_ = 0;
31        }
32        return *this;
33    }
34
35    std::size_t size() const noexcept { return size_; }
36    std::size_t capacity() const noexcept { return cap_; }
37
38    T& operator[](std::size_t i) {
39        if (i >= size_) throw std::out_of_range("index");
40        return data_[i];
41    }
42
43    void push_back(const T& value) {
44        if (size_ == cap_) grow_(cap_ == 0 ? 1 : 2 * cap_);
45        new (data_ + size_) T(value);   // placement new — copy-construct in place
46        ++size_;
47    }
48
49    void pop_back() {
50        if (size_ == 0) throw std::out_of_range("pop_back");
51        --size_;
52        data_[size_].~T();              // explicit destructor
53        if (cap_ > 1 && size_ <= cap_ / 4) grow_(cap_ / 2);
54    }
55
56private:
57    void grow_(std::size_t new_cap) {
58        T* new_data = static_cast<T*>(::operator new(new_cap * sizeof(T)));
59        for (std::size_t i = 0; i < size_; ++i) {
60            new (new_data + i) T(std::move_if_noexcept(data_[i]));
61            data_[i].~T();
62        }
63        ::operator delete(data_);
64        data_ = new_data;
65        cap_ = new_cap;
66    }
67
68    T* data_;
69    std::size_t size_;
70    std::size_t cap_;
71};

Interactive: Build Your Vector

Step through any of the four scenarios below. The amber flash on the buffer marks a real reallocation and copy. Try toggling growth between $2\times$, $1.5\times$, and $1.25\times$; you'll see fewer wasted slots on the smaller factors but more frequent (and slightly more expensive) copies. The fourth scenario is the hysteresis bug — set shrink to at size ≤ cap/2 and watch the total-copy counter explode as the size oscillates across the boundary.

Real-World Implementations

Every general-purpose language ships a dynamic array. The differences are in the constants:

Edge Cases and Exception Safety

1. Initial capacity 0 vs lazy alloc. std::vector and Rust Vec allocate nothing on construction; the first push_back bootstraps to capacity 1. Our Python version uses 4 for clearer demos. Both are valid. Never use 0 with a multiplicative growth rule unless you also handle the $c \cdot 2 = 0$ bootstrap.
2. Capacity overflow. When $c$ approaches SIZE_MAX, doubling overflows. Real implementations check $c' \leq \textsf{max\_size}()$ and either throw std::length_error or saturate.
3. Concurrency. None of these structures is thread-safe. Concurrent appends race on both the buffer pointer and the size field; concurrent resizes can free a buffer another thread is reading. Concurrent variants exist (Java CopyOnWriteArrayList, lock-free rings) but have very different semantics and cost models.
4. Exception safety on resize. If T's copy/move throws halfway through a grow, the container must remain in a usable state. The C++ idiom of std::move_if_noexcept is precisely the strong-guarantee pattern: move when safe, copy-with-rollback when not.
5. Move-only types. Vector<std::unique_ptr<T>> requires move-construction in the resize loop — copies don't exist. Our implementation handles this because we always pass through std::move_if_noexcept.

Pitfalls and Common Bugs

• Forgetting to null the popped slot in Python. The ctypes array holds a strong reference; without self._A[self._n] = None the popped object stays alive until the slot is overwritten. Subtle leak.
• Off-by-one in the shift loop for insert/delete. The boundaries are range(n, i, -1) for insert (n down to i+1, exclusive of i) and range(i, n - 1) for delete (i up to n−2). Test with insert(0, v), insert(n, v), delete(0), delete(n−1) — the four corner cases catch most off-by-ones.
• Iterator invalidation after resize. A C++ std::vector::iterator captured before push_back can be a dangling pointer afterward. Python iterators re-read the buffer pointer each step, so they are safer; but inserting/deleting during a Python loop still skips or repeats elements.
• Shrink-at-1/2 oscillation. Already discussed. Use 1/4 trigger, halve on shrink.
• Forgetting delete[] or ::operator delete in C++. Manual memory management is the price of control. RAII (the destructor we wrote) is what makes it bearable.
• Pointer aliasing during resize. If two slots in the source buffer point to the same object and you copy them naively, fine; but with non-trivial constructors, double-construction is a real concern. Our placement-new + destruct-old loop handles this correctly because it processes each source slot exactly once.

Quick Checks

With this we close Chapter 5. Every section that follows — linked lists, stacks, queues, hash tables — builds on or contrasts with the dynamic array. When designers ask “is a dynamic array enough for this problem?”, they are weighing exactly the costs we have just measured: amortized O(1) append, O(1) random access, O(n − i) middle-of-array mutation, and contiguous memory for cache locality. In Chapter 6 we trade that contiguity for O(1) front insertion and pay for it in cache misses. The next chapter is, in many ways, this chapter's shadow.