In the previous chapter you learned that a normal array has a fixed size. Once you create new int[5], it can hold exactly five integers, no more.
But in real programs we often don't know the size in advance. How many students will register today? How many messages will arrive in a chat? How many numbers will the user type?
We want something that feels like an array (fast access by index) but can grow whenever we add more elements.
That is exactly what a dynamic array gives us. In Java, the dynamic array you use every day is ArrayList. In Python it is list, and in C++ it is vector.
In this chapter we will open the box and see how a dynamic array works internally, why adding an element is O(1) "on average" even though resizing costs O(n), and what interviewers expect you to know about it.
What is a Dynamic Array?
A dynamic array is a resizable array. It stores elements in a normal fixed-size array internally, and when that array becomes full, it creates a bigger array, copies the old elements into it, and continues.
So a dynamic array is not magic. It is just a normal array plus some bookkeeping.
It keeps track of two different numbers:
Term | Meaning |
|---|---|
Size (or length) | How many elements are actually stored right now |
Capacity | How many elements the internal array can hold before it must grow |
For example, a dynamic array with size 3 and capacity 4 looks like this:
Index: 0 1 2 3
┌────┬────┬────┬────┐
data: │ 10 │ 20 │ 30 │ │
└────┴────┴────┴────┘
used used used free
size = 3 (elements stored)
capacity = 4 (slots available)The last slot is reserved but unused. The user of the dynamic array only "sees" the first size elements. Index 3 is not a valid index yet, even though memory exists there.
The rule is always:
0 ≤ size ≤ capacityHow Growing Works, Step by Step
Let's start with capacity 2 and add the numbers 10, 20, 30, 40, 50.
add(10): there is space, so put it at index 0.
[10 | ] size = 1, capacity = 2add(20): there is space, so put it at index 1.
[10 | 20 ] size = 2, capacity = 2 (now full)add(30): the array is full. So the dynamic array:
Creates a new array with double the capacity (4).
Copies the old elements
10, 20into it.Throws away the old array (in Java, the garbage collector frees it later).
Puts
30at index 2.
old: [10 | 20 ]
│ │ copy
↓ ↓
new: [10 | 20 | 30 | ] size = 3, capacity = 4add(40): there is space.
[10 | 20 | 30 | 40 ] size = 4, capacity = 4 (full again)add(50): full again, so double to capacity 8, copy 4 elements, then add.
[10 | 20 | 30 | 40 | 50 | | | ] size = 5, capacity = 8Notice something important: resizing happened only twice (at the 3rd and the 5th add). Most adds were just "write into the next free slot". That observation is the key to the complexity analysis below.
Building a Dynamic Array in Java
Let's write our own small dynamic array of integers. We start with capacity 2 so we can see it grow quickly. (Real implementations start bigger.)
class DynamicArray {
private int[] data;
private int size;
DynamicArray() {
data = new int[2]; // small starting capacity so we can see it grow
size = 0;
}
int size() {
return size;
}
int capacity() {
return data.length;
}
int get(int index) {
checkIndex(index);
return data[index];
}
void set(int index, int value) {
checkIndex(index);
data[index] = value;
}
// Add at the end: amortized O(1)
void add(int value) {
if (size == data.length) {
resize(data.length * 2);
}
data[size] = value;
size++;
}
// Insert at a position: O(n) because of shifting
void insert(int index, int value) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
if (size == data.length) {
resize(data.length * 2);
}
for (int i = size; i > index; i--) {
data[i] = data[i - 1];
}
data[index] = value;
size++;
}
// Remove from a position: O(n) because of shifting
int removeAt(int index) {
checkIndex(index);
int removed = data[index];
for (int i = index; i < size - 1; i++) {
data[i] = data[i + 1];
}
size--;
// Shrink when only a quarter is used (never below 2)
if (size > 0 && size == data.length / 4 && data.length > 2) {
resize(data.length / 2);
}
return removed;
}
private void resize(int newCapacity) {
System.out.println(" resize: " + data.length + " -> " + newCapacity);
int[] bigger = new int[newCapacity];
for (int i = 0; i < size; i++) {
bigger[i] = data[i];
}
data = bigger;
}
private void checkIndex(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder("[");
for (int i = 0; i < size; i++) {
sb.append(data[i]);
if (i < size - 1) {
sb.append(", ");
}
}
return sb.append("]").toString();
}
}
class Main {
public static void main(String[] args) {
DynamicArray arr = new DynamicArray();
for (int value = 10; value <= 50; value += 10) {
System.out.println("add(" + value + ")");
arr.add(value);
System.out.println(" " + arr + " size=" + arr.size() + " capacity=" + arr.capacity());
}
arr.insert(1, 15);
System.out.println("After insert(1, 15): " + arr);
System.out.println("get(3) = " + arr.get(3));
arr.set(0, 5);
System.out.println("After set(0, 5): " + arr);
System.out.println("removeAt(2) returned " + arr.removeAt(2));
System.out.println("Now: " + arr + " size=" + arr.size() + " capacity=" + arr.capacity());
System.out.println("Removing until 2 elements are left:");
while (arr.size() > 2) {
arr.removeAt(arr.size() - 1);
}
System.out.println("Now: " + arr + " size=" + arr.size() + " capacity=" + arr.capacity());
}
}Output:
add(10)
[10] size=1 capacity=2
add(20)
[10, 20] size=2 capacity=2
add(30)
resize: 2 -> 4
[10, 20, 30] size=3 capacity=4
add(40)
[10, 20, 30, 40] size=4 capacity=4
add(50)
resize: 4 -> 8
[10, 20, 30, 40, 50] size=5 capacity=8
After insert(1, 15): [10, 15, 20, 30, 40, 50]
get(3) = 30
After set(0, 5): [5, 15, 20, 30, 40, 50]
removeAt(2) returned 20
Now: [5, 15, 30, 40, 50] size=5 capacity=8
Removing until 2 elements are left:
resize: 8 -> 4
Now: [5, 15] size=2 capacity=4A few things to notice in this code:
checkIndexcompares withsize, not withdata.length. Slots beyondsizeexist in memory but are not valid elements.insertallowsindex == size, which means "insert at the end".getandremoveAtdo not.When inserting, we shift from right to left (
i = sizedown toindex + 1). Shifting left to right would overwrite values before copying them.When the size dropped to a quarter of the capacity (2 out of 8), the array shrank to half (4). We'll see why "a quarter" and not "a half" shortly.
Time Complexity of Each Operation
Operation | Time | Why |
|---|---|---|
|
| Direct index into the internal array |
|
| Usually one write; occasionally a full copy |
|
| Elements after |
|
| Elements after |
Remove the last element |
| Nothing to shift |
Search for a value |
| Linear scan (unless the data is sorted) |
Space |
| Capacity is at most a constant times the number of elements (with doubling, and with quarter-full shrinking if elements are removed) |
The interesting row is add. A single add can take O(n) time when it triggers a resize. So why do we call it O(1)?
Amortized Analysis: Why add() Is O(1)
Amortized time means the average cost per operation over a long sequence of operations, in the worst case. It is not about luck or random input. It is a guarantee: any sequence of n adds takes O(n) total time, so each add costs O(1) on average.
Think of it like a monthly metro pass. One day you pay a lot (buying the pass), but spread over 30 days, each ride is cheap.
Counting the Work (Aggregate Method)
Suppose we start with capacity 1 and double each time it is full. Let's add n = 9 elements and count the work.
add number | Capacity before | Resize? | Elements copied | Total work (copies + 1 write) |
|---|---|---|---|---|
1 | 1 | No | 0 | 1 |
2 | 1 | Yes, to 2 | 1 | 2 |
3 | 2 | Yes, to 4 | 2 | 3 |
4 | 4 | No | 0 | 1 |
5 | 4 | Yes, to 8 | 4 | 5 |
6, 7, 8 | 8 | No | 0 | 1 each = 3 |
9 | 8 | Yes, to 16 | 8 | 9 |
Total copies = 1 + 2 + 4 + 8 = 15. Total writes = 9. Total work = 24, which is about 2.67 units per add.
In general, with doubling, the copies are:
1 + 2 + 4 + 8 + ... + 2^k where 2^k < n
= 2^(k+1) - 1
< 2nSo for n adds:
Total work < n (writes) + 2n (copies) = 3n = O(n)
Amortized cost per add = O(n) / n = O(1)The big copies are rare, and each one is paid for by all the cheap adds that came before it.
The "Savings" View (Accounting Method)
Another way to see it: pretend every add pays 3 coins.
1 coin pays for writing the element itself.
2 coins are saved in the "bank".
Suppose the array just doubled to capacity c, holding c/2 elements. Before it is full again, c/2 new elements are added, each saving 2 coins. That is c coins in the bank, which is exactly enough to copy all c elements at the next resize. The bank never goes negative, so 3 coins per add (a constant) is always enough.
Why Double? Why Not Grow by a Fixed Amount?
A tempting idea is: "when full, add 10 more slots". That saves memory, but it destroys performance.
With a fixed increment k, resizes happen at sizes k, 2k, 3k, ..., and the copies add up to:
k + 2k + 3k + ... + (n/k)·k ≈ n² / (2k) = O(n²)So n adds cost O(n²) total, which is O(n) amortized per add. Much worse.
Let's measure it. This program simulates n adds starting from capacity 10 and counts how many element copies each strategy causes:
class Main {
// Simulates n add() calls and counts how many element copies resizing causes
static long countCopies(int n, int startCapacity, String strategy) {
int capacity = startCapacity;
int size = 0;
long copies = 0;
int resizes = 0;
for (int i = 0; i < n; i++) {
if (size == capacity) {
copies += size; // copy every existing element
resizes++;
if (strategy.equals("double")) {
capacity = capacity * 2;
} else {
capacity = capacity + 10; // grow by a fixed amount
}
}
size++;
}
System.out.println(strategy + ": resizes=" + resizes + ", copies=" + copies);
return copies;
}
public static void main(String[] args) {
int n = 1000;
countCopies(n, 10, "double");
countCopies(n, 10, "plus10");
n = 1_000_000;
countCopies(n, 10, "double");
countCopies(n, 10, "plus10");
}
}Output:
double: resizes=7, copies=1270
plus10: resizes=99, copies=49500
double: resizes=17, copies=1310710
plus10: resizes=99999, copies=49999500000Let's verify the first two lines by hand (n = 1000, start capacity 10):
Doubling: resizes happen when the size reaches 10, 20, 40, 80, 160, 320, 640. That is 7 resizes, and copies =
10 + 20 + 40 + 80 + 160 + 320 + 640 = 1270.Plus 10: resizes happen at sizes 10, 20, 30, ..., 990. That is 99 resizes, and copies =
10 × (1 + 2 + ... + 99) = 10 × 4950 = 49500.
For one million adds, doubling copies about 1.3 million elements (less than 2n), while "plus 10" copies about 50 billion. That is the difference between O(n) and O(n²) total work.
The rule: grow by a constant factor (like ×2 or ×1.5), never by a constant amount. Any factor greater than 1 gives
O(1)amortized add.
What Real Libraries Use
Language | Dynamic array | Growth (typical implementation) |
|---|---|---|
Java |
| About ×1.5 in OpenJDK (new capacity = old + old / 2) |
Python |
| About ×1.125 plus a small constant in CPython |
C++ |
| ×2 in GCC's libstdc++, ×1.5 in Microsoft's library |
These are implementation details, not promises. The Java documentation only guarantees that adding an element has constant amortized time cost. A smaller factor wastes less memory but resizes more often; a bigger factor resizes less often but may leave more slots empty. Both are O(1) amortized.
Shrinking: Why a Quarter, Not a Half?
If many elements are removed, a dynamic array may shrink to save memory. The obvious rule "shrink to half when the array is half full" has a nasty problem called thrashing.
Imagine capacity 8 with 8 elements, and the operations alternate add, remove, add, remove:
add → size 9 > 8 → grow to 16 (copy 8)
remove → size 8 = 16/2 → shrink to 8 (copy 8)
add → size 9 > 8 → grow to 16 (copy 8)
remove → size 8 = 16/2 → shrink to 8 (copy 8)
...Every single operation copies the whole array, so each costs O(n).
The fix is to leave a gap between the "grow" point and the "shrink" point:
Grow (double) when the array is full.
Shrink (halve) when the array is only one quarter full.
Right after either kind of resize, the array is about half full, so many operations must happen before the next resize. This keeps both add and remove-from-end at O(1) amortized.
Note that Java's ArrayList never shrinks on its own. If you remove many elements and want to release memory, you can call trimToSize().
Using ArrayList in Java
In practice and in interviews, you will use ArrayList rather than writing your own. Here are the methods you will use most:
import java.util.ArrayList;
import java.util.List;
class Main {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
list.add(10);
list.add(20);
list.add(30);
list.add(40);
System.out.println(list);
list.add(1, 15); // insert at index 1
System.out.println(list);
System.out.println(list.get(2));
list.set(0, 5);
System.out.println(list);
list.remove(1); // removes the element at INDEX 1
System.out.println(list);
list.remove(Integer.valueOf(30)); // removes the VALUE 30
System.out.println(list);
System.out.println(list.size());
System.out.println(list.contains(40));
}
}Output:
[10, 20, 30, 40]
[10, 15, 20, 30, 40]
20
[5, 15, 20, 30, 40]
[5, 20, 30, 40]
[5, 20, 40]
3
trueMethod | What it does | Time |
|---|---|---|
| Append at the end |
|
| Insert at index |
|
| Read / replace at index |
|
| Remove at index |
|
| Remove first occurrence of a value |
|
| Linear search |
|
| Number of elements (not capacity) |
|
Two more useful tips:
If you know roughly how many elements you will add, create the list with an initial capacity, for example
new ArrayList<>(100000). This avoids repeated resizing. The list's size is still 0; only the capacity is set.ArrayListstores objects, sointvalues are boxed intoInteger. For very large amounts of numbers where performance matters, a plainint[]is faster and uses less memory.
Dynamic Array vs Static Array vs Linked List
Feature | Static array | Dynamic array | Linked list |
|---|---|---|---|
Size | Fixed | Grows and shrinks | Grows and shrinks |
Access by index |
|
|
|
Add at end | Not possible when full |
|
|
Insert / delete at front |
|
|
|
Memory layout | Contiguous | Contiguous (some unused capacity) | Scattered nodes plus a reference per node |
Cache friendliness | Excellent | Excellent | Poor |
You will study linked lists in detail later. For most everyday tasks, a dynamic array is the default choice because index access is fast and its elements sit next to each other in memory, which modern CPUs read very efficiently.
Common Mistakes
1. Confusing size with capacity
After new ArrayList<>(10), calling list.get(0) throws IndexOutOfBoundsException, because the size is 0. Capacity is reserved space, not elements.
2. Calling remove(int) when you meant remove(Object)
For a List<Integer>, list.remove(1) removes the element at index 1. To remove the value 1, write list.remove(Integer.valueOf(1)). You saw both in the example above.
3. Comparing Integer objects with ==
import java.util.ArrayList;
import java.util.List;
class Main {
public static void main(String[] args) {
List<Integer> nums = new ArrayList<>(List.of(1, 2, 3, 4, 5, 6));
nums.removeIf(x -> x % 2 == 0);
System.out.println(nums);
List<Integer> a = new ArrayList<>(List.of(1000, 1000));
System.out.println(a.get(0) == a.get(1));
System.out.println(a.get(0).equals(a.get(1)));
}
}Output:
[1, 3, 5]
false
true== on two Integer objects compares references, not values. Java caches Integer objects only for small values (by default -128 to 127), so == may "work" for small numbers and then fail for 1000. Always use equals(), or unbox to int first. (The first line also shows removeIf, the clean way to remove elements matching a condition.)
4. Removing elements inside a for-each loop
import java.util.ArrayList;
import java.util.List;
class Main {
public static void main(String[] args) {
List<Integer> nums = new ArrayList<>(List.of(1, 2, 3, 4));
for (Integer x : nums) {
if (x == 1) {
nums.remove(x); // modifying the list inside for-each
}
}
}
}This throws java.util.ConcurrentModificationException. Changing the list's structure while a for-each loop is iterating over it is not allowed. Use removeIf, an explicit Iterator with iterator.remove(), or loop over indexes backwards.
5. Inserting at the front in a loop
Calling list.add(0, x) n times costs O(n²) in total, because every insert shifts all existing elements. If you need fast insertion at both ends, use a deque (covered later), or add at the end and reverse once at the end.
6. Saying "add is always O(1)"
Be precise: a single add can be O(n). It is O(1) amortized. Interviewers love to ask about this difference.
Interview Tips
"How does ArrayList work internally?" It wraps an array. When the array is full, it allocates a larger one (about 1.5 times in OpenJDK), copies the elements over, and continues. Index access is
O(1), add at end isO(1)amortized, insert or delete in the middle isO(n)."Prove that add is amortized O(1)." With doubling, the copies over
nadds are1 + 2 + 4 + ... < 2n, so total work is under3n. Mention the accounting argument (3 coins per add) if asked for another proof."Why not grow by a fixed amount?" Because the copies become
k + 2k + 3k + ..., which isO(n²)total."When would you shrink?" At one-quarter full, to half the capacity, to avoid thrashing.
Amortized is not average-case. Average-case depends on input distribution; amortized is a worst-case guarantee over a sequence of operations.
If a problem gives you the final size up front, allocate exactly that much (an
int[]ornew ArrayList<>(n)). It is faster and shows you understand what happens underneath.
The Main Idea
A dynamic array is a normal array that replaces itself with a bigger array when it runs out of space.
size == capacity ?
→ allocate new array (capacity × growth factor)
→ copy old elements
→ add the new elementIndex access stays
O(1), just like a normal array.Adding at the end is
O(1)amortized because resizes are rare and the total copying is less than2n.Growth must be by a factor, not a fixed amount.
Shrink at one quarter full, not half, to avoid thrashing.
In Java this is
ArrayList, in Pythonlist, in C++vector.
A dynamic array trades an occasional expensive copy for the freedom to grow, and because the array grows by a constant factor, the average cost of each add stays constant.