Data Structures (Python)

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.

Implemented

• 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
• 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)

Complexity (typical)

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)

Setup

Create and activate a virtual environment (macOS/Linux):

python3 -m venv .venv
source .venv/bin/activate
python3 -m pip install --upgrade pip

Install dependencies and run tests:

python3 -m pip install pytest
python3 -m pip install -e .
python3 -m pytest -q

Notes

• 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.