Data Structures
Tree Structures
Hierarchical structure where each node has at most two children. Forms the basis for more specialized tree structures. Excellent for representing hierarchical relationships and recursive algorithms.
- Hierarchical parent-child structure
- Each node has max 2 children
- O(n) operations worst case
- Recursive traversal patterns
Ordered binary tree where left children are smaller and right children are larger. Enables efficient searching, insertion, and deletion when balanced. In-order traversal yields sorted sequence.
- Sorted left-right ordering
- O(log n) average operations
- O(n) worst case unbalanced
- In-order traversal is sorted
Self-balancing binary search tree maintaining strict height balance. Guarantees O(log n) operations through automatic rotations. Named after inventors Adelson-Velsky and Landis.
- Self-balancing on insert/delete
- O(log n) guaranteed operations
- Strict balance factor (-1, 0, 1)
- More balanced than Red-Black
Self-balancing binary search tree using color coding for balance. Provides guaranteed O(log n) operations with less strict balancing than AVL. Widely used in language standard libraries.
- Self-balancing with color properties
- O(log n) guaranteed operations
- Faster insertion than AVL
- Used in C++ STL and Java TreeMap
Hash-Based Structures
Key-value storage using hash functions for constant-time access. Handles collisions through chaining or open addressing. Fundamental for caching, indexing, and fast lookups in modern computing.
- O(1) average lookup/insert/delete
- Key-value pair storage
- Collision handling required
- Hash function determines distribution
Collection of unique elements using hash-based storage. Provides constant-time membership testing without storing values. Perfect for uniqueness constraints and fast existence checks.
- O(1) membership checking
- Stores unique elements only
- No key-value pairs, just keys
- Fast duplicate detection
Graph Structures
2D array representation where matrix[i][j] indicates edge existence between vertices i and j. Provides O(1) edge lookup but uses O(V²) space. Ideal for dense graphs with frequent edge queries.
- O(1) edge lookup time
- O(V²) space complexity
- Best for dense graphs
- Simple edge weight storage
Array of lists where each vertex stores its neighbors. Space-efficient for sparse graphs using O(V+E) space. Standard representation for most graph algorithms and real-world networks.
- O(V+E) space complexity
- Best for sparse graphs
- Efficient neighbor iteration
- Standard for graph traversal
Simple list of all edges in the graph. Minimal space usage at O(E) with easy edge-centric operations. Best for algorithms that primarily iterate through edges rather than vertices.
- Simplest representation
- O(E) space complexity
- Edge-centric operations
- Easy to add/remove edges
Heap Structures
Complete binary tree where parent is always smaller than children. Root contains minimum element. Essential for priority queues and algorithms requiring repeated minimum extraction.
- O(log n) insert and delete
- O(1) get minimum element
- Complete binary tree structure
- Parent smaller than children
Complete binary tree where parent is always larger than children. Root contains maximum element. Used in heap sort and scenarios requiring maximum element access.
- O(log n) insert and delete
- O(1) get maximum element
- Complete binary tree structure
- Parent larger than children
Array-based implementation of complete binary tree. Uses mathematical relationships between parent and child indices. Space-efficient and cache-friendly due to array storage.
- Array-based implementation
- Parent at i, children at 2i+1, 2i+2
- Complete tree property
- Cache-friendly memory layout
Linear Structures
Fixed-size sequential collection storing elements in contiguous memory locations. Provides constant-time access by index, making it the foundation for many algorithms and data structures.
- Fixed size at creation
- O(1) random access by index
- O(n) search in unsorted array
- Contiguous memory allocation
Dynamic collection of nodes connected by pointers, allowing efficient insertion and deletion at any position. Trades direct access for flexibility in size and structure modifications.
- Dynamic size - grows/shrinks easily
- O(1) insert/delete at known position
- O(n) search and random access
- Non-contiguous memory allocation
Last-In-First-Out (LIFO) structure supporting push and pop operations. Essential for function call management, parsing, and backtracking algorithms. Simple yet powerful for many sequential operations.
- LIFO principle
- O(1) push and pop operations
- Function call management
- Expression evaluation
First-In-First-Out (FIFO) structure for ordered processing. Critical for scheduling, breadth-first search, and managing resources. Ensures fair processing order in many applications.
- FIFO principle
- O(1) enqueue and dequeue
- Breadth-first traversal
- Task scheduling and ordering