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.
| Term | Definition | Chapter |
|---|---|---|
| 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 |
| accumulator | A 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 queue | A 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 list | A 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 matrix | A 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 |
| adjacent | Said of two vertices joined by an edge; each is then a neighbor of the other. | 14 · Graphs |
| aging | Raising 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 |
| algorithm | A finite, unambiguous sequence of steps that solves a problem, taking an input and producing the correct output in a finite time. | 1 · Introduction |
| algorithm analysis | The 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 |
| aliasing | Reaching one object through two or more references, so that a change made through one reference is seen through the others. | 1 · Introduction |
| amortized analysis | Analysis 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 |
| ancestor | A node on the path from a given node up to the root: its parent, its parent's parent, and so on. | 9 · Trees |
| array | A 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 covariance | Java'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 |
| asymptotic | Describing how a function behaves as its input grows without bound, ignoring constant factors and lower-order terms. | 2 · Algorithm Analysis |
| autoboxing | Java'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 case | The expected running time of an algorithm over all inputs of a given size, under an assumed probability distribution of inputs. | 2 · Algorithm Analysis |
| AVL tree | A 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+ tree | A 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-tree | A 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 edge | In 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 |
| backtracking | A 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 factor | For 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 parentheses | The stack problem of checking that every opening bracket in an expression is closed by a matching bracket in the right order. | 7 · Stacks |
| base case | The input on which a recursive method answers directly without calling itself, which stops the recursion. | 4 · Recursion |
| best case | The input of a given size on which an algorithm does the least work, and the running time it takes there. | 2 · Algorithm Analysis |
| Big O | Notation 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 Omega | Notation 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 Theta | Notation 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 notation | The 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 heap | A 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 recursion | Recursion in which each call makes two recursive calls, as in the naive Fibonacci method or merge sort. | 4 · Recursion |
| binary search | A 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 tree | A tree in which every node has at most two children, distinguished as the left child and the right child. | 9 · Trees |
| binomial heap | A priority queue stored as a forest of binomial trees, which supports merging two heaps in O(log n). | 11 · Priority Queues and Heaps |
| bipartite graph | A 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 mask | An 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 vector | A 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 height | In 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 construction | Building 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 stack | An 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 force | Solving a problem by directly trying every possibility, simple to write but often slow, such as rescanning the array for each element. | 7 · Stacks |
| BST property | The 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 sort | A 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 |
| bucket | One 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 |
| buffer | A memory area, usually a queue, where data waits between a producer and a consumer that run at different speeds. | 8 · Queues and Deques |
| byte | A group of eight bits, the smallest addressable unit of memory, able to hold 256 different values. | 1 · Introduction |
| cache | A small, fast memory near the processor that holds recently used blocks of main memory, which makes access to nearby addresses cheap. | 3 · Arrays |
| cache miss | An 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 stack | The stack of frames the runtime keeps for active method calls; a call pushes a frame and a return pops it. | 7 · Stacks |
| call tree | A tree diagram of a recursive computation in which each node is one call and its children are the calls it makes. | 4 · Recursion |
| capacity | The 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 |
| chain | In separate chaining, the linked list of entries stored in one bucket of a hash table. | 12 · Maps and Hash Tables |
| character encoding | A rule that maps characters to numbers and those numbers to bytes, such as ASCII or UTF-8. | 1 · Introduction |
| child | A node directly below another node in a tree, joined to it by an edge. | 9 · Trees |
| circular queue | An 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 list | A 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 code | Code that uses a data structure only through its public interface, without depending on how it is implemented. | 1 · Introduction |
| code point | The number that Unicode assigns to a character, independent of how it is stored in bytes. | 1 · Introduction |
| collection | An 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 |
| collision | The 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 |
| comparator | An 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 time | The 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 tree | A 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 graph | A 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 |
| complexity | The amount of a resource, usually time or memory, that an algorithm uses, expressed as a function of the input size. | 2 · Algorithm Analysis |
| compression function | The 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 |
| connected | Said of an undirected graph in which there is a path between every pair of vertices. | 14 · Graphs |
| connected component | A maximal set of vertices of an undirected graph in which every pair is joined by a path. | 14 · Graphs |
| contiguous | Stored 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 |
| correctness | The property of an algorithm that it produces the right output for every valid input and terminates. | 2 · Algorithm Analysis |
| covariance | A typing relation in which a container of a subtype is treated as a container of its supertype, as Java does for arrays. | 3 · Arrays |
| covariant | Having covariance; Java arrays are covariant because String[] is a subtype of Object[], while generic lists are not. | 3 · Arrays |
| cursor | The 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 |
| cycle | In 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 detection | Determining whether following next references in a linked list ever returns to an earlier node instead of reaching null. | 5 · Linked Lists |
| d-ary heap | A 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 structure | A way of organizing data in memory together with the operations on it, chosen so that the needed operations are efficient. | 1 · Introduction |
| data type | A set of values together with the operations allowed on them, such as int with its arithmetic operations. | 1 · Introduction |
| decision tree | The 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 copy | A 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 tree | A search tree in which every node has only one child, so it behaves like a linked list with height n - 1. | 10 · Search Trees |
| degree | In a tree, the number of children of a node; the degree of a tree is the largest degree of its nodes. | 9 · Trees |
| dense graph | A graph with close to the maximum possible number of edges, on the order of n squared. | 14 · Graphs |
| depth | The 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 |
| dequeue | The queue operation that removes and returns the element at the front. | 8 · Queues and Deques |
| descendant | A node in the subtree below a given node: its children, their children, and so on. | 9 · Trees |
| deterministic | Always 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 |
| difference | The set of elements that belong to the first set but not to the second, written A - B. | 13 · Sets and Disjoint Sets |
| digital data | Information such as text, numbers, images and sound represented as sequences of bits. | 1 · Introduction |
| Dijkstra's algorithm | A 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 addressing | Storing 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 cycle | A 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 hashing | An 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 experiment | An 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 list | A linked list in which each node holds references to both the next and the previous node. | 5 · Linked Lists |
| down-heap | Restoring 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 array | An 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 stack | A stack that grows as needed, either by resizing its array or by using linked nodes, so it never overflows. | 7 · Stacks |
| edge | A connection between two nodes of a tree or two vertices of a graph. | 9 · Trees |
| edge list | A graph representation that stores all edges in one list, each as a pair of endpoints, possibly with a weight. | 14 · Graphs |
| element | One item stored in a data structure, such as one value in an array. | 3 · Arrays |
| empirical analysis | Measuring an algorithm's running time by running it on inputs of various sizes, as opposed to analyzing it mathematically. | 2 · Algorithm Analysis |
| enqueue | The queue operation that adds an element at the rear. | 8 · Queues and Deques |
| Euler tour | A 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 |
| exception | An object signaling an error or unusual condition, thrown by code that detects it and caught by code that can handle it. | 7 · Stacks |
| expression tree | A binary tree representing an arithmetic expression, with operators in internal nodes and operands in leaves. | 9 · Trees |
| external node | A node with no children; another name for a leaf. | 9 · Trees |
| fail-fast | Describing 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 heap | A 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 |
| FIFO | First 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 stack | A stack whose array capacity is set at creation and never changes, so pushing onto a full stack is an error. | 7 · Stacks |
| floating point | A 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 algorithm | Moving 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 |
| forest | A collection of disjoint trees. | 9 · Trees |
| front | The end of a queue from which elements are removed. | 8 · Queues and Deques |
| full binary tree | A binary tree in which every node has either zero or two children. | 9 · Trees |
| garbage collector | The part of the Java runtime that automatically reclaims the memory of objects that no reference can reach. | 1 · Introduction |
| generic | Written with type parameters so that one class or method works for many element types while the compiler still checks types. | 1 · Introduction |
| generics | The Java feature that lets classes, interfaces and methods take type parameters, as in List<String>, giving type safety without casts. | 1 · Introduction |
| graph | A set of vertices together with a set of edges, each edge joining a pair of vertices. | 14 · Graphs |
| half-open interval | A 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 code | An integer computed from a key, the first step of a hash function before compression to a table index. | 12 · Maps and Hash Tables |
| hash function | A 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 set | A 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 table | An 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 |
| head | The first node of a linked list, through which the rest of the list is reached. | 5 · Linked Lists |
| heap | A tree-based structure satisfying the heap-order property, used to implement priority queues. | 11 · Priority Queues and Heaps |
| heap memory | The region of memory where Java allocates objects created with new; they stay there until the garbage collector reclaims them. | 3 · Arrays |
| heap sort | A 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 property | The 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 |
| height | The 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 slot | The 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 method | Evaluating 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 |
| immutability | The property of an object whose state cannot change after it is created. | 1 · Introduction |
| immutable | Unable 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 |
| implementation | The concrete code and data representation that realize an interface or abstract data type. | 1 · Introduction |
| in-degree | In a directed graph, the number of edges coming into a vertex. | 14 · Graphs |
| in-place | Describing an algorithm that rearranges data within the input array, using only a constant amount of extra memory. | 3 · Arrays |
| incident | Said of an edge and a vertex when the vertex is one of the edge's endpoints. | 14 · Graphs |
| index | The integer position of an element in an array or list; Java indices start at 0. | 3 · Arrays |
| infix | Expression notation that writes each binary operator between its operands, as in 3 + 4. | 7 · Stacks |
| initializer | A brace-enclosed list of values that creates and fills an array in its declaration, as in int[] a = {1, 2, 3}. | 3 · Arrays |
| inorder | A 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 sort | A sorting algorithm that takes elements one by one and inserts each into its place among the already sorted elements to its left. | 3 · Arrays |
| interface | A declaration of the operations a type provides, without their implementation; in Java, a type that classes implement. | 1 · Introduction |
| internal node | A tree node that has at least one child. | 9 · Trees |
| intersection | The set of elements that belong to both of two sets, written A ∩ B. | 13 · Sets and Disjoint Sets |
| invariant | A 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 function | An 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 |
| inversion | A 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 vertex | A vertex with no incident edges, that is, of degree 0. | 14 · Graphs |
| iterator | An 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 array | A two-dimensional array whose rows have different lengths, possible in Java because each row is a separate array. | 3 · Arrays |
| Java Collections Framework | Java'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 algorithm | A topological sort that repeatedly outputs a vertex of in-degree 0 and removes its outgoing edges, using a queue. | 14 · Graphs |
| key | The 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 pair | An entry of a map, associating a unique key with its value. | 12 · Maps and Hash Tables |
| Kruskal's algorithm | A 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 expression | A short anonymous function written inline, as in (a, b) -> a - b, often passed as a comparator. | 6 · The List ADT and Java Collections |
| leaf | A tree node with no children. | 9 · Trees |
| level | The set of all tree nodes at the same depth; level d contains the nodes at depth d. | 9 · Trees |
| level-order | A tree traversal that visits nodes level by level from the root, left to right within a level, using a queue. | 9 · Trees |
| LIFO | Last in, first out: the order in which a stack removes elements, newest first. | 7 · Stacks |
| linear probing | An 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 recursion | Recursion in which each call makes at most one recursive call. | 4 · Recursion |
| linear search | Searching 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 list | A 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 |
| list | An ordered sequence of elements in which each element has a position and duplicates are allowed. | 6 · The List ADT and Java Collections |
| listener | An 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 factor | The 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 entry | A 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 |
| loitering | Keeping 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 |
| loop | A program construct such as for or while that repeats a block of statements; distinct from a cycle in a graph. | 2 · Algorithm Analysis |
| loop invariant | A condition true before and after every iteration of a loop, used to prove that the loop computes the right result. | 2 · Algorithm Analysis |
| lower bound | A 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 |
| map | An 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 induction | A 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 |
| matrix | A rectangular table of values arranged in rows and columns, stored in Java as a two-dimensional array. | 3 · Arrays |
| max-heap | A 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 |
| median | The 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 test | The set operation that asks whether a given element belongs to the set. | 13 · Sets and Disjoint Sets |
| memoization | Storing 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 leak | Memory that remains allocated after the program no longer needs it; in Java it happens when unused objects are still referenced. | 3 · Arrays |
| merge sort | A 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-heap | A 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 |
| mode | The value that occurs most often in a data set. | 3 · Arrays |
| monotonic stack | A stack whose contents stay sorted, maintained by popping every item that would break the order before pushing a new one. | 7 · Stacks |
| multidimensional array | An array indexed by two or more indices; in Java, an array whose elements are themselves arrays. | 3 · Arrays |
| multimap | A map in which one key may be associated with several values. | 13 · Sets and Disjoint Sets |
| multiple recursion | Recursion in which a call may make more than two recursive calls, as when exploring the choices of a backtracking search. | 4 · Recursion |
| multiplicity | The number of times an element occurs in a multiset. | 13 · Sets and Disjoint Sets |
| multiset | A 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 |
| mutable | Able to be changed after creation. | 6 · The List ADT and Java Collections |
| next greater element | For each item of a sequence, the first later item that is larger than it; found in O(n) with a monotonic stack. | 7 · Stacks |
| node | A 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-primitive | Built from primitive types and other structures, such as arrays, lists, trees and graphs, rather than holding a single simple value. | 1 · Introduction |
| null | The 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 error | A 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 addressing | A 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 |
| operand | A value on which an operator acts, such as 3 and 4 in 3 + 4. | 7 · Stacks |
| operator | A symbol for an operation on operands, such as +, -, * or /. | 7 · Stacks |
| out-degree | In a directed graph, the number of edges leaving a vertex. | 14 · Graphs |
| overflow | The error of pushing an element onto a full stack of fixed capacity. | 7 · Stacks |
| overload | To define several methods with the same name but different parameter lists in one class. | 6 · The List ADT and Java Collections |
| parent | The node directly above a given node in a tree; every node except the root has exactly one. | 9 · Trees |
| pass by value | Java'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 |
| path | A 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 compression | A 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 tree | A binary tree in which every internal node has two children and all leaves are at the same depth. | 9 · Trees |
| perfect hash | A 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 structure | A 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 |
| pointer | A variable that holds the memory address of another value; Java references play this role in linked structures. | 5 · Linked Lists |
| pop | The stack operation that removes and returns the top element. | 7 · Stacks |
| position | An 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 list | A 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 |
| postfix | Expression notation that writes each operator after its operands, as in 3 4 +, evaluated with a stack and needing no parentheses. | 7 · Stacks |
| postorder | A tree traversal that visits a node's subtrees first and the node last. | 9 · Trees |
| predecessor | The element that comes immediately before a given element in order; in a BST, the node with the next smaller key. | 10 · Search Trees |
| prefix | Expression notation that writes each operator before its operands, as in + 3 4. | 7 · Stacks |
| prefix averages | Computing, 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 |
| preorder | A tree traversal that visits a node first and then its subtrees. | 9 · Trees |
| Prim's algorithm | A minimum spanning tree algorithm that grows one tree from a start vertex, each time adding the cheapest edge leaving the tree. | 14 · Graphs |
| primary clustering | Linear 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 operation | A basic step, such as an assignment, comparison or arithmetic operation, counted as one unit of time when analyzing an algorithm. | 2 · Algorithm Analysis |
| primitive type | One of Java's built-in non-object types, such as int, double, char and boolean, whose variables hold the value itself. | 1 · Introduction |
| priority queue | An 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 sequence | The order of slots that a key tries in an open-addressing hash table, starting at its home slot. | 12 · Maps and Hash Tables |
| probing | Checking a slot of an open-addressing hash table while inserting or searching for a key. | 12 · Maps and Hash Tables |
| pruning | Skipping parts of a search space that cannot contain an answer, such as BST subtrees outside a query range. | 10 · Search Trees |
| push | The stack operation that adds an element on top. | 7 · Stacks |
| quadratic probing | An open-addressing method that, on a collision, tries slots 1, 4, 9, 16, ... positions beyond the home slot. | 12 · Maps and Hash Tables |
| queue | A 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 sort | A 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-Find | A 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 condition | A 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 access | Reaching any element directly by its index in constant time, as in an array. | 3 · Arrays |
| range query | A 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 |
| rank | In 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 |
| rear | The end of a queue at which elements are added. | 8 · Queues and Deques |
| recurrence relation | An equation that defines a function in terms of its values on smaller inputs, such as T(n) = 2T(n/2) + n. | 4 · Recursion |
| recursion | A technique in which a method solves a problem by calling itself on smaller instances of the same problem. | 4 · Recursion |
| recursive step | The part of a recursive method that reduces the problem to smaller instances and calls itself on them. | 4 · Recursion |
| red-black tree | A 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 |
| reference | A value that refers to an object in memory; Java variables of non-primitive type hold references, not the objects themselves. | 1 · Introduction |
| relaxation | Updating 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 address | The 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 buffer | Another name for a circular queue: a fixed array whose indices wrap around from the last slot to the first. | 8 · Queues and Deques |
| robustness | The ability of a program to handle unexpected or invalid inputs gracefully instead of failing. | 2 · Algorithm Analysis |
| root | The single node at the top of a tree, the only node without a parent. | 9 · Trees |
| rotation | A 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 robin | A 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 time | The phase when a program executes, during which errors such as an out-of-bounds index are detected. | 1 · Introduction |
| scheduler | The part of an operating system that decides which waiting process or thread runs next. | 8 · Queues and Deques |
| search tree | A 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 clustering | The tendency, in quadratic probing, of keys with the same home slot to follow the same probe sequence. | 12 · Maps and Hash Tables |
| selection sort | A sorting algorithm that repeatedly selects the smallest remaining element and swaps it into the next position. | 3 · Arrays |
| self-balancing search tree | A BST that keeps its height O(log n) by repairing itself with rotations or recoloring after every insertion and deletion. | 10 · Search Trees |
| self-loop | An edge that joins a vertex to itself. | 14 · Graphs |
| self-referential structure | A class that contains a field of its own type, such as a node holding a reference to the next node. | 5 · Linked Lists |
| sentinel | A 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 chaining | A collision-resolution method in which each bucket holds a list of all entries whose keys hash to that index. | 12 · Maps and Hash Tables |
| set | A collection of distinct elements in no particular order, whose main operation is the membership test. | 13 · Sets and Disjoint Sets |
| shallow copy | A copy that duplicates an object but not the objects it refers to, so the copy and the original share them. | 3 · Arrays |
| short-circuit evaluation | Evaluating && 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 path | A path between two vertices with the fewest edges, or with the smallest total weight in a weighted graph. | 14 · Graphs |
| sibling | A node that has the same parent as a given node. | 9 · Trees |
| simple path | A path that does not repeat any node or vertex. | 9 · Trees |
| simple uniform hashing | The 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 path | The problem of finding shortest paths from one source vertex to every other vertex of a graph. | 14 · Graphs |
| singly linked list | A linked list in which each node holds a reference only to the next node. | 5 · Linked Lists |
| skewed tree | A binary tree in which every node has only a left child or only a right child, degenerating into a chain. | 9 · Trees |
| sliding window | A 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 |
| slot | One cell of a hash table's array, which in open addressing holds at most one entry. | 12 · Maps and Hash Tables |
| slow and fast pointers | Two references traversing a linked list at different speeds, used to find the middle node or detect a cycle. | 5 · Linked Lists |
| sorted list | A 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 complexity | The amount of memory an algorithm needs as a function of its input size. | 2 · Algorithm Analysis |
| spanning tree | A subgraph of a connected graph that is a tree and contains every vertex. | 14 · Graphs |
| sparse graph | A graph with far fewer edges than possible, on the order of the number of vertices. | 14 · Graphs |
| splay tree | A 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 |
| stack | A linear structure that adds and removes elements at one end only, the top, in last-in, first-out order. | 7 · Stacks |
| stack frame | The record of one method call on the call stack, holding its parameters, local variables and return address. | 4 · Recursion |
| stack trace | The 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 entry | An 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 |
| starvation | The situation in which a low-priority item waits forever because higher-priority items keep arriving. | 11 · Priority Queues and Heaps |
| static array | An array whose size is fixed when it is created and cannot change afterwards. | 3 · Arrays |
| stock span | For 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 |
| stream | In 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 modification | A 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 |
| subset | A set all of whose elements also belong to another set. | 13 · Sets and Disjoint Sets |
| subtree | A node of a tree together with all its descendants. | 9 · Trees |
| successor | The element that comes immediately after a given element in order; in a BST, the node with the next larger key. | 10 · Search Trees |
| swap | Exchanging the values stored at two positions, usually through a temporary variable. | 3 · Arrays |
| tail | The last node of a linked list. | 5 · Linked Lists |
| tail call | A call that is the last action of a method, so nothing remains to be done after it returns. | 4 · Recursion |
| tail call optimization | A 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 pointer | A reference to the last node of a linked list, kept so that insertion at the end takes O(1). | 5 · Linked Lists |
| tail recursion | Recursion in which the recursive call is the method's last action, so it can be converted mechanically into a loop. | 4 · Recursion |
| tentative distance | In 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 |
| thread | An 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 bound | A bound that is both an upper and a lower bound up to constant factors, stated with Big Theta. | 2 · Algorithm Analysis |
| time complexity | The 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 |
| TimSort | The 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 |
| top | The end of a stack where elements are pushed and popped, or the operation that returns the top element without removing it. | 7 · Stacks |
| topological sort | An 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 Hanoi | Moving 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-off | A choice in which making one operation or resource cheaper makes another more expensive, the central issue in choosing a data structure. | 1 · Introduction |
| transpose | The matrix obtained by turning the rows of a matrix into columns, so that T[j][i] = M[i][j]. | 3 · Arrays |
| traversal | Visiting every element of a data structure once in a systematic order. | 5 · Linked Lists |
| tree | A 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 array | An array indexed by a row and a column, stored in Java as an array of row arrays. | 3 · Arrays |
| type parameter | A placeholder for a type, such as E in ArrayList<E>, replaced by an actual type when the generic class is used. | 1 · Introduction |
| type safety | The guarantee that a program performs only operations valid for the types of its values, checked largely by the compiler in Java. | 1 · Introduction |
| unboxing | Java's automatic conversion of a wrapper object back into its primitive value, for example Integer to int. | 6 · The List ADT and Java Collections |
| underflow | The error of popping or reading the top of an empty stack. | 7 · Stacks |
| undirected graph | A graph whose edges have no direction, each simply joining two vertices. | 14 · Graphs |
| undo | An editor feature implemented with a stack: each change is pushed, and undo pops and reverses the latest one. | 7 · Stacks |
| Unicode | The standard that assigns a code point to every character of every writing system. | 1 · Introduction |
| union | The 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 rank | A 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 size | A union-find rule that attaches the root of the smaller tree under the root of the larger one. | 13 · Sets and Disjoint Sets |
| universe | The 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 list | A 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 |
| unwinding | The return phase of recursion, in which the calls finish one by one and their frames are popped off the call stack. | 4 · Recursion |
| up-heap | Restoring 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 bound | A function that another function eventually stays at or below, up to a constant factor; stated with Big O. | 2 · Algorithm Analysis |
| value | The data associated with a key in a map entry. | 12 · Maps and Hash Tables |
| varargs | A Java parameter declared with ..., which accepts any number of arguments and receives them as an array. | 3 · Arrays |
| vertex | A basic element of a graph, connected to other vertices by edges. | 14 · Graphs |
| view | A 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 |
| weight | A number attached to an edge of a graph, such as a distance or cost. | 14 · Graphs |
| weighted graph | A graph in which each edge has a weight. | 14 · Graphs |
| worst case | The input of a given size on which an algorithm does the most work, and the running time it takes there. | 2 · Algorithm Analysis |
| wrapper class | A 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-zag | The 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 |
No terms match your search.
Course page: Data Structures · Course Map · © Sercan Külcü. All rights reserved.