Dynamic Arrays: How They Work

What Is a Dynamic Array?

A dynamic array is an array-based data structure that can automatically grow or shrink as elements are added or removed. Unlike a fixed-size array, a dynamic array does not require the programmer to know the final number of elements when the structure is created.

Dynamic arrays are commonly implemented using a regular array as their underlying storage. When the existing storage becomes full, a larger array is allocated and the existing elements are copied into it.

Why Are Dynamic Arrays Needed?

A traditional fixed-size array requires its capacity to be determined when the array is allocated. This can be inconvenient when the number of elements changes during program execution.

Size vs Capacity

Two concepts are important when understanding dynamic arrays: size and capacity.

• Size is the number of elements currently stored.
• Capacity is the amount of storage currently available.

Values:

[10, 20, 30, 40, _, _, _, _]

Size     = 4
Capacity = 8

The unused positions represent available capacity. New elements can be added without immediately allocating another array until that capacity has been exhausted.

How Dynamic Array Resizing Works

Suppose a dynamic array has a capacity of four and all four positions are occupied.

Before resizing:

[10, 20, 30, 40]

Size     = 4
Capacity = 4

When another element is inserted, the implementation can allocate a larger array, copy the existing elements, and continue the insertion.

After resizing:

[10, 20, 30, 40, 50, _, _, _]

Size     = 5
Capacity = 8

A common strategy is to increase capacity by a growth factor, such as doubling it. The exact strategy depends on the language and implementation.

Steps Performed During Resizing

1. Detect that the current storage is full.
2. Allocate a larger underlying array.
3. Copy the existing elements into the new array.
4. Replace the old storage with the new storage.
5. Insert the new element.

The copying step is what makes an individual resize operation expensive. However, resizing does not happen on every insertion when capacity grows geometrically.

Implementing a Dynamic Array in JavaScript

JavaScript's built-in Array already provides dynamic array behavior. However, implementing a simplified version helps demonstrate how resizing works internally.

class DynamicArray {
  constructor(capacity = 2) {
    this.data = new Array(capacity);
    this.size = 0;
  }

  push(value) {
    if (this.size === this.data.length) {
      this.resize();
    }

    this.data[this.size] = value;
    this.size++;
  }

  resize() {
    const newCapacity = this.data.length * 2;
    const newData = new Array(newCapacity);

    for (let i = 0; i < this.size; i++) {
      newData[i] = this.data[i];
    }

    this.data = newData;
  }

  get(index) {
    if (index < 0 || index >= this.size) {
      throw new Error("Index out of bounds");
    }

    return this.data[index];
  }
}

const numbers = new DynamicArray();

numbers.push(10);
numbers.push(20);
numbers.push(30);
numbers.push(40);

console.log(numbers.get(2));
// 30

console.log(numbers.data.length);
// 8

Appending Elements to a Dynamic Array

Adding an element to the end of a dynamic array is normally efficient. When unused capacity is available, the new value can be placed directly at the next available position.

const values = [10, 20, 30];

values.push(40);

console.log(values);
// [10, 20, 30, 40]

If the underlying storage needs to grow, the insertion may temporarily require copying existing elements into a larger storage area.

Dynamic Array Insertion at an Index

Inserting an element into the middle of a dynamic array still requires shifting the elements after the insertion position.

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

values.splice(2, 0, 30);

console.log(values);
// [10, 20, 30, 40, 50]

Dynamic resizing solves the capacity problem, but it does not eliminate the cost of shifting elements during insertion.

Removing Elements from a Dynamic Array

Elements can also be removed from a dynamic array. Removing an element from the end generally avoids shifting other elements, while removing from the beginning or middle can require elements to be moved.

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

values.pop();

console.log(values);
// [10, 20, 30]

Some dynamic-array implementations also reduce capacity when the array becomes sufficiently empty. Shrinking is normally done carefully to avoid repeatedly resizing the storage when elements are added and removed around the same size.

Amortized Time Complexity

One of the most important concepts associated with dynamic arrays is amortized complexity.

A resize operation can take O(n)

As a result, appending n elements has an overall O(n) cost, giving an O(1) amortized cost per append.

Capacity growth:

2 → 4 → 8 → 16 → 32 → 64

const users = [];

users.push("Asha");
users.push("Rahul");
users.push("Priya");

console.log(users);
// ["Asha", "Rahul", "Priya"]

users.push("Arun");

console.log(users.length);
// 4