Welcome to the Dynamic Arrays module. A dynamic array is a static array with a smart management layer built around it. It provides the lightning-fast access speed of a static array, while automatically growing in size whenever it fills up.

Dynamic arrays are what high-level languages hand you by default: Python’s list, JavaScript’s Array, C++‘s std::vector, and Java’s ArrayList.


Before you start

  • You understand contiguous memory and O(1) indexing. See arrays.
  • You can read Big-O notation and know what ‘amortised’ means informally.

What you will be able to do after this lesson:

  1. Explain why a fixed-size array must be reallocated to grow.
  2. Compute the total copies for n appends under doubling, and show it is under 2n.
  3. Explain why doubling gives amortised O(1) and fixed-chunk growth does not.
  4. Explain why append is cheap and insert-at-front is not.

Study route: read the mechanism, run the lab, then attempt the independent task before opening the hint.

1. Why Do Dynamic Arrays Exist? (Real-World Motivation)

Imagine buying an expandable accordion suitcase for travel:

  • When you start packing, it takes up a compact space.
  • If you run out of room, you un-zipper the extension seam to double its capacity.

In real-world software, you almost never know in advance how many records a user will load, how many items will be added to a shopping cart, or how many messages will arrive over a network connection.

Static arrays demand a fixed size at creation time. Dynamic arrays eliminate that restriction by automatically managing capacity behind the scenes.


Terms used with dynamic arrays

  1. Dynamic array: This is an array that can grow. It is also called a resizable array, a vector in C++, an ArrayList in Java, and simply a list in Python. Underneath it is still a plain fixed-size array — the growing is a trick played on top.

  2. Length: This is how many elements are actually stored right now. This is the number you get from len().

  3. Capacity: This is how many elements the underlying memory block could hold before it runs out. It is usually larger than the length, and it is invisible from outside.

  4. Headroom: This is the spare space, capacity - length. It is what lets an append happen without any copying, and it is the whole reason appends are usually instant.

  5. Growth factor: This is the multiplier used when the block runs out of room — commonly , sometimes . The array allocates a new, larger block and copies everything across. That it is a multiplier and not a fixed amount is the single most important detail, and section 3 shows why.

  6. Reallocation: This is the expensive step: request a bigger block, copy every existing element into it, then release the old block. It is , and it is what you are trying to do rarely.

  7. Amortised : This means that although a single operation can occasionally be slow, the average cost across a long run of operations is constant. Appending is amortised : most appends are instant, the occasional one copies everything, and the total still works out to constant time per append. It is a statement about the total, never a promise about any one call.

3. How Dynamic Resizing Works

Internally, a dynamic array tracks both its current length and underlying capacity.

State 1: Headroom Available

length = 3, capacity = 4
+-------+-------+-------+-------+
|  10   |  22   |   7   |   _   |  <-- 1 empty slot left
+-------+-------+-------+-------+

Appending 41 fills the empty slot. Now length = 4, capacity = 4.


State 2: Array Full (length == capacity) — The Resize Trigger

When you call append(99) and length == capacity, the dynamic array executes a 4-step resize algorithm:

Step 1: Allocate a new block with DOUBLE the capacity (capacity = 8)
+---+---+---+---+---+---+---+---+
| _ | _ | _ | _ | _ | _ | _ | _ |
+---+---+---+---+---+---+---+---+

Step 2: Copy existing elements from old block to new block
+---+---+---+---+---+---+---+---+
| 10| 22| 7 | 41| _ | _ | _ | _ |
+---+---+---+---+---+---+---+---+

Step 3: Free the old memory block.

Step 4: Append the new element 99
+---+---+---+---+---+---+---+---+
| 10| 22| 7 | 41| 99| _ | _ | _ |
+---+---+---+---+---+---+---+---+
Now length = 5, capacity = 8 (3 empty headroom slots remaining!)

4. Mathematical Proof: Why Doubling Makes Append “Amortized ”

A single resize operation costs because every single element must be copied to the new memory location. Why, then, do computer scientists claim that append() is ?

Because capacity doubles, resizes become exponentially rarer as the array grows!

Counting the Total Copies

Suppose you append elements starting from a capacity of 1:

Appends 1-2:   Resize to 2   (Cost: 1 copy)
Appends 3-4:   Resize to 4   (Cost: 2 copies)
Appends 5-8:   Resize to 8   (Cost: 4 copies)
Appends 9-16:  Resize to 16  (Cost: 8 copies)

Total Copies across ALL 16 appends = 1 + 2 + 4 + 8 = 15 copies!

Mathematically, for appends:

  • Total work for appends: insertions + copies = operations.
  • Average (Amortized) cost per append: !

IMPORTANT

Why Fixed Additive Growth Fails: If you increased capacity by a fixed amount (e.g. slots each time instead of multiplying by ), the total copy work would be , causing append() to degrade to a slow average cost!


