Chapter 07 of 65

Dynamic Arrays

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 ≤ capacity

How 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 = 2

add(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:

  1. Creates a new array with double the capacity (4).

  2. Copies the old elements 10, 20 into it.

  3. Throws away the old array (in Java, the garbage collector frees it later).

  4. Puts 30 at index 2.

old: [10 | 20 ]
        │    │      copy
        ↓    ↓
new: [10 | 20 | 30 |    ]      size = 3, capacity = 4

add(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 = 8

Notice 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=4

A few things to notice in this code:

  • checkIndex compares with size, not with data.length. Slots beyond size exist in memory but are not valid elements.

  • insert allows index == size, which means "insert at the end". get and removeAt do not.

  • When inserting, we shift from right to left (i = size down to index + 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

get(i) / set(i, x)

O(1)

Direct index into the internal array

add(x) at the end

O(1) amortized, O(n) worst case for a single call

Usually one write; occasionally a full copy

insert(i, x)

O(n)

Elements after i shift right

removeAt(i)

O(n)

Elements after i shift left

Remove the last element

O(1) (amortized, if shrinking is used)

Nothing to shift

Search for a value

O(n)

Linear scan (unless the data is sorted)

Space

O(n)

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
< 2n

So 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=49999500000

Let'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

ArrayList

About ×1.5 in OpenJDK (new capacity = old + old / 2)

Python

list

About ×1.125 plus a small constant in CPython

C++

std::vector

×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
true

Method

What it does

Time

add(x)

Append at the end

O(1) amortized

add(i, x)

Insert at index i

O(n)

get(i) / set(i, x)

Read / replace at index i

O(1)

remove(int i)

Remove at index i

O(n) (O(1) for the last index)

remove(Object o)

Remove first occurrence of a value

O(n)

contains(x) / indexOf(x)

Linear search

O(n)

size()

Number of elements (not capacity)

O(1)

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.

  • ArrayList stores objects, so int values are boxed into Integer. For very large amounts of numbers where performance matters, a plain int[] 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

O(1)

O(1)

O(n)

Add at end

Not possible when full

O(1) amortized

O(1) with a tail reference

Insert / delete at front

O(n)

O(n)

O(1)

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 is O(1) amortized, insert or delete in the middle is O(n).

  • "Prove that add is amortized O(1)." With doubling, the copies over n adds are 1 + 2 + 4 + ... < 2n, so total work is under 3n. 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 is O(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[] or new 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 element
  • Index 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 than 2n.

  • 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 Python list, 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.