Glossary

119 terms from Data Structures and Algorithms in Java, 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 from each vertex to the list of its neighbors. Alex's road map stores "Roastery" with the list of places one road away.
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): A cost that is occasionally slow but averages out to constant time over many operations. `ArrayList.add(x)` at the end is amortized O(1) because the rare move to a bigger block is spread over many adds.
array: Items stored side by side in memory in numbered slots, so any index is reached in one step. A plain Java array such as `int[]` has a fixed length.
ArrayDeque: A Java collection (say "deck") that adds and removes at both ends in O(1). It works as a queue with `offer` and `poll`, or as a stack with `push` and `pop`.
ArrayList: Java's dynamic array: a list stored in an array that grows when it fills. Reading by index is fast, but adding or removing at the front shifts every item.
Arrays.binarySearch: Java's built-in binary search on a sorted array (or a sorted list for `Collections`). It returns the index if found, or -(insertion point) - 1 if not.
Arrays.toString: A method that turns an array into readable text such as [48, 61, 55]. Printing an array directly shows only a memory code.
autoboxing: Java's automatic conversion between a primitive like `int` or `char` and its object form `Integer` or `Character`. It lets a `Set<Integer>` hold plain numbers.
average case: The cost you can expect in typical use, as opposed to the worst case. HashMap lookups are O(1) in the average case because collisions are rare.

B

balanced tree: A tree whose subtrees have similar heights, so its height is about log₂ n and lookups are O(log n). Self-balancing trees such as AVL and red-black trees rearrange nodes on insert to stay balanced.
base case: The case a recursive method answers directly without calling itself, such as an empty list adding up to 0. Without one, recursion never stops.
BFS (breadth-first search): A graph search that visits the start, then its neighbors, then their neighbors, ring by ring, using a queue and a visited set. It finds the route with the fewest stops.
Big-O notation: A way of describing how the number of steps a piece of code takes grows as the input size n grows. It drops constants and smaller terms, keeping only the shape of the growth.
Big-O shapes (O(1), O(log n), O(n), O(n log n), O(n²), O(V + E)): The common growth rates: O(1) constant (same steps at any size), O(log n) halving each step (about 20 for a million items), O(n) linear (twice the data, twice the work), O(n log n) a good sort, O(n²) usually a loop inside a loop, and O(V + E) for BFS and DFS on a graph with V vertices and E edges.
binary search: Finding an item in a sorted array by checking the middle and discarding the half that cannot hold the target, repeating until found. It takes O(log n) steps.
binary search tree (BST): A binary tree where, at every node, smaller values go in the left subtree and bigger values in the right. Insert and contains take one step per level.
binary tree: A tree in which each node has at most two children, called left and right.
bucket: One slot in the array a HashMap keeps inside. A key's hash picks the bucket where its pair is stored and later found.

C

call stack: The stack of method calls that have started but not finished. Java adds a note for each call and removes it on return; too many unfinished calls cause StackOverflowError.
cameFrom: A map used in BFS that records, for each place, the place it was first reached from. Walking back from the goal through it rebuilds the route.
capacity: The number of slots an ArrayList has reserved, including spare ones at the end. When they run out, it moves everything to a bigger block.
child, parent: In a tree, a node's children are the nodes directly below it, and it is their parent.
class: A blueprint for making objects, with their own fields and methods. Every Java program lives in a class.
Collections.reverse: A method that reverses a list in place. BFS uses it to turn a route built backward into one that reads from start to goal.
collision: When two different keys hash to the same bucket. Java then compares the keys in that bucket with `equals` to find the right one.
Comparable: An interface for types that can compare themselves, through `compareTo`, which returns negative, zero or positive. `<T extends Comparable<T>>` lets one method such as `mergeSort` work for any such type, and a `Comparable` record such as `Delivery` can go in a `PriorityQueue` without a separate comparator.
comparator: An object, often written as a lambda or method reference, that says which of two items goes first. You pass it to sort methods or to a `PriorityQueue`.
computeIfAbsent: A `Map` method that returns the value for a key, first creating and storing it from a lambda if the key is missing. It is handy for building an adjacency list, where a place's empty neighbor list is created the first time the place appears.
constructor: A special method in a class that runs when you create an object with `new`, setting up its fields.
CSV: A plain-text file with one record per line and values separated by commas. The planner reads `roads.csv` and `deliveries.csv`.

D

data structure: A way of arranging data so the jobs you need are easy and fast, such as an `ArrayList` or a `HashMap`.
Deque: The Java interface for a double-ended queue, which adds and removes at both ends. `ArrayDeque` implements it.
DFS (depth-first search): A graph search that goes as deep as possible down one road before backing up to try the next. It finds everything you can reach, often written recursively.
Dijkstra's algorithm: An algorithm for the fastest route in a weighted graph. It would fix the planner's problem that the fewest stops is not always the fewest minutes; it is taught in the next book.
directed, undirected: A directed edge goes one way only, like a one-way street. An undirected edge works in both directions, like Alex's roads.
divide and conquer: Splitting a problem into halves, solving each half, and combining the answers, as merge sort does.
doubly linked list: A linked list where each node also points back to the node before it. Java's `java.util.LinkedList` is one.
dynamic array: An array that grows when it fills up, by moving everything to a bigger block. Java's `ArrayList` is one.

