Data Structures and Algorithms in JavaScript

Glossary

100 terms from Data Structures and Algorithms in JavaScript, in plain words, each with the chapter that teaches it.

Search the glossary

A

Adjacency list: A way to store a graph as a Map whose keys are places and whose values are arrays of neighboring places. In Alex's map, graph.get("Pearl") gives Pearl's neighbors, Burnside and Alberta.
Algorithm: A step-by-step method for doing a job, such as checking each order in turn until you find the one you want.
Amortized: A cost averaged over many operations. A push onto a JavaScript array occasionally has to move everything to a bigger block, but that is rare, so push is O(1) on average over many pushes.
Array: A list that stores items side by side in numbered slots, so reading any index is O(1). Adding or removing at the front is slow because every item must shift.
Array.from: A built-in that builds an array of `n` items by calling a function for each position, as in `Array.from({ length: n }, fn)`. It is handy for making test data, such as an array of order IDs from 1 to 1,000,000.
Arrow function: A short, nameless function written like `(a, b) => a.total - b.total`. It is often passed straight to `sort` or `toSorted` as the compare function.
Average case: The cost you can expect in a typical run. Map lookups are O(1) in the average case because collisions are rare.

B

Balanced tree: A tree whose subtrees are about the same height at every node, so its height is about log₂ n and lookups are O(log n). An unbalanced tree, such as one built from sorted inserts, becomes a chain with O(n) lookups.
Base case: The input a recursive function answers directly without calling itself, such as an empty array in sumList. Without one, recursion never stops.
Big-O notation: A way to describe how the number of steps grows as the input size n grows, ignoring constants and smaller terms. O(1) stays flat, O(n) grows in step with n, O(n²) usually comes from a loop inside a loop, and O(V + E) is the cost of BFS and DFS, where V is the number of vertices and E the number of edges.
Binary search: Finding an item in a sorted array by checking the middle and discarding the half that can't hold the target. It takes O(log n) steps, at most about 20 for a million items.
Binary search tree (BST): A binary tree where, at every node, everything in the left subtree is smaller and everything in the right subtree is bigger. Lookup and insert take one step per level.
Binary tree: A tree in which each node has at most two children, called left and right.
Breadth-first search (BFS): A graph search that visits the start, then its neighbors, then their neighbors, ring by ring, using a queue. Because it reaches places in rings, it finds the route with the fewest stops.
Bucket: One slot in the array a hash map keeps inside. A key's hash number picks which bucket its pair is stored in.

C

Call stack: The stack of function calls that haven't finished yet. Each call adds a note on top and removes it when the function returns, and it has a fixed size.
cameFrom: A Map used in BFS that records, for each place, the place you came from when you first reached it. Walking back through it from the goal and reversing gives the route.
Child, parent: In a tree, a child is a node directly below another node, and that other node is its parent.
Class: A blueprint for making objects that have their own fields and methods, such as Stack or LinkedList. You create an object from it with new.
Collision: When two different keys hash into the same bucket, as "mug" and "tea" did. The Map checks a few more slots to find the right key.
Comparator: A function given to sort that receives two items and returns a negative number, 0 or a positive number to say which goes first. It must return a number, not true or false.
CSV (comma-separated values): A plain-text file where each line is a row and the values in it are separated by commas, with a header line first. The planner reads its roads and deliveries from CSV files.

D

Data structure: A way of arranging data so the jobs you need are easy and fast, such as an array, which keeps order, or a map, which finds a value by key.
Depth-first search (DFS): A graph search that goes as far as it can down one road before backing up to try the next. It finds everything reachable and can be written with recursion or a stack.
Deque: A double-ended queue: a list you can add to and remove from at both ends. JavaScript has no built-in one, and a queue built from linked nodes with a head and a tail gives O(1) adds and removals without the slow `shift` of an array.
Dequeue, enqueue: Enqueue adds an item at the back of a queue, and dequeue takes the item off the front.
Dijkstra's algorithm: An algorithm for finding the fastest route in a weighted graph. The planner needs it because fewest stops isn't always fewest minutes; it is taught in the next book.
Divide and conquer: Splitting a problem in half, solving each half, then combining the answers. Merge sort works this way.
Doubly linked list: A linked list where each node also links back to the node before it, so you can walk in both directions.
Dynamic array: An array that grows when it fills up, which is how JavaScript's Array works. The engine keeps spare slots at the end and moves everything to a bigger block when they run out.

