jsrosetta

Data structures

Implementing a dynamic array

Build a dynamic array on top of fixed storage in Node.js, Go and Rust: length, capacity, doubling when full, push/pop/insert/remove and their complexity.

By
Minimum versions
Node.js ≥ 14.6Go ≥ 1.23Rust ≥ 1.58
Verified on
Node.js 24.12.0Go 1.27.1Rust 1.98.1

Node.js code is an ES module: save it as .mjs or set "type": "module" in package.json.

Node.js's Array, Go's slice and Rust's Vec are all dynamic arrays: one contiguous block of memory (for Array, in V8's usual fast-elements mode) with spare room at the end, and when that room runs out, a bigger block is allocated and the data copied over. This post rebuilds that structure on top of storage treated as fixed-size, so you can see how length (the number of elements in use) differs from capacity (the number of slots allocated). Node.js has no fixed-size array for arbitrary values, so we use new Array(capacity) and promise never to call push or change its length. Go uses a slice made with make([]T, capacity) but never calls append. Rust uses Box<[Option<T>]>, with None marking unused slots, so no unsafe is needed.

Structure and growing the capacity

Each version keeps two things: the data storage and the element count length. capacity is just the length of data. When you push into a full array, grow allocates storage twice as large, copies the old elements over, and only then writes the new one.

class DynamicArray {
  #data; // fixed storage: read/write by index only, never push or change length
  #length = 0;
 
  constructor(capacity = 4) {
    this.#data = new Array(capacity);
  }
 
  get length() {
    return this.#length;
  }
 
  get capacity() {
    return this.#data.length;
  }
 
  push(value) {
    const isFull = this.#length === this.capacity;
    if (isFull) {
      this.#grow();
    }
    this.#data[this.#length] = value;
    this.#length += 1;
  }
 
  #grow() {
    // doubling a capacity of 0 is still 0, so grow to at least 1
    const next = new Array(Math.max(1, this.capacity * 2));
    for (let i = 0; i < this.#length; i++) {
      next[i] = this.#data[i];
    }
    this.#data = next;
  }
}
 
const arr = new DynamicArray(2);
for (let i = 1; i <= 5; i++) {
  arr.push(i * 10);
  console.log(`len=${arr.length} cap=${arr.capacity}`);
}
// → len=1 cap=2
// → len=2 cap=2
// → len=3 cap=4
// → len=4 cap=4
// → len=5 cap=8

A single grow costs O(n) because every element is copied, but thanks to doubling, the total number of copies after n push calls stays under roughly 2n. Spread evenly, each push costs O(1) — this is called amortized O(1). If each growth only added a fixed number of slots (say +10), the total number of copies would be O(n²).

Complete version: get, set, pop, insert, remove and iteration

The complete version adds index reads/writes, inserting/removing in the middle, and iteration. push is now just an insert at the end, and pop is a remove of the last element.

  • An out-of-range get returns "no value" the way each language usually does: JS returns undefined, Go returns an extra bool ("comma ok"), Rust returns Option<&T>.
  • set, insert and remove with a bad index are programming errors: JS throws a RangeError, Go and Rust panic — just like Rust's Vec::insert/Vec::remove or an out-of-range slice access in Go.
  • After a remove, the last slot is cleared (JS assigns undefined, Go assigns the zero value) so the storage holds no reference to the removed element and the GC can reclaim it. Rust has no GC: take() is required to move the value out of the slot, which leaves None behind.
class DynamicArray {
  #data;
  #length = 0;
 
  constructor(capacity = 4) {
    this.#data = new Array(capacity);
  }
 
  get length() {
    return this.#length;
  }
 
  get capacity() {
    return this.#data.length;
  }
 
  get(index) {
    const inRange = Number.isInteger(index) && index >= 0 && index < this.#length;
    if (!inRange) {
      return undefined;
    }
    return this.#data[index];
  }
 