E

edge: A connection between two vertices in a graph, such as a road between two places.
enqueue, dequeue: Adding an item at the back of a queue, and taking one off the front. In Java's `Deque` these are `offer` and `poll`.
equals: The method that checks whether two objects are equal in value. Keys must have `equals` and `hashCode` that agree, and strings and `Character` objects must be compared with `equals`, not `==` or `!=`.

F

field: A value stored inside an object, such as `node.next` or `items` in `ArrayStack`.
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.
Files and Path: Standard-library classes for reading files. `Files.readAllLines(path)` returns a file's lines as a list, and `throws IOException` passes a missing-file problem up to `main`.
final: A keyword meaning a variable always refers to the same value or object. `static final` makes a constant shared by the whole class, written in capitals.
Format codes (%02d, %-12s, %4d): Codes in `String.format` that control how a value prints: `%02d` prints a whole number at least 2 characters wide with a leading zero (9 becomes `09`), `%-12s` pads text on the right to 12 characters, and `%4d` right-aligns a number in 4 characters.

G

garbage collector: The part of Java that frees objects no variable refers to any more, so you never delete nodes yourself.
generic class: A class with a type placeholder such as `<T>` that the user picks, so one `ArrayStack<T>` or `Node<T>` can hold strings, characters or anything else. Type arguments must be classes, such as `Character` rather than `char`.
getOrDefault: A Map method that returns the value for a key, or a fallback you give if the key is missing. `counts.getOrDefault(name, 0) + 1` is the usual way to count items.
graph: A set of vertices joined by edges, like places joined by roads. It handles loops that a list or tree cannot.

H

hash function: A function that turns any key into a whole number, which a HashMap uses to pick a bucket. Java's version is `hashCode()`.
hash map: A structure that stores key-value pairs and finds a value by its key without searching, in O(1) on average. Java's version is `HashMap`; `HashSet` is the same idea with keys only.
hashable: Usable as a HashMap key or HashSet item because its `hashCode` and `equals` agree and its fields never change. Strings, numbers and records of those qualify; lists are risky.
hashCode: The Java method every object has that returns its hash number. Equal objects must return equal hash codes.
HashSet: A hash map with keys and no values, so `contains(x)` and `add(x)` are O(1) on average. It is used to track items already seen.
head: The first node of a linked list, the only one the list object keeps. Removing it is a special case.
heap: A binary tree with every level full except maybe the last, stored in an array, where each parent is no bigger than its children. The smallest item is at index 0, and add and remove take O(log n).
heap sort: A sorting algorithm that builds a heap from the items and repeatedly removes the largest or smallest one. It runs in O(n log n) time.
height: The number of levels on a tree's longest path from the root to a leaf. Balanced trees have height about log₂ n.

I

immutable: Cannot be changed after it is made, like a `String` or a record. A mutable object such as a list is a dangerous HashMap key.
in place: Changing an array or list itself rather than making a new copy, as `reverseInPlace` and `sort` do.
in-order traversal: A tree walk that visits the left subtree, then the node, then the right subtree. On a BST it gives the values in sorted order.
insertion point: The index where a value not in a sorted array would go to keep it sorted. `Arrays.binarySearch` returns -(insertion point) - 1 for missing values.
insertion sort: A sort that goes through the array and slides each item into place among the sorted items before it, like sorting a hand of cards. It is O(n²) but fast on nearly sorted data.
instance, object: One value made from a class, such as one `Node` or one `ArrayStack`.
integer division: Dividing two `int`s with `/` drops the remainder (`7 / 2` is `3`), and `%` gives the remainder. It is used to find the middle index of a list and to split a number of minutes into hours and minutes.
interface: A set of methods a class promises to provide, such as `List`, `Map` and `Deque`. You declare a variable with the interface type and create a class that implements it, like `ArrayList`, `HashMap` or `ArrayDeque`.

J

Javadoc: The official documentation for Java's classes, which states each method's cost and, for sorts, which algorithm is used and whether it is stable.
JDK: The Java Development Kit, the free download that includes the tools needed to compile and run Java programs. Recent versions can run a single source file directly with `java File.java`.
JIT warm-up: Java compiles frequently used code to faster machine code as the program runs, so early timings are slower and noisy. This is why measured times vary between runs.

L

lambda: A small function with no name, written where it is needed, such as `(a, b) -> Integer.compare(b.total(), a.total())`.
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, each holding a value and a link to the next, with the first one called the head. Adding at the front is O(1), but finding or indexing is O(n).
LinkedHashMap: A map that remembers the order items were inserted, unlike a plain HashMap.
List.of: Makes a list that cannot be changed. Sorting or adding to it throws `UnsupportedOperationException`, so copy it into a new `ArrayList` first.

M

