Glossary

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

Search the glossary

A

Adjacency list: A way to store a graph as a dict whose keys are places and whose values are lists of neighboring places. In Alex's map, graph["Pearl"] is ['Burnside', 'Alberta'].
Algorithm: A step-by-step method for doing a job, such as looking at each order in turn until you find the one you want.
Amortized O(1): A cost that is O(1) on average over many operations, even though an occasional one is slow. Python's list `append` is amortized O(1) because the rare move to a bigger block is spread over many appends.
Array: Items stored side by side in memory in numbered slots, so any index can be reached in one step.
Attribute: A variable stored inside an object, such as `self.items` in a Stack or `node.next` in a linked list.
Average case: The cost you can expect on a typical run. Dict lookups are O(1) in the average case because collisions are rare.

B

Balanced tree: A tree whose subtrees have 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, can become a long chain.
Base case: The input a recursive function can answer directly without calling itself, such as an empty list in `sum_list`. 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 the data, and O(n²) usually comes from a loop inside a loop.
Binary search: Finding an item in a sorted list by checking the middle and discarding the half that can't hold the target, repeating until found. It takes O(log n) steps, at most 20 for a million order IDs.
Binary search tree (BST): A binary tree where, at every node, smaller values go in the left subtree and bigger values in the right. This lets insert and lookup throw away a whole subtree at each step.
Binary tree: A tree in which each node has at most two children, called left and right.
bisect: A Python module with tested binary searches. `bisect_left(items, x)` returns the index where x would go in the sorted list (the first copy if present), and `bisect_right` returns the index after any copies.
Breadth-first search (BFS): A way to explore a graph ring by ring from a start place, using a queue and a visited set. Because it reaches each place by the fewest roads first, it finds the fewest-stop route.
Bucket: One slot in the internal array of a hash map, chosen by hashing a key. Looking up a key goes straight to its bucket.

C

Call stack: Python's stack of function calls that haven't finished yet. Each call is pushed on top with its local variables and removed when it returns.
came_from: A dict that records, for each place BFS reaches, the place it came from. Walking back through it from the goal gives the route.
Child, parent: In a tree, the children of a node are the nodes directly below it, and it is their parent.
Class: A blueprint for making objects that have their own attributes and methods, such as `Stack` or `Node`.
collections: A standard-library Python module that includes `deque`.
Collision: When two different keys hash to the same bucket. Python then checks a few more slots to find the right key.

D

Data structure: A way of arranging data so that the jobs you need are easy and fast, such as a list, dict or tree.
Depth-first search (DFS): A way to explore a graph by going as deep as possible down one road before backing up to try the next, using recursion or a stack. It finds everything reachable from a place.
Deque: A double-ended queue from the `collections` module that adds and removes at either end in O(1). Kettle & Crane's support tickets use `append` and `popleft` on a deque to be served first in, first out.
Dequeue, enqueue: The two queue operations: enqueue adds an item at the back of the line, and dequeue takes one off the front.
Dict: Python's built-in hash map: it stores key-value pairs and finds a value by its key in O(1) on average.
Dict as an index: A dict built once from a list, keyed by a field such as SKU, so each later lookup is O(1) instead of an O(n) loop.
Dijkstra's algorithm: An algorithm for finding the fastest route in a weighted graph. It would fix the planner's problem that fewest stops isn't always fewest minutes.
Directed, undirected: A directed edge goes one way only, like a one-way street. An undirected edge works in both directions, like a road you can drive either way.
Divide and conquer: A strategy of 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 points back to the one before it. Python's `deque` is built from blocks linked in both directions.
Dynamic array: An array that grows when it fills up. A Python list 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.

F

f-string format codes (:02d, :<, :>): Codes after a colon inside an f-string's braces that control layout: `<` and `>` align text left or right in a given width, and `:02d` prints a whole number at least 2 characters wide with a leading zero, so 9 prints as 09.
FIFO, LIFO: First in, first out describes a queue, where the oldest item is served first. Last in, first out describes a stack, where the newest item comes off first.
Floor division (//) and modulo (%): `//` divides and drops the remainder (`7 // 2` is 3), while `%` gives the remainder (`7 % 2` is 1). Together they let you find a middle index in a list or turn 570 minutes into 9 hours and 30 minutes.

G

Graph: A set of vertices joined by edges, such as places joined by roads on Alex's delivery map. Graphs can hold loops, which lists and trees can't.

H

Hash function: A function that turns any key into a whole number, which a dict uses to pick the key's bucket. Within one run the same key always gives the same number.
Hash map: A structure that stores key-value pairs and finds a value by its key without searching, in O(1) on average. Python's dict is a hash map, and a set is one with keys only.
Hashable: Able to be used as a dict key or set item because its hash never changes: strings, numbers and tuples of hashable items. Lists are unhashable because they can change.
Heap: A binary tree with full levels (the last filling from the left), stored in a plain list. In a min-heap every parent is no bigger than its children, so the smallest item is always at index 0.
heapq: A Python module that treats an ordinary list as a min-heap. `heappush` and `heappop` are O(log n), `heapify` rearranges an existing list in O(n), and `nlargest`/`nsmallest` return the top few items.
Height: The number of levels on a tree's longest path from the root down to a leaf. A balanced tree of n items has height about log₂ n.

I

Immutable: Can't be changed after it's made, like a string or a tuple. `text += "more"` builds a new string rather than changing the old one.
In place: Changing the list itself instead of making a new copy, such as reversing a list by swapping from both ends with no extra space.
In-order traversal: Visiting a binary tree's left subtree, then the node, then the right subtree. In a BST this gives the values in sorted order. A pre-order traversal visits the node first.
Insertion sort: Sorting like a hand of cards: take each item and shift bigger items right to drop it into its place. It is O(n²) but very fast on nearly sorted lists.
Instance, object: One value made from a class. Calling `Stack()` gives you a new object with its own empty `items` list.

K

Key function: A function passed as `key=` that gives the value to sort or compare by. Python calls it once on each item, as when sorting Sam's orders by their total.

L

Lambda: A small function with no name, written inline with one expression that is returned automatically, such as `lambda order: order["total"]`.
Linear search: Checking items one by one from the start until you find the target. Priya's order check this way takes up to a million steps for a million orders.
Linked list: A chain of nodes where each node holds a value and a link to the next, and the list keeps only the first node, called the head. Adding at the front is O(1) but finding an item is O(n).

M

Max-heap: A heap that gives the largest item first. Since `heapq` only makes min-heaps, you push negative priorities and negate them again after popping.
Memoization: Saving the answer to each function call the first time it is computed so it isn't worked out again when the same call repeats. It speeds up recursive functions that solve the same smaller problem many times.
Merge sort: A sort that splits the list in half, sorts each half recursively, then merges the two sorted halves. It runs in O(n log n).
Method: A function that belongs to a class and is called on an object with a dot, such as `history.push("x")`.

N

Neighbor: A vertex joined to another by an edge, such as Burnside and Hawthorne being neighbors of 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.
None: Python's value meaning "nothing here". A linked list's last `next` and a missing tree child are `None`, and you test for it with `is None` rather than `==`.

O

Off-by-one error: A mistake of exactly one in an index or comparison, like writing `while low < high` instead of `<=` in binary search.
Other O(n log n) sorts (quicksort, heap sort): Quicksort and heap sort are two sorting methods that, like merge sort, run in O(n log n) time. They are common alternatives to merge sort for sorting large lists.

P

Priority queue: A queue that serves the most urgent item first rather than the oldest. A heap is the usual way to build one.
Push, pop, peek: The three stack operations: push adds an item to the top, pop removes and returns 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 answered in arrival order. A `deque` makes an efficient one.

R

Reading CSV files (CSV, with open, enumerate, continue): CSV (comma-separated values) is a plain-text format with one row per line and values split by commas. The planner opens each file with `with open` (which closes it automatically), uses `enumerate` to spot line 0 as the header, and `continue` to skip that line.
Recursion: A function solving a problem by calling itself on a smaller piece of the same problem, until it reaches a base case. It suits nested data like the shop's categories.
Recursion limit: The deepest the call stack may go, about 1,000 calls by default, before Python raises `RecursionError`. Missing base cases or very long flat lists can trigger it.
Root, leaf: The root is the top node of a tree, and a leaf is a node with no children.

S

self: Inside a method, `self` is the object the method was called on, passed in by Python automatically. `__init__` is the special method that runs once to set up a new object.
Self-balancing tree (AVL, red-black): A tree that rearranges its nodes as items are inserted so its height stays near log₂ n. AVL trees and red-black trees are examples, and databases use relatives of them to index rows.
Set: A hash map with keys and no values, so adding and testing `x in my_set` are O(1) on average. A `seen` set turns O(n²) duplicate and pair checks into one O(n) pass.
Shifting: Moving items along a list to open or close a gap, which costs O(n). It's why `insert(0, x)` and `pop(0)` are slow.
SKU: Stock-keeping unit: a product's stock code, such as "HE-5" for House Espresso 5 lb, used as a dict key for fast lookups.
Slice: A piece of a list or string taken with `items[a:b]`, which makes a copy costing O(k). A step of -1 (`[::-1]`) gives a reversed copy.
Space: The memory an algorithm needs. For example, `has_duplicate` with a set uses O(n) extra space to gain speed.
Stable sort: A sort that keeps items with equal keys in their original order. Python's sort is always stable, so Steam & Co stays ahead of Little Owl when both totals are 144.
Stack: A last-in, first-out pile where you add and remove at the top only, like a stack of coffee cups. It suits undo and bracket checking.
Step: The unit used to measure an algorithm's cost, such as one comparison per order checked. Counting steps instead of seconds gives a measure that doesn't depend on how fast a particular computer is.
Subtree: Any node in a tree together with everything below it; it is itself a tree.

T

time.perf_counter(): A function in Python's `time` module that returns a reading from a precise clock in seconds. You read it before and after some code and subtract to get the time taken.
Timsort: Python's built-in sorting algorithm, a mix of merge sort and insertion sort that spots stretches already in order. It is stable and O(n log n).
Traversal: Visiting every node in turn, such as walking a linked list from head to the end or visiting every node of a tree.
Tree: A structure that stores items in levels, like a family tree or folders inside folders, with a root at the top and children below.
Tuple unpacking: Splitting a tuple into separate variables in one statement, such as `a, b = b, a` to swap two values or `day, cafe = heappop(orders)`.

V

Vertex: A point in a graph, such as a place on Alex's map. Vertices are also called nodes.
visited set: A set of places a search has already reached so none is handled twice. Without it, BFS would loop forever around Roastery, Burnside and Hawthorne.

W

Weighted graph: A graph whose edges carry numbers, such as minutes of driving.
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's the case planned for because it hurts users most.