DSA Glossary
DSA Glossary
A comprehensive list of terms used in the Data Structures and Algorithms course.
A
Algorithm
A step-by-step procedure for solving a problem or performing a computation.
Amortized Analysis
The average time complexity of an operation over a sequence of operations, even if a single operation might be expensive (e.g., resizing a dynamic array).
Array
A collection of elements identified by index or key, stored in contiguous memory locations.
B
Big O Notation
A mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Used to classify algorithms according to how their run time or space requirements grow as the input size grows.
Binary Heap
A complete binary tree that satisfies the heap property.
Binary Search Tree (BST)
A binary tree where the left child is smaller than the parent and the right child is greater.
Binary Tree
A tree data structure in which each node has at most two children, referred to as the left child and the right child.
Breadth-First Search (BFS)
A graph traversal algorithm that explores all neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.
C
Circular Linked List
A linked list where the last node points back to the first node instead of null.
Cycle Detection
The process of determining whether a linked list contains a loop.
D
Depth-First Search (DFS)
A graph traversal algorithm that explores as far as possible along each branch before backtracking.
Deque (Double-Ended Queue)
A linear data structure that supports insertion and removal of elements from both the front and the back.
Dijkstra’s Algorithm
An algorithm for finding the shortest paths between nodes in a graph.
Doubly Linked List
A linked list where each node has two pointers: one to the next node and one to the previous node.
Dynamic Array
An array that can resize itself during execution (e.g., ArrayList in Java, slice in Go).
F
FIFO (First-In, First-Out)
The principle where the first element added is the first one to be removed. Used in Queues.
Floyd’s Cycle-Finding Algorithm
Also known as the “Tortoise and Hare” algorithm. A pointer algorithm that uses two pointers moving at different speeds to detect a cycle in a sequence of values.
H
Hash Table
A data structure that implements an associative array abstract data type, a structure that can map keys to values.
Head
The first node in a linked list.
Heap
See Binary Heap.
Heapify
The process of creating a heap data structure from a binary tree or array.
Height
The number of edges on the longest path from a node to a leaf.
I
Immutability
The property of an object whose state cannot be modified after it is created. Strings in Java and Go are immutable.
Infix Notation
Arithmetic notation in which operators are written between operands (e.g., 3 + 4).
Inorder Traversal
A DFS traversal: Left, Root, Right.
L
Leaf
A tree node with no children.
LIFO (Last-In, First-Out)
The principle where the last element added is the first one to be removed. Used in Stacks.
Linked List
A linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next.
Lowest Common Ancestor (LCA)
The deepest node in a tree that is an ancestor of two specific nodes.
M
Max Heap
A binary heap where the parent key is greater than or equal to the child keys.
Min Heap
A binary heap where the parent key is less than or equal to the child keys.
Monotonic Stack
A stack where elements are always sorted (either increasing or decreasing).
N
Naive Search
A simple string searching algorithm that checks for the pattern at all possible positions in the text. Time complexity O(N*M).
Node
The fundamental building block of a linked list or tree, containing data and references to other nodes.
P
Pointer
A variable that stores the memory address of another variable. In Java, this is abstracted as a Reference.
Postfix Notation (RPN)
Mathematical notation in which operators follow their operands (e.g., 3 4 +).
Postorder Traversal
A DFS traversal: Left, Right, Root.
Preorder Traversal
A DFS traversal: Root, Left, Right.
Prev
The pointer in a Doubly Linked List node that points to the preceding node.
Priority Queue
A data structure where each element has a priority, and elements with higher priority are served before elements with lower priority.
Q
Queue
A linear data structure that follows the FIFO principle.
R
Reference
A value that enables a program to indirectly access a particular datum, such as a variable’s value or a record, in the computer’s memory or in some other storage device.
Root
The topmost node in a tree.
S
Sentinel Node
A dummy node used to simplify boundary conditions in linked lists and trees. Also known as a Dummy Node.
Shunting-yard Algorithm
An algorithm for parsing mathematical expressions from infix notation to postfix notation.
Singly Linked List
A linked list where each node points only to the next node.
Sliding Window
A technique for solving subarray or substring problems by maintaining a window that slides over the data to avoid re-computation.
Stack
A linear data structure that follows the LIFO principle.
String
A sequence of characters. In many languages, strings are immutable objects.
String Pool
A special memory region where the JVM stores string literals to save space.
StringBuilder
A mutable sequence of characters in Java, used for efficient string concatenation.
T
Tail
The last node in a linked list. In a standard list, its next pointer is null.
Tortoise and Hare
See Floyd’s Cycle-Finding Algorithm.
Trie (Prefix Tree)
A tree-based data structure used to store a dynamic set of strings where the keys are usually strings.
Two Pointers
A technique where two pointers iterate through a data structure (usually an array or string) in different directions or at different speeds to solve problems efficiently.
V
Visualizer
An interactive tool used in this course to demonstrate how algorithms work step-by-step.