main method: The method `public static void main(String[] args)` where Java starts running a program. `args` holds any words typed after the program name.
max-heap: A heap where the largest item comes out first. In Java you get one from `PriorityQueue` with `Comparator.reverseOrder()`.
memoization: Saving the answer to a call the first time so a recursive method does not solve the same smaller problem again. The next book covers it.
merge sort: A recursive sort that splits the list in half, sorts each half, and merges the sorted halves. It is O(n log n) and stable.
method reference: A short way to name an existing method, such as `Order::total`, which stands for the lambda `order -> order.total()`.

N

natural order: The way a type sorts itself by default, such as numbers smallest first and strings alphabetically. `list.sort(null)` and a `PriorityQueue` with no comparator use it.
neighbor: A vertex joined to another by an edge, such as a place one road away.
node: One item in a linked list or tree, holding a value and links to other nodes.
NoSuchElementException: The error Java throws when you take from an empty collection with a method that insists on an item, such as `pop` on our `ArrayStack` or `removeFirst()` on a deque. `poll` returns `null` instead.
null: The value meaning "nothing here", such as the last node's `next` or the result of `get` on a missing key. Using a `null` value as if it were an object throws `NullPointerException`.

O

off-by-one error: A mistake of exactly one in an index or comparison, such as `while (low < high)` instead of `<=` or `low = middle` instead of `middle + 1` in binary search.
offer, poll, peek: The queue methods: `offer` adds at the back, `poll` removes and returns the front, and `peek` looks at the front without removing. On an empty queue `poll` and `peek` return `null`.

P

pre-order traversal: A tree walk that visits a node before its subtrees, handy for printing a tree's shape.
priority queue: A queue that always serves the most urgent item first rather than the oldest, like the order that must ship soonest.
PriorityQueue: Java's priority queue, a min-heap in an array. `offer` and `poll` are O(log n), `peek` is O(1), and a `Comparator` chooses what counts as smaller.
push, pop, peek: The stack operations: add to the top, remove the top item, and look at the top without removing it. All are O(1).

Q

queue: A first-in, first-out line of items. Priya's support tickets are answered in the order they arrived.
quicksort: A sort that Java uses for arrays of primitives such as `int[]`. It is O(n log n) on typical data and not stable, which does not matter for plain numbers.

R

record: A short class form that holds named components and gets `equals`, `hashCode` and `toString` for free. Because it cannot change, a record is a safe HashMap key, such as `CityProduct` or `Road`.
recursion: A method solving a problem by calling itself on a smaller piece of the same problem, with a base case that stops it.
red-black tree: Kinds of self-balancing binary search tree that rearrange nodes on insert to keep the height near log₂ n. Java's `TreeMap` is a red-black tree.
root, leaf: The root is the top node of a tree, and a leaf is a node with no children.

S

shifting: Moving items along a list to open or close a gap. Adding or removing at the front of an ArrayList shifts every other item, costing O(n).
space cost: The memory code uses, which Big-O describes too. `hasDuplicate` with an array is O(1) extra space, while a copy of the array is O(n).
stable sort: A sort that keeps equal items in their original order, such as Steam & Co staying before Little Owl when both total 144. Object sorts in Java are stable.
stack: A last-in, first-out pile where you add and remove at the top only. It suits undo and bracket checking.
StackOverflowError: The error Java throws when the call stack gets too tall, caused by recursion with no base case or by very deep recursion.
static: A keyword marking a method or field as belonging to the class itself, so it can be called without creating an object.
step: The unit Big-O counts instead of seconds, such as one comparison per order checked. Counting steps gives the same answer on any computer.
StringBuilder: A text buffer you can change. Appending is O(1) on average, so it is the fast way to build long text instead of `+=` on an immutable String.
subList: A view of part of a list that copies nothing (O(1)), so changing it changes the original. Wrap it in `new ArrayList<>(...)` for an independent copy.
subtree: A node together with everything below it, which is itself a tree.
System.nanoTime: A method that returns a reading from a precise clock in nanoseconds. Subtracting a reading taken before from one taken after gives how long code took.

T

thenComparing: Comparator helpers: `thenComparing` adds a tie-breaker used only when the first comparison is equal, `reversed()` flips a comparator, and `Comparator.reverseOrder()` gives the opposite of natural order.
TimSort: The algorithm behind `List.sort` and `Arrays.sort` on objects: a mix of merge sort and insertion sort that is stable and O(n log n).
top-k with a small heap: Finding the k biggest items by keeping a min-heap of only k items: offer each item and `poll` the smallest whenever the heap grows to k + 1. It costs O(n log k), which beats sorting everything when k is small.
traversal: Visiting every node of a linked list or tree in turn. For a list, start at the head and follow `next` until `null`.
TreeMap: A Java map that keeps its keys sorted, built on a red-black tree, so its operations are O(log n).

U

unbalanced tree: A tree whose shape has become lopsided, such as a chain from inserting sorted values, with height n and O(n) lookups.

V

vertex: A point in a graph, such as a place on Alex's map. Vertices are joined by edges.
visited set: The set of places a search has already reached, so none is handled twice and loops do not run forever.

W

weighted graph: A graph whose edges carry numbers, such as minutes of driving between places.
worst case: The most work an algorithm can need for an input of a given size, such as linear search when the target is last or missing. It is what we usually plan for.