A systematic study of fundamental data structures implemented from first principles, combining empirical benchmarking, correctness verification, and analytical evaluation of performance, scalability, and failure modes under realistic workloads.
- Dynamic Arrays
- Singly and Doubly Linked Lists
- Stack (Array-based and Linked List–based)
- Queue (Standard and Circular)
- Binary Search Tree
- Hash Table (Chaining and Open Addressing)
- Time complexity under different access patterns
- Space utilization and memory overhead
- Edge case handling and failure scenarios
- Performance degradation at scale
- Trade-offs between competing implementations
- Sequential vs random access
- High insertion vs high lookup workloads
- Small vs large input sizes
- Collision-heavy hash table cases
- Degenerate tree structures
structures/: Core data structure implementationstests/: Unit tests validating correctness and edge casesbenchmarks/: Performance benchmarking scriptsanalysis/: Written evaluation of time–space trade-offs and failuresresults/: Benchmark outputs and summarized findings
- Dynamic arrays outperform linked lists in most real-world access patterns despite worse insertion complexity.
- Poor hash functions drastically degrade hash table performance under skewed inputs.
- Unbalanced binary search trees collapse to linear performance without rebalancing.
Detailed discussions on time complexity, space trade-offs, and edge cases are available in the analysis/ directory.
pip install -r requirements.txt
python benchmarks/benchmark_hash_table.pyWhile theoretical complexity provides upper bounds, real systems are affected by cache locality, memory allocation, and access patterns. This project explores those practical realities through empirical measurement and structured analysis.
- Add self-balancing trees (AVL, Red-Black)
- Compare custom implementations to standard library equivalents
- Visualize memory usage and cache effects
- Port implementations to a lower-level language for comparison