A dynamic array is an array that automatically resizes itself when it runs out of space, letting you keep adding elements without deciding the exact size up front. It stores elements in a contiguous block of memory, just like a regular (static) array, so you still get instant access to any element by its index. The difference is what happens behind the scenes when the array fills up: it allocates a bigger block of memory, copies everything over, and frees the old one.
If you’ve used a Python list, a C++ vector, or a Java ArrayList, you’ve already used a dynamic array. Understanding how they work under the hood explains why they’re fast in practice and where they can trip you up.
How a Dynamic Array Differs From a Static Array
A static array has a fixed size set at creation. If you declare an array of 10 elements, that’s all you get. If your program later needs to store an 11th item, you’re out of luck unless you manually create a new, larger array yourself. This makes static arrays simple and predictable, but rigid.
A dynamic array removes that limitation. It tracks two numbers internally: its size (how many elements it currently holds) and its capacity (how many elements it has room for). When size equals capacity, the array triggers a resize operation automatically. You, as the programmer, just keep adding elements. The resizing details are hidden from you.
What Happens During a Resize
Resizing is the core trick that makes dynamic arrays work, and it follows four steps:
- Allocate a new, larger block of memory. The array creates a brand-new contiguous block, typically double the current capacity. So an array with a capacity of 8 would allocate space for 16.
- Copy existing elements. Every element from the old array gets copied into the new one, preserving order and position.
- Free the old memory. The original block is deallocated so it doesn’t sit around wasting space.
- Update the pointer. The array’s internal reference now points to the new, larger block. From the outside, nothing appears to have changed.
You can’t just tack extra memory onto the end of the existing array. The computer stores arrays in consecutive memory addresses, and the space right after your array might already be occupied by something else. That’s why a full copy to a new location is necessary.
Why Doubling the Capacity Matters
The choice to double (or at least multiply by a constant factor) is deliberate. Imagine instead that the array grew by just one slot every time you added an element. Each addition would require copying all existing elements, so adding n elements would cost roughly n² total operations. That gets slow fast.
Doubling avoids this. Yes, individual resize events are expensive because every element must be copied. But those events happen less and less frequently as the array grows. After doubling from 8 to 16, you get 8 free additions before the next resize. After doubling from 16 to 32, you get 16 free additions. The expensive copies get spread across a growing number of cheap, instant additions.
This is what computer scientists call “amortized O(1)” time for appending. The math works out cleanly: the total cost of adding n elements is always at most 3n operations when using a doubling strategy. Divide by n, and each addition costs roughly 3 operations on average, a constant. So while any single append could be slow (if it triggers a resize), the average across many appends stays fast.
Time Complexity at a Glance
Dynamic arrays inherit the best property of regular arrays: constant-time random access. Looking up the element at position 5 or position 5,000 takes the same amount of time because elements sit in consecutive memory and the computer can jump directly to any index.
For other operations, the performance breaks down like this:
- Access by index: O(1), always instant.
- Append (add to end): O(1) amortized. Most appends are instant; occasional resizes cost O(n) but are rare enough to average out.
- Insert or delete at an arbitrary position: O(n) in the worst case, because elements after the insertion point must be shifted forward or backward to maintain order.
- Search (unsorted): O(n), since you may need to check every element.
The worst-case cost of a single append is O(n) because of the copy step during resizing. If someone asks about “one insertion, worst case,” the answer is O(n). If they ask about amortized time across many insertions, it’s O(1). Both answers are correct depending on the framing.
The Memory Tradeoff
Doubling capacity means that, right after a resize, up to half your allocated memory could be empty. If you’re using a growth factor of 2, as much as 50% of the memory might be wasted in the worst case. Some implementations use a smaller growth factor (1.5 is common) to reduce this waste, at the cost of slightly more frequent resizes.
Growth factors in real-world implementations range from about 1.25 to 2. Python’s list, Java’s ArrayList, and C++’s vector all use geometric growth, though the exact factor varies by language and version.
What About Shrinking?
Most dynamic array implementations never shrink automatically. Once memory is allocated, it stays allocated even if you remove most of the elements. The reasoning is practical: shrinking introduces overhead, and in most real programs, an array that was once large will likely be large again soon. Automatic shrinking can also interfere with the amortized O(1) guarantee for appends if elements are repeatedly added and removed near the shrink threshold.
Languages like C++ offer explicit “shrink to fit” functions that let you reclaim memory manually when you know the array won’t grow again. But this is opt-in, not automatic.
Why Dynamic Arrays Beat Linked Lists for Most Tasks
Linked lists are another data structure that can grow and shrink freely, but dynamic arrays outperform them in most practical scenarios. The key advantage is cache locality. Because dynamic array elements are stored in a contiguous block of memory, your processor can load nearby elements into its cache all at once. Linked list nodes, by contrast, can be scattered anywhere in memory, so accessing each node may require a separate trip to main memory.
Dynamic arrays also use less memory per element. A linked list stores a pointer (or two) alongside every single element, which adds up quickly. A dynamic array has some wasted capacity at the end, but no per-element overhead.
Linked lists do have a genuine advantage for frequent insertions and deletions in the middle of a sequence, since they can splice nodes in and out without shifting other elements. But for the common pattern of building a list by appending and then reading through it, dynamic arrays are faster and more memory-efficient.
Dynamic Arrays in Common Languages
You rarely need to build a dynamic array from scratch. Every major language provides one in its standard library:
- Python: The built-in
listtype is a dynamic array. When you callappend(), it handles resizing transparently. - C++:
std::vectoris the standard dynamic array. It provides methods likepush_back()for appending andreserve()for pre-allocating capacity when you know the eventual size. - Java:
ArrayListserves the same role, automatically growing as elements are added.
If you know roughly how many elements you’ll need, most of these implementations let you set an initial capacity. This avoids unnecessary early resizes. For example, if you’re loading 10,000 records, pre-allocating space for 10,000 means the array won’t need to double through sizes 16, 32, 64, and so on to get there.
When to Use a Dynamic Array
Dynamic arrays are the default choice for ordered collections in most programming. They work well when you need fast access by index, plan to add elements primarily at the end, and want predictable memory layout. They’re the backbone of everything from database query results to pixel buffers in graphics.
They’re a poor fit when you need frequent insertions or deletions in the middle of a large collection, or when the worst-case cost of a single operation matters more than the average cost. In real-time systems where even one slow operation could cause a missed deadline, the occasional O(n) resize can be a problem. For those cases, other data structures like linked lists or ring buffers may be more appropriate.