Clean, from-scratch implementations of core data structures in Python, emphasizing:
- correctness and explicit invariants
- time and space tradeoffs
- tests that demonstrate expected behavior and edge cases
The goal is not to outperform Python's built-ins, but to make the internal behavior of these structures explicit, readable, and inspectable.
- DynamicArray (
ds.dynamic_array.DynamicArray)- append / pop
- insert / remove_at
- automatic growth (×2) with optional shrink (¼-full)
- Stack (
ds.stack.Stack)- LIFO stack implemented via composition over
DynamicArray
- LIFO stack implemented via composition over
- Queue (
ds.queue.Queue)- FIFO queue using a circular buffer (ring), amortized O(1) enqueue/dequeue
- BinarySearchTree (
ds.bst.BinarySearchTree)- insert / contains
- inorder (sorted), preorder, and postorder traversals (iterative)
| Structure | Operation | Time |
|---|---|---|
| DynamicArray | get / set | O(1) |
| DynamicArray | append | amortized O(1) |
| DynamicArray | insert / remove_at | O(n) |
| Stack | push / pop / peek | amortized O(1) |
| Queue (ring) | enqueue / dequeue / peek | amortized O(1) |
| BST (unbalanced) | insert / contains | O(h), worst-case O(n) |
Create and activate a virtual environment (macOS/Linux):
python3 -m venv .venv
source .venv/bin/activate
python3 -m pip install --upgrade pipInstall dependencies and run tests:
python3 -m pip install pytest
python3 -m pip install -e .
python3 -m pytest -q- These implementations are intentionally small and pedagogical.
- Each module maintains explicit invariants and is backed by tests.
- The focus is on clarity and fundamental tradeoffs rather than production optimization.