Back to Catalog
Data Structures
Random Access
Dynamic Arrays
Auto-resizing array — O(1) amortized append with O(1) index access. Best of both worlds.
Intent & Description
Real-world Use Case
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.
Source
📌 TL;DR
Dynamic Array = static array that doubles when full. O(1) amortized push, O(1) index access. What every language’s built-in array/list actually is. Use it. Just know the resize spike exists.
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
Disadvantages
- 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
Implementation Example
// 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
console.log(da.get(5)); // 50 — O(1)
da.pop(); // removes 90
// In practice just use:
const arr = [];
arr.push(1, 2, 3); // JS Array IS a dynamic array