Data Structures Dictionary

Terms used in the course, each with a short definition and the chapter where it is explained. The chapter column links to that chapter's slides.

TermDefinitionChapter
abstract data type (ADT)A specification of a data type by its values and operations only, saying what the operations do but not how they are implemented.1 · Introduction
accumulatorA parameter that carries the partial result down the recursive calls, so that a tail-recursive method has nothing left to do after its call returns.4 · Recursion
adaptable priority queueA priority queue that can also remove an arbitrary entry or change its key, usually by keeping location-aware entries.11 · Priority Queues and Heaps
adjacency listA graph representation that stores, for each vertex, a list of its neighbors; it uses O(n + m) space and suits sparse graphs.14 · Graphs
adjacency matrixA graph representation as an n × n table whose cell [u][v] records whether, or with what weight, an edge joins u and v.14 · Graphs
adjacentSaid of two vertices joined by an edge; each is then a neighbor of the other.14 · Graphs
agingRaising the priority of a waiting item step by step over time, so that low-priority items are not starved by newer high-priority ones.11 · Priority Queues and Heaps
algorithmA finite, unambiguous sequence of steps that solves a problem, taking an input and producing the correct output in a finite time.1 · Introduction
algorithm analysisThe study of how much time and memory an algorithm needs as a function of its input size, used to compare and predict performance.2 · Algorithm Analysis
aliasingReaching one object through two or more references, so that a change made through one reference is seen through the others.1 · Introduction
amortized analysisAnalysis of the average cost per operation over a worst-case sequence of operations, so that rare expensive steps are spread across many cheap ones.6 · The List ADT and Java Collections
ancestorA node on the path from a given node up to the root: its parent, its parent's parent, and so on.9 · Trees
arrayA fixed-size sequence of elements of one type stored side by side in memory, each reached by an integer index in constant time.3 · Arrays
array covarianceJava's rule that an array of a subtype counts as an array of its supertype, so a wrong store is caught only at run time with ArrayStoreException.3 · Arrays
ASCII (American Standard Code for Information Interchange)A 7-bit character code assigning the numbers 0 to 127 to English letters, digits, punctuation and control characters.1 · Introduction
asymptoticDescribing how a function behaves as its input grows without bound, ignoring constant factors and lower-order terms.2 · Algorithm Analysis
autoboxingJava's automatic conversion of a primitive value into an object of its wrapper class, for example int to Integer.6 · The List ADT and Java Collections
average caseThe expected running time of an algorithm over all inputs of a given size, under an assumed probability distribution of inputs.2 · Algorithm Analysis
AVL treeA self-balancing binary search tree in which the heights of every node's two subtrees differ by at most 1, restored by rotations.10 · Search Trees
B+ treeA B-tree variant that keeps all records in the leaves, linked in key order, while internal nodes hold only keys for routing.10 · Search Trees
B-treeA balanced multiway search tree whose nodes hold many keys and children, keeping all leaves at one depth; used for disks and databases.10 · Search Trees
back edgeIn a depth-first search, an edge that leads from a vertex to one of its ancestors still in progress; its presence reveals a cycle.14 · Graphs
backtrackingA recursive search that builds a solution one choice at a time and undoes the last choice as soon as it cannot lead to a solution.4 · Recursion
balance factorFor a binary tree node, the height of its left subtree minus the height of its right subtree, an empty subtree counting as -1.10 · Search Trees
balanced parenthesesThe stack problem of checking that every opening bracket in an expression is closed by a matching bracket in the right order.7 · Stacks
base caseThe input on which a recursive method answers directly without calling itself, which stops the recursion.4 · Recursion
best caseThe input of a given size on which an algorithm does the least work, and the running time it takes there.2 · Algorithm Analysis
Big ONotation for an upper bound: f(n) = O(g(n)) if f(n) ≤ c · g(n) for some constant c > 0 and all n ≥ n0.2 · Algorithm Analysis
Big OmegaNotation for a lower bound: f(n) = Ω(g(n)) if f(n) ≥ c · g(n) for some constant c > 0 and all n ≥ n0.2 · Algorithm Analysis
Big ThetaNotation for a tight bound: f(n) = Θ(g(n)) if f is both O(g(n)) and Ω(g(n)), so f and g grow at the same rate.2 · Algorithm Analysis
big-O notationThe O(·) notation used to state how an operation's cost grows with input size, such as O(1) access or O(n) insertion in an array.3 · Arrays
binary heapA complete binary tree with the heap-order property, usually stored in an array, giving O(log n) insertion and removal of the top element.11 · Priority Queues and Heaps
binary recursionRecursion in which each call makes two recursive calls, as in the naive Fibonacci method or merge sort.4 · Recursion
binary searchA search in a sorted array that compares the target with the middle element and discards half of the range at each step, in O(log n).2 · Algorithm Analysis
binary search tree (BST)A binary tree in which every key in a node's left subtree is smaller than the node's key and every key in its right subtree larger.10 · Search Trees
binary treeA tree in which every node has at most two children, distinguished as the left child and the right child.9 · Trees
binomial heapA priority queue stored as a forest of binomial trees, which supports merging two heaps in O(log n).11 · Priority Queues and Heaps
bipartite graphA graph whose vertices can be split into two groups so that every edge joins a vertex of one group to a vertex of the other.14 · Graphs
bit (binary digit)The smallest unit of digital data, holding one of two values, 0 or 1.1 · Introduction
bit maskAn integer whose set bits select particular positions, used with bitwise AND, OR and NOT to test, set or clear those bits.13 · Sets and Disjoint Sets
bit vectorA set representation for a small universe 0 to U - 1 that stores U bits, bit i being 1 exactly when i is in the set.13 · Sets and Disjoint Sets
black heightIn a red-black tree, the number of black nodes on every path from a node down to a NIL leaf, which is the same for all such paths.10 · Search Trees
bottom-up heap constructionBuilding a heap from n items by placing them in an array and running down-heap on each internal node from the last to the root, in O(n).11 · Priority Queues and Heaps
bounded stackAn array-based stack whose capacity is fixed when it is created, so a push onto a full stack causes overflow.7 · Stacks
breadth-first search (BFS)A graph traversal that visits vertices in order of their distance in edges from the start, using a queue.14 · Graphs
brute forceSolving a problem by directly trying every possibility, simple to write but often slow, such as rescanning the array for each element.7 · Stacks
BST propertyThe ordering rule of a binary search tree: keys in the left subtree are smaller and keys in the right subtree larger than the node's key.10 · Search Trees
bubble sortA sorting algorithm that repeatedly sweeps the array swapping adjacent elements that are out of order, so the largest moves to the end each pass.3 · Arrays
bucketOne cell of a hash table's array; with separate chaining, a bucket holds the list of all entries whose keys hash to that index.12 · Maps and Hash Tables
bufferA memory area, usually a queue, where data waits between a producer and a consumer that run at different speeds.8 · Queues and Deques
byteA group of eight bits, the smallest addressable unit of memory, able to hold 256 different values.1 · Introduction
cacheA small, fast memory near the processor that holds recently used blocks of main memory, which makes access to nearby addresses cheap.3 · Arrays
cache missAn access to data not present in the cache, forcing a slow fetch from main memory; scattered linked nodes cause many of them.6 · The List ADT and Java Collections
call stackThe stack of frames the runtime keeps for active method calls; a call pushes a frame and a return pops it.7 · Stacks
call treeA tree diagram of a recursive computation in which each node is one call and its children are the calls it makes.4 · Recursion
capacityThe number of elements an array or array-based structure can hold before it must grow, as opposed to the number it currently holds.3 · Arrays
chainIn separate chaining, the linked list of entries stored in one bucket of a hash table.12 · Maps and Hash Tables
character encodingA rule that maps characters to numbers and those numbers to bytes, such as ASCII or UTF-8.1 · Introduction
childA node directly below another node in a tree, joined to it by an edge.9 · Trees
circular queueAn array-based queue whose front and rear indices wrap around to 0 after the last slot, using arithmetic modulo the capacity.8 · Queues and Deques
circularly linked listA linked list whose last node points back to the first instead of to null, so traversal can continue around the cycle.5 · Linked Lists
client codeCode that uses a data structure only through its public interface, without depending on how it is implemented.1 · Introduction
code pointThe number that Unicode assigns to a character, independent of how it is stored in bytes.1 · Introduction
collectionAn object that groups a number of elements into a single unit; in Java, the root interface of most container types.6 · The List ADT and Java Collections
collisionThe situation in which two different keys are mapped by the hash function to the same index of a hash table.12 · Maps and Hash Tables
comparatorAn object that defines an ordering on elements by comparing two of them, letting a sort or ordered structure use an order other than the natural one.6 · The List ADT and Java Collections
compile timeThe phase when source code is translated by the compiler, during which errors such as type mismatches are detected before the program runs.1 · Introduction
complete binary treeA binary tree in which every level except possibly the last is full and the last level is filled from the left with no gaps.9 · Trees
complete graphA simple graph in which every pair of distinct vertices is joined by an edge; with n vertices it has n(n - 1)/2 edges.14 · Graphs
complexityThe amount of a resource, usually time or memory, that an algorithm uses, expressed as a function of the input size.2 · Algorithm Analysis
compression functionThe second step of a hash function, which maps an arbitrary integer hash code to an index in the range 0 to N - 1.12 · Maps and Hash Tables
connectedSaid of an undirected graph in which there is a path between every pair of vertices.14 · Graphs
connected componentA maximal set of vertices of an undirected graph in which every pair is joined by a path.14 · Graphs
contiguousStored in adjacent memory locations with no gaps, as the elements of an array are.3 · Arrays
contract (equals/hashCode)Java's rule that objects equal under equals must return the same hashCode, which hash-based collections rely on to find keys.12 · Maps and Hash Tables
correctnessThe property of an algorithm that it produces the right output for every valid input and terminates.2 · Algorithm Analysis
covarianceA typing relation in which a container of a subtype is treated as a container of its supertype, as Java does for arrays.3 · Arrays
covariantHaving covariance; Java arrays are covariant because String[] is a subtype of Object[], while generic lists are not.3 · Arrays
cursorThe conceptual position of an iterator, which sits between elements; each call to next() moves it past one element.6 · The List ADT and Java Collections
cycleIn a graph, a path of at least one edge that starts and ends at the same vertex; distinct from a loop in a program.14 · Graphs
cycle detectionDetermining whether following next references in a linked list ever returns to an earlier node instead of reaching null.5 · Linked Lists
d-ary heapA heap stored as a complete tree whose nodes have up to d children, giving height log_d n and faster insertion than a binary heap.11 · Priority Queues and Heaps
data structureA way of organizing data in memory together with the operations on it, chosen so that the needed operations are efficient.1 · Introduction
data typeA set of values together with the operations allowed on them, such as int with its arithmetic operations.1 · Introduction
decision treeThe call tree of a backtracking search, in which each level makes one choice and each root-to-leaf path is one sequence of choices.4 · Recursion
deep copyA copy that duplicates an object and, recursively, the objects it refers to, so the copy shares no mutable parts with the original.3 · Arrays
degenerate treeA search tree in which every node has only one child, so it behaves like a linked list with height n - 1.10 · Search Trees
degreeIn a tree, the number of children of a node; the degree of a tree is the largest degree of its nodes.9 · Trees
dense graphA graph with close to the maximum possible number of edges, on the order of n squared.14 · Graphs
depthThe number of edges on the path from the root down to a node; the root has depth 0.9 · Trees
depth-first search (DFS)A graph traversal that follows one path as far as possible before backing up, implemented with recursion or an explicit stack.14 · Graphs
deque (double-ended queue)A linear structure that allows insertion and removal at both the front and the rear.8 · Queues and Deques
dequeueThe queue operation that removes and returns the element at the front.8 · Queues and Deques
descendantA node in the subtree below a given node: its children, their children, and so on.9 · Trees
deterministicAlways giving the same output for the same input; a hash function must be deterministic so a key is always sought where it was stored.12 · Maps and Hash Tables
differenceThe set of elements that belong to the first set but not to the second, written A - B.13 · Sets and Disjoint Sets
digital dataInformation such as text, numbers, images and sound represented as sequences of bits.1 · Introduction
Dijkstra's algorithmA single-source shortest-path algorithm for graphs with non-negative edge weights that repeatedly settles the unsettled vertex of smallest tentative distance.14 · Graphs
direct addressingStoring each key at the array index equal to the key itself, which gives O(1) operations but needs an array as large as the key range.12 · Maps and Hash Tables
directed acyclic graph (DAG)A directed graph with no directed cycle; exactly the graphs that have a topological order.14 · Graphs
directed cycleA directed path of at least one edge that returns to its starting vertex while following edge directions.14 · Graphs
directed graph (digraph)A graph whose edges have a direction, each going from one vertex to another.14 · Graphs
disjoint sets (union-find)A structure that maintains a partition of elements into non-overlapping sets, supporting find (which set?) and union (merge two sets).13 · Sets and Disjoint Sets
double hashingAn open-addressing method whose probe step is given by a second hash function, so different keys follow different probe sequences.12 · Maps and Hash Tables
doubling experimentAn empirical test that measures running time as the input size doubles; the ratio of successive times reveals the growth rate.2 · Algorithm Analysis
doubly linked listA linked list in which each node holds references to both the next and the previous node.5 · Linked Lists
down-heapRestoring heap order by moving an element down, swapping it with its larger (or smaller) child until neither child should be above it.11 · Priority Queues and Heaps
dynamic arrayAn array-based list that grows by allocating a larger array, usually twice the size, and copying the elements when it becomes full.3 · Arrays
dynamic size stackA stack that grows as needed, either by resizing its array or by using linked nodes, so it never overflows.7 · Stacks
edgeA connection between two nodes of a tree or two vertices of a graph.9 · Trees
edge listA graph representation that stores all edges in one list, each as a pair of endpoints, possibly with a weight.14 · Graphs
elementOne item stored in a data structure, such as one value in an array.3 · Arrays
empirical analysisMeasuring an algorithm's running time by running it on inputs of various sizes, as opposed to analyzing it mathematically.2 · Algorithm Analysis
enqueueThe queue operation that adds an element at the rear.8 · Queues and Deques
Euler tourA walk around a tree that passes each edge twice and meets each node from the left, below and the right, unifying preorder, inorder and postorder.9 · Trees
exceptionAn object signaling an error or unusual condition, thrown by code that detects it and caught by code that can handle it.7 · Stacks
expression treeA binary tree representing an arithmetic expression, with operators in internal nodes and operands in leaves.9 · Trees
external nodeA node with no children; another name for a leaf.9 · Trees
fail-fastDescribing an iterator that throws an exception as soon as it detects that its collection was structurally modified from outside during traversal.6 · The List ADT and Java Collections
Fibonacci heapA priority queue built as a forest of trees, with O(1) amortized insertion and key decrease, used in the fastest versions of Dijkstra's and Prim's algorithms.11 · Priority Queues and Heaps
FIFOFirst in, first out: the order in which a queue removes elements, oldest first.8 · Queues and Deques
first-in, last-out (FILO)Another name for the stack order: the first element pushed is the last one popped.7 · Stacks
fixed size stackA stack whose array capacity is set at creation and never changes, so pushing onto a full stack is an error.7 · Stacks
floating pointA representation of real numbers with a sign, a significand and an exponent, as in Java's float and double; most decimals are stored approximately.1 · Introduction
Floyd's cycle detection algorithmMoving a slow pointer one step and a fast pointer two steps through a list; they meet exactly when the list has a cycle.5 · Linked Lists
forestA collection of disjoint trees.9 · Trees
frontThe end of a queue from which elements are removed.8 · Queues and Deques
full binary treeA binary tree in which every node has either zero or two children.9 · Trees
garbage collectorThe part of the Java runtime that automatically reclaims the memory of objects that no reference can reach.1 · Introduction
genericWritten with type parameters so that one class or method works for many element types while the compiler still checks types.1 · Introduction
genericsThe Java feature that lets classes, interfaces and methods take type parameters, as in List<String>, giving type safety without casts.1 · Introduction
graphA set of vertices together with a set of edges, each edge joining a pair of vertices.14 · Graphs
half-open intervalA range [start, end) that includes start and excludes end, the convention of Java methods such as subList; its length is end - start.6 · The List ADT and Java Collections
hash codeAn integer computed from a key, the first step of a hash function before compression to a table index.12 · Maps and Hash Tables
hash functionA function that maps a key to an index of a hash table, ideally fast, deterministic and spreading keys uniformly.12 · Maps and Hash Tables
hash setA set implemented with a hash table, giving expected O(1) add, remove and membership test, with no ordering of elements.13 · Sets and Disjoint Sets
hash tableAn array of buckets in which a hash function computes where each key is stored, giving expected O(1) insertion, search and deletion.12 · Maps and Hash Tables
headThe first node of a linked list, through which the rest of the list is reached.5 · Linked Lists
heapA tree-based structure satisfying the heap-order property, used to implement priority queues.11 · Priority Queues and Heaps
heap memoryThe region of memory where Java allocates objects created with new; they stay there until the garbage collector reclaims them.3 · Arrays
heap sortA sorting algorithm that builds a heap from the array and repeatedly moves the top element to the end, in O(n log n) time and in place.11 · Priority Queues and Heaps
heap-order propertyThe rule that every node's key is at least (max-heap) or at most (min-heap) its children's keys, so the root holds the extreme key.11 · Priority Queues and Heaps
heightThe number of edges on the longest path from a node down to a leaf; the height of a tree is the height of its root.9 · Trees
home slotThe first slot a key tries in an open-addressing hash table, given directly by its hash value h(k).12 · Maps and Hash Tables
Horner's methodEvaluating a polynomial by repeatedly multiplying the running total by x and adding the next coefficient, used to compute string hash codes.12 · Maps and Hash Tables
immutabilityThe property of an object whose state cannot change after it is created.1 · Introduction
immutableUnable to be changed after creation; an immutable object such as a String can be shared safely without copying.6 · The List ADT and Java Collections
implementationThe concrete code and data representation that realize an interface or abstract data type.1 · Introduction
in-degreeIn a directed graph, the number of edges coming into a vertex.14 · Graphs
in-placeDescribing an algorithm that rearranges data within the input array, using only a constant amount of extra memory.3 · Arrays
incidentSaid of an edge and a vertex when the vertex is one of the edge's endpoints.14 · Graphs
indexThe integer position of an element in an array or list; Java indices start at 0.3 · Arrays
infixExpression notation that writes each binary operator between its operands, as in 3 + 4.7 · Stacks
initializerA brace-enclosed list of values that creates and fills an array in its declaration, as in int[] a = {1, 2, 3}.3 · Arrays
inorderA binary tree traversal that visits the left subtree, then the node, then the right subtree; on a BST it gives keys in sorted order.9 · Trees
insertion sortA sorting algorithm that takes elements one by one and inserts each into its place among the already sorted elements to its left.3 · Arrays
interfaceA declaration of the operations a type provides, without their implementation; in Java, a type that classes implement.1 · Introduction
internal nodeA tree node that has at least one child.9 · Trees
intersectionThe set of elements that belong to both of two sets, written A ∩ B.13 · Sets and Disjoint Sets
invariantA condition that remains true at specified points throughout the execution of an algorithm or the life of a data structure.2 · Algorithm Analysis
inverse Ackermann functionAn extremely slowly growing function, at most 4 for any practical input, that bounds the amortized cost of union-find operations.13 · Sets and Disjoint Sets
inversionA pair of positions (i, j) in an array with i < j but a[i] > a[j]; insertion sort performs one shift per inversion.3 · Arrays
isolated vertexA vertex with no incident edges, that is, of degree 0.14 · Graphs
iteratorAn object that steps through the elements of a collection one at a time with hasNext() and next(), hiding how they are stored.6 · The List ADT and Java Collections
jagged arrayA two-dimensional array whose rows have different lengths, possible in Java because each row is a separate array.3 · Arrays
Java Collections FrameworkJava's standard library of collection interfaces such as List, Set and Map, their implementations, and algorithms that operate on them.6 · The List ADT and Java Collections
Kahn's algorithmA topological sort that repeatedly outputs a vertex of in-degree 0 and removes its outgoing edges, using a queue.14 · Graphs
keyThe value used to order, find or identify an entry, such as the priority in a priority queue or the lookup value in a map.11 · Priority Queues and Heaps
key-value pairAn entry of a map, associating a unique key with its value.12 · Maps and Hash Tables
Kruskal's algorithmA minimum spanning tree algorithm that considers edges in increasing weight order and adds each one that does not form a cycle, using union-find.14 · Graphs
lambda expressionA short anonymous function written inline, as in (a, b) -> a - b, often passed as a comparator.6 · The List ADT and Java Collections
leafA tree node with no children.9 · Trees
levelThe set of all tree nodes at the same depth; level d contains the nodes at depth d.9 · Trees
level-orderA tree traversal that visits nodes level by level from the root, left to right within a level, using a queue.9 · Trees
LIFOLast in, first out: the order in which a stack removes elements, newest first.7 · Stacks
linear probingAn open-addressing method that, on a collision, tries the next slots one by one, wrapping around at the end of the table.12 · Maps and Hash Tables
linear recursionRecursion in which each call makes at most one recursive call.4 · Recursion
linear searchSearching by examining the elements one by one from the start until the target is found or the elements run out, in O(n).3 · Arrays
linked listA sequence of nodes, each holding an element and a reference to the next node, so it can grow and shrink without shifting elements.5 · Linked Lists
listAn ordered sequence of elements in which each element has a position and duplicates are allowed.6 · The List ADT and Java Collections
listenerAn object registered to be notified when an event occurs, such as a button click; listener lists are traversed often but changed rarely.6 · The List ADT and Java Collections
load factorThe ratio n/N of the number of stored entries to the number of buckets in a hash table, which determines the expected search cost.12 · Maps and Hash Tables
location-aware entryA priority queue entry that stores its current index in the heap array, so it can be found in O(1) for removal or key change.11 · Priority Queues and Heaps
loiteringKeeping a reference to an object that is no longer needed, such as in a popped stack cell, which stops the garbage collector from reclaiming it.7 · Stacks
loopA program construct such as for or while that repeats a block of statements; distinct from a cycle in a graph.2 · Algorithm Analysis
loop invariantA condition true before and after every iteration of a loop, used to prove that the loop computes the right result.2 · Algorithm Analysis
lower boundA function that another function eventually stays at or above, up to a constant factor; stated with Big Omega.2 · Algorithm Analysis
MAD method (Multiply-Add-and-Divide)A compression function h(k) = ((a · k + b) mod p) mod N, with p a prime larger than N and a, b chosen at random.12 · Maps and Hash Tables
mapAn abstract data type that stores key-value pairs with unique keys and looks up a value by its key.12 · Maps and Hash Tables
mathematical inductionA proof technique that shows a statement for a base case and then shows that its truth for n implies its truth for n + 1.4 · Recursion
matrixA rectangular table of values arranged in rows and columns, stored in Java as a two-dimensional array.3 · Arrays
max-heapA heap in which every node's key is at least as large as its children's, so the largest key is at the root.11 · Priority Queues and Heaps
medianThe middle value of a data set when it is sorted, or the average of the two middle values when their number is even.3 · Arrays
membership testThe set operation that asks whether a given element belongs to the set.13 · Sets and Disjoint Sets
memoizationStoring the results of a function's calls so that a repeated call with the same arguments returns the stored result instead of recomputing it.4 · Recursion
memory leakMemory that remains allocated after the program no longer needs it; in Java it happens when unused objects are still referenced.3 · Arrays
merge sortA divide-and-conquer sorting algorithm that sorts the two halves of an array recursively and merges them, in O(n log n) time.3 · Arrays
min-heapA heap in which every node's key is at most its children's keys, so the smallest key is at the root.11 · Priority Queues and Heaps
minimum spanning tree (MST)A spanning tree of a connected weighted graph whose total edge weight is as small as possible.14 · Graphs
modeThe value that occurs most often in a data set.3 · Arrays
monotonic stackA stack whose contents stay sorted, maintained by popping every item that would break the order before pushing a new one.7 · Stacks
multidimensional arrayAn array indexed by two or more indices; in Java, an array whose elements are themselves arrays.3 · Arrays
multimapA map in which one key may be associated with several values.13 · Sets and Disjoint Sets
multiple recursionRecursion in which a call may make more than two recursive calls, as when exploring the choices of a backtracking search.4 · Recursion
multiplicityThe number of times an element occurs in a multiset.13 · Sets and Disjoint Sets
multisetA collection like a set in which an element may occur more than once and order does not matter; also called a bag.13 · Sets and Disjoint Sets
mutableAble to be changed after creation.6 · The List ADT and Java Collections
next greater elementFor each item of a sequence, the first later item that is larger than it; found in O(n) with a monotonic stack.7 · Stacks
nodeA basic unit of a linked list, tree or graph, holding an element and links to other nodes; in a graph also called a vertex.5 · Linked Lists
non-primitiveBuilt from primitive types and other structures, such as arrays, lists, trees and graphs, rather than holding a single simple value.1 · Introduction
nullThe special reference value that refers to no object, used for example to mark the end of a linked list.5 · Linked Lists
off-by-one errorA bug in which a loop or index goes one step too far or stops one step too early, such as using <= instead of <.3 · Arrays
open addressingA collision-resolution method that stores every entry in the table array itself, probing other slots when the home slot is taken.12 · Maps and Hash Tables
operandA value on which an operator acts, such as 3 and 4 in 3 + 4.7 · Stacks
operatorA symbol for an operation on operands, such as +, -, * or /.7 · Stacks
out-degreeIn a directed graph, the number of edges leaving a vertex.14 · Graphs
overflowThe error of pushing an element onto a full stack of fixed capacity.7 · Stacks
overloadTo define several methods with the same name but different parameter lists in one class.6 · The List ADT and Java Collections
parentThe node directly above a given node in a tree; every node except the root has exactly one.9 · Trees
pass by valueJava's parameter passing, in which a method receives a copy of each argument; for a reference, the copied address still points to the same object.1 · Introduction
pathA sequence of nodes or vertices in which each consecutive pair is joined by an edge; its length is the number of edges.9 · Trees
path compressionA union-find optimization that, during find, makes every node on the path point directly to the root, flattening the tree.13 · Sets and Disjoint Sets
perfect binary treeA binary tree in which every internal node has two children and all leaves are at the same depth.9 · Trees
perfect hashA hash function that maps every possible key to a different index, so no collisions occur; possible only when the keys are known in advance.12 · Maps and Hash Tables
persistent data structureA structure in which every update makes a new version while old versions remain usable, sharing the unchanged parts.6 · The List ADT and Java Collections
pointerA variable that holds the memory address of another value; Java references play this role in linked structures.5 · Linked Lists
popThe stack operation that removes and returns the top element.7 · Stacks
positionAn object representing an element's place in a positional list, which stays valid through other insertions and removals until that element is removed.6 · The List ADT and Java Collections
positional listA list ADT whose operations refer to positions rather than indices, allowing O(1) insertion and removal at a known position.6 · The List ADT and Java Collections
postfixExpression notation that writes each operator after its operands, as in 3 4 +, evaluated with a stack and needing no parentheses.7 · Stacks
postorderA tree traversal that visits a node's subtrees first and the node last.9 · Trees
predecessorThe element that comes immediately before a given element in order; in a BST, the node with the next smaller key.10 · Search Trees
prefixExpression notation that writes each operator before its operands, as in + 3 4.7 · Stacks
prefix averagesComputing, for each index i, the average of the first i + 1 elements; a running sum does it in O(n) instead of O(n squared).2 · Algorithm Analysis
preorderA tree traversal that visits a node first and then its subtrees.9 · Trees
Prim's algorithmA minimum spanning tree algorithm that grows one tree from a start vertex, each time adding the cheapest edge leaving the tree.14 · Graphs
primary clusteringLinear probing's tendency to form long runs of occupied slots that grow faster the longer they get, slowing searches.12 · Maps and Hash Tables
primitive operationA basic step, such as an assignment, comparison or arithmetic operation, counted as one unit of time when analyzing an algorithm.2 · Algorithm Analysis
primitive typeOne of Java's built-in non-object types, such as int, double, char and boolean, whose variables hold the value itself.1 · Introduction
priority queueAn abstract data type that stores entries with keys and always removes the entry with the smallest (or largest) key first.11 · Priority Queues and Heaps
probe sequenceThe order of slots that a key tries in an open-addressing hash table, starting at its home slot.12 · Maps and Hash Tables
probingChecking a slot of an open-addressing hash table while inserting or searching for a key.12 · Maps and Hash Tables
pruningSkipping parts of a search space that cannot contain an answer, such as BST subtrees outside a query range.10 · Search Trees
pushThe stack operation that adds an element on top.7 · Stacks
quadratic probingAn open-addressing method that, on a collision, tries slots 1, 4, 9, 16, ... positions beyond the home slot.12 · Maps and Hash Tables
queueA linear structure that adds elements at the rear and removes them from the front, in first-in, first-out order.8 · Queues and Deques
quick sortA divide-and-conquer sorting algorithm that partitions the array around a pivot and sorts the two parts recursively, O(n log n) on average.3 · Arrays
Quick-FindA union-find representation that stores each element's set name in an array, so find is O(1) but union must rename a set in O(n).13 · Sets and Disjoint Sets
race conditionA bug in which the result depends on the unpredictable timing of threads, such as two threads both acting on a check that is no longer true.6 · The List ADT and Java Collections
random accessReaching any element directly by its index in constant time, as in an array.3 · Arrays
range queryA query that reports all keys between a lower and an upper bound; in a BST it takes O(h + s) with pruning.10 · Search Trees
rankIn union-find, an integer stored at each root that bounds its tree's height and decides which root is attached to which.13 · Sets and Disjoint Sets
rearThe end of a queue at which elements are added.8 · Queues and Deques
recurrence relationAn equation that defines a function in terms of its values on smaller inputs, such as T(n) = 2T(n/2) + n.4 · Recursion
recursionA technique in which a method solves a problem by calling itself on smaller instances of the same problem.4 · Recursion
recursive stepThe part of a recursive method that reduces the problem to smaller instances and calls itself on them.4 · Recursion
red-black treeA self-balancing BST whose nodes are colored red or black under rules that keep every path's length within a factor of two.10 · Search Trees
referenceA value that refers to an object in memory; Java variables of non-primitive type hold references, not the objects themselves.1 · Introduction
relaxationUpdating a vertex's tentative distance when a path through a neighboring vertex is found to be shorter.14 · Graphs
resizing (rehashing)Moving all entries of a hash table into a larger array, recomputing each index, when the load factor exceeds a threshold.12 · Maps and Hash Tables
return addressThe point in the caller where execution resumes when a method call finishes, stored in the call's stack frame.4 · Recursion
reverse Polish notation (RPN)Another name for postfix notation, in which operators follow their operands.7 · Stacks
ring bufferAnother name for a circular queue: a fixed array whose indices wrap around from the last slot to the first.8 · Queues and Deques
robustnessThe ability of a program to handle unexpected or invalid inputs gracefully instead of failing.2 · Algorithm Analysis
rootThe single node at the top of a tree, the only node without a parent.9 · Trees
rotationA local restructuring of a binary search tree that changes a parent-child relationship while preserving the BST property, used to rebalance.10 · Search Trees
round robinA scheduling method that gives each process in a queue a fixed time slice in turn, returning unfinished ones to the rear.8 · Queues and Deques
run timeThe phase when a program executes, during which errors such as an out-of-bounds index are detected.1 · Introduction
schedulerThe part of an operating system that decides which waiting process or thread runs next.8 · Queues and Deques
search treeA tree whose keys are arranged so that a search can follow a single path from the root, discarding subtrees at each step.10 · Search Trees
secondary clusteringThe tendency, in quadratic probing, of keys with the same home slot to follow the same probe sequence.12 · Maps and Hash Tables
selection sortA sorting algorithm that repeatedly selects the smallest remaining element and swaps it into the next position.3 · Arrays
self-balancing search treeA BST that keeps its height O(log n) by repairing itself with rotations or recoloring after every insertion and deletion.10 · Search Trees
self-loopAn edge that joins a vertex to itself.14 · Graphs
self-referential structureA class that contains a field of its own type, such as a node holding a reference to the next node.5 · Linked Lists
sentinelA dummy node placed at the start or end of a linked list that holds no data and removes special cases at the boundaries.5 · Linked Lists
separate chainingA collision-resolution method in which each bucket holds a list of all entries whose keys hash to that index.12 · Maps and Hash Tables
setA collection of distinct elements in no particular order, whose main operation is the membership test.13 · Sets and Disjoint Sets
shallow copyA copy that duplicates an object but not the objects it refers to, so the copy and the original share them.3 · Arrays
short-circuit evaluationEvaluating && and || from left to right and stopping as soon as the result is known, which lets a guard prevent an invalid access.3 · Arrays
shortest pathA path between two vertices with the fewest edges, or with the smallest total weight in a weighted graph.14 · Graphs
siblingA node that has the same parent as a given node.9 · Trees
simple pathA path that does not repeat any node or vertex.9 · Trees
simple uniform hashingThe analysis assumption that each key is equally likely to hash to any bucket, independently of the other keys.12 · Maps and Hash Tables
single-source shortest pathThe problem of finding shortest paths from one source vertex to every other vertex of a graph.14 · Graphs
singly linked listA linked list in which each node holds a reference only to the next node.5 · Linked Lists
skewed treeA binary tree in which every node has only a left child or only a right child, degenerating into a chain.9 · Trees
sliding windowA fixed-length range that moves along a sequence one step at a time; a deque finds each window's maximum in O(n) total.8 · Queues and Deques
slotOne cell of a hash table's array, which in open addressing holds at most one entry.12 · Maps and Hash Tables
slow and fast pointersTwo references traversing a linked list at different speeds, used to find the middle node or detect a cycle.5 · Linked Lists
sorted listA priority queue implementation that keeps entries ordered by key, giving O(1) removal of the minimum but O(n) insertion.11 · Priority Queues and Heaps
space complexityThe amount of memory an algorithm needs as a function of its input size.2 · Algorithm Analysis
spanning treeA subgraph of a connected graph that is a tree and contains every vertex.14 · Graphs
sparse graphA graph with far fewer edges than possible, on the order of the number of vertices.14 · Graphs
splay treeA self-adjusting BST that moves each accessed node to the root by rotations, giving O(log n) amortized cost.10 · Search Trees
stable (sort)Describing a sorting algorithm that keeps elements with equal keys in their original relative order.3 · Arrays
stackA linear structure that adds and removes elements at one end only, the top, in last-in, first-out order.7 · Stacks
stack frameThe record of one method call on the call stack, holding its parameters, local variables and return address.4 · Recursion
stack traceThe list of method calls active on the call stack at the moment an exception is thrown, printed to show where the error occurred.4 · Recursion
stale entryAn outdated entry left in a priority queue after a vertex's distance improved, skipped when removed in the lazy version of Dijkstra's algorithm.14 · Graphs
starvationThe situation in which a low-priority item waits forever because higher-priority items keep arriving.11 · Priority Queues and Heaps
static arrayAn array whose size is fixed when it is created and cannot change afterwards.3 · Arrays
stock spanFor each day, the number of consecutive days up to and including it with a price at most that day's price; computed in O(n) with a stack.7 · Stacks
streamIn Java, a sequence of elements drawn from a collection on which operations such as filter, map and count are chained.6 · The List ADT and Java Collections
structural modificationA change to a collection that alters its number of elements, such as add or remove; replacing an element with set is not one.6 · The List ADT and Java Collections
subsetA set all of whose elements also belong to another set.13 · Sets and Disjoint Sets
subtreeA node of a tree together with all its descendants.9 · Trees
successorThe element that comes immediately after a given element in order; in a BST, the node with the next larger key.10 · Search Trees
swapExchanging the values stored at two positions, usually through a temporary variable.3 · Arrays
tailThe last node of a linked list.5 · Linked Lists
tail callA call that is the last action of a method, so nothing remains to be done after it returns.4 · Recursion
tail call optimizationA compiler technique that reuses the current stack frame for a tail call instead of pushing a new one; Java does not perform it.4 · Recursion
tail pointerA reference to the last node of a linked list, kept so that insertion at the end takes O(1).5 · Linked Lists
tail recursionRecursion in which the recursive call is the method's last action, so it can be converted mechanically into a loop.4 · Recursion
tentative distanceIn Dijkstra's algorithm, the length of the shortest path to a vertex found so far, which becomes final when the vertex is settled.14 · Graphs
threadAn independent path of execution within a program; several threads can run at once and share the same data.6 · The List ADT and Java Collections
tight boundA bound that is both an upper and a lower bound up to constant factors, stated with Big Theta.2 · Algorithm Analysis
time complexityThe running time of an algorithm, counted in primitive operations, as a function of its input size.2 · Algorithm Analysis
time slice (quantum)The fixed maximum time a process may run in round-robin scheduling before returning to the rear of the ready queue.8 · Queues and Deques
TimSortThe hybrid merge sort Java uses for object lists, which detects runs already in order and merges them; O(n log n) and stable.6 · The List ADT and Java Collections
tombstone (DEFUNCT)A marker left in an open-addressing slot when its entry is deleted, so searches continue past it instead of stopping.12 · Maps and Hash Tables
topThe end of a stack where elements are pushed and popped, or the operation that returns the top element without removing it.7 · Stacks
topological sortAn ordering of the vertices of a directed acyclic graph in which every edge goes from an earlier vertex to a later one.14 · Graphs
Towers of HanoiMoving n disks between three pegs, one at a time, never a larger on a smaller; the recursive solution takes 2^n - 1 moves.4 · Recursion
trade-offA choice in which making one operation or resource cheaper makes another more expensive, the central issue in choosing a data structure.1 · Introduction
transposeThe matrix obtained by turning the rows of a matrix into columns, so that T[j][i] = M[i][j].3 · Arrays
traversalVisiting every element of a data structure once in a systematic order.5 · Linked Lists
treeA nonlinear structure of nodes connected by edges in a hierarchy, with one root and exactly one path between any two nodes.9 · Trees
two-dimensional arrayAn array indexed by a row and a column, stored in Java as an array of row arrays.3 · Arrays
type parameterA placeholder for a type, such as E in ArrayList<E>, replaced by an actual type when the generic class is used.1 · Introduction
type safetyThe guarantee that a program performs only operations valid for the types of its values, checked largely by the compiler in Java.1 · Introduction
unboxingJava's automatic conversion of a wrapper object back into its primitive value, for example Integer to int.6 · The List ADT and Java Collections
underflowThe error of popping or reading the top of an empty stack.7 · Stacks
undirected graphA graph whose edges have no direction, each simply joining two vertices.14 · Graphs
undoAn editor feature implemented with a stack: each change is pushed, and undo pops and reverses the latest one.7 · Stacks
UnicodeThe standard that assigns a code point to every character of every writing system.1 · Introduction
unionThe set of elements that belong to at least one of two sets, written A ∪ B; also the operation that merges two disjoint sets.13 · Sets and Disjoint Sets
union by rankA union-find rule that attaches the root of lower rank under the root of higher rank, keeping trees shallow.13 · Sets and Disjoint Sets
union by sizeA union-find rule that attaches the root of the smaller tree under the root of the larger one.13 · Sets and Disjoint Sets
universeThe set of all elements that may appear in the sets under consideration, such as 0 to U - 1 for a bit vector.13 · Sets and Disjoint Sets
unsorted listA priority queue implementation that keeps entries in arrival order, giving O(1) insertion but O(n) removal of the minimum.11 · Priority Queues and Heaps
unwindingThe return phase of recursion, in which the calls finish one by one and their frames are popped off the call stack.4 · Recursion
up-heapRestoring heap order after an insertion by swapping the new element with its parent while it should be above it.11 · Priority Queues and Heaps
upper boundA function that another function eventually stays at or below, up to a constant factor; stated with Big O.2 · Algorithm Analysis
valueThe data associated with a key in a map entry.12 · Maps and Hash Tables
varargsA Java parameter declared with ..., which accepts any number of arguments and receives them as an array.3 · Arrays
vertexA basic element of a graph, connected to other vertices by edges.14 · Graphs
viewA collection object that presents part or all of another collection without copying it, so changes to one appear in the other.6 · The List ADT and Java Collections
weightA number attached to an edge of a graph, such as a distance or cost.14 · Graphs
weighted graphA graph in which each edge has a weight.14 · Graphs
worst caseThe input of a given size on which an algorithm does the most work, and the running time it takes there.2 · Algorithm Analysis
wrapper classA class such as Integer or Double whose objects hold a single primitive value, so it can be used where an object is required.6 · The List ADT and Java Collections
zig, zig-zig, zig-zagThe three kinds of splay step, by whether the node is a child of the root, or is on the same or opposite side as its parent.10 · Search Trees

Course page: Data Structures · Course Map · © Sercan Külcü. All rights reserved.