Building an Array in JavaScript from Scratch

Arrays are a core feature of JavaScript, offering an efficient way to store and manipulate collections of data. But how do they work under the hood? By building an array from scratch, we can deepen our understanding of this versatile data structure.

What Is an Array?

An array is an ordered collection of elements. In JavaScript:

• Indexed: Each element is accessible by a numeric index starting from 0.
• Dynamic: Arrays grow or shrink automatically as needed.
• Flexible: Arrays can store any type of data.

Example:

const fruits = ['apple', 'banana', 'cherry']
console.log(fruits[0]) // Output: "apple"

Arrays in JavaScript are objects with a special structure. They inherit their methods and properties from the Array.prototype.

How JavaScript’s Built-In Arrays Work

JavaScript provides a built-in Array object with numerous methods for data manipulation. These methods are not defined directly on the array instance but on its prototype.

The Prototype Chain

1. Arrays inherit methods like push, pop, splice, and map from Array.prototype.
2. If a method is not found in the array instance, JavaScript looks for it in Array.prototype.
3. If it’s still not found, it continues up the prototype chain to Object.prototype.

const arr = [1, 2, 3]
console.log(arr.push) // Function from Array.prototype

This system ensures all arrays share the same efficient implementation of methods.

Building an Array from Scratch

To understand arrays better, we’ll create our own implementation. Here’s how:

Step 1: Define the Class

We start by creating a CustomArray class with two properties:

1. length: Tracks the number of elements.
2. data: An object to store the elements.

class CustomArray {
  constructor() {
    this.length = 0
    this.data = {}
  }
}

Step 2: Add a push Method

The push method adds an element at the next available index.

push(item) {
  this.data[this.length] = item;
  this.length++;
  return this.length;
}

Step 3: Retrieve an Element

To retrieve an element by its index, we implement a get method.

get(index) {
  return this.data[index];
}

Step 4: Remove the Last Element

The pop method removes and returns the last element.

pop() {
  if (this.length === 0) return undefined;
  const lastItem = this.data[this.length - 1];
  delete this.data[this.length - 1];
  this.length--;
  return lastItem;
}

Step 5: Remove an Element by Index

To delete an element and shift the remaining ones, we implement a delete method.

delete(index) {
  const item = this.data[index];
  this._shiftItems(index);
  return item;
}

_shiftItems(index) {
  for (let i = index; i < this.length - 1; i++) {
    this.data[i] = this.data[i + 1];
  }
  delete this.data[this.length - 1];
  this.length--;
}

Step 6: Add/Remove Elements at the Start

The shift and unshift methods handle elements at the start of the array.

shift() {
  if (this.length === 0) return undefined;
  const firstItem = this.data[0];
  this._shiftItems(0);
  return firstItem;
}

unshift(item) {
  for (let i = this.length; i > 0; i--) {
    this.data[i] = this.data[i - 1];
  }
  this.data[0] = item;
  this.length++;
  return this.length;
}

Step 7: Implementing splice

The splice method allows you to add, remove, or replace elements at any position in the array. It’s a powerful tool, but it highlights a key limitation of arrays: inserting or deleting in the middle is expensive because it requires shifting elements.

splice(index, deleteCount, ...items) {
  // Remove elements
  for (let i = index; i < index + deleteCount; i++) {
    delete this.data[i];
  }

  // Shift elements for insertion
  if (items.length > 0) {
    for (let i = this.length - 1; i >= index; i--) {
      this.data[i + items.length] = this.data[i];
    }

    // Insert new elements
    items.forEach((item, i) => {
      this.data[index + i] = item;
    });

    this.length += items.length;
  }

  this.length -= deleteCount;
}

Performance Analysis

Time Complexity

Operation	Time Complexity	Explanation
push	O(1)	Adds an element to the end.
pop	O(1)	Removes the last element.
shift	O(n)	Shifts all elements forward.
unshift	O(n)	Shifts all elements backward.
splice	O(n)	Shifting elements makes it costly.
get	O(1)	Direct access by index.

Space Complexity

• Native Arrays: Use contiguous memory, minimizing overhead.
• Custom Array: Uses an object, adding memory overhead for keys.

When to Use Arrays

• Use arrays when:

  • You need ordered collections.
  • Fast access by index is required.
  • Built-in methods like map or filter simplify your work.

• Avoid arrays when:

  • Data has unique keys (use an object or Map).
  • You need frequent insertions/deletions in the middle (splice is O(n)`).
  • Sparse datasets are better suited to objects or Maps for memory efficiency.

Key Takeaways

By implementing a custom array, we’ve explored its inner workings and limitations. The splice method, in particular, demonstrates how arrays are less efficient for middle insertions compared to hash table-based structures like objects or Maps.

While native arrays are powerful and optimized, this exercise highlights key performance considerations and decision-making factors when choosing data structures. Understanding arrays at this level equips you to make better design choices and optimize your code effectively.