Dynamic arrays: how lists grow

In the arrays post, you learned the core tradeoff of a true array: blazing-fast O(1) indexing, but fixed size. That fixed-size rule is the reason arrays are simple and cache-friendly — and also the reason they are inconvenient in real programs, where you usually do not know the final length up front. A dynamic array keeps the same contiguous-memory benefits while hiding the painful part: when it runs out of room, it allocates a new fixed-size array, copies the old elements, and continues.

If you understand Big-O and fixed arrays, you’re ready for the key idea behind Python’s list, Java’s ArrayList, and C++‘s vector.

What is a dynamic array?

A dynamic array is not a magical infinitely large array. It is a small wrapper around three pieces of state:

1. a pointer/reference to a fixed-size underlying array,
2. the current length (how many elements you are actually using), and
3. the current capacity (how many elements fit before resizing).

For example, suppose the underlying array has capacity 8, but you have only appended 5 values:

• length = 5
• capacity = 8
• used slots = [10, 20, 30, 40, 50]
• spare slots = 3

From the outside, it behaves like an array that can grow. Underneath, it is still the same old contiguous block from the previous lesson. The only trick is that the language runtime quietly replaces that block with a larger one when needed.

That is the first big mental model to lock in:

A dynamic array is a fixed-size array underneath, plus resize logic on top.

How resizing works

Appending into spare capacity is cheap: write the next value into the next free slot and increment length.

The expensive moment is when length == capacity.

At that point, a typical dynamic array does this:

1. allocate a new fixed-size array with larger capacity,
2. copy the old elements into the new array,
3. point the dynamic array at the new block,
4. free or discard the old block,
5. write the new value.

This is why the operation is sometimes fast and sometimes surprisingly expensive. If capacity is available, append is a single write. If the array is full, append temporarily becomes “allocate + copy everything + write once.”

A concrete example helps:

• Start with capacity 4: [7, 9, 2, 5]
• Append 8
• But there is no empty slot
• Allocate capacity 8
• Copy 7, 9, 2, 5
• Write 8
• New state: [7, 9, 2, 5, 8, _, _, _]

The resize is expensive in that moment, but you do not pay it on every append. That delayed-cost pattern is exactly why we use amortized analysis.

Why growth is multiplicative, not additive

A smart dynamic array does not increase capacity by +1 each time. That would turn repeated appends into a disaster because every append near the limit would trigger another full copy.

Instead, implementations usually grow multiplicatively:

• double the capacity (×2), or
• grow by about 1.5x.

Why? Because each expensive resize buys you many cheap appends afterward.

The tradeoff is always the same:

• larger growth factor → fewer copies, more unused memory after each resize
• smaller growth factor → tighter memory usage, more frequent copies

There is no free lunch. A growth factor is just a policy choice about whether you want to spend more on memory or more on copying.

Amortized analysis with real numbers

Let’s walk through append for 17 elements using a simple doubling policy, starting from capacity 1.

The capacities evolve like this:

• append 1: fits in capacity 1
• append 2: resize to 2, copy 1 old element
• append 3: resize to 4, copy 2 old elements
• append 4: fits
• append 5: resize to 8, copy 4 old elements
• append 6, 7, 8: fit
• append 9: resize to 16, copy 8 old elements
• append 10 through 16: fit
• append 17: resize to 32, copy 16 old elements

So which appends are expensive? Only these:

• append 2 copied 1 element
• append 3 copied 2 elements
• append 5 copied 4 elements
• append 9 copied 8 elements
• append 17 copied 16 elements

Total copied elements:

1 + 2 + 4 + 8 + 16 = 31

Total newly written elements from the appends themselves:

17

So across 17 appends, the total work is proportional to:

31 copies + 17 writes = 48 element moves

That is an average of less than 3 element moves per append.

More importantly, for n appends with doubling, the copy series looks like:

1 + 2 + 4 + 8 + ... < 2n

So the total work across many appends is linear, O(n), which means the average cost per append is O(1).

That average-over-time guarantee is what amortized O(1) means.

It does not mean every append is O(1). It means:

Most appends are cheap, and the rare expensive resizes are spread out enough that the average cost stays constant.

Why additive growth becomes O(n²)

Suppose you increased capacity by just +1 every time the array filled up.

To append n elements, you would copy roughly:

1 + 2 + 3 + 4 + ... + (n - 1)

That sum is about n² / 2, so total work becomes O(n²).

That is the hidden reason multiplicative growth matters so much. Without it, a dynamic array would lose the performance property that makes it useful in the first place.

Capacity vs length: an important distinction

Beginners often confuse these two:

• length/size = how many elements logically exist
• capacity = how many elements can fit before another resize

If a vector has length 10 and capacity 16, the last 6 slots are reserved space. They are not part of the user-visible array yet, but they are why the next 6 appends can stay cheap.

Shrinking: why removing elements is trickier than it looks

Growing is only half the story. What happens after you remove a lot of elements?

One option would be to shrink immediately on every deletion. But that creates a new problem: thrashing.

Imagine capacity 16, length 9. Remove one item and shrink to 8. Append one item and grow back to 16. Remove one item and shrink again. That would cause constant allocate-copy-free cycles near the boundary.

So practical implementations are conservative about shrinking:

• some do not shrink automatically at all,
• some shrink only when the array becomes much smaller than capacity,
• some offer a manual shrink-to-fit API.