5. Time & Space Complexity Summary

OperationTime ComplexityNotes
Access by Index (arr[i])Direct formula calculation ().
Append at End Amortized worst-case only on the rare resize step.
Pop from EndShrinks length counter; no shifting needed.
Insert / Delete at FrontMust shift all subsequent elements right/left.
Search (Unsorted)Linear scan.

6. Practical Optimizations & Gotchas

  1. Pre-Allocation Optimization: If you know you will store 100,000 items, pre-allocate the capacity upfront ([None] * 100000 in Python or vector.reserve(100000) in C++) to prevent all resize copies!
  2. Front Operations Are Still : Dynamic arrays solve the dynamic sizing problem, but inserting at index 0 still requires shifting every item. If you need fast front insertions, use Queues or Linked Lists.

The dynamic array ADT

A dynamic array supports everything a plain array does, and adds the operation an array cannot have.

  1. get(i) and set(i, value) — Exactly as for a plain array. . The underlying storage is still one contiguous block, so the address arithmetic is unchanged.

  2. append(value) — Adds value to the end. Amortised . Usually it writes into spare headroom and returns immediately. Occasionally there is no headroom left, and it must allocate a bigger block and copy everything, which is for that one call.

  3. pop() — Removes and returns the last element. . Nothing needs to move, because nothing sits after it.

  4. insert(i, value) — Inserts at position i, shifting everything after it up one place. . The shifting is unavoidable: contiguous storage means there is no gap to insert into.

  5. delete(i) — Removes the element at i and shifts everything after it down. , for the same reason.

  6. length() — How many elements are stored. .

The one claim worth being precise about

“Appending is ” is a statement about a sequence, not about a single call. Any individual append may be the unlucky one that triggers a copy of a million elements. If you are writing something latency-sensitive — an audio callback, a control loop, a game frame — that occasional spike is real and will show up in your worst-case timing, even though your average looks perfect.

The fix, when it matters, is to reserve capacity up front if you know roughly how many elements are coming. Most languages expose this: reserve() in C++, ensureCapacity() in Java. Python does not expose it directly, which is one reason building a list by repeated append in a hot loop is sometimes replaced by preallocating a list of the right size.

Implementation - complete runnable example

Runnable example: save as dynamic_arrays_lab.py and run python3 dynamic_arrays_lab.py. Standard library only; writes no files. Everything is counted rather than timed, so your output will match this exactly.

"""Dynamic arrays: why doubling gives amortised O(1) append.
 
Counts element copies exactly, so the amortisation is arithmetic rather
than a claim."""
 
class GrowableArray:
    """A dynamic array built on a fixed-capacity store, like a real one."""
    def __init__(self, growth=2):
        self.data, self.size, self.capacity = [None], 0, 1
        self.growth, self.copies, self.resizes = growth, 0, 0
 
    def append(self, value):
        if self.size == self.capacity:
            self._resize(max(1, int(self.capacity * self.growth)))
        self.data[self.size] = value
        self.size += 1
 
    def _resize(self, new_capacity):
        """The expensive step: allocate bigger, copy everything across."""
        bigger = [None] * new_capacity
        for i in range(self.size):
            bigger[i] = self.data[i]
        self.copies += self.size
        self.resizes += 1
        self.data, self.capacity = bigger, new_capacity
 
    def __getitem__(self, i):
        if not 0 <= i < self.size:
            raise IndexError(i)
        return self.data[i]
 
    def insert_front(self, value):
        """O(n): everything must shift right to make room."""
        if self.size == self.capacity:
            self._resize(max(1, int(self.capacity * self.growth)))
        for i in range(self.size, 0, -1):
            self.data[i] = self.data[i - 1]
        self.copies += self.size
        self.data[0] = value
        self.size += 1
 
def append_cost(n, growth):
    a = GrowableArray(growth)
    for i in range(n):
        a.append(i)
    return a.copies, a.resizes
 
