Data structures and algorithms implemented from scratch with interactive Pygame visualizations for sorting and maze solving.
This repository contains clean, well-documented implementations of fundamental data structures and algorithms in Python. Each implementation is built from first principles without relying on built-in high-level abstractions, accompanied by comprehensive test suites and interactive visualizations.
All 19 data structures implemented with full test coverage:
| Category | Data Structure | Key Operations |
|---|---|---|
| Linear | Dynamic Array | O(1) amortized append, O(1) access |
| Singly Linked List | O(1) prepend, O(n) search | |
| Doubly Linked List | O(1) insert/delete at known position | |
| Stack | O(1) push/pop (LIFO) | |
| Queue | O(1) enqueue/dequeue (FIFO) | |
| Deque | O(1) operations at both ends | |
| Hash-based | Hash Map | O(1) average insert/lookup/delete |
| Hash Set | O(1) average membership testing | |
| Trees | Binary Tree | Tree traversals (inorder, preorder, postorder) |
| Binary Search Tree | O(log n) average operations | |
| AVL Tree | O(log n) guaranteed (self-balancing) | |
| Segment Tree | O(log n) range queries and updates | |
| Trie | O(k) prefix operations, k = key length | |
| Heaps | Min Heap / Max Heap | O(log n) insert, O(1) peek, O(log n) extract |
| Priority Queue | O(log n) operations via heap | |
| Graphs | Adjacency List | O(1) add edge, efficient for sparse graphs |
| Adjacency Matrix | O(1) edge lookup, O(V) add vertex | |
| Union-Find | Near O(1) with path compression | |
| Caching | LRU Cache | O(1) get/put with eviction |
Interactive visualization of 7 sorting algorithms with real-time animation, sound feedback, and performance metrics.
| Algorithm | Time Complexity | Space | Stable |
|---|---|---|---|
| Bubble Sort | O(n²) | O(1) | Yes |
| Insertion Sort | O(n²) | O(1) | Yes |
| Selection Sort | O(n²) | O(1) | No |
| Merge Sort | O(n log n) | O(n) | Yes |
| Quick Sort | O(n log n) avg | O(log n) | No |
| Heap Sort | O(n log n) | O(1) | No |
| Counting Sort | O(n + k) | O(k) | Yes |
- Single Mode: Watch one algorithm sort step-by-step
- Comparison Mode: Race two algorithms side-by-side on identical data
- Adjustable Speed: Control animation speed from slow analysis to fast execution
- Variable Data Size: Test with 25 to 1,000 elements
- Audio Feedback: Hear the sort with pitch mapped to bar heights
- Live Metrics: Track comparisons, swaps, and elapsed time
# Run the sorting visualizer
sorting-vizInteractive visualization of maze generation and pathfinding algorithms with animated step-by-step execution.
| Algorithm | Characteristics |
|---|---|
| Recursive Backtracking (DFS) | Long corridors, high "river" factor |
| Prim's Algorithm | Uniform, many short dead ends |
| Kruskal's Algorithm | Uniform distribution via Union-Find |
| Algorithm | Guarantees | Use Case |
|---|---|---|
| Depth-First Search | Finds a path | Memory-efficient exploration |
| Breadth-First Search | Shortest path (unweighted) | Optimal for uniform cost |
| Dijkstra's Algorithm | Shortest path (weighted) | General pathfinding |
| A* Search | Shortest path + heuristic | Efficient optimal pathfinding |
- Multiple Grid Sizes: Small (15x15) to Huge (101x101)
- Generation Animation: Watch mazes being carved in real-time
- Comparison Mode: Race two solving algorithms on identical mazes
- Visual Feedback: See visited cells, frontier, and final path
- Consistent Seeds: Reproducible mazes for fair algorithm comparison
# Run the maze visualizer
maze-viz# Clone the repository
git clone https://github.com/jwlutz/dsa_fundamentals.git
cd dsa_fundamentals
# Install with pip
pip install -e .
# Or install dependencies directly
pip install pygame numpy# Main menu (access both visualizers)
dsa-viz
# Direct access
sorting-viz
maze-vizfrom data_structures import (
DynamicArray, Stack, Queue,
HashMap, BinarySearchTree, AVLTree,
MinHeap, MaxHeap, Trie, UnionFind,
GraphAdjList, LRUCache
)
# Example: LRU Cache
cache = LRUCache(capacity=3)
cache.put("a", 1)
cache.put("b", 2)
cache.get("a") # Returns 1, marks "a" as recently used
cache.put("c", 3)
cache.put("d", 4) # Evicts "b" (least recently used)
# Example: Union-Find for connectivity
uf = UnionFind(10)
uf.union(0, 1)
uf.union(1, 2)
uf.connected(0, 2) # True
uf.connected(0, 3) # False# Run all tests
pytest tests/
# Run with coverage
pytest tests/ --cov=data_structuresdsa_fundamentals/
├── data_structures/ # Core implementations
│ ├── dynamic_array.py
│ ├── singly_linked_list.py
│ ├── doubly_linked_list.py
│ ├── stack.py
│ ├── queue.py
│ ├── deque.py
│ ├── hash_map.py
│ ├── hash_set.py
│ ├── binary_tree.py
│ ├── binary_search_tree.py
│ ├── avl_tree.py
│ ├── heap.py
│ ├── priority_queue.py
│ ├── trie.py
│ ├── segment_tree.py
│ ├── graph_adjacency_list.py
│ ├── graph_adjacency_matrix.py
│ ├── union_find.py
│ └── lru_cache.py
├── visualizers/ # Pygame visualizations
│ ├── main.py # Main menu launcher
│ ├── sorting_viz.py # Sorting algorithms
│ └── maze_viz.py # Maze generation & solving
├── tests/ # Unit tests
└── pyproject.toml
MIT License