23 · Data Structures & Algorithms (for Frontend)

The computer-science foundation, from zero: Big-O complexity, the core data structures (arrays, linked lists, hash maps, sets, stacks, queues, trees, heaps, graphs, tries), and the algorithmic patterns that recur in interviews and in real frontend work (rendering trees, virtual DOM diffing, routing, autocomplete, scheduling). Practical, JS-flavored, not academic.

Positioning

Two reasons a senior frontend engineer needs this. First, interviews — senior roles (and the Ireland/Critical-Skills track) test DSA via LeetCode-style problems. Second, and more importantly, the work itself is full of data structures: the DOM and React’s Fiber tree are trees (01, 05), the virtual-DOM diff is a tree algorithm, routers use tries/trees, autocomplete uses tries + debouncing, state normalization uses hash maps, the event loop uses queues (02), and React’s Lanes use bitmasks. Understanding complexity is also how you avoid shipping an accidental O(n²) render. This file starts from basic programming knowledge and builds the vocabulary.

Foundations: Big-O notation (complexity)

Big-O describes how an algorithm’s time or space grows as input size n grows — the shape of the cost, ignoring constants. It’s how you compare approaches and predict scaling.

Key ideas: drop constants and lower-order terms (O(2n + 5) → O(n)); analyze the worst case by default (also know average/amortized); space complexity matters too (a memo trades space for time). The practical senior instinct: a nested loop over the same array is O(n²) — can a hash map make it O(n)? That single move solves a huge fraction of problems.

Deep dive: core data structures

Each entry: what it is, the cost of common operations, and where it shows up in frontend.

Array (contiguous, indexed)

• Access by index O(1); search O(n); insert/delete at end O(1) amortized, at front/middle O(n) (shifting).
• JS arrays are dynamic + heterogeneous (and engine-optimized when “packed”; 01). The default sequence everywhere.

Hash Map / Hash Set (Map/Set/object)

• Insert/lookup/delete O(1) average (O(n) worst with collisions). The single most useful structure for turning O(n²) into O(n): build a map for O(1) lookups instead of re-scanning.
• Frontend uses: normalizing state by id (06), de-duplication (Set), memo caches (05), counting/grouping, adjacency lists for graphs. Prefer Map over plain objects for dynamic keyed collections (true any-key, size, iteration order, no prototype pitfalls).

Linked List

• Nodes pointing to next (singly) / prev+next (doubly). Insert/delete given a node O(1); access by position O(n).
• Rare to hand-write in frontend, but React’s hook state is a linked list on the fiber (05), and the fiber tree uses child/sibling/return pointers. Knowing it explains the Rules of Hooks.

Stack (LIFO)

• Push/pop O(1). Uses: the call stack (02), undo/redo, DFS, expression parsing, browser history (back), bracket-matching. Trivially an array with push/pop.

Queue (FIFO) & Deque

• Enqueue/dequeue O(1) (use a deque/linked list; array.shift() is O(n)). Uses: the task/microtask queues in the event loop (02), BFS, request/animation scheduling, rate-limit buffers, React’s work scheduling concepts.

Tree

• Hierarchical nodes (a root, children). The DOM, the CSSOM, React’s Fiber tree, JSON, file systems, comment threads, routing tables are all trees.
• Binary Search Tree (BST): ordered; search/insert O(log n) when balanced, O(n) when degenerate. Balanced trees (AA/red-black/B-trees) keep it O(log n).
• Traversals: depth-first (pre/in/post-order) and breadth-first (level-order). The virtual-DOM diff and any “walk the component/DOM tree” operation is a traversal.

Heap / Priority Queue

• A tree keeping the min/max at the root; insert/extract O(log n), peek O(1). Uses: scheduling by priority (conceptually like React’s Lanes prioritization, 05), “top-K” problems, Dijkstra.

Graph

• Nodes + edges (directed/undirected, weighted/unweighted). Represented as an adjacency list (a hash map of node → neighbors) or matrix.
• Uses: dependency graphs (your module graph, 14), navigation/relationships, recommendation links, state machines (06). Algorithms: BFS (shortest path in unweighted), DFS (reachability/cycles/topological sort), Dijkstra/A* (weighted shortest path), topological sort (build ordering, task scheduling).

Trie (prefix tree)

• Tree keyed by string prefixes; lookup is O(length of key), independent of how many keys exist. The structure behind autocomplete/typeahead, search suggestions, and many routers (path-prefix matching). Pair with debouncing (02) for a real search box.

Deep dive: algorithmic patterns (the interview toolkit)

These recurring patterns solve most LeetCode-style problems and map to real tasks:

• Two pointers — one array, two indices moving toward each other or in tandem (pair-sum in a sorted array, dedupe, palindrome). Often turns O(n²) → O(n).
• Sliding window — a moving range over a sequence (longest substring without repeats, max sum of k consecutive, rate-limiting). O(n) instead of recomputing.
• Hash map for O(1) lookup — “have I seen this / its complement?” (two-sum, grouping anagrams, first unique). The most common single trick.
• Binary search — O(log n) on sorted data (or on a monotonic answer space — “search the answer”). Know the off-by-one boundaries.
• BFS / DFS — tree/graph traversal (level-order vs deep; shortest path vs reachability; flood fill; tree problems).
• Recursion + memoization → Dynamic Programming — overlapping subproblems solved once and cached (Fibonacci, edit distance, coin change). Top-down memo or bottom-up tabulation. React’s reconciliation and the diffing of two trees is conceptually a constrained tree-DP (React uses heuristics + keys to keep it O(n), 05).
• Greedy — locally optimal choices (interval scheduling, some shortest-path). Fast but must prove correctness.
• Sorting — know that good comparison sorts are O(n log n); JS Array.sort is a stable sort (TimSort-class in V8). Provide a comparator for objects; beware default lexicographic sorting of numbers.

