Skip to content
Tutorials Center
My learning

Topics

Lesson 15 of 225 ยท Arrays and Lists

Dynamic Arrays

Build your own resizable array in Python. Learn capacity vs size, why doubling makes append O(1) amortized, when to shrink, and how Python lists over-allocate.

A plain array has a fixed size: you decide its length when you create it. But real programs rarely know in advance how many items they will store. You read lines from a file, collect search results, record events. You want to keep calling append and never worry about running out of room.

A dynamic array gives you that. It is a fixed-size array hidden behind a wrapper that grows when it fills up. Python's list is exactly this, and so are ArrayList in Java and std::vector in C++. In this lesson you will build one yourself, count the work it does, and see why appending is fast even though growing sounds expensive.

Size vs capacity

A dynamic array tracks two numbers:

  • size (or length): how many items the user has stored.
  • capacity: how many slots the underlying fixed array has.

Size is always less than or equal to capacity. The unused slots at the end are free space waiting for future appends.

TEXT
capacity = 8, size = 5

index:  0   1   2   3   4   5   6   7
      +---+---+---+---+---+---+---+---+
      | A | B | C | D | E | . | . | . |
      +---+---+---+---+---+---+---+---+
                              ^ next append goes here (O(1))

Appending when size < capacity is trivial: write into slot size and add one to size. The interesting case is when the array is full.

Growing: allocate, copy, switch

When size == capacity and the user appends, the array must:

  1. Allocate a new, bigger fixed array.
  2. Copy all existing items into it (size copies).
  3. Use the new array from now on, and let the old one go.
  4. Write the new item.

That copy is O(n), so one unlucky append is expensive. The question is how big the new array should be. This decision determines the whole performance of the structure.

Why growing by a constant is bad, and doubling is good

Suppose you grow by a fixed 10 slots each time. Appending n items triggers about n / 10 resizes, each copying up to n items. The total copying is on the order of nยฒ/20: O(nยฒ). That is far too slow.

Now suppose you double the capacity each time. Capacities go 1, 2, 4, 8, 16, โ€ฆ and the copies at each resize are 1, 2, 4, 8, โ€ฆ items. Those add up to less than twice the final size. So appending n items does fewer than 2n copies in total, plus the n plain writes. Total work is O(n), which means each append costs O(1) on average. This is called amortized O(1). The idea is covered fully in Amortized Analysis.

Let's build it and measure the work by counting copies instead of timing.

Python A DynamicArray with doubling

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the output closely. The capacity jumps 1, 2, 4, 8, 16 exactly when the array was full. Most appends cause no copying at all; the resizes are rare and get rarer as the array grows.

Counting the total: doubling vs adding a constant

Let's compare growth policies directly with a counter, appending 10,000 items under each.

Python Doubling versus growing by a constant

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Doubling stays under 2 copies per append no matter how large n gets. Adding a constant makes the per-append cost grow with n, which is the signature of an O(nยฒ) total. Other growth factors (1.5, 1.125) also give amortized O(1); what matters is multiplying, not adding.

Doubling is not sacred. Python's list grows by roughly one eighth, Java's ArrayList by one half. A smaller factor wastes less memory but resizes more often. All of them are amortized O(1).

Insert in the middle is still O(n)

Dynamic resizing only fixes appending at the end. Inserting or deleting elsewhere still shifts items, exactly as in Arrays and Python Lists. The wrapper can add insert and pop methods that keep the same shift loops.

Shrinking

If a program appends a million items and then removes nearly all of them, the capacity stays huge and wastes memory. A good dynamic array shrinks too. The rule of thumb: halve the capacity when the size drops to one quarter of it, not one half.

Why one quarter? Suppose you shrank as soon as the array was half full. Right after a doubling, the array is only just over half full, so a single pop would shrink it again, and the next append would grow it again. Alternating those two calls would copy the whole array every time. Shrinking at one quarter leaves a wide buffer: after a shrink the array is only half full, so many cheap operations (at least a quarter of the new capacity) must happen before the next resize in either direction.

Python Grow at full, shrink at one quarter

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Note the line self._data[self._size] = None. Without it the array would keep a reference to the popped object and Python could not free it. That kind of hidden leak is a real mistake in hand-built containers.

Python's list over-allocates

CPython's list does the same trick in C. You cannot see capacity directly, but sys.getsizeof reports the memory the list object holds, which jumps in steps as capacity grows (on this runner a reference takes 4 bytes; on most desktop builds it takes 8).

Python Watching a list grow in steps

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The size only changes at certain lengths. Between those points, appends are free. The exact byte counts are an implementation detail that differs between Python versions, so never write code that depends on them; what matters is the stepped pattern, which is the visible sign of over-allocation.

Complexity table

Operation Time Notes
Index read/write O(1) Same as a plain array
Append O(1) amortized, O(n) worst Worst case is the resize
Pop from end O(1) amortized May shrink
Insert/delete in the middle O(n) Shifting
Space O(n) Capacity is at most a constant times size

The key trade-off: you accept an occasional slow append in exchange for a fast average and a simple interface. If you need every single operation to be fast (for example in a real-time system), a dynamic array's rare O(n) pause matters, and a linked list or pre-sized array may suit better.

Common mistakes

  • Growing by a constant instead of multiplying, which silently makes appends O(n) on average.
  • Treating amortized as worst case. A single append can still take O(n); only the average over many is O(1).
  • Forgetting to clear popped slots in a hand-built array (a memory leak in languages with garbage collection).
  • Shrinking at half-full, which allows thrashing between grow and shrink.
  • Pre-sizing with [None] * n and then calling append: you end up with n Nones followed by your data. Use assignment by index, or start empty.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the difference between size and capacity in a dynamic array?

    Size is how many items you have. Capacity is how many the underlying array can hold before it has to grow, so size <= capacity.
  2. 2. Why does doubling the capacity give amortized O(1) appends?

    Copies of 1 + 2 + 4 + ... add up to less than the final size times two, so n appends cost O(n) in total, which is O(1) each on average.
  3. 3. If a dynamic array grows by adding 10 slots each time, appending n items takes about

    There are about n/10 resizes, each copying up to n items, which is quadratic. Growth must multiply the capacity to stay linear.
  4. 4. Why shrink at one quarter full rather than at one half?

    Shrinking at half would let a few alternating appends and pops cause a resize each time. A quarter leaves a buffer so resizes stay rare.
  5. 5. What does sys.getsizeof show as a list grows by appends?

    CPython allocates extra capacity so most appends need no reallocation, which shows up as a stepped size curve.

Summary

  • A dynamic array is a fixed array plus a size counter; it reallocates and copies when full.
  • Growing by a multiplicative factor (like 2) makes append amortized O(1); growing by a constant makes it O(n) on average.
  • Insert and delete in the middle remain O(n).
  • Shrink at about one quarter full to avoid thrashing, and clear unused slots.
  • Python's list is a dynamic array that over-allocates, visible as stepped sys.getsizeof values.

Next: Two Pointers