Glossary

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

Search the glossary

#

%02d: A format verb that prints a whole number at least 2 characters wide, padded with a leading zero, so 9 prints as `09`. `Sprintf` builds the text instead of printing it.

A

Adjacency list: A way to store a graph as a map from each place to a slice of its neighbors. Alex's map is stored as `map[string][]string`, so finding the roads out of Burnside is one lookup.
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 O(1): The average cost per operation over many operations. `append` is occasionally slow when it copies to a bigger array, but that is rare enough that each append averages out to O(1).
Array: Items stored side by side in numbered slots, so any index is reached in one step. A dynamic array, like Go's slice, grows when it fills up.
Average case: The cost you can expect on 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, so its height is about log₂ n and lookups are fast. A tree built from already-sorted inserts becomes an unbalanced chain with O(n) lookups.
Base case: The input a recursive function answers directly without calling itself, such as an empty slice 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. It drops constants and smaller terms, so only the shape of the growth matters.
Big-O shapes (O(1), O(log n), O(n), O(n log n), O(n²)): The common growth rates. O(1) is constant (same steps however big the data); O(log n) halves the work each step (a million items need about 20); O(n) grows in step with the data; O(n log n) is the cost of a good sort; O(n²) is usually a loop inside a loop.
Binary search: Finding an item in sorted data by checking the middle and discarding the half that cannot hold the target. It takes O(log n) steps, at most 20 for a million order IDs.
Binary search tree (BST): A binary tree where everything in a node's left subtree is smaller and everything in its right subtree is bigger. Insert and lookup 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): Visiting a graph ring by ring from the start, using a queue. Because it reaches each place by the fewest roads first, it finds the route with the fewest stops.
Bucket: One slot in the array a hash map keeps inside. A key's hash picks the bucket where its pair is stored.

C

Call stack: Go's pile of notes about function calls that have not finished yet. Each call goes on top and comes off when it returns, last in, first out.
cameFrom map: A map used in BFS that records, for each place, the place you came from when you first reached it. Walking it backward from the goal rebuilds the route.
Capacity: The number of slots in the array behind a slice, found with `cap`. When length reaches capacity, `append` allocates a bigger array and copies the items over.
Child, parent: In a tree, a child is a node directly below another node, and that node is its parent.
cmp.Compare: A function from Go's `cmp` package that compares two numbers or strings and returns negative, 0 or positive. It is the usual building block of a comparison function.
Collision: When two different keys hash into the same bucket. Go then checks the few entries in that bucket to find the right key.
Comma-ok idiom: Go's way to report whether something worked without exceptions: a second `ok` result that is `false` when a map key is missing or a stack is empty.
Comparable key: A type that `==` works on, so it can be a map key or set item: strings, numbers, booleans, arrays and structs of those. Slices, maps and functions are not comparable.
Comparison function: A function that takes two items and returns a negative number if the first goes first, a positive number if the second goes first and 0 for a tie. You pass it to `slices.SortFunc` to sort structs by any field.
Constant (const): A named value that never changes while the program runs, declared with `const`. The planner uses constants for the start place, start time and unload minutes.
container/heap: A standard-library package that keeps a slice arranged as a heap. You supply a type with five methods, then call `heap.Push` and `heap.Pop` (O(log n)) or `heap.Init` (O(n)).
container/list: A standard-library doubly linked list with O(1) `PushBack`, `PushFront` and `Remove`. It works as a queue, a stack or both.
CSV (comma-separated values): A plain-text file format where each line is a row and fields are separated by commas. The planner reads `roads.csv` and `deliveries.csv` with Go's `encoding/csv` package.

D

Data structure: A way of arranging data so the jobs you need are easy and fast, such as a slice, a map or a tree.
defer: A Go keyword that schedules a call to run when the surrounding function ends. The planner uses it to close a file once reading is done.
Depth-first search (DFS): Exploring a graph as deep as possible down one road before backing up to try the next. It finds everything reachable and is often written recursively.
Dequeue, enqueue: Enqueue adds an item at the back of a queue, and dequeue takes the item at the front. Priya's tickets are enqueued as they arrive and dequeued in that same order.
Dijkstra's algorithm: An algorithm for finding the fastest route in a weighted graph. It would fix the planner's late Daybreak delivery, and is taught in the next book.
Directed, undirected: An undirected edge works in both directions, like a two-way road. A directed edge goes one way only, like a one-way street.
Divide and conquer: Splitting a problem in half, solving each half, and combining the answers. Merge sort works this way.

E

Edge: A connection between two vertices in a graph, such as a road between two places.