A common strategy is to shrink only when usage drops well below half, such as 25% full. The exact threshold varies, but the reason is always the same: avoid oscillating between growth and shrink on small workload changes.

The lesson: deleting from a dynamic array does not imply the underlying buffer immediately gets smaller.

How real languages implement this idea

The exact growth formulas differ, but the underlying model is the same across major languages.

# Python's list is a dynamic array of object references.
# Capacity is hidden, but append is amortized O(1).

nums = []
for x in range(5):
    nums.append(x)

nums.append(99)     # usually just writes into spare capacity
nums.insert(0, -1)  # O(n): shifts every existing element right
nums.pop()          # O(1) from the tail
nums.pop(0)         # O(n): shifts every remaining element left

import java.util.ArrayList;

ArrayList<Integer> nums = new ArrayList<>();
nums.add(10);
nums.add(20);
nums.add(30);

nums.add(40);          // amortized O(1)
nums.add(1, 15);       // O(n): shifts elements right
nums.remove(nums.size() - 1); // O(1) at tail
nums.remove(0);        // O(n): shifts elements left

nums.trimToSize();     // optional manual compaction

#include <vector>
using namespace std;

vector<int> nums;
nums.reserve(8);       // optional: pre-allocate capacity
nums.push_back(10);
nums.push_back(20);
nums.push_back(30);

nums.push_back(40);    // amortized O(1)
nums.insert(nums.begin() + 1, 15); // O(n): shifts elements
nums.pop_back();       // O(1) at tail
nums.erase(nums.begin()); // O(n): shifts elements left

nums.shrink_to_fit();  // request capacity reduction

A few language-specific details matter:

Python list

Python’s list stores references to Python objects, not raw integers inline the way a low-level C array might. That means each slot points to an object elsewhere in memory. Even so, the reference slots themselves live in one contiguous dynamic array, which is why indexing and append behavior still follow the same model.

Python intentionally hides capacity. You get the convenience of a resizable array without capacity-management APIs, but the tradeoff is less direct control.

Java ArrayList

ArrayList is a classic textbook dynamic array: a backing array plus size bookkeeping. It grows automatically, offers indexed access, and keeps insert/remove in the middle at O(n) because shifting still happens. Methods like ensureCapacity() and trimToSize() make the size-vs-capacity distinction explicit.

C++ vector

std::vector is the most explicit of the three. It exposes size(), capacity(), reserve(), and shrink_to_fit(), so you can directly observe the dynamic-array mechanics: contiguous storage, occasional reallocation, amortized O(1) push_back, and O(n) insertion/deletion away from the end.

Insert and delete in the middle are still O(n)

A dynamic array solves the size problem, not the shifting problem.

This is the mistake many people make after learning about ArrayList or vector: “If it resizes automatically, maybe insert anywhere is cheap too?”

No. The underlying storage is still contiguous. So if you insert at the front or middle, elements must move.

Example: insert 99 at index 2 into

[10, 20, 30, 40, 50]

To preserve order, the array must become

[10, 20, 99, 30, 40, 50]

That means 30, 40, and 50 must each shift one position right.

Likewise, deleting from the front:

[10, 20, 30, 40, 50] -> remove 10 -> [20, 30, 40, 50]

requires every remaining element to shift one position left.

So dynamic arrays preserve the old array rule from the previous post:

Great at random access and tail growth, bad at modifications near the front.

When should you use a dynamic array?

Use a dynamic array when you want:

• fast indexed access,
• fast iteration with good cache locality,
• lots of appends at the end,
• a simple default container for “a growing sequence of things.”

That is why it is the default in so many languages. Most real workloads are append-heavy and read-heavy, so dynamic arrays win often.

But a dynamic array is less ideal when:

• you insert/remove near the front constantly,
• stable references/pointers through reallocation matter,
• you need guaranteed no-copy growth in the middle of the structure.

Those are the kinds of problems that lead us toward other structures, especially linked lists. Linked lists trade away contiguous memory and O(1) indexing in exchange for different update behavior. You will see that tradeoff more clearly in the next stage of the series.

Key takeaways

1. A dynamic array is a fixed-size array underneath. The “dynamic” part is just resize logic plus length/capacity bookkeeping.
2. Append is O(1) amortized, not always O(1). Most appends are cheap; the occasional resize copies all old elements.
3. Multiplicative growth is the secret. Policies like 2x or 1.5x keep total append work linear over time, unlike additive growth.
4. Length and capacity are different. Extra reserved slots are intentional and are what make future appends cheap.
5. Deleting does not necessarily free memory immediately. Real implementations shrink cautiously to avoid grow/shrink thrashing.
6. Dynamic arrays do not fix middle insertion cost. Insert/delete away from the tail are still O(n) because contiguous storage requires shifting.
7. Python list, Java ArrayList, and C++ vector are all versions of the same core idea.

Practice problems

• Insert Delete GetRandom O(1) (Medium) — why arrays are great for tail operations and random access
• Remove Element (Easy) — in-place compaction on array-like storage
• Move Zeroes (Easy) — shifting/compaction thinking without extra arrays
• Merge Sorted Array (Easy) — how to avoid unnecessary shifting by writing from the back

What’s next

Next up: linked lists. Dynamic arrays solved the “fixed size” limitation of arrays, but they did not solve the “shifting elements is expensive” limitation. Linked lists attack that exact problem by storing nodes separately and connecting them with pointers — giving up contiguous memory and O(1) indexing in the process.