  set(index, value) {
    this.#checkIndex(index, this.#length);
    this.#data[index] = value;
  }
 
  push(value) {
    this.insert(this.#length, value);
  }
 
  pop() {
    const isEmpty = this.#length === 0;
    if (isEmpty) {
      return undefined;
    }
    return this.remove(this.#length - 1);
  }
 
  insert(index, value) {
    this.#checkIndex(index, this.#length + 1); // index === length is allowed: append at the end
    const isFull = this.#length === this.capacity;
    if (isFull) {
      this.#grow();
    }
    // shift elements from index one slot right, back to front so nothing is overwritten
    for (let i = this.#length; i > index; i--) {
      this.#data[i] = this.#data[i - 1];
    }
    this.#data[index] = value;
    this.#length += 1;
  }
 
  remove(index) {
    this.#checkIndex(index, this.#length);
    const value = this.#data[index];
    for (let i = index; i < this.#length - 1; i++) {
      this.#data[i] = this.#data[i + 1];
    }
    this.#length -= 1;
    this.#data[this.#length] = undefined; // drop the reference so the GC can reclaim it
    return value;
  }
 
  *[Symbol.iterator]() {
    for (let i = 0; i < this.#length; i++) {
      yield this.#data[i];
    }
  }
 
  #checkIndex(index, limit) {
    const inRange = Number.isInteger(index) && index >= 0 && index < limit;
    if (!inRange) {
      throw new RangeError(`index ${index} out of range (length ${this.#length})`);
    }
  }
 
  #grow() {
    const next = new Array(Math.max(1, this.capacity * 2));
    for (let i = 0; i < this.#length; i++) {
      next[i] = this.#data[i];
    }
    this.#data = next;
  }
}
 
const arr = new DynamicArray();
for (const value of ["a", "b", "c"]) {
  arr.push(value);
}
arr.insert(1, "x");
console.log([...arr]); // → [ 'a', 'x', 'b', 'c' ]
 
arr.set(0, "A");
console.log(arr.get(0)); // → A
console.log(arr.get(10)); // → undefined
 
console.log(arr.remove(2)); // → b
console.log(arr.pop()); // → c
console.log([...arr], arr.length, arr.capacity); // → [ 'A', 'x' ] 2 4

insert and remove have to shift every element after the index by one slot, so they cost O(n); inserting or removing at the end (push/pop) shifts nothing. Iteration uses each language's own iterator mechanism: a [Symbol.iterator] generator so [...arr] and for...of work, an iter.Seq[T] so for v := range arr.All() and slices.Collect work, and in Rust an impl Iterator<Item = &T> over data[..len].

Complexity

Operation Time Notes
get / set O(1) direct access by index
push O(1) amortized O(n) when it has to grow
pop O(1) storage is never shrunk
insert / remove in the middle O(n) shifts the following elements
Full iteration O(n)

Compared with the built-in types

The built-in types of all three languages follow the same idea and differ only in their growth factor. The numbers below were measured on Node.js 24.12, Go 1.27 and Rust 1.98 (V8's capacity was inspected with %DebugPrint under node --allow-natives-syntax); they are implementation details rather than language guarantees, and may change in later releases.

Node.js (V8) Go Rust
Type Array slice + append Vec<T>
Reading capacity no API cap(s) v.capacity()
Preallocating capacity new Array(n) preallocates but also sets length = n (a holey array), so it is not equivalent make([]T, 0, n) Vec::with_capacity(n)
Growth n + n/2 + 16 (about 1.5×) 2× up to 256 elements, then gradually down to about 1.25× 2×, first allocation is at least 4 slots (8 for 1-byte elements, 1 for elements over 1 KiB)
Capacity under repeated push 17 → 43 → … 256 → 512 → 848 → 1280 (int64) 256 → 512 → 1024 → 2048 (i64)
Automatic shrinking yes, when pop/shrinking length leaves more than half of the storage empty no no, call shrink_to_fit()