Interview Cake 
Quick reference
| Average Case | Worst Case | |
|---|---|---|
| space | O(n) | O(n) |
| lookup | O(1) | O(1) |
| append | O(1) | O(n) |
| insert | O(n) | O(n) |
| delete | O(n) | O(n) |
A dynamic array is an array that automatically resizes itself as you add elements. When it runs out of room, it allocates a bigger underlying array (usually twice as big) and copies everything over, which keeps appends at O(1) time on average.
That fixes the biggest limitation of plain arrays: they're fixed size, so you need to specify how many elements your array will hold ahead of time. With a dynamic array, you don't.
Strengths:
- Fast lookups. Just like arrays, retrieving the element at a given index takes time.
- Variable size. You can add as many items as you want, and the dynamic array will expand to hold them.
- Cache-friendly. Just like arrays, dynamic arrays place items right next to each other in memory, making efficient use of caches.
Weaknesses:
- Slow worst-case appends. Usually, adding a new element at the end of the dynamic array takes time. But if the dynamic array doesn't have any room for the new item, it'll need to expand, which takes time.
-
Costly inserts and deletes. Just like arrays, elements are stored adjacent to each other. So adding or removing an item in the middle of the array requires "scooting over" other elements, which takes time.
In Java
In Java, dynamic arrays are called ArrayLists.
Here's what they look like:
Size vs. Capacity
When you allocate a dynamic array, your dynamic array implementation makes an underlying fixed-size array. The starting size depends on the implementation—let's say our implementation uses 10 indices. Now say we append 4 items to our dynamic array. At this point, our dynamic array has a length of 4. But the underlying array has a length of 10.
We'd say this dynamic array's size is 4 and its capacity is 10. The dynamic array stores an endIndex to keep track of where the dynamic array ends and the extra capacity begins.
Doubling Appends
What if we try to append an item but our array's capacity is already full?
To make room, dynamic arrays automatically make a new, bigger underlying array. Usually twice as big.
Why not just extend the existing array? Because that memory might already be taken by another program.
Each item has to be individually copied into the new array.
Copying each item over costs time! So whenever appending an item to our dynamic array forces us to make a new double-size underlying array, that append takes time.
That's the worst case. But in the best case (and the average case), appends are just time.
Amortized cost of appending
- The time cost of each special "doubling append" doubles each time.
- At the same time, the number of appends you get until the next doubling append also doubles.
These two things sort of "cancel out," and we can say each append has an average cost or amortized cost of .
Given this, in industry we usually wave our hands and say dynamic arrays have a time cost of for appends, even though strictly speaking that's only true for the average case or the amortized cost.
Dynamic Array vs. Linked List
The other common way to store a growable list of items is a linked list. Here's how they stack up:
| Dynamic array | Linked list | |
|---|---|---|
| Get the item at index i | O(1) | O(i) (walk from the head) |
| Append to the end | O(1) amortized | O(1) (if you keep a pointer to the tail) |
| Insert or delete at the front | O(n) (shift everything over) | O(1) |
| Insert or delete in the middle | O(n) | O(1) once you're there (but getting there is O(n)) |
| Memory | Items sit next to each other (cache-friendly), plus some unused capacity | Nodes are scattered around memory, and each one needs extra space for its pointers |
Dynamic arrays are usually the better default: fast lookups by index and cache-friendly memory make them quicker for most everyday work. Reach for a linked list when you're doing lots of inserts and deletes at the front, or in the middle of a list you're already walking through. In Java, that's the choice between ArrayList and LinkedList—and ArrayList is almost always the one you want.
Interview coming up?
Get the free 7-day email crash course. You'll learn how to think algorithmically, so you can break down tricky coding interview questions.
No prior computer science training necessary—we'll get you up to speed quickly, skipping all the overly academic stuff.
No spam. One-click unsubscribe whenever.
You're in! Head over to your email inbox right now to read day one!
