Data Structures in JavaScript
A data structure is just a way of organising values so the operations you care about are cheap. JavaScript gives you a small set of built-ins that cover most needs — Array, Object, Map, Set — plus the building blocks (objects and references) to roll your own when you need a tree, a linked list or a graph. This page walks through the ones that come up most often.
Array as stack and queue
A stack is LIFO — last in, first out. A queue is FIFO — first in, first out. Array can play either role.
stack-queue.js
// Stack — push/pop at the end, both O(1)
const stack = [];
stack.push('a'); stack.push('b'); stack.push('c');
stack.pop(); // 'c'
// Queue — push at the end, shift from the front
const queue = [];
queue.push('a'); queue.push('b'); queue.push('c');
queue.shift(); // 'a'Map and Set
Map is a true key/value store with O(1) lookups, insertion order, and any value (not just strings) as a key. Set is the same idea for "is this value in the collection?". Reach for them over plain objects when keys are not strings or when you iterate the collection a lot.
map-set.js
const counts = new Map();
for (const word of 'the cat sat on the mat'.split(' ')) {
counts.set(word, (counts.get(word) ?? 0) + 1);
}
counts.get('the'); // 2
counts.size; // 5
const unique = new Set(['a', 'b', 'a', 'c']);
unique.has('a'); // true
unique.size; // 3
[...unique]; // ['a','b','c']Mappreserves insertion order —for (const [k, v] of map)is deterministic.Mapkeys can be objects, functions, anything. Objects can only key by string/symbol.Use
Setfor de-duplication:[...new Set(arr)]is the idiomatic one-liner.
Object as a hash map
The plain object is still a fine hash map for string keys — small, fast, JSON-friendly. The one pitfall is its prototype: keys like toString already exist. For dictionaries built from untrusted input, use Object.create(null).
dictionary.js
const cache = Object.create(null); // no inherited properties
cache['user:42'] = { name: 'Ada' };
cache['user:99'] = { name: 'Linus' };
'__proto__' in cache; // false — safeLinked list
A linked list is a chain of nodes, each holding a value and a reference to the next. Insertions and removals at the head (or anywhere you already have a node) are O(1) — but indexed access is O(n). Useful as a study exercise and for problems where you splice nodes around without copying.
linked-list.js
class LinkedList {
constructor() { this.head = null; }
prepend(value) {
this.head = { value, next: this.head };
}
toArray() {
const out = [];
for (let n = this.head; n; n = n.next) out.push(n.value);
return out;
}
reverse() {
let prev = null, curr = this.head;
while (curr) {
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
this.head = prev;
}
}
const list = new LinkedList();
list.prepend(3); list.prepend(2); list.prepend(1);
list.toArray(); // [1, 2, 3]
list.reverse();
list.toArray(); // [3, 2, 1]Trees
A tree is a connected structure with one root and no cycles. Each node holds a value and a list of children. DOM elements, file systems and parsed JSON are all trees you already use every day.
tree-traversal.js
const root = {
value: 'docs',
children: [
{ value: 'intro.md', children: [] },
{ value: 'guide', children: [
{ value: 'install.md', children: [] },
{ value: 'usage.md', children: [] },
] },
],
};
function dfs(node, visit) {
visit(node);
for (const child of node.children) dfs(child, visit);
}
dfs(root, n => console.log(n.value));docs intro.md guide install.md usage.md
Graph
A graph is a generalisation of a tree — nodes connected by edges, possibly with cycles, possibly directed. The most common JS representation is an adjacency list: a map from each node to its neighbours.
graph.js
const graph = new Map();
function addEdge(a, b) {
if (!graph.has(a)) graph.set(a, new Set());
if (!graph.has(b)) graph.set(b, new Set());
graph.get(a).add(b);
graph.get(b).add(a); // undirected
}
addEdge('A', 'B');
addEdge('A', 'C');
addEdge('B', 'D');
// BFS — shortest unweighted distance from start
function distances(start) {
const out = new Map([[start, 0]]);
const queue = [start];
while (queue.length) {
const node = queue.shift();
for (const next of graph.get(node) ?? []) {
if (!out.has(next)) {
out.set(next, out.get(node) + 1);
queue.push(next);
}
}
}
return out;
}
distances('A'); // Map(4) { 'A' => 0, 'B' => 1, 'C' => 1, 'D' => 2 }Adjacency list (Map of Sets) is compact and fast for sparse graphs.
Adjacency matrix (2D array of booleans) is wasteful for sparse graphs but answers "is there an edge?" in O(1).
For weighted graphs, store
[neighbour, weight]pairs instead of just neighbours.
Choosing the right one
Need index-based access and ordering? —
Array.Need uniqueness or "is this in the set?" —
Set.Need key/value with non-string keys or insertion order? —
Map.Need a parent/child hierarchy? — tree of objects.
Need many-to-many relationships or cycles? — graph (adjacency list).