Data Structures Glossary
Alphabetical Index of Definitions
- Array Data Structure
- Binary Heap
- Binary Search Tree (BST)
- Graph Data Structure
- Linked List Data Structure
- Queue Data Structure
- Recursion
- Stack
- Tree Data Structure
Array Data Structure
[cite_start]
An array stores items (or their references) at contiguous memory locations[cite: 11, 12]. [cite_start]It offers advantages like random access, where the i-th item can be accessed in O(1) time, and cache friendliness, because items are stored contiguously[cite: 14, 15]. [cite_start]Arrays are not ideal for operations like insertion in the middle, deletion from the middle, or searching in unsorted data[cite: 16]. [cite_start]It is a fundamental and linear data structure used to build other data structures such as Stack, Queue, Deque, Graph, and Hash Table[cite: 17, 18].
Binary Heap
[cite_start]
A Binary Heap is a complete binary tree that stores data efficiently to allow quick access to the maximum or minimum element[cite: 253]. [cite_start]A heap can be either a Min Heap or a Max Heap[cite: 254]. [cite_start]In a Min Heap, the root key is the smallest, and this property holds recursively for all nodes[cite: 255]. [cite_start]Conversely, in a Max Heap, the largest key is at the root[cite: 256]. [cite_start]A binary heap is typically represented as an array[cite: 336]. [cite_start]The parent of a node at index $i$ is at index $(i-1)/2$, the left child is at index $2i+1$, and the right child is at index $2i+2$[cite: 341, 342, 343, 347].
Binary Search Tree (BST)
[cite_start]
A Binary Search Tree (BST) is a binary tree where each node has a unique key and satisfies a specific ordering property[cite: 187]. [cite_start]For every node, all values in its left subtree are strictly less than its value, and all values in its right subtree are strictly greater[cite: 187, 188]. [cite_start]This ordering property holds recursively for all subtrees[cite: 245]. [cite_start]This structure enables efficient searching, insertion, and deletion operations, with a time complexity of O(log n) in a balanced tree[cite: 189, 246].
Graph Data Structure
[cite_start]
A graph is a non-linear data structure that consists of a finite set of vertices (or nodes) and a set of edges (or links) that connect pairs of nodes[cite: 409]. [cite_start]It is used to represent relationships between different entities[cite: 410, 411].
Linked List Data Structure
[cite_start]
A linked list is a fundamental data structure that allows for efficient insertion and deletion operations when compared to arrays[cite: 81, 82]. [cite_start]It is also used to implement other data structures like stacks, queues, and deques[cite: 83]. [cite_start]In contrast to an array which is a contiguous data structure, a linked list is non-contiguous with memory allocated element by element[cite: 97, 98, 103, 104].
Queue Data Structure
[cite_start]
A Queue Data Structure is a fundamental concept in computer science used for storing and managing data in a specific order[cite: 55]. [cite_start]It follows the “First in, First out” (FIFO) principle, where the first element added to the queue is the first one to be removed[cite: 56]. [cite_start]Queues are used as a buffer in computer systems to handle speed mismatches between devices, like a CPU and keyboard[cite: 57, 58]. [cite_start]They are also used in operating system algorithms like CPU Scheduling and Memory Management, and in algorithms like Breadth-First Search (BFS)[cite: 59].
Recursion
[cite_start]
Recursion is a programming technique where a function calls itself within its own definition[cite: 3]. [cite_start]It is typically used to solve problems that can be broken down into smaller instances of the same problem[cite: 4, 5].
Stack
[cite_start]
A stack is a linear data structure that follows the Last In, First Out (LIFO) principle[cite: 23, 29]. [cite_start]This means the element inserted last is the first one to come out[cite: 30]. [cite_start]It behaves like a stack of plates, where the last plate added is the first one to be removed[cite: 31]. [cite_start]Stacks are important for managing function calls and memory, and are widely used in algorithms such as the stock span problem and the next greater element problem[cite: 24].
Tree Data Structure
[cite_start]
A Tree Data Structure is a non-linear data structure where a collection of elements called nodes are connected by edges[cite: 120]. [cite_start]There is exactly one path between any two nodes in the tree[cite: 120]. [cite_start]Examples of tree types include Binary Tree, Ternary Tree, and N-ary Tree[cite: 142]. [cite_start]A Binary Tree has at most two children per node, a Ternary Tree has at most three, and an N-ary Tree has at most n children per node[cite: 142].
