docs/concepts/data-structures.mdx
Why does finding an item in an array take longer as it grows? Why can you look up an object property instantly regardless of how many properties it has? The answer lies in data structures.
// Array: searching gets slower as the array grows
const users = ['alice', 'bob', 'charlie', /* ...thousands more */]
users.includes('zara') // Has to check every element - O(n)
// Object: lookup is instant regardless of size
const userMap = { alice: 1, bob: 2, charlie: 3, /* ...thousands more */ }
userMap['zara'] // Direct access - O(1)
A data structure is a way of organizing data so it can be used efficiently. As Donald Knuth emphasizes in The Art of Computer Programming, the choice of data structure often matters more than the choice of algorithm. The right structure makes your code faster and cleaner. The wrong one can make simple operations painfully slow.
<Info> **What you'll learn in this guide:** - JavaScript's built-in structures: Array, Object, Map, Set, WeakMap, WeakSet - When to use each built-in structure - How to implement: Stack, Queue, Linked List, Binary Search Tree - Choosing the right data structure for the job - Common interview questions and patterns </Info> <Warning> **Prerequisites:** This guide shows time complexity (like O(1) and O(n)) for operations. If you're not familiar with Big O notation, check out our [Algorithms & Big O guide](/concepts/algorithms-big-o) first. We also use [classes](/concepts/factories-classes) for implementations. </Warning>Think of data structures like different ways to organize a library. You could:
┌─────────────────────────────────────────────────────────────────────────┐
│ DATA STRUCTURE TRADE-OFFS │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ ARRAY OBJECT/MAP LINKED LIST │
│ ┌─┬─┬─┬─┬─┐ ┌────────────┐ ┌───┐ ┌───┐ │
│ │0│1│2│3│4│ │ key: value │ │ A │──►│ B │──► │
│ └─┴─┴─┴─┴─┘ │ key: value │ └───┘ └───┘ │
│ └────────────┘ │
│ ✓ Fast index access ✓ Fast key lookup ✓ Fast insert/delete │
│ ✓ Ordered ✓ Flexible keys ✗ Slow search │
│ ✗ Slow insert in middle ✗ No order (Object) ✗ No index access │
│ │
└─────────────────────────────────────────────────────────────────────────┘
Every data structure has trade-offs. Your job is to pick the one that makes your most frequent operations fast.
JavaScript gives you several data structures out of the box. Let's look at each one.
An Array is an ordered collection of values, accessed by numeric index. It's the most common data structure in JavaScript.
const fruits = ['apple', 'banana', 'cherry']
// Access by index - O(1)
fruits[0] // 'apple'
// Add to end - O(1)
fruits.push('date') // ['apple', 'banana', 'cherry', 'date']
// Remove from end - O(1)
fruits.pop() // 'date'
// Add to beginning - O(n) - shifts all elements!
fruits.unshift('apricot') // ['apricot', 'apple', 'banana', 'cherry']
// Search - O(n)
fruits.indexOf('banana') // 3
fruits.includes('mango') // false
Time Complexity:
| Operation | Method | Complexity | Why |
|---|---|---|---|
| Access by index | arr[i] | O(1) | Direct memory access |
| Add/remove at end | push(), pop() | O(1) | No shifting needed |
| Add/remove at start | unshift(), shift() | O(n) | Must shift all elements |
| Search | indexOf(), includes() | O(n) | Must check each element |
| Insert in middle | splice() | O(n) | Must shift elements after |
When to use Arrays:
An Object stores key-value pairs where keys are strings or Symbols. It's JavaScript's fundamental way to group related data.
const user = {
name: 'Alice',
age: 30,
email: '[email protected]'
}
// Access - O(1)
user.name // 'Alice'
user['age'] // 30
// Add/Update - O(1)
user.role = 'admin'
// Delete - O(1)
delete user.email
// Check if key exists - O(1)
'name' in user // true
user.hasOwnProperty('name') // true
Limitations of Objects:
.size propertyWhen to use Objects:
A Map is like an Object but with superpowers: keys can be any type, it maintains insertion order, and has a .size property.
const map = new Map()
// Keys can be ANY type
map.set('string', 'works')
map.set(123, 'number key')
map.set({ id: 1 }, 'object key')
map.set(true, 'boolean key')
// Access - O(1)
map.get('string') // 'works'
map.get(123) // 'number key'
// Size is built-in
map.size // 4
// Check existence - O(1)
map.has('string') // true
// Delete - O(1)
map.delete(123)
// Iteration (maintains insertion order)
for (const [key, value] of map) {
console.log(key, value)
}
Map vs Object:
| Feature | Map | Object |
|---|---|---|
| Key types | Any | String or Symbol |
| Order | Guaranteed insertion order | Preserved (integer keys sorted first) |
| Size | map.size | Object.keys(obj).length |
| Iteration | Directly iterable | Need Object.keys() |
| Performance | Better for frequent add/delete | Better for static data |
| Prototype | None | Has prototype chain |
When to use Map:
// Common use: counting occurrences
function countWords(text) {
const words = text.toLowerCase().split(/\s+/)
const counts = new Map()
for (const word of words) {
counts.set(word, (counts.get(word) || 0) + 1)
}
return counts
}
countWords('the cat and the dog')
// Map { 'the' => 2, 'cat' => 1, 'and' => 1, 'dog' => 1 }
A Set stores unique values. Duplicates are automatically ignored.
const set = new Set()
// Add values - O(1)
set.add(1)
set.add(2)
set.add(2) // Ignored - already exists
set.add('hello')
set.size // 3 (not 4!)
// Check existence - O(1)
set.has(2) // true
// Delete - O(1)
set.delete(1)
// Iteration
for (const value of set) {
console.log(value)
}
The classic use case: removing duplicates
const numbers = [1, 2, 2, 3, 3, 3, 4]
const unique = [...new Set(numbers)] // [1, 2, 3, 4]
Set Operations (ES2024+):
<Note> These methods are part of ES2024 and are supported in all modern browsers as of late 2024. Check [browser compatibility](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set#browser_compatibility) if you need to support older browsers. </Note>const a = new Set([1, 2, 3])
const b = new Set([2, 3, 4])
// Union: elements in either set
a.union(b) // Set {1, 2, 3, 4}
// Intersection: elements in both sets
a.intersection(b) // Set {2, 3}
// Difference: elements in a but not in b
a.difference(b) // Set {1}
// Symmetric difference: elements in either but not both
a.symmetricDifference(b) // Set {1, 4}
// Subset check
new Set([1, 2]).isSubsetOf(a) // true
When to use Set:
WeakMap and WeakSet are special versions where keys (WeakMap) or values (WeakSet) are held "weakly." This means they don't prevent garbage collection.
WeakMap:
.keys(), .values(), .forEach()).size propertyconst privateData = new WeakMap()
class User {
constructor(name, password) {
this.name = name
// Store private data that can't be accessed externally
privateData.set(this, { password })
}
checkPassword(input) {
return privateData.get(this).password === input
}
}
const user = new User('Alice', 'secret123')
user.name // 'Alice'
user.password // undefined - it's private!
user.checkPassword('secret123') // true
// When 'user' is garbage collected, the private data is too
WeakSet:
const processed = new WeakSet()
function processOnce(obj) {
if (processed.has(obj)) {
return // Already processed
}
processed.add(obj)
// Do expensive processing...
}
When to use Weak versions:
JavaScript doesn't have built-in Stack, Queue, or Linked List classes, but they're easy to implement and important to understand.
A Stack follows Last-In-First-Out: the last item added is the first removed. Think of a stack of plates.
┌─────────────────────────────────────────────────────────────────────────┐
│ STACK (LIFO) │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ push(4) pop() │
│ │ │ │
│ ▼ ▼ │
│ ┌───┐ ┌───┐ │
│ │ 4 │ ◄─ top │ │ │
│ ├───┤ ├───┤ │
│ │ 3 │ │ 3 │ ◄─ top │
│ ├───┤ ├───┤ │
│ │ 2 │ │ 2 │ │
│ ├───┤ ├───┤ │
│ │ 1 │ │ 1 │ │
│ └───┘ └───┘ │
│ │
│ "Last in, first out" - like a stack of plates │
│ │
└─────────────────────────────────────────────────────────────────────────┘
Real-world uses:
Implementation:
class Stack {
constructor() {
this.items = []
}
push(item) {
this.items.push(item)
}
pop() {
return this.items.pop()
}
peek() {
return this.items[this.items.length - 1]
}
isEmpty() {
return this.items.length === 0
}
size() {
return this.items.length
}
}
// Usage
const stack = new Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.peek() // 3 (look at top without removing)
stack.pop() // 3
stack.pop() // 2
stack.size() // 1
Time Complexity: All operations are O(1).
A Queue follows First-In-First-Out: the first item added is the first removed. Think of a line at a store. According to the Stack Overflow Developer Survey 2023, queues and other fundamental data structures remain among the most commonly tested topics in technical interviews.
┌─────────────────────────────────────────────────────────────────────────┐
│ QUEUE (FIFO) │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ enqueue(4) dequeue() │
│ │ │ │
│ ▼ ▼ │
│ ┌───┬───┬───┬───┐ ┌───┬───┬───┐ │
│ │ 4 │ 3 │ 2 │ 1 │ ───────────────────────► │ 4 │ 3 │ 2 │ │
│ └───┴───┴───┴───┘ └───┴───┴───┘ │
│ back front back front │
│ │
│ "First in, first out" - like a line at a store │
│ │
└─────────────────────────────────────────────────────────────────────────┘
Real-world uses:
Implementation:
class Queue {
constructor() {
this.items = []
}
enqueue(item) {
this.items.push(item)
}
dequeue() {
return this.items.shift() // Note: O(n) with arrays!
}
front() {
return this.items[0]
}
isEmpty() {
return this.items.length === 0
}
size() {
return this.items.length
}
}
// Usage
const queue = new Queue()
queue.enqueue('first')
queue.enqueue('second')
queue.enqueue('third')
queue.dequeue() // 'first'
queue.front() // 'second'
A Linked List is a chain of nodes where each node points to the next. Unlike arrays, elements aren't stored in contiguous memory.
┌─────────────────────────────────────────────────────────────────────────┐
│ LINKED LIST │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ head tail │
│ │ │ │
│ ▼ ▼ │
│ ┌──────────┐ ┌──────────┐ ┌──────────┐ ┌──────────┐ │
│ │ value: 1 │ │ value: 2 │ │ value: 3 │ │ value: 4 │ │
│ │ next: ───────► │ next: ───────► │ next: ───────► │ next: null│ │
│ └──────────┘ └──────────┘ └──────────┘ └──────────┘ │
│ │
│ Nodes can be anywhere in memory - connected by references │
│ │
└─────────────────────────────────────────────────────────────────────────┘
Linked List vs Array:
| Operation | Array | Linked List |
|---|---|---|
| Access by index | O(1) | O(n) |
| Insert at beginning | O(n) | O(1) |
| Insert at end | O(1) | O(1) with tail pointer |
| Insert in middle | O(n) | O(1) if you have the node |
| Search | O(n) | O(n) |
Implementation:
class Node {
constructor(value) {
this.value = value
this.next = null
}
}
class LinkedList {
constructor() {
this.head = null
this.size = 0
}
// Add to beginning - O(1)
prepend(value) {
const node = new Node(value)
node.next = this.head
this.head = node
this.size++
}
// Add to end - O(n)
append(value) {
const node = new Node(value)
if (!this.head) {
this.head = node
} else {
let current = this.head
while (current.next) {
current = current.next
}
current.next = node
}
this.size++
}
// Find a value - O(n)
find(value) {
let current = this.head
while (current) {
if (current.value === value) {
return current
}
current = current.next
}
return null
}
// Convert to array for easy viewing
toArray() {
const result = []
let current = this.head
while (current) {
result.push(current.value)
current = current.next
}
return result
}
}
// Usage
const list = new LinkedList()
list.prepend(1)
list.append(2)
list.append(3)
list.prepend(0)
list.toArray() // [0, 1, 2, 3]
list.find(2) // Node { value: 2, next: Node }
When to use Linked Lists:
A Binary Search Tree (BST) is a hierarchical structure where each node has at most two children. The left child is smaller, the right child is larger.
┌─────────────────────────────────────────────────────────────────────────┐
│ BINARY SEARCH TREE │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ ┌────┐ │
│ │ 10 │ ◄─ root │
│ └────┘ │
│ / \ │
│ ┌────┐ ┌────┐ │
│ │ 5 │ │ 15 │ │
│ └────┘ └────┘ │
│ / \ \ │
│ ┌────┐ ┌────┐ ┌────┐ │
│ │ 3 │ │ 7 │ │ 20 │ │
│ └────┘ └────┘ └────┘ │
│ │
│ Rule: left child < parent < right child │
│ This makes searching fast: just go left or right! │
│ │
└─────────────────────────────────────────────────────────────────────────┘
Time Complexity:
| Operation | Average | Worst (unbalanced) |
|---|---|---|
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
Implementation:
class TreeNode {
constructor(value) {
this.value = value
this.left = null
this.right = null
}
}
class BinarySearchTree {
constructor() {
this.root = null
}
insert(value) {
const node = new TreeNode(value)
if (!this.root) {
this.root = node
return
}
let current = this.root
while (true) {
if (value < current.value) {
// Go left
if (!current.left) {
current.left = node
return
}
current = current.left
} else {
// Go right
if (!current.right) {
current.right = node
return
}
current = current.right
}
}
}
search(value) {
let current = this.root
while (current) {
if (value === current.value) {
return current
}
current = value < current.value ? current.left : current.right
}
return null
}
// In-order traversal: left, root, right (gives sorted order)
inOrder(node = this.root, result = []) {
if (node) {
this.inOrder(node.left, result)
result.push(node.value)
this.inOrder(node.right, result)
}
return result
}
}
// Usage
const bst = new BinarySearchTree()
bst.insert(10)
bst.insert(5)
bst.insert(15)
bst.insert(3)
bst.insert(7)
bst.insert(20)
bst.search(7) // TreeNode { value: 7, ... }
bst.search(100) // null
bst.inOrder() // [3, 5, 7, 10, 15, 20] - sorted!
When to use BST:
A Graph consists of nodes (vertices) connected by edges. Think social networks (people connected by friendships) or maps (cities connected by roads).
┌─────────────────────────────────────────────────────────────────────────┐
│ GRAPH │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ A ─────── B │
│ /│\ │ │
│ / │ \ │ │
│ / │ \ │ │
│ C │ D ────┘ │
│ \ │ / │
│ \ │ / │
│ \│/ │
│ E │
│ │
│ Adjacency List representation: │
│ A: [B, C, D, E] │
│ B: [A, D] │
│ C: [A, E] │
│ ... │
│ │
└─────────────────────────────────────────────────────────────────────────┘
Basic Implementation (Adjacency List):
class Graph {
constructor() {
this.adjacencyList = new Map()
}
addVertex(vertex) {
if (!this.adjacencyList.has(vertex)) {
this.adjacencyList.set(vertex, [])
}
}
addEdge(v1, v2) {
this.adjacencyList.get(v1).push(v2)
this.adjacencyList.get(v2).push(v1) // For undirected graph
}
// Breadth-First Search - uses Queue (FIFO)
bfs(start) {
const visited = new Set()
const queue = [start]
const result = []
while (queue.length) {
const vertex = queue.shift()
if (visited.has(vertex)) continue
visited.add(vertex)
result.push(vertex)
for (const neighbor of this.adjacencyList.get(vertex)) {
if (!visited.has(neighbor)) {
queue.push(neighbor)
}
}
}
return result
}
// Depth-First Search - uses Stack (LIFO) via recursion
dfs(start, visited = new Set(), result = []) {
if (visited.has(start)) return result
visited.add(start)
result.push(start)
for (const neighbor of this.adjacencyList.get(start)) {
this.dfs(neighbor, visited, result)
}
return result
}
}
// Usage
const graph = new Graph()
graph.addVertex('A')
graph.addVertex('B')
graph.addVertex('C')
graph.addEdge('A', 'B')
graph.addEdge('A', 'C')
graph.addEdge('B', 'C')
graph.bfs('A') // ['A', 'B', 'C'] - level by level
graph.dfs('A') // ['A', 'B', 'C'] - goes deep first
Real-world uses:
┌─────────────────────────────────────────────────────────────────────────┐
│ WHICH DATA STRUCTURE SHOULD I USE? │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ Need ordered data with index access? │
│ └──► ARRAY │
│ │
│ Need key-value pairs with string keys? │
│ └──► OBJECT (static data) or MAP (dynamic) │
│ │
│ Need key-value with any type as key? │
│ └──► MAP │
│ │
│ Need unique values only? │
│ └──► SET │
│ │
│ Need LIFO (last in, first out)? │
│ └──► STACK │
│ │
│ Need FIFO (first in, first out)? │
│ └──► QUEUE │
│ │
│ Need fast insert/delete at beginning? │
│ └──► LINKED LIST │
│ │
│ Need fast search + sorted data? │
│ └──► BINARY SEARCH TREE │
│ │
│ Modeling relationships/connections? │
│ └──► GRAPH │
│ │
└─────────────────────────────────────────────────────────────────────────┘
| Use Case | Best Structure | Why |
|---|---|---|
| Todo list | Array | Ordered, index access |
| User settings | Object | String keys, static |
| Word frequency counter | Map | Easy increment, any key |
| Tag system | Set | Unique values |
| Browser back button | Stack | LIFO |
| Task scheduler | Queue | FIFO |
| Playlist with prev/next | Linked List (doubly) | O(1) traversal |
| Dictionary/autocomplete | Trie | Fast prefix search |
| Social network | Graph | Connections |
Interview questions often test your understanding of data structures. Here are patterns you'll encounter:
<AccordionGroup> <Accordion title="Array: Two Sum"> **Problem:** Find two numbers in an array that add up to a target.**Approach:** Use a Map to store numbers you've seen. For each number, check if `target - number` exists in the Map.
```javascript
function twoSum(nums, target) {
const seen = new Map()
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i]
if (seen.has(complement)) {
return [seen.get(complement), i]
}
seen.set(nums[i], i)
}
return []
}
twoSum([2, 7, 11, 15], 9) // [0, 1]
```
**Why Map?** O(1) lookup turns O(n²) brute force into O(n).
**Approach:** Push opening brackets onto stack. When you see a closing bracket, pop and check if it matches.
```javascript
function isValid(s) {
const stack = []
const pairs = { ')': '(', ']': '[', '}': '{' }
for (const char of s) {
if (char in pairs) {
// Closing bracket - check if it matches
if (stack.pop() !== pairs[char]) {
return false
}
} else {
// Opening bracket - push to stack
stack.push(char)
}
}
return stack.length === 0
}
isValid('([{}])') // true
isValid('([)]') // false
```
**Approach:** Keep track of previous, current, and next. Reverse pointers as you go.
```javascript
function reverseList(head) {
let prev = null
let current = head
while (current) {
const next = current.next // Save next
current.next = prev // Reverse pointer
prev = current // Move prev forward
current = next // Move current forward
}
return prev // New head
}
```
**Key insight:** You need three pointers to avoid losing references.
**Approach:** Floyd's Tortoise and Hare - use two pointers, one fast (2 steps) and one slow (1 step). If they meet, there's a cycle.
```javascript
function hasCycle(head) {
let slow = head
let fast = head
while (fast && fast.next) {
slow = slow.next
fast = fast.next.next
if (slow === fast) {
return true // They met - cycle exists
}
}
return false // Fast reached end - no cycle
}
```
**Why this works:** In a cycle, the fast pointer will eventually "lap" the slow pointer.
**Approach:** Recursively find the depth of left and right subtrees, take the max.
```javascript
function maxDepth(root) {
if (!root) return 0
const leftDepth = maxDepth(root.left)
const rightDepth = maxDepth(root.right)
return Math.max(leftDepth, rightDepth) + 1
}
```
**Base case:** Empty tree has depth 0.
**Approach:** Use two stacks. Push to stack1. For dequeue, if stack2 is empty, pour all of stack1 into stack2 (reversing order), then pop from stack2.
```javascript
class QueueFromStacks {
constructor() {
this.stack1 = [] // For enqueue
this.stack2 = [] // For dequeue
}
enqueue(item) {
this.stack1.push(item)
}
dequeue() {
if (this.stack2.length === 0) {
// Pour stack1 into stack2
while (this.stack1.length) {
this.stack2.push(this.stack1.pop())
}
}
return this.stack2.pop()
}
}
```
**Amortized O(1):** Each element is moved at most twice.
Arrays are great for ordered data with index access. Push/pop are O(1), but shift/unshift are O(n).
Objects store string-keyed data. Use them for static configuration and entity data.
Map is the better choice when keys aren't strings, you need .size, or you add/delete frequently.
Set stores unique values. The [...new Set(arr)] trick removes duplicates instantly.
Stack (LIFO) is perfect for undo/redo, parsing expressions, and DFS traversal.
Queue (FIFO) is ideal for task scheduling and BFS traversal. Use a linked list for O(1) dequeue.
Linked Lists excel at insertions/deletions but lack random access. Use when you frequently modify the beginning.
Binary Search Trees give O(log n) search/insert/delete on average. They keep data sorted.
Choose based on your most frequent operation. What makes one structure fast makes another slow.
Interview tip: When you need O(1) lookup, think Map or Set. When you need to track order of operations, think Stack or Queue.
</Info>Use Map when:
- Keys are not strings (objects, numbers, etc.)
- You need to know the size frequently (`.size` vs `Object.keys().length`)
- You add/delete keys often (Map is optimized for this)
- You need guaranteed insertion order
- You want to avoid prototype chain issues
Use Object when:
- Keys are known strings
- You're working with JSON data
- You need object destructuring or spread syntax
`pop()` removes from the end. No other elements need to move.
`shift()` removes from the beginning. Every remaining element must be re-indexed:
- Element at index 1 moves to 0
- Element at index 2 moves to 1
- ...and so on
This is why Queue implementations with arrays have O(n) dequeue. For O(1), use a linked list or object with head/tail pointers.
**Stack (LIFO):** Last In, First Out
- Like a stack of plates - you take from the top
- `push()` and `pop()` operate on the same end
- Use for: undo/redo, back button, recursion
**Queue (FIFO):** First In, First Out
- Like a line at a store - first person in line is served first
- `enqueue()` adds to back, `dequeue()` removes from front
- Use for: task scheduling, BFS, print queues
Linked List wins when:
- You frequently insert/delete at the beginning (O(1) vs O(n))
- You don't need random access by index
- You're implementing a queue (O(1) dequeue)
- Memory is fragmented (nodes can be anywhere)
Array wins when:
- You need index-based access
- You iterate sequentially often
- You mostly add/remove from the end
- You need `.length`, `.map()`, `.filter()`, etc.
BSTs use the rule: left < parent < right. This means:
- To find a value, compare with root
- If smaller, go left; if larger, go right
- Each comparison eliminates half the remaining nodes
This gives O(log n) search, insert, and delete (on average).
**Catch:** If you insert sorted data, the tree becomes a linked list (all nodes on one side), and operations become O(n). Self-balancing trees (AVL, Red-Black) solve this.
The cleanest way is with Set:
```javascript
const unique = [...new Set(array)]
```
This works because:
1. `new Set(array)` creates a Set (which only keeps unique values)
2. `[...set]` spreads the Set back into an array
Time complexity: O(n) - each element is processed once.