# Dynamic Arrays

> Auto-resizing array — O(1) amortized append with O(1) index access. Best of both worlds.

- **Category**: Data Structures
- **Subcategory**: linear
- **Canonical URL**: https://designpattern.fyi/data_structures/dynamic-arrays/

---

## Description
Clean, reusable architecture pattern.


## Use Cases
JavaScript's Array, Python's list, Java's ArrayList, C++'s std::vector — all dynamic arrays. Every time you call array.push() in production code, you are using this structure.



## Implementation Example

```javascript
// Dynamic array implemented from scratch (what JS Array does internally)
class DynamicArray {
  #data;
  #size = 0;
  #capacity;

  constructor(initialCapacity = 4) {
    this.#capacity = initialCapacity;
    this.#data = new Array(this.#capacity);
  }

  get length() { return this.#size; }

  // O(1) — Read by index
  get(i) {
    if (i < 0 || i >= this.#size) throw new RangeError(`Index ${i} out of bounds`);
    return this.#data[i];
  }

  // O(1) amortized — Append to end
  push(value) {
    if (this.#size === this.#capacity) this.#resize(); // O(n) but rare
    this.#data[this.#size++] = value;
  }

  // O(1) amortized — Remove from end
  pop() {
    if (this.#size === 0) throw new Error('Empty array');
    const val = this.#data[--this.#size];
    // Shrink at 25% utilization to reclaim memory (avoid thrashing)
    if (this.#size > 0 && this.#size === Math.floor(this.#capacity / 4)) {
      this.#resize(Math.floor(this.#capacity / 2));
    }
    return val;
  }

  // O(n) — Insert at arbitrary index (shifts elements right)
  insert(i, value) {
    if (this.#size === this.#capacity) this.#resize();
    for (let j = this.#size; j > i; j--) this.#data[j] = this.#data[j - 1];
    this.#data[i] = value;
    this.#size++;
  }

  // O(n) — Double the internal buffer (copy all elements)
  #resize(newCapacity = this.#capacity * 2) {
    const newData = new Array(newCapacity);
    for (let i = 0; i < this.#size; i++) newData[i] = this.#data[i];
    this.#data = newData;
    this.#capacity = newCapacity;
    // Amortized: each element is copied at most O(log n) times across all resizes
  }

  [Symbol.iterator]() {
    let i = 0;
    return { next: () => i < this.#size
      ? { value: this.#data[i++], done: false }
      : { done: true }
    };
  }
}

// Usage
const da = new DynamicArray();
for (let i = 0; i < 10; i++) da.push(i * 10); // Resizes happen internally at 4, 8
da.pop();               // removes 90

// In practice just use:
const arr = [];
arr.push(1, 2, 3); // JS Array IS a dynamic array

```



## Trade-offs


### Advantages

- O(1) amortized append — feels like constant time for the developer

- O(1) random access by index preserved from static arrays

- No upfront size commitment needed

- Cache-friendly — still contiguous memory between resizes




### Considerations & Drawbacks

- Occasional O(n) resize spike — can cause latency jitter in real-time systems

- Memory usage can be up to 2x the current size (half the capacity unused after a resize)

- Insert/delete in the middle is still O(n) — shifting elements

- Copy on resize means peak memory = old buffer + new buffer simultaneously







---
**Reference**: [Original Source](https://www.bigocheatsheet.com)