Dynamic Arrays

Picture this. You make an array to hold 5 names. Then a 6th person joins. Now what? A normal array has a fixed size. So there is no room left. You are stuck. A dynamic array fixes exactly this. It is an array that grows on its own when it gets full. So you never have to guess the size up front.

😩 The Problem With Fixed Arrays

A normal array picks its size the moment you create it. That size never changes after that. So you hit trouble fast.

• If you guess too small, you run out of room. You cannot add any more.
• If you guess too big, most of the slots sit empty. That wastes memory.
• And most of the time you simply do not know how many items will come.

So a fixed array forces you to predict the future. That is the real pain. You want something that just grows when you need more space.

🛒 A Simple Analogy

Think of a small restaurant with 4 chairs at one table. That is your fixed array.

• A 5th friend shows up. There is no chair left.
• The waiter does not squeeze them in. Instead they move everyone to a bigger table with 8 chairs.
• Everyone carries their plate over and sits down. Now there is plenty of room for more friends.

A dynamic array does the same thing. When the current space is full, it grabs a bigger space. Then it moves everything over and keeps going. You never had to book the big table in advance.

🧠 How a Dynamic Array Works

Here is the trick. A dynamic array keeps track of two different numbers.

• Capacity is how many items it can hold right now. This is the size of the actual block of memory.
• Size is how many items it currently holds. This is always less than or equal to capacity.

So when you add an item and size is still below capacity, it just drops the item in the next free slot. That is easy and fast. The interesting part is what happens when size equals capacity. That means the array is full.

When it is full and you add one more item, the dynamic array does this:

• It makes a brand new array. This one is usually double the old capacity.
• It copies every existing item from the old array into the new one.
• It adds your new item into the new array.
• It throws away the old array. Now it uses the new bigger one.

Here is the same idea as a picture. Say capacity starts at 4 and it is full.

⏱️ Amortized O(1) Append, in Plain Words

When you add to the end of a dynamic array, most of the time it is super fast. It just drops the item in a free slot. That is O(1), which means constant time. But once in a while the array is full. So it has to copy everything to a bigger array. That copy is O(n), which means the time grows in line with the number of items.

So is adding fast or slow? The answer is amortized O(1). Amortized just means the average cost spread over many adds.

Think of it like rent split over a year. One month you pay a big deposit. But spread across all twelve months, your average monthly cost is still small. It works the same way here.

• The cheap adds happen very often.
• The expensive copy happens rarely. That is because doubling keeps space free for a long time.
• Spread that rare big cost over all the cheap adds. The average comes out to constant time.

So in everyday terms, adding to the end of a dynamic array is fast. That is the whole reason these are so popular.

💻 Built-In Dynamic Arrays in Each Language

Good news. You almost never build a dynamic array by hand. Every language gives you one ready to use. Below, each example starts with a small list. It adds a few items and prints the result. So you can watch it grow.

#include <stdio.h>
#include <stdlib.h>

// Add an item to the end, growing the array if it is full
int* append(int *arr, int *size, int *capacity, int value) {
    // If full, double the capacity and move everything to the bigger block
    if (*size == *capacity) {
        *capacity = *capacity * 2;
        arr = (int *)realloc(arr, (*capacity) * sizeof(int));
        printf("Array full. Grew capacity to %d\n", *capacity);
    }

    // Drop the new value into the next free slot
    arr[*size] = value;
    (*size)++;
    return arr;
}

int main() {
    int capacity = 2;            // start small so we can see it grow
    int size = 0;
    int *arr = (int *)malloc(capacity * sizeof(int));

    int values[] = {10, 20, 30, 40, 50};
    int count = sizeof(values) / sizeof(values[0]);

    for (int i = 0; i < count; i++) {
        arr = append(arr, &size, &capacity, values[i]);
    }

    printf("Final array: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    free(arr);
    return 0;
}

Array full. Grew capacity to 4
Array full. Grew capacity to 8
Final array: 10 20 30 40 50

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // A vector is a dynamic array. It starts empty.
    vector<int> arr;

    int values[] = {10, 20, 30, 40, 50};

    // Add each value to the end; the vector grows by itself
    for (int value : values) {
        arr.push_back(value);
    }

    cout << "Final array: ";
    for (int value : arr) {
        cout << value << " ";
    }
    cout << endl;

    cout << "Size: " << arr.size() << endl;
    return 0;
}

Final array: 10 20 30 40 50
Size: 5

import java.util.ArrayList;

public class DynamicArray {
    public static void main(String[] args) {
        // An ArrayList is a dynamic array. It starts empty.
        ArrayList<Integer> arr = new ArrayList<>();

        int[] values = {10, 20, 30, 40, 50};

        // Add each value to the end; it grows by itself
        for (int value : values) {
            arr.add(value);
        }

        System.out.println("Final array: " + arr);
        System.out.println("Size: " + arr.size());
    }
}

Final array: [10, 20, 30, 40, 50]
Size: 5

def main():
    # A Python list is a dynamic array. It starts empty.
    arr = []

    values = [10, 20, 30, 40, 50]

    # Add each value to the end; the list grows by itself
    for value in values:
        arr.append(value)

    print("Final array:", arr)
    print("Size:", len(arr))

if __name__ == "__main__":
    main()

Final array: [10, 20, 30, 40, 50]
Size: 5

function main() {
  // A JavaScript array is a dynamic array. It starts empty.
  let arr = [];

  const values = [10, 20, 30, 40, 50];

  // Add each value to the end; the array grows by itself
  for (const value of values) {
    arr.push(value);
  }

  console.log("Final array:", arr);
  console.log("Size:", arr.length);
}
main();

Final array: [ 10, 20, 30, 40, 50 ]
Size: 5

📊 Cost of Common Operations

Here is how a dynamic array behaves for the operations you use most.

⚠️ Common Mistakes and Misconceptions

A few things trip people up with dynamic arrays. Let’s clear them out.

• Thinking every add is slow because of the copy. It is not. The copy is rare. So adding to the end is fast on average.
• Assuming the array shrinks the memory back the moment you remove items. Most do not shrink on their own. So the capacity can stay large for a while.
• Believing adding at the start is as cheap as adding at the end. It is not. Everything has to shift over. So it is O(n).
• Forgetting that capacity and size are different. There can be empty reserved slots. So size is what counts, not capacity.

🧩 What You’ve Learned

You now understand how an array can grow on its own and why that stays fast. Here is the recap.

• ✅ A fixed array cannot change size. So it either runs out of room or wastes space.
• ✅ A dynamic array fixes this. When full, it makes a bigger array, usually double, and copies everything over.
• ✅ Capacity is how much it can hold. Size is how much it currently holds.
• ✅ Adding to the end is amortized O(1). So it is fast on average, even though the rare copy is O(n).
• ✅ Most languages give you a built-in dynamic array: C++ vector, Java ArrayList, Python list, JavaScript array. C makes you grow it yourself with realloc.

🚀 What’s Next?

You’ve seen how arrays grow. Now connect it back to the basics and the operations that build on it.

• Array Datastructure covers how arrays sit in memory and why a plain array has a fixed size.
• Insert Element in Array shows the shifting work behind adding at the start, middle, and end.