# Performance Implications of Different Data Structures in JavaScript

> Explore the performance implications of JavaScript data structures. Understand how choosing the right structure optimizes operations from O(1) to O(n), preventing bottlenecks.

- Repository: [Leonardo Maldonado/33-js-concepts](https://github.com/leonardomso/33-js-concepts)
- Tags: performance
- Published: 2026-03-04

---

**Choosing the wrong JavaScript data structure—such as using an Array for high-throughput queues or an unbalanced Binary Search Tree for sorted data—can degrade operations from O(1) to O(n) and introduce memory bottlenecks due to cache misses and garbage collection pressure.**

Understanding the performance implications of different data structures in JavaScript is essential for writing efficient applications. The leonardomso/33-js-concepts repository provides detailed analysis of how built-in collections and custom implementations impact runtime complexity, memory layout, and engine optimization. These characteristics determine whether your code scales linearly or collapses under load when handling frequent insertions, deletions, or lookups.

## Built-in Collections and Big O Characteristics

### Arrays: Fast Stack, Slow Queue

JavaScript Arrays provide **O(1)** time for index access `arr[i]` and stack operations `push`/`pop`. However, `shift()`, `unshift()`, and `splice()` force the engine to re-index every remaining element, resulting in **O(n)** time complexity. According to `docs/concepts/data-structures.mdx`, this makes Arrays ideal for sequential data and LIFO stacks, but dangerous for FIFO queues or frequent front insertion.

### Objects vs. Maps for Key-Value Storage

Plain Objects offer **O(1)** property reads and writes for string keys, but coerce all keys to strings and lack a built-in size property. In contrast, `Map` preserves insertion order, accepts any value type as keys (including objects and functions), and maintains a `.size` property with **O(1)** access. The trade-off is higher memory overhead for large datasets, as Maps implement hash tables with additional pointer management.

### Sets for Uniqueness and Weak References for Memory

`Set` provides **O(1)** `add`, `has`, and `delete` operations, making it optimal for deduplication and existence checks. `WeakMap` and `WeakSet` share the same operational complexity but hold keys weakly, allowing the garbage collector to reclaim entries when the key object is no longer referenced. As documented in `docs/beyond/concepts/weakmap-weakset.mdx`, this prevents memory leaks in caches but sacrifices iteration capabilities—neither structure exposes `.size` or supports enumeration.

## Linear Structures and Their Bottlenecks

### Custom Stacks

A Stack implemented as a thin wrapper over an Array delivers **O(1)** `push`, `pop`, and `peek` operations. This structure excels in recursion simulation, undo/redo systems, and depth-first search (DFS) traversal without performance penalties.

### The Array Queue Problem and Linked List Solutions

Using `push` for enqueue and `shift` for dequeue creates an **O(n)** bottleneck because `shift()` rewrites the entire array to re-index elements. For high-throughput queues, the repository recommends a **Linked List** or a **two-stack implementation** (input and output stacks) to achieve amortized **O(1)** dequeue. While Linked Lists provide **O(1)** prepend operations, they lack constant-time index access and suffer from poor cache locality due to scattered node allocation across the heap.

## Hierarchical and Graph Structures

### Binary Search Trees

A Binary Search Tree (BST) offers **O(log n)** average time for search, insertion, and deletion when balanced. Without self-balancing mechanisms (AVL or Red-Black trees), a degenerate BST degrades to **O(n)** linked-list performance. This structure suits sorted data maintenance, range queries, and auto-complete features where logarithmic access is critical.

### Graph Representations

Adjacency lists (typically Arrays of Arrays or Maps) provide **O(1)** edge insertion and **O(V + E)** traversal complexity for breadth-first and depth-first searches. They efficiently model sparse relationships, though dense graphs with many edges may consume excessive memory compared to adjacency matrices.

## Engine-Level Performance Factors

### Cache Locality and Memory Layout

V8 stores dense Arrays as contiguous memory blocks, delivering excellent CPU cache performance for sequential scans. Linked structures scatter nodes across the heap, causing cache misses that slow iteration. When Arrays become sparse or use mixed-type keys, V8 falls back to hash-table representation, degrading sequential access speed.

### Garbage Collection Pressure

`WeakMap` and `WeakSet` reduce GC pressure by allowing automatic cleanup when key objects disappear, avoiding the memory leaks common in long-running caches using regular `Map` or `Set`. Regular collections require explicit `delete` calls to free references and prevent unbounded growth.

## Practical Implementation Examples

### Avoiding Linear Dequeue with Arrays

```javascript
// ❌ O(n) dequeue - forces re-indexing
const slowQueue = [];
slowQueue.push('a');
slowQueue.push('b');
slowQueue.shift(); // O(n) - every element moves

// ✅ O(1) stack operations
const stack = [];
stack.push(1); // O(1)
stack.push(2);
stack.pop();   // O(1)

```

### Map for Complex Keys

```javascript
const map = new Map();
const objKey = { id: 1 };

map.set(objKey, 'value');    // O(1)
console.log(map.get(objKey)); // 'value'

// Objects coerce keys to strings, causing collisions
const obj = {};
obj[{ id: 1 }] = 'value';
obj[{ id: 2 }] = 'other'; // Overwrites the slot

```

### Set Deduplication

```javascript
const numbers = [1, 2, 2, 3, 3, 3];
const unique = [...new Set(numbers)]; // [1, 2, 3] - O(n)

```

### Amortized O(1) Queue with Two Stacks

```javascript
class QueueFromStacks {
  constructor() {
    this.inStack = [];
    this.outStack = [];
  }

  enqueue(item) {
    this.inStack.push(item); // O(1)
  }

  dequeue() {
    if (this.outStack.length === 0) {
      while (this.inStack.length) {
        this.outStack.push(this.inStack.pop());
      }
    }
    return this.outStack.pop(); // O(1) amortized
  }
}

```

### BST Search Implementation

```javascript
class BST {
  constructor() {
    this.root = null;
  }

  search(value) {
    let node = this.root;
    while (node) {
      if (value === node.value) return node;
      node = value < node.value ? node.left : node.right;
    }
    return null; // O(log n) average, O(n) worst
  }
}

```

## Summary

- **Arrays** deliver **O(1)** stack operations but **O(n)** front insertion; avoid `shift()` for high-throughput queues.
- **Maps** outperform Objects for non-string keys and frequent mutations, though they consume more memory for large datasets.
- **Sets** provide **O(1)** uniqueness checks ideal for deduplication workloads.
- **WeakMap/WeakSet** prevent memory leaks via weak references but cannot be enumerated or sized.
- **Two-stack queues** achieve amortized **O(1)** dequeue, eliminating the linear cost of array re-indexing.
- **Balanced BSTs** maintain **O(log n)** operations; unbalanced trees risk degrading to **O(n)** linked-list traversal.
- **Contiguous array storage** maximizes CPU cache locality, while linked structures scatter memory and increase cache misses.

## Frequently Asked Questions

### Why is Array.prototype.shift() slow compared to push()?

`shift()` removes the first element and forces the JavaScript engine to decrement the index of every remaining element, resulting in **O(n)** linear time. `push()` simply adds an element to the end without affecting other indices, maintaining **O(1)** constant time. For queue implementations requiring frequent dequeue operations, use a Linked List or the two-stack pattern instead of native array methods.

### When should I choose Map over a plain Object?

Use **Map** when you need non-string keys (objects, functions), guaranteed insertion order, or frequent additions and removals with size tracking. Objects coerce all keys to strings and lack a built-in size property, while `Map` preserves key types and provides **O(1)** `.size` access. However, for simple string-keyed configuration objects with static schemas, plain Objects have lower memory overhead.

### How do WeakMap and WeakSet prevent memory leaks?

`WeakMap` and `WeakSet` hold "weak" references to their keys, meaning they do not prevent the garbage collector from reclaiming the key object when no other references exist. This makes them ideal for attaching private data or caching results tied to specific object lifetimes without requiring manual cleanup. Once the key object is garbage collected, the entry automatically disappears from the collection.

### What is the fastest way to implement a queue in JavaScript?

The fastest approach for high-throughput queues is a **two-stack implementation** (input and output stacks) providing amortized **O(1)** enqueue and dequeue, or a **Linked List** with tail pointer offering **O(1)** operations for both ends. Native Array methods fail here because `shift()` is **O(n)**. As detailed in `docs/concepts/data-structures.mdx`, avoid using `array.shift()` for FIFO structures that process thousands of items per second.