Append (insert at end)
Compare a spare-capacity append against one that must grow the buffer first.
1#include <vector>2// Fixed counterpart: std::array<int, N>.3// std::vector supplies native storage; size/capacity stay explicit for tracing.4struct DynArray {5std::vector<int> slots;6int size;7int capacity;8};910void append(DynArray& a, int v) {11if (a.size == a.capacity) {12int nextCapacity = a.capacity == 0 ? 1 : 2 * a.capacity; std::vector<int> bigger(nextCapacity);13for (int i = 0; i < a.size; ++i) {14bigger[i] = a.slots[i];15}16a.slots.swap(bigger); a.capacity = nextCapacity; // retired storage follows RAII17}18a.slots[a.size] = v;19a.size += 1;20}
55nullnullnull00Modeled slot addresses: base 0x100 + index × 4-byte teaching slot. Native C/C++ uses sizeof(int); Java and Python expose indexed elements rather than stable raw
addresses.
Buffer · size 5 / capacity 5
size5
capacity5
oldCapacitynull
inull
readIndexnull
writeIndexnull
appendsCompleted0
totalElementCopies0
resultnull
resultIndexnull
slots[0]=7 · [1]=14 · [2]=21 · [3]=28 · [4]=35
size5
capacity5
oldCapacitynull
inull
readIndexnull
writeIndexnull
appendsCompleted0
totalElementCopies0
resultnull
resultIndexnull
slots[0]=7 · [1]=14 · [2]=21 · [3]=28 · [4]=35
operation-count.value 0 → 3 highlight
O(n) time · O(n) space
worstA second/resized buffer can hold a linear number of slots, so peak auxiliary storage is O(n).
- size == capacity == 5, so a 10-slot buffer is allocated first.
- All 5 elements are copied — one read and one write each — before the new value lands.
- The copy loop grows linearly with n: O(n) time and O(n) transient auxiliary space.
Assumptions behind this claim
- Logical elements occupy consecutive indexed backing slots; only the explicit C-style teaching model exposes base + index × slot size.
- A full buffer grows by doubling its capacity before the write.
- Installing a grown backing store counts the backing-reference and capacity writes; C frees its retired allocation explicitly, while C++ lifetime rules and Java/Python runtimes govern physical reclamation, which is outside the portable count.
- size == capacity when the append starts.
- Each displayed read, write, comparison, allocation, or copy is one counted primitive.
- Trace construction and visualization bookkeeping are excluded from the algorithm count.
size equals capacity — there is no free slot, so the buffer must grow first.
About this implementation
A dynamic array keeps elements contiguous. Access is O(1) index arithmetic; inserting or deleting anywhere but the end shifts every following element (O(n)). Appending is O(1) when a spare slot exists, but O(n) when the buffer is full and must double — averaged over many appends, doubling keeps it amortized O(1). Compare to C arrays (fixed), C++ vector, Java ArrayList, and Python list, which all grow this way underneath.