Data Structures Glossary
Recursion
Recursion is a programming technique where a function calls itself within its own definition. It is usually used to solve problems that can be broken down into smaller instances of the same problem.
Array Data Structure
An array stores items (or their references) at contiguous memory locations. It allows random access in O(1) time, is cache friendly due to locality of reference, and is a fundamental linear data structure used to build others such as stacks, queues, and hash tables. However, it is inefficient for operations like insertion or deletion in the middle or searching in an unsorted array.
Stack
A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. In a stack, the last element added is the first to be removed. Stacks are used for managing function calls, memory, parsing, and algorithmic problems like the stock span problem and next greater element.
Queue
A queue is a linear data structure that follows the First In, First Out (FIFO) principle. It is used in buffering, CPU scheduling, memory management, and algorithms like BFS and level order traversal of trees. The first element added is the first to be removed.
Linked List
A linked list consists of nodes connected by pointers, allowing efficient insertion and deletion. Unlike arrays, linked lists use non-contiguous memory and require sequential access. Types include singly linked list, doubly linked list, and circular linked list.
Tree Data Structure
A tree is a non-linear data structure in which nodes are connected by edges and exactly one path exists between any two nodes. Types include binary tree, ternary tree, and n-ary tree. Trees are used for hierarchical data representation, such as file systems and decision trees.
Binary Search Tree (BST)
A BST is a binary tree where the left subtree contains values less than the node’s value, and the right subtree contains values greater. This ordering allows efficient search, insertion, and deletion (O(log n) in balanced trees). Self-balancing BSTs like AVL and Red-Black trees maintain efficiency.
Binary Heap
A binary heap is a complete binary tree used for efficient retrieval of the smallest (min-heap) or largest (max-heap) element. It is typically represented as an array and supports operations like insert, delete, and extract in O(log n) time. Common applications include priority queues, heap sort, and graph algorithms like Dijkstra’s.
Graph Data Structure
A graph consists of a set of vertices (nodes) connected by edges (links). It is used to represent relationships between entities. Graphs can be directed or undirected, weighted or unweighted, and are used in applications such as networking, pathfinding, and dependency resolution.