Frontend-specific algorithmic moments

• Virtual DOM diffing / reconciliation (05) — comparing two trees; keys convert an O(n³) general tree-diff into an O(n) heuristic. This is the reason list keys matter.
• Debounce/throttle (02, 04) — control event frequency (search, scroll, resize); time-based algorithmic control.
• Virtualization / windowing — render only visible items (binary-search the scroll offset; O(visible) not O(n)) — how you list 100k rows (15).
• Memoization — useMemo/useCallback/React Compiler cache pure computations (05); same idea as DP caching.
• Normalization — store entities in a hash map by id, reference by id elsewhere (O(1) updates, no duplication; 06).

Worked example: two-sum, the canonical O(n²)→O(n) move

// ❌ Brute force: nested loops, O(n²)
function twoSumSlow(nums, target) {
  for (let i = 0; i < nums.length; i++)
    for (let j = i + 1; j < nums.length; j++)
      if (nums[i] + nums[j] === target) return [i, j];
}

// ✅ Hash map: one pass, O(n) time / O(n) space — "have I seen the complement?"
function twoSum(nums, target) {
  const seen = new Map();                       // value → index
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (seen.has(need)) return [seen.get(need), i];
    seen.set(nums[i], i);
  }
}

The pattern — trade space for time with a hash map to avoid re-scanning — recurs constantly, including in real code (e.g., joining two lists by id in one pass instead of nested finds, which is a silent O(n²) in many components).

Pitfalls & gotchas

• Accidental O(n²) in React — array.find/includes inside a map over the same data; nested loops in a render. Build a Map first.
• array.shift()/unshift() in loops — O(n) each → O(n²); use a real queue/deque or push+reverse.
• Default .sort() on numbers — sorts lexicographically ([1,10,2]); always pass a comparator.
• Deep recursion on large trees/inputs — stack overflow (no reliable TCO in JS, 22); convert to iterative BFS/DFS with an explicit stack/queue.
• Mutating while iterating — index/skip bugs.
• Ignoring space complexity — a memo that caches unbounded keys is a memory leak (02).
• Premature micro-optimization — readability first; optimize the algorithm (the Big-O), not the constants, and only after measuring (15, 20).
• Forgetting key semantics — wrong/index keys break the diff heuristic and cause subtle list bugs (05).

Interview questions

1. Explain Big-O. Give an O(1), O(log n), O(n), O(n log n), O(n²) example each.
2. When does a hash map turn O(n²) into O(n)? Give a real frontend case.
3. Array vs linked list vs hash map — operation costs and when to use each.
4. Stack vs queue — and where each appears in the browser/runtime.
5. Tree traversals (DFS pre/in/post vs BFS) — and how the DOM/Fiber relate.
6. How do keys change the complexity of React’s diff?
7. Explain two-pointer and sliding-window with a problem each.
8. BFS vs DFS — when to choose which?
9. What is memoization, and how does it relate to dynamic programming and useMemo?
10. Why is array.shift() in a loop a performance trap?

Recommendations

• Internalize Big-O; reflexively ask “is this nested loop O(n²)? Can a Map fix it?”
• Reach for the right structure: Map/Set for lookups/dedupe, arrays for ordered sequences, trees for hierarchy, adjacency lists for graphs, tries for prefix search.
• Learn the patterns (two-pointer, sliding window, hash-map lookup, BFS/DFS, binary search, memoization/DP) — they cover most interview problems and many real tasks.
• Normalize entity state by id; virtualize long lists; debounce/throttle high-frequency events.
• For interviews (Ireland track), practice on LeetCode/NeetCode by pattern, not by random grinding; state complexity for every solution.
• Optimize algorithms over constants, and only after profiling (15, 20).

Books & references

• “Grokking Algorithms” (2nd ed) — Aditya Bhargava. Illustrated, from-zero, the friendliest intro to Big-O, search, sort, graphs, DP. Best starting point.
• NeetCode (neetcode.io) — the best curated, pattern-organized practice path for interviews; free roadmap + explanations.
• “Cracking the Coding Interview” — Gayle Laakmann McDowell. The classic interview-prep catalog.
• “The Algorithm Design Manual” — Steven Skiena. The practical reference once you’re past basics.
• “Introduction to Algorithms” (CLRS) — the rigorous academic reference (dip in, don’t read cover-to-cover).
• visualgo.net and “JavaScript Algorithms” (trekhleb, GitHub) — visualizations and JS implementations of every structure here.
• LeetCode — practice; filter by pattern/tag and track complexity.

Connections

• 01-browser-engines-and-rendering.md — the DOM/render trees; packed-array engine optimizations.
• 05-react-internals-and-patterns.md — Fiber tree, hook linked list, reconciliation diff, keys, Lanes bitmask, memoization.
• 02-javascript-deep-dive.md — call stack, task/microtask queues, closures behind memoization, debounce.
• 06-state-management-and-stores.md — normalization by hash map; selectors/derivation.
• 15-performance-and-core-web-vitals.md — virtualization, avoiding O(n²) renders, algorithmic perf.
• 14-build-tools-and-bundlers.md — the module dependency graph and topological build ordering.
• 22-functional-programming.md — recursion, reduce, memoization as DP.