Data Structures and Algorithms in JavaScript

The part of computer science that survives contact with real JavaScript: how growth curves behave, why array shift is the most expensive line in most slow apps, how stacks, queues, hash maps, trees and graphs are built out of the objects you already know, and the classic interview problems, solved and measured.

What you will be able to do

  • Read a piece of code and name its complexity class without running it
  • Measure with performance.now and explain when the measurement disagrees with the theory
  • Say precisely why push is amortised O(1) while shift is O(n)
  • Implement a stack, a queue, a deque and a singly linked list, and choose between them
  • Use objects, Map and a hand-built hash table, and explain average versus worst case lookup
  • Traverse trees depth first and breadth first, recursively and iteratively
  • Model a graph as an adjacency list and find a shortest unweighted path
  • Solve two-sum, anagram grouping, flatten, deep clone, memoised fibonacci, curry and deepEqual
  • Build an LRU cache, an event emitter and a bounded promise pool from scratch
  • Talk through a problem the way an interviewer wants to hear it

Lessons

  1. Complexity Intuition — Big-O is not a speed. It is the shape of the line you get when you double the input. Constants decide whether you notice today, the shape decides whether you are doomed later. (18 min)
  2. Stacks, Queues and Linked Lists — A data structure is a promise about which operations stay cheap. A stack promises the end, a queue promises both ends, a linked list promises anywhere you already hold a reference to. (20 min)
  3. Hash Maps, Trees and Graphs — A hash map turns a key into an address so lookup does not depend on size. A tree is a graph that agreed not to have cycles. A graph is just a map from each node to its neighbours. (22 min)