E

Edge: A connection between two vertices in a graph, such as a road between two places.
ENOENT: The error Node throws when readFileSync can't find a file. In the planner it usually means you ran the program outside the folder holding the CSV files.
ES modules: JavaScript's standard `import` and `export` system for sharing code between files. In Node.js it is switched on by a `package.json` containing `{ "type": "module" }`. ECMAScript is the official language standard, and ES2023 is its 2023 edition.

F

Field: A variable stored inside each object made from a class, such as items = [] in Stack. Methods reach it through this.
FIFO, LIFO: FIFO means first in, first out, like a queue of Priya's tickets. LIFO means last in, first out, like a stack of coffee cups.

G

Garbage collector: The part of JavaScript that automatically frees memory for nodes that no variable or link points to any more, so you never free them by hand.
Graph: A set of vertices joined by edges, such as places joined by roads. It suits maps with loops that a list or tree can't hold.

H

Hash function: A function that turns any key into a whole number. A Map uses that number to pick the bucket where the key's pair is stored.
Hash key: What a Map or Set hashes and compares. Strings, numbers and booleans match by value, while objects and arrays match only if they are the very same object, so compound keys are joined into one string like "Portland|mug".
Hash map: A structure that stores key-value pairs and finds a value by its key without searching, in O(1) on average. JavaScript's Map is one; a Set is the same with keys and no values.
Head: The first node of a linked list, which is all a LinkedList object stores. A queue also keeps a tail, the last node.
Heap: A binary tree stored in a plain array where every parent comes out no later than its children, so in a min-heap the smallest item is at index 0. Push and pop are O(log n), and it is not stable.
Height: The number of levels on the longest path from a tree's root down to a leaf. An empty tree has height 0.

I

Immutable: Can't be changed after it is made. Strings are immutable, so text += "more" builds a brand-new string.
In place: Changing an array itself instead of making a copy. Swapping from both ends reverses an array in place using O(1) extra space.
In-order traversal: Visiting a tree's left subtree, then the node, then the right subtree, which gives a BST's values in sorted order. Pre-order visits the node before its subtrees.
Index (lookup Map): A Map built once from a list, keyed by a field such as a SKU, so each later lookup is O(1) instead of a loop that is O(n).
Insertion sort: Sorting like a hand of cards: take each item and slide the bigger ones before it right to drop it into place. It is O(n²) but very fast on nearly sorted data.
Instance, object: One value made from a class with new, such as a single Stack with its own items array.
Invariant: A statement that stays true throughout a loop. In lowerBound, the answer is always between low and high.

L

Linear search: Checking items one by one from the start until you find the target. It is O(n).
Linked list: A chain of nodes where each node holds a value and a link to the next, and the last link is null. Adding at the front is O(1), but finding an item means walking the chain, O(n).
localeCompare: A string method that compares two texts and returns a negative number, 0 or a positive number, which makes it handy inside a compare function for sorting text.
Logarithm: The number of times n can be halved down to 1; log₂ 8 is 3 and log₂ 1,000,000 is about 20. It is why halving algorithms such as binary search are so fast.
Lower bound: A reusable binary search, `lowerBound(items, x)`, that returns the index where `x` would go to keep a sorted array sorted, or the index of its first copy if it is already there. It is O(log n) and suits lookups such as choosing a shipping tier by weight.

M

Max-heap: A heap that gives the biggest item first. You make one from the MinHeap class by flipping the comparison to a > b.
Memoization: Saving the answer to a call the first time so it isn't worked out again. It helps recursive functions that solve the same smaller problem many times; the next book covers it.
Merge sort: A sort that splits the array in half, sorts each half recursively, then merges the two sorted halves. It is O(n log n) and stable.
Method: A function that belongs to a class and is called with a dot, such as history.push("x").

N

Neighbor: A vertex joined to another by an edge, such as Burnside and the Roastery.
Node: One item in a linked list or tree, holding a value and links to other nodes. In a graph, nodes are also called vertices.
Node.js: A program that runs JavaScript outside a browser, such as on a computer or server. LTS means long-term support, a release kept stable and maintained for a long time.
node:fs: Node's built-in file-system module. readFileSync reads a whole file at once, and the planner uses it to load its CSV files.

