Overview
Data structures organize and store data for efficient access and modification. Choosing the right structure is critical for algorithm performance — the same problem can be O(n) or O(1) depending on the choice.
Arrays vs Linked Lists
Arrays offer fast random access but slow insertion in the middle. Linked lists flip the trade-off — O(1) insert/delete at a known node, but O(n) to reach it. Pick based on your dominant operation.
| Array | Linked List |
|---|---|
| Access: O(1) | Access: O(n) |
| Insert/Delete middle: O(n) | Insert/Delete at node: O(1) |
| Fixed or dynamic size | Always dynamically sized |
| Cache-friendly (contiguous) | Cache-unfriendly (scattered) |
Stacks & Queues
Stacks follow Last-In-First-Out (LIFO); queues follow First-In-First-Out (FIFO). Both are thin abstractions over arrays or linked lists — the difference is purely which end you remove from.
// Stack (LIFO)
const stack = [];
stack.push(1); stack.push(2); stack.push(3);
console.log(stack.pop()); // 3
// Queue (FIFO)
const queue = [];
queue.push(1); queue.push(2); queue.push(3);
console.log(queue.shift()); // 1Trees & Graphs
Trees are hierarchical structures with a root and child nodes. Binary Search Trees keep elements sorted for O(log n) search; heaps maintain priority order for efficient min/max retrieval.
Hash Maps
A hash map converts a key to an array index via a hash function, enabling O(1) average-case lookup, insert, and delete. Collisions occur when two keys map to the same index.
const map = new Map();
map.set("name", "Alice");
map.set("age", 30);
console.log(map.get("name")); // "Alice"
console.log(map.size); // 2