Glossary

81 terms, plain English

Grouped by chapter. Press ⌘K to search any of them.

01 Introduction to Data Structures

Abstraction: Hiding implementation details behind an interface so users only see what they need. Learn →
ADT (Abstract Data Type): A description of data plus the operations on it, saying what they do but not how they are implemented. Learn →
Data structure: A way of organising data in memory so that the operations you need are efficient. Learn →
Linear data structure: Items form a sequence, each with at most one predecessor and one successor: arrays, linked lists, stacks, queues. Learn →
Non-linear data structure: Items branch or connect freely: trees and graphs. Learn →
Primitive data structure: Built-in types operated on directly by the machine: int, char, float, bool, pointers. Learn →
Row-major order: How C++ stores a 2-D array: row 0 first, then row 1. Address of a[i][j] = base + (i·cols + j)·size. Learn →
Static vs dynamic: Static structures have a size fixed when they are created (arrays); dynamic ones grow and shrink at run time (linked lists). Learn →

02 Algorithm & Algorithm Analysis

Algorithm: A finite, well-defined sequence of steps that turns input into the desired output. Learn →
Best / average / worst case: The running time on the most favourable, typical, and least favourable input of size n. Learn →
Big-O (O): Upper bound: f(n) = O(g(n)) if f(n) ≤ c·g(n) for all n ≥ k, for some constants c > 0 and k. Learn →
Big-Omega (Ω): Lower bound: f(n) ≥ c·g(n) for all n ≥ k. Learn →
Big-Theta (Θ): Tight bound: f(n) is both O(g(n)) and Ω(g(n)). Learn →
Definiteness: Every step is precise and unambiguous. Learn →
Empirical analysis: Measuring an algorithm by running it and timing it. Depends on the machine and the input. Learn →
Finiteness: An algorithm must stop after a finite number of steps. Learn →
Little-o / little-omega: Strict bounds: f grows strictly slower (o) or strictly faster (ω) than g. Learn →
T(n): The running time of an algorithm as a function of input size n, in time units. Learn →
Theoretical analysis: Counting basic operations as a function of input size n. Machine-independent. Learn →
Time unit: One basic operation (assignment, single I/O, Boolean or arithmetic op, return) counted as 1 in T(n). Learn →
Time/space trade-off: Using more memory to save time (or the reverse), e.g. storing results instead of recomputing them. Learn →

03 Simple Sorting & Searching

Base case: The input a recursive function answers directly, without recursing. Learn →
Binary search: Repeatedly halve a sorted range by comparing with the middle item. O(log n). Learn →
Call stack: Memory where each active function call keeps its parameters and local variables. Learn →
In-place: Uses only O(1) extra memory besides the input (recursion stack aside). Learn →
Linear search: Check each item in turn. O(n). Works on unsorted data. Learn →
Pass: One full sweep of the outer loop of a sort. Learn →
Pointer sort: Sorting an array of pointers (or indices) to records instead of moving the records themselves. Learn →
Recursion: A function that calls itself on a smaller input, stopping at a base case. Learn →
Stable sort: A sort that keeps equal keys in their original relative order. Learn →

04 Linked Lists

Dangling pointer: A pointer to memory that has already been freed. Learn →
Doubly linked list: Each node has both next and prev pointers, allowing backward traversal and O(1) delete given a node. Learn →
Dummy (sentinel) node: A fake node placed before the head so every real node has a predecessor. Learn →
Head: Pointer to the first node of a linked list. Learn →
Heap (memory): Memory for dynamic allocation with new/delete. Lives until you free it. Learn →
Memory leak: Heap memory that is no longer reachable but was never deleted. Learn →
Node: One element of a linked structure: data plus pointer(s) to other nodes. Learn →
Pointer: A variable that stores a memory address. Learn →

05 Stacks & Queues

Circular queue: Array queue whose indices wrap around with % N so freed slots are reused. Learn →
Deque: Double-ended queue: insert and remove at both ends in O(1). Learn →
FIFO: First In, First Out. Learn →
LIFO: Last In, First Out. Learn →
Overflow / underflow: Pushing onto a full stack / popping from an empty one. Learn →
Queue: FIFO collection: enqueue at the rear, dequeue from the front. Learn →
Stack: LIFO collection: push and pop at the top only. Learn →

06 Trees

Binary tree: A tree in which every node has at most two children, left and right. Learn →
BST: Binary search tree: for every node, left subtree < node < right subtree. Learn →
Depth / height: Depth: edges from the root down to a node. Height: edges from a node down to its deepest leaf. Learn →
Full / complete / perfect: Full: 0 or 2 children everywhere. Complete: all levels full except the last, filled from the left. Perfect: all levels full. Learn →
General tree: A tree whose nodes may have any number of children. Learn →
Inorder successor: The next value in sorted order; for a node with a right child, the minimum of its right subtree. Learn →
Left-child, right-sibling: Stores a general tree with two pointers per node: first child and next sibling. Learn →
Level-order traversal: Visit a tree level by level using a queue (BFS on a tree). Learn →
Preorder / inorder / postorder: Depth-first traversals: Node-Left-Right / Left-Node-Right / Left-Right-Node. Learn →
Root / leaf: The top node (no parent) / a node with no children. Learn →

07 Graphs

Adjacency list: For each vertex, a list of its neighbours. O(V + E) space. Learn →
Adjacency matrix: V×V table where m[u][v] = 1 (or the weight) if there is an edge u→v. O(V²) space. Learn →
BFS: Breadth-first search: explore neighbours in waves using a queue. Finds fewest-edge paths. Learn →
Connected graph: There is a path between every pair of vertices. Learn →
DAG: Directed acyclic graph: a digraph with no directed cycles. Learn →
Degree: Number of edges at a vertex. In a digraph, split into in-degree and out-degree. Learn →
DFS: Depth-first search: go as deep as possible, then backtrack, using recursion or a stack. Learn →
Directed graph (digraph): A graph whose edges are one-way arrows. Learn →
Graph: G = (V, E): a set of vertices and a set of edges between them. Learn →
Path / cycle: A sequence of vertices joined by edges / a path that returns to its start. Learn →

08 Advanced Sorting & Searching

Collision: Two different keys hashing to the same index. Learn →
Divide and conquer: Split a problem into smaller parts, solve them recursively, combine the results. Learn →
Gap (shell sort): The distance between compared items in a shell sort pass; shrinks to 1. Learn →
Hash function: Maps a key to an index of the hash table, e.g. h(k) = k mod M. Learn →
Heapify: Sift a node down until the heap property holds below it. O(log n). Learn →
Linear probing: On a collision, try the next slot (h + i) % M until an empty one. Learn →
Load factor: α = n / M, how full a hash table is. Learn →
Max-heap: A complete binary tree where every parent is ≥ its children; stored in an array. Learn →
Partition: Rearranging a range so items smaller than the pivot come before it and bigger ones after. Learn →
Pivot: The item quick sort partitions around. Learn →
Separate chaining: Each table slot holds a list of all keys that hash there. Learn →

LU Level Up: Problem Patterns

Floyd's cycle detection: Slow pointer moves 1, fast moves 2; they meet if and only if there is a cycle. Learn →
Monotonic stack: A stack kept in increasing or decreasing order; answers next-greater/smaller queries in O(n). Learn →
Prefix sum: p[i] = sum of the first i items; any range sum is p[r+1] − p[l]. Learn →
Sliding window: Maintain an answer for a contiguous range while it moves, adding and removing one item per step. Learn →
Two pointers: Two indices moving through data to replace a pair search with one pass. Learn →