O

Off-by-one error: A mistake of exactly one in an index or comparison, such as using while low < high instead of <=, which skips the last item.

P

package.json: A settings file for a Node.js project. Containing `{ "type": "module" }`, it tells Node to treat `.js` files as ES modules so `import` and `export` work.
padStart / padEnd: String methods that pad text with a character up to a set width, on the left or right. They line up table columns and turn 9 into "09" in clock times.
performance.now(): A built-in Node function that returns a precise clock reading in milliseconds. Read it before and after some code and subtract to time it.
Priority queue: A queue that always serves the most urgent item first, such as Sam's order that must ship soonest. A heap is the usual way to build one.
Property: A value stored on an object, such as node.next or order.total.
Push, pop, peek: Stack operations: push adds to the top, pop removes the top item, and peek looks at the top without removing it. All are O(1).

Q

Queue: A first-in, first-out line of items, like Priya's support tickets. An array with shift is simple but slow; a linked queue gives O(1) enqueue and dequeue.
Quicksort, heap sort: Two other well-known sorting methods that run in O(n log n) time, like merge sort.

R

RangeError: Maximum call stack size exceeded: The error JavaScript throws when recursion goes too deep, usually because of a missing base case or a very long input. Use a loop for long flat arrays.
Reachable: A place is reachable if some chain of roads leads to it from the start. DFS collects every reachable place into a set, which the planner uses to catch cafés with no road to them.
Recursion: A function solving a problem by calling itself on a smaller piece of the same problem. It needs a base case to stop and works well on nested data like shop categories.
Reference: A link that points at an object rather than copying it. A linked list's next field is a reference to another node.
reverse(): The array method that turns an array around in place. BFS uses it to flip a route built backward from goal to start.
Root, leaf: The root is the top node of a tree; a leaf is a node with no children.

S

Self-balancing tree: A tree, such as an AVL tree or red-black tree, that rearranges nodes as you insert to keep its height near log₂ n, avoiding the long-chain worst case.
Set: A hash map with keys and no values, so has, add and delete are O(1) on average. A seen set turns duplicate and pair-sum checks into one O(n) pass.
Shifting: Moving items along an array to open or close a gap, which costs O(n). It is why unshift, shift and splice are slow on big arrays.
Sift up, sift down: The heap steps that restore order. Push adds an item at the end and swaps it up past larger parents; pop moves the last item to the root and swaps it down past smaller children.
Slice: An array or string method that returns a copy of a range of items, costing O(k) for k items. Changing a slice doesn't change the original.
Space: The memory an algorithm needs, which Big-O also describes. A copy of the list is O(n) space, while a few variables are O(1).
Spread operator: The ... syntax that hands the items of an array to a function one by one, as in push(...left.slice(i)).
Stable sort: A sort that keeps equal items in their original order. JavaScript's sort is stable, but a heap is not.
Stack: A last-in, first-out pile where you push and pop at the top only. It suits undo and bracket checking.
Steps: The unit used to measure code instead of seconds, such as one comparison per order checked. Counting steps shows how work grows with the input.
Subtree: Any tree node together with everything below it, which is itself a tree.

T

this: Inside a method, the object the method was called on, so this.items is that particular stack's array.
Timsort: The sorting algorithm V8 uses for sort, a mix of merge sort and insertion sort. It is O(n log n) and stable.
Top-k: Finding the k best items by keeping a min-heap of size k and popping whenever it grows too big. It costs O(n log k), better than sorting everything when k is small.
toSorted / sort: toSorted returns a new sorted array, while sort sorts the array itself. Without a compare function both sort as strings, so numbers come out in the wrong order.
Traversal: Visiting every node of a structure in turn, such as following next links through a linked list or visiting every node of a tree.
Tree: A structure that stores items in levels, with a root at the top and children below, like a family tree or folders inside folders.

V

V8: The JavaScript engine in Node and Chrome. It uses Timsort for sort and hash tables for Map and Set.
Vertex: A point in a graph, such as a place on Alex's map. Also called a node.
visited set: A Set of places a search has already reached, so none is handled twice. Without it, BFS would loop forever around a cycle of roads.

W

Weighted graph: A graph whose edges carry numbers, such as minutes of driving time.
Worst case: The most work an algorithm can need for an input of size n, such as searching for the last or a missing order ID. It is the case you plan for.