if __name__ == "__main__":
    print("GROWTH BY DOUBLING -- copies during n appends")
    print(f"  {'n':>7s} {'copies':>10s} {'resizes':>9s} {'copies/append':>14s}")
    for n in (10, 100, 1000, 10000):
        copies, resizes = append_cost(n, 2)
        print(f"  {n:7d} {copies:10,d} {resizes:9d} {copies/n:14.2f}")
    print("  -> copies per append approaches 1 and never exceeds 2.")
    print("     THAT is what 'amortised O(1)' means: some appends are")
    print("     expensive, but the average over any run is constant.")
    print()
 
    print("WHY DOUBLING, NOT ADDING A FIXED AMOUNT")
    print(f"  {'strategy':>22s} {'copies for n=10000':>20s}")
    a = GrowableArray(2)
    for i in range(10000): a.append(i)
    print(f"  {'double (x2)':>22s} {a.copies:20,d}")
    # grow by a constant chunk instead
    size = cap = copies = 0
    for i in range(10000):
        if size == cap:
            copies += size
            cap += 100
        size += 1
    print(f"  {'grow by 100 each time':>22s} {copies:20,d}")
    print(f"  -> fixed-chunk growth is O(n^2) overall; doubling is O(n).")
    print()
 
    print("APPEND vs INSERT AT FRONT")
    back = GrowableArray()
    for i in range(1000): back.append(i)
    front = GrowableArray()
    for i in range(1000): front.insert_front(i)
    print(f"  1000 appends        : {back.copies:8,d} copies")
    print(f"  1000 front inserts  : {front.copies:8,d} copies")
    print(f"  -> front insertion is O(n) per operation, O(n^2) overall.")
 
    copies_2x, _ = append_cost(10000, 2)
    assert copies_2x < 2 * 10000, "doubling must stay under 2 copies per append"
    assert copies_2x < copies, "doubling must beat fixed-chunk growth"
    assert front.copies > 100 * back.copies
    a = GrowableArray()
    for i in range(5): a.append(i * i)
    assert [a[i] for i in range(5)] == [0, 1, 4, 9, 16]
    print()
    print("dynamic_arrays_lab: passed")

Expected output:

GROWTH BY DOUBLING -- copies during n appends
        n     copies   resizes  copies/append
       10         15         4           1.50
      100        127         7           1.27
     1000      1,023        10           1.02
    10000     16,383        14           1.64
  -> copies per append approaches 1 and never exceeds 2.
     THAT is what 'amortised O(1)' means: some appends are
     expensive, but the average over any run is constant.

WHY DOUBLING, NOT ADDING A FIXED AMOUNT
                strategy   copies for n=10000
             double (x2)               16,383
   grow by 100 each time              495,000
  -> fixed-chunk growth is O(n^2) overall; doubling is O(n).

APPEND vs INSERT AT FRONT
  1000 appends        :    1,023 copies
  1000 front inserts  :  500,523 copies
  -> front insertion is O(n) per operation, O(n^2) overall.

dynamic_arrays_lab: passed

7. Check Your Understanding (University Self-Assessment)

  1. Question: If a dynamic array currently has length = 8 and capacity = 8, how many elements will be copied during the next append() operation if the growth factor is ?

    • Click for AnswerAnswer: 8 elements will be copied to the new block of capacity 16, plus 1 insertion for the new element.
  2. Question: What is the difference between Length and Capacity in a dynamic array?

    • Click for AnswerAnswer: Length is how many items are actively stored. Capacity is the total allocated memory block size including empty headroom slots.
  3. Question: Why would changing a dynamic array’s growth strategy from “multiply capacity by 2” to “add 100 slots when full” be a terrible performance decision?

    • Click for AnswerAnswer: Adding fixed slots causes resizes to occur at linear frequency. The total work for N appends becomes quadratic O(n²), turning the average cost of append() from O(1) into O(n).

Practice - independent task

Implement pop() and automatic shrinking, then measure the hazard it creates.

  • Add pop() removing the last element in O(1).
  • Add shrinking: when size drops below half capacity, halve the capacity.
  • Now write a loop that repeatedly appends one element and pops it, at exactly the boundary where capacity flips. Count the copies.
  • You should see thrashing - every single operation triggers a resize.
  • Fix it by shrinking only when size drops below a quarter of capacity. Re-measure.

Done when: you can state how many copies the naive shrink rule costs for 1000 alternating operations versus the quarter rule, and explain why hysteresis fixes it.

Hint - open only after an attempt With shrink-at-half, an array sitting at exactly half capacity that gains one element grows (copying everything), and losing it again shrinks (copying everything). Each operation is O(n), so the sequence is O(n^2).
Shrinking at a quarter leaves a gap between the grow threshold and the shrink threshold, so a single element cannot cross both. That gap is hysteresis, and every real implementation has some form of it.

Before moving on

You are done with this module when you can, closed-book:

  • Explain why growing requires allocate-and-copy rather than extending in place.
  • Compute total copies for n appends under doubling and show it is bounded by 2n.
  • Explain why growing by a fixed chunk is O(n^2) overall.
  • State why amortised O(1) is not the same as O(1).

Recap: A dynamic array wraps a fixed-capacity block, reallocating when full. Doubling means the copies form a geometric series summing to under 2n, so n appends cost O(n) in total and each append is amortised O(1) - some are expensive, the average is constant. Growing by a fixed amount instead makes the total O(n^2). Front insertion remains O(n) because contiguity must be preserved.

Next: Hash Maps - the structure that gives up ordering entirely to buy O(1) lookup by key.

  • Arrays — The static contiguous foundation
  • Linked Lists — The pointer-based alternative with front insertions
  • Stacks and Queues — LIFO/FIFO structures built using dynamic arrays
↑ Back to Data Structures — University-Style Teaching Notes