Glossary

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

Search the glossary

A

Adjacency list: A way to store a graph as a HashMap whose keys are places and whose values are Vecs of each place's neighbors. In Alex's map, the Roastery's list is Burnside, Hawthorne and Sellwood.
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: Averaged over many operations. A Vec's push is amortized O(1) because the rare slow move to a bigger block is spread across many cheap pushes.
Array: Items stored side by side in memory in numbered slots, so any index is reached in one step: O(1).
as_deref(): An `Option` method that turns a `&Option<Box<Node>>` into an `Option<&Node>`, giving a borrowed look at the next node without taking ownership. It is commonly used to walk a linked list one node at a time.
Average case: The cost you can expect on a typical run. Hash map lookups are O(1) in the average case because collisions are rare.

B

Balanced tree: A tree whose two subtrees at each node have about the same height, so its height is about log₂ n and lookups are O(log n). Inserting already-sorted IDs makes an unbalanced chain; self-balancing trees such as AVL and red-black trees rearrange nodes to avoid that.
Base case: The input a recursive function answers directly without calling itself, such as an empty list in sum_list. Without one, the calls never stop.
Big-O notation: A way to describe how the number of steps grows as the input size n grows. It drops constants and smaller terms, so n²/2 is still O(n²).
Binary search: Finding an item in a sorted list by checking the middle and discarding the half that can't hold the target. It takes O(log n) steps, at most 20 for a million items. Rust's slice method binary_search returns Ok(index) or Err(index).
Binary search tree (BST): A binary tree in which everything in a node's left subtree is smaller and everything in its right subtree is bigger. Lookups and inserts take one step per level.
Binary tree: A tree where each node has at most two children, called left and right.
BinaryHeap: Rust's heap type in std::collections, stored in a Vec. It is a max-heap, so pop returns the biggest item; push and pop are O(log n) and peek is O(1).
Borrow: Using a value through a reference without taking ownership of it. A plain & borrow only reads, while &mut lets the code change the value.
Box: A pointer that puts a value on the heap and owns it. It gives a Node a fixed size so a node can link to another node, and when the box goes away so does what it holds.
Breadth-first search (BFS): Visiting a graph ring by ring from the start using a queue and a visited set. It reaches each place by the fewest roads, so it finds the fewest-stop route.
BTreeMap: A standard-library map that keeps its keys in sorted order, with O(log n) lookups, inserts and removals. It is the choice when you need to find values by key and also walk them in key order.
Bucket: One slot in the internal array of a hash map. A key's hash number picks the bucket where its pair is stored.

C

Call stack: The pile of notes about function calls that haven't finished, each with its local variables and where to continue. A call puts a note on top and a return takes it off, last in, first out.
came_from: A map from each place to the place BFS came from when it first reached it, with the start mapping to None. Walking back through it from the goal and reversing gives the route.
Capacity: The spare slots a Vec keeps at its end. When they run out, the Vec moves everything to a bigger block.
Child, parent: A child is a node directly below another in a tree; the node directly above it is its parent.
clone(): A method that makes an independent copy of a value. BFS clones each neighbor because the queue and the visited set each need their own copy.
Closure: A small nameless function written right where it is needed, with its parameters between bars, such as `|a, b| b.total.cmp(&a.total)`. Closures are often passed to methods like `sort_by_key` and `sort_by` to say what to compare.
Collision: When two different keys hash to the same bucket. The map checks a few more slots to find the right key.
const: A keyword that declares a value fixed for the whole program, such as START_TIME. By convention the name is written in capitals.

D

Data structure: A way of arranging data so the jobs you need are easy and fast. A Vec keeps items in order and a HashMap finds a value by its key.
Depth-first search (DFS): Exploring a graph by going as deep as possible down one road before backing up to try the next. It finds everything reachable and can be written with recursion or a stack.
Dequeue, enqueue: Enqueue adds an item at the back of a queue; dequeue takes an item off the front.
derive: An attribute that asks the compiler to write trait code for a struct. Deriving Hash, PartialEq and Eq makes a struct usable as a key. Deriving the ordering traits compares fields in the order written, which is why Delivery lists deadline first.
Dijkstra's algorithm: An algorithm that finds the fastest route in a weighted graph. The planner would use it to choose routes by fewest minutes rather than fewest stops, and the next book teaches it.
Directed, undirected: A directed edge goes one way only, like a one-way street. An undirected edge works in both directions, like a two-way road.
Divide and conquer: Splitting a problem in half, solving each half, then combining the answers. Merge sort works this way.
Dynamic array: An array that grows when it fills up, like a Vec. It keeps spare capacity and moves to a bigger block only occasionally.

E

Edge: A connection between two vertices in a graph, such as a road between two places.
entry().or_default(): A HashMap pattern that finds the value for a key, or creates a default one (an empty Vec, or 0 with or_insert(0)) if the key is new. It is used to count items and to add neighbors to a graph.

F

Field: A named value stored inside a struct, such as node.next or order.total.
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.

G

Generic: Code written for any type T, such as Stack<T>, so the same code can make a Stack<String> or a Stack<char>.
Graph: A set of vertices joined by edges, such as Alex's places joined by roads. Graphs can hold loops that a vector or tree can't.

H

Hash function: A function that turns any key into a whole number, which the map uses to pick a bucket. Equal keys must always give the same number.
Hash map: A structure that stores key-value pairs and finds a value by its key in O(1) on average, like a coat check. Rust's version is HashMap.
Hashable: A type that can be a HashMap key or HashSet item because it implements Hash and Eq. Strings, integers, tuples and Vecs of them qualify, but f64 does not because NaN isn't equal to itself.
HashSet: A hash map with keys and no values, used to check whether an item has been seen. insert and contains are O(1) on average.
Head: The first node of a linked list. The LinkedList struct keeps only its head and reaches everything else through links.
Heap: A binary tree with every level full except perhaps the last, stored level by level in a Vec so the extreme item is at index 0. The children of index i are at 2*i+1 and 2*i+2.
Heap (memory): The memory area for values whose size or lifetime isn't fixed. A Box puts a node there and keeps a fixed-size pointer in its place.
Heapify: Rearranging an existing Vec into a heap in O(n) steps, as BinaryHeap::from(vec) does.
Height: The number of levels on the longest path from the root down to a leaf. An empty tree has height 0.

I

Immutable: Can't be changed after it's made. In Rust a binding without mut is immutable, so changing methods like sort need let mut.
In place: Changing a Vec or slice itself instead of making a new one. Swapping from both ends reverses a vector in place.
In-order traversal: A walk that visits the left subtree, then the node, then the right subtree. In a BST that gives the values in sorted order. Pre-order visits the node before its subtrees.
Insertion sort: Sorting like a hand of cards: take each item and shift bigger items right to drop it into the gap. It is O(n²) but fast on nearly sorted lists.
Instant: A std::time type that reads a precise clock. Call .elapsed() later to get the time passed, and .as_secs_f64() to see it in seconds.
Iterator chain: A series of methods such as chars().rev().collect() that hand out items one at a time, change them, and gather the results into a type you name.

K

Key function: A function or closure passed to sort_by_key that gives the value to sort by, such as a struct's total field.

L

Linear search: Looking at each item from the start until you find the target. It is O(n).
Linked list: A chain of nodes, each holding a value and a link to the next. Adding at the front is O(1) but finding an item is O(n); a doubly linked list also links back.

M

Max-heap, min-heap: A min-heap has every parent no bigger than its children, so the smallest item is at the root. A max-heap is the reverse, and Rust's BinaryHeap is a max-heap.
Memoization: Saving the answer to each repeated smaller problem so it isn't worked out again. The next book covers it.
Merge sort: Splitting a list in half, sorting each half recursively, then merging the sorted halves. It runs in O(n log n).
Method: A function that belongs to a type, defined in an impl block and called with a dot. &self methods only read, and &mut self methods change the value.

N

NaN: A special floating-point value meaning "not a number", which isn't equal even to itself. That is why f64 can't be a hash key or be fully sorted with Ord.
Neighbor: A vertex joined to another by an edge.
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.

O

Off-by-one error: A mistake of exactly one in an index or comparison, such as using while low < high instead of <=, or low = middle instead of middle + 1, in binary search.
Option: An enum that is either Some(value) or None, Rust's way to say maybe nothing. It's used for pop on an empty stack, for a missing key or for the end of a linked list.
Ordering: The result of x.cmp(&y): Less, Equal or Greater. The .then(...) method compares a second pair only when the first comparison is Equal, so you can sort by two fields.
Ownership: The Rust rule that each value has one owner, which frees it when it goes away. A node owns the Box holding the next node, and each Category is owned by its parent.

P

Panic: A crash Rust triggers when code does something impossible, such as indexing past the end of a Vec or calling unwrap() on None. The program stops with a message naming the problem.
partition_point: A slice method that returns the index of the first item where a test turns false, using binary search. It suits tier lookups like Kettle & Crane's shipping rates and works on f64 data.
Pattern matching: Taking a value apart by its shape: match chooses an arm, if let runs a block when the value fits a pattern such as Some(x), and while let loops until it stops fitting.
Priority queue: A queue that always serves the most urgent item first, even if it arrived last. A heap is the usual way to build one.
Push, pop, peek: Push adds an item to the top of a stack, pop removes the top item, and peek looks at it without removing it. All are O(1) on a stack.

Q

Queue: A first-in, first-out line of items, like Priya's support tickets answered in arrival order. VecDeque is the efficient Rust choice.

R

Recursion: A function solving a problem by calling itself on a smaller piece of the same problem. It needs a base case to stop.
Recursive case: The part of a recursive function that makes the problem smaller and calls itself on it.
retain: A `Vec` method that keeps only the items for which a closure returns true and removes the rest, in place. For example, it can drop one road from a place's list of neighbors.
Reverse: A wrapper from std::cmp that flips an item's ordering. Wrapping items in it makes the max-heap BinaryHeap hand out the smallest first.
reverse(): A Vec method that reverses the items in place. BFS uses it to turn a route built from goal to start into start to goal.
Root, leaf: The root is the top node of a tree, and a leaf is a node with no children.
rustc -O: The command to compile a single Rust file with the optimizer on. Without -O, timings mean little, and the optimizer may delete a search whose result is never used.

S

Shifting: Moving items along a list to open or close a gap. Inserting or removing at the front of a Vec shifts every item, which costs O(n).
Slice: A borrowed view of a run of items in a Vec or array, such as &[u32] or &items[1..]. Slicing copies nothing and is O(1), while to_vec() makes a copy.
Space: The memory an algorithm needs. Big-O describes it too: has_duplicate uses O(1) extra space, while a copy would be O(n).
Stable sort: A sort that keeps equal items in their original order. Rust's sort, sort_by and sort_by_key are stable, while sort_unstable is usually a bit faster but may swap equal items.
Stack: A last-in, first-out pile where items are added and removed at the top only. It can be built as a generic `Stack<T>` on top of a `Vec`, and is used for things like undo and bracket checking.
Stack overflow: The crash when the call stack grows past its fixed memory, usually from missing base cases or very deep recursion. In Rust the process aborts rather than raising a catchable error.
String: A String is a growable array of UTF-8 bytes. push_str appends in place, join glues pieces with a separator, and a &str is a borrowed view of text. Because a character can take several bytes, Rust refuses code[0].
Struct: A type that groups named fields, such as Node, Order or Stack<T>.
Subtree: A node together with everything below it, which is itself a tree.

T

take(): An Option method that pulls the value out and leaves None behind. It lets linked-list code move a node without moving out of a borrow.
Trait: A set of methods a type offers, such as Hash and Hasher, which you import with use to call their methods. A trait bound requires that a type has it.
Traversal: Visiting every node in turn, such as following a linked list's links until None, or walking a tree. In-order gives a BST's values sorted, and pre-order visits the node first.
Tree: A structure that stores items in levels, like a family tree or a folder of folders, with a root at the top. The shop's categories form a tree.
Tuple: A fixed group of values such as (city, product) or (priority, item). Tuples of hashable values can be map keys, and they compare item by item, which is how they sort and order heaps.
type alias: A type declaration that gives a long type a short name, such as type Graph = HashMap<String, Vec<String>>.

U

unwrap() and expect(): Methods that take the value out of an `Option` and panic if it is `None`; `expect` lets you supply the panic message. They are best used only where a value is certain to be present, such as right after a check.
usize, isize: The whole-number types for positions in a list: usize can't go below 0, and isize is signed so it can hold -1. Indexes must be usize, so isize values are converted with as usize.

V

Vec: Rust's growable dynamic array, with O(1) index reads and push/pop at the end. insert(0, x) and remove(0) shift items and cost O(n).
VecDeque: A double-ended queue in std::collections, pronounced "vec-deck", with O(1) adds and removes at both ends. Use push_back and pop_front for a queue instead of Vec::remove(0).
Vertex: A point in a graph, such as a place on Alex's map.
visited set: The places a search has already reached, so none is handled twice. Without it, BFS would loop around the Roastery, Burnside and Hawthorne forever.

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 a missing target in linear search. It is used for planning because it describes the slowest outcome users could face.