What does "dynamic array" mean?

AlgorithmsJunior~3 min read

Short answer

A dynamic array is a variable-size array stored in a contiguous memory region that automatically grows (and sometimes shrinks) its capacity on additions/removals, giving fast index access and amortized O(1) time for appending to the end.

Detailed answer

The key idea

A dynamic array combines the properties of a plain (static) array with the flexibility of resizing. Inside it has:

a fixed-length buffer (capacity) in contiguous memory;
a counter of the actual number of elements (size), which can be smaller than capacity.

When size reaches capacity as elements are added, a new, larger buffer is created (usually twice the size), all elements are copied into it, and the old one is freed. This strategy gives amortized O(1) for a push to the end: the expensive grow operations happen rarely and are "spread out" over many cheap additions.

Complexity of operations

Index access: O(1), direct addressed access.
Appending to the end (push): amortized O(1), O(n) in the worst case on a rare reallocation and copy.
Removing from the end (pop): O(1).
Inserting/removing in the middle or at the start: O(n), requires shifting elements.
Searching by value: O(n), unless there is an extra structure (an index/hash).

How it works inside

There are size and capacity fields. size ≤ capacity is guaranteed.
When space runs out, the buffer is reallocated with growth, for example ×2 (sometimes ×1.5). The larger the growth factor, the less often copying happens, but the higher the average "empty" memory margin.
A "shrink" is sometimes implemented for a large size reduction (for example, if size ≤ capacity/4, halve capacity) to return memory to the system.
Elements sit sequentially in memory, which improves reference locality and CPU cache hits during a linear traversal.

Pros

Fast random access O(1).
Amortized O(1) appends to the end.
Good cache locality on iteration.

Cons

Inserts/removes in the middle/at the start cost O(n) because of the shifting.
Sometimes uses more memory than needed (capacity > size).
Reallocations can cause rare but "expensive" pauses (undesirable in real-time systems).

Comparison with alternatives

A static array: a fixed size, no reallocations; a dynamic array changes, more convenient when the element count is not known ahead of time.
A linked list: cheap inserts/removes in the middle, but no random access (O(n)) and worse cache locality.
Across languages: C++ has std::vector, Java has ArrayList, C# has List, Python has list, JavaScript has Array (in JS, arrays are already essentially dynamic).

Sample implementation (TypeScript)

class DynArray<T> {
  private buf: (T | undefined)[];
  private _size = 0;
  private _capacity: number;

  constructor(initialCapacity = 0) {
    this._capacity = initialCapacity;
    this.buf = new Array<T | undefined>(this._capacity);
  }

  size(): number { return this._size; }
  capacity(): number { return this._capacity; }
  isEmpty(): boolean { return this._size === 0; }

  get(i: number): T {
    if (i < 0 || i >= this._size) throw new RangeError("Index out of bounds");
    return this.buf[i] as T;
  }

  set(i: number, value: T): void {
    if (i < 0 || i >= this._size) throw new RangeError("Index out of bounds");
    this.buf[i] = value;
  }

  push(value: T): void {
    if (this._size === this._capacity) this.resizeUp();
    this.buf[this._size++] = value;
  }

  pop(): T | undefined {
    if (this._size === 0) return undefined;
    const v = this.buf[--this._size];
    this.buf[this._size] = undefined; // help the GC
    // Optional: shrink if it became too empty
    // if (this._size > 0 && this._size <= this._capacity / 4) this.resizeDown();
    return v as T;
  }

  insert(index: number, value: T): void {
    if (index < 0 || index > this._size) throw new RangeError("Index out of bounds");
    if (this._size === this._capacity) this.resizeUp();
    for (let i = this._size; i > index; i--) this.buf[i] = this.buf[i - 1];
    this.buf[index] = value;
    this._size++;
  }

  removeAt(index: number): T {
    if (index < 0 || index >= this._size) throw new RangeError("Index out of bounds");
    const v = this.buf[index] as T;
    for (let i = index; i < this._size - 1; i++) this.buf[i] = this.buf[i + 1];
    this.buf[--this._size] = undefined;
    return v;
  }

  private resizeUp(): void {
    const newCap = this._capacity === 0 ? 1 : this._capacity * 2;
    const newBuf = new Array<T | undefined>(newCap);
    for (let i = 0; i < this._size; i++) newBuf[i] = this.buf[i];
    this.buf = newBuf;
    this._capacity = newCap;
  }

  // private resizeDown(): void {
  //   const newCap = Math.max(1, Math.floor(this._capacity / 2));
  //   if (newCap < this._size) return; // safety
  //   const newBuf = new Array<T | undefined>(newCap);
  //   for (let i = 0; i < this._size; i++) newBuf[i] = this.buf[i];
  //   this.buf = newBuf;
  //   this._capacity = newCap;
  // }
}

// Usage
const a = new DynArray<number>(2);
a.push(10);
a.push(20);
a.push(30); // triggers a buffer grow
console.log(a.size(), a.capacity()); // 3, 4
console.log(a.get(1)); // 20
a.insert(1, 15); // [10, 15, 20, 30]
a.pop(); // removes 30
a.removeAt(0); // removes 10

Note: in JavaScript, plain arrays are already dynamic, so the example above illustrates the concept of a growth and shifting strategy, not low-level memory management.

When to use it

A collection with frequent appends at the end and rare middle insertions.
Fast random access by index is needed.
Good performance on iteration is needed (data locality).

Pitfalls and details

Reallocation is sometimes "expensive": it copies every element; in critical spots you can pre-reserve capacity ahead of time (for example, vector::reserve in C++).
Growth by ×2 gives a simple proof of amortized O(1): each element is copied a bounded number of times (on the order of log n), and the cost of copying is spread over many cheap pushes.
Too small a growth factor (for example, +1) makes appends O(n) on average; too large a one increases peak memory use.
In some languages, old pointers/iterators to elements become invalid on reallocation (relevant to C++). In managed environments, references to the elements themselves stay valid, but a pointer to the internal buffer can change.

Summary

A dynamic array is a basic and efficient data structure for sequences with fast index access and frequent appends at the end. Its key to performance is strategic capacity management (usually doubling) and contiguous placement of elements in memory.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.