F

Field: A variable stored inside a struct, such as `Next` in a linked-list node. Every value of the struct gets its own copy.
FIFO, LIFO: First in, first out is how a queue serves items, like a line at the counter. Last in, first out is how a stack works, like a pile of cups.
Function literal: A function with no name, written inline where it is needed, such as `func(a, b Order) int { ... }` passed to a sort.

G

Garbage collector: The part of Go that automatically frees memory nobody points to any more. That is why removing a linked-list node only needs to skip it.
Generics: A Go feature for writing one type or function that works for many types instead of a single concrete type. For example, a generic stack can hold strings, integers or any other type without being rewritten.
go run, go vet: Go commands: `go run file.go` compiles and runs a file in one step, and `go vet file.go` checks it for likely mistakes without running it.
goroutine: Go's lightweight unit of running code. Each goroutine has its own call stack, which starts small and grows on demand up to a limit of 1 GB on 64-bit machines.
Graph: A set of vertices joined by edges, such as places joined by roads. Unlike a list or tree, it can contain loops.

H

Hash function: A function that turns any key into a whole number, which a map uses to pick a bucket. The same key always gives the same number within one run.
Hash map: A structure that stores key-value pairs and finds a value by its key without searching, in O(1) on average. Go's `map` is a hash map.
hash/maphash: A Go standard-library package that computes hash values for strings and bytes. A random seed makes the numbers differ between runs, but within one run the same input always gives the same hash.
Heap: A binary tree stored in a slice where every parent is no bigger than its children (a min-heap), so the smallest item is always at index 0. Push and pop are O(log n).
Heap sort: An O(n log n) sorting method based on a heap. Go's built-in sort falls back to it in bad cases.
Height: The number of levels on a tree's longest path from the root to a leaf. Binary search tree operations cost O(height).

I

Immutable: Cannot be changed after it is made. Go strings are immutable, so `code[0] = 'X'` does not compile and `+=` builds a whole new string.
In place: Changing a slice itself instead of making a new copy. `reverseInPlace` swaps items inside the original slice.
In-order traversal: Visiting a tree's left subtree, then the node, then the right subtree. In a binary search tree this gives the values in sorted order. Pre-order visits the node first.
Index map: A map built once from a slice, keyed by a field such as a product's SKU, so each later lookup is O(1) instead of an O(n) loop.
Insertion sort: Sorting by taking each item and sliding bigger ones right to drop it into place, like sorting a hand of cards. It is O(n²) but fast on nearly sorted data.
Integer division: Dividing two whole numbers with `/` drops the remainder (`7 / 2` is `3`), and `%` gives the remainder. It is used to find a slice's middle index with `len(items) / 2` and to turn minutes into hours.
Interface: A set of methods a type must have. `heap.Interface` needs five: `Len`, `Less`, `Swap`, `Push` and `Pop`.

L

Linear search: Checking items one by one from the start until you find the target. It is O(n), like `findOrder` for Priya's order IDs.
Linked list: A chain of nodes where each holds a value and a pointer to the next; the list keeps only the first node, the head. A doubly linked list also points back to the previous node.

M

Max-heap: A heap that pops the biggest item first. You make one by flipping `Less` to use `>`.
Memoization: Saving the answer to a call the first time so it is not worked out again. It speeds up recursive functions that repeat the same smaller problems.
Merge (sorted slices): Combining two already-sorted slices into one by repeatedly taking the smaller front item. It is the second half of merge sort.
Merge sort: A divide-and-conquer sort that splits the slice in half, sorts each half recursively and merges the sorted halves. It is O(n log n) and stable.
Method: A function attached to a type and called with a dot, such as `history.Push("x")`.

N

Neighbor: A vertex joined to another by an edge. In Alex's map, Burnside is a neighbor of the Roastery.
nil: Go's value for a pointer, map or slice that points at nothing. It marks the end of a linked list or an empty tree spot; using it as if it pointed to something causes a panic.
Node: One item in a linked list or tree, holding a value and links to other nodes.

O

O(V + E): The cost of BFS and DFS, where V is the number of vertices and E the number of edges: each place and each road is handled a fixed number of times.
Off-by-one error: A mistake of exactly one in an index, loop bound or comparison, such as `for low < high` instead of `<=` in binary search.

P

Panic: A crash Go raises for a serious runtime mistake, such as a nil pointer, an index out of range or popping an empty heap. The program stops and prints an error.
Pattern-defeating quicksort: The algorithm behind `slices.Sort` and `sort.Slice`. It is O(n log n) but not stable; `sort.SliceStable` and `SortStableFunc` are the stable options.
Pointer: A value that refers to another value in memory instead of holding a copy. `*Node` means a pointer to a Node, and a linked list's links are pointers.
Pointer receiver: The part of a method declaration before the name, such as `(s *Stack)`, saying which object the method works on. A pointer receiver lets the method change the original; a plain receiver changes only a copy.
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.
Push, pop, peek: Push adds an item to the top of a stack, pop removes and returns the top item, and peek looks at it 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. In Go it is a slice with `append` and `q[1:]`, or `container/list`.
Quicksort: A common O(n log n) sorting method that splits data around a pivot value. Go's built-in sort is a variant of it.

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 and a recursive case that shrinks the problem.
Root, leaf: The root is the top node of a tree, and a leaf is a node with no children.
Rune: Go's type for a single character, written in single quotes. Converting a string to `[]rune` gives one value per character, so accented letters reverse correctly.

S

Self-balancing tree: A search tree, such as an AVL or red-black tree, that rearranges its nodes as you insert to keep its height near log₂ n. Databases use relatives of these to index rows.
Set: A collection of unique items with fast membership tests. Go has no set type, so a set is a map with keys and no useful values, such as `map[int]struct{}` or `map[int]bool`.
Shifting: Moving items along a slice to open or close a gap. Inserting or deleting at the front shifts every other item, which is why it costs O(n).
Slice: Go's dynamic array: a window onto an array with a length and a capacity. A sub-slice like `items[a:b]` shares the same array rather than copying it.
slices package: A standard-library package of helper functions for slices, such as `Insert`, `Delete`, `Contains`, `Clone`, `Sort` and `BinarySearch`.
slices.Reverse: A function that reverses a slice in place. BFS uses it to turn a route built from goal to start into start to goal.
slices.SortFunc: Functions that sort a slice in place using a comparison function you supply. The `Stable` versions keep equal items in their original order; plain `SortFunc` may not.
sort.Search: Binary-search helpers in the `sort` package. `sort.Search(n, f)` returns the first index where `f` becomes true, and `SearchInts` returns the index where a value would go in a sorted slice.
Space: The memory an algorithm needs. For example, the duplicate check with a set uses O(n) extra space.
Stable sort: A sort that keeps equal items in their original order. Steam & Co stays ahead of Little Owl when both orders total 144.
Stack: A last-in, first-out pile where you add and remove at the top only, like cups. Useful for undo and bracket checking.
Stack overflow: A fatal error that ends the program when recursion goes so deep that the call stack passes its size limit, usually because there is no base case.
Steps: The unit used to measure code instead of seconds, such as one comparison per order checked. Counting steps lets you compare algorithms on any computer.
strconv.Atoi: A Go function that converts text such as "30" into the whole number 30.
strings.Builder: Tools for building text efficiently. `strings.Builder` keeps one growing buffer, and `strings.Join` glues pieces together once, avoiding the repeated copying of `+=`.
strings.Cut: A Go function that splits text at a separator, returning the part before, the part after and whether the separator was found. The planner uses it to split "09:30" at the colon.
Struct: A type that groups named fields, with methods attached to it. A value of a struct type is called an object or instance.
Subtree: A node together with everything below it, which is itself a tree.

T

time.Now and time.Since: Go's way to time code: `time.Now()` reads the clock, and `time.Since(start)` gives the elapsed time as a duration that prints with its unit, such as `2.9ms`.
Traversal: Visiting every node of a list or tree once, such as following `Next` links until `nil`.
Tree: Items stored in levels, like a family tree or folders in folders, with a root at the top and children below. Kettle & Crane's category list is a tree.
Two-index technique: Moving two indexes toward each other from both ends of a slice, as in reversing in place. It is O(n) time and O(1) extra space.
Type assertion: Syntax such as `.(Item)` that tells Go a value of type `any` actually holds a particular type. It is needed after `heap.Pop`, which returns `any`.

V

Vertex: A point in a graph, such as a place on Alex's delivery map.
Visited set: A `map[string]bool` of places a search has already reached, so none is handled twice. Without it, BFS would loop around a cycle forever.

W

Weighted graph: A graph whose edges carry numbers, such as driving minutes between places. The weights let algorithms compare routes by total cost instead of by number of stops.
Worst case: The most work an algorithm can need for an input of size n, such as a missing target in linear search. It is what we usually plan for because it is what hurts users.

Z

Zero value: The default value Go gives a variable or field that was not set: 0 for numbers, "" for strings, nil for slices, maps and pointers. A missing map key reads as the zero value.