Tags: web-dev concept

Data Structures

Date: 2026-08-17

---

Different ways of arranging data in memory, each fast at some operations and slow at others. Choosing the right one is the optimisation — no amount of tuning makes a linear scan behave like a hash lookup.

---

A data structure is an arrangement of data that makes certain operations cheap by making others expensive. There is no general-purpose winner; there is only a match between the structure and the operations you actually perform.

The five that cover almost everything

ARRAY / LIST      ordered, indexed
  read by index   O(1)     instant
  find a value    O(n)     scan it all
  append          O(1)*    amortised
  insert middle   O(n)     shift everything

MAP / OBJECT      key → value
  read by key     O(1)
  insert          O(1)
  ordered?        insertion order, JS
  find by value   O(n)

SET               unique membership
  has?            O(1)
  add             O(1)
  no duplicates, no order guarantee

TREE              hierarchy, or sorted
  find (balanced) O(log n)
  in-order walk   sorted output
  the DOM is one

GRAPH             arbitrary relationships
  nodes and edges, possibly cyclic
  "who follows whom", "what depends
  on what"

The decision, in one line

Ask what operation happens most, then pick the structure that makes it O(1).

"is this ID in the list?"
  array   → O(n) per check
  Set     → O(1) per check

10,000 checks against 10,000 items:
  array   100,000,000 comparisons
  Set              10,000 lookups

That’s the whole point of knowing them. It isn’t micro-optimisation — it’s the difference between a page that renders and one that hangs — Time and Space Complexity.

The one people get wrong

Repeatedly searching an array. It’s the single most common performance bug in application code, and it looks innocent:

// O(n × m) — quietly quadratic
products.filter(p =>
  featuredIds.includes(p.id)
)
 
// O(n + m) — build the index once
const featured = new Set(featuredIds)
products.filter(p => featured.has(p.id))

At 50 products nobody notices. At 5,000 the page freezes, and the fix is two lines.

Structures worth recognising

Not ones you’ll implement, but ones you’ll meet:

• Stack — last in, first out. The call stack, undo history, DOM traversal
• Queue — first in, first out. Job queues, event loops, BFS
• Linked list — cheap insert anywhere, no indexed access. Rare in application code, common inside runtimes
• Hash table — the thing a map is built from. Collisions and load factor are why “O(1)” is average rather than guaranteed
• Trie — prefix tree. Autocomplete and routing tables
• B-tree — the shape of nearly every database index — Indexing

Where the abstraction leaks

• JavaScript objects are not plain hash maps. Keys are strings or symbols, insertion order is mostly preserved, and engines optimise “shape” behind the scenes. Map is the honest one — any key type, guaranteed order, and better for frequent insert and delete
• Arrays in JS are objects with integer-ish keys. Sparse arrays and non-integer keys deoptimise them badly
• “O(1)” hash lookups degrade when hashes collide. Rare, but adversarially triggerable — hash-flooding is a real denial-of-service class

The connection to everything else

Every performance question upstream of the browser is a data structure question in disguise. An index is a tree. A cache is a map. A CDN is a distributed map keyed by URL. Recognising the structure tells you immediately what will be fast and what won’t — Caching Strategies, Indexing.