py-ds-academy 0.5.7

Data structures implemented from scratch for learning and experimentation.

py-ds-academy

A small playground project for implementing classic data structures from scratch in Python.

The goal is learning + correctness (with tests), not squeezing out every last micro-optimization.

---

🧱 Project Goals

• Implement core data structures from scratch in Python
• Use type hints, clean APIs, and unit tests
• Compare different implementations (e.g., list-backed vs linked)
• Practice algorithmic reasoning & complexity analysis

---

📦 Project Layout

py-ds-academy/
├─ pyproject.toml
├─ README.md
├─ .python-version
├─ src/
│  └── py_ds/
│     ├── __init__.py
│     └── datastructures/
│        ├── __init__.py
│        ├── stack.py
│        ├── queue.py
│        ├── heaps.py
│        ├── linked_lists/
│        │  ├── __init__.py
│        │  ├── base.py
│        │  ├── singly_linked.py
│        │  └── doubly_linked.py
│        └── trees/
│           ├── __init__.py
│           ├── base.py
│           ├── binary_search_tree.py
│           └── avl.py
└─ tests/
   ├─ test_stack.py
   ├─ test_queue.py
   ├─ test_linked_list.py
   ├─ test_doubly_linked_list.py
   ├─ test_max_heap.py
   ├─ test_min_heap.py
   ├─ test_binary_search_tree.py
   └─ test_avl_tree.py

All importable code lives under src/py_ds/.

---

🚀 Getting Started

Requires uv.

# create venv from .python-version
uv venv

# install dependencies (if any)
uv sync

# run tests
uv run pytest

You can also drop into a REPL:

uv run python

>>> from py_ds import Stack, Queue, SinglyLinkedList, DoublyLinkedList
>>> from py_ds import MinHeap, MaxHeap, BinarySearchTree, AVLTree

>>> # Stack example
>>> s = Stack([1, 2, 3])
>>> s.pop()
3

>>> # Queue example
>>> q = Queue([1, 2, 3])
>>> q.dequeue()
1

>>> # Linked List example
>>> ll = SinglyLinkedList([1, 2, 3])
>>> ll.append(4)
>>> list(ll)
[1, 2, 3, 4]

>>> # Heap example
>>> h = MinHeap([3, 1, 4, 1, 5])
>>> h.pop()
1

>>> # BST example
>>> bst = BinarySearchTree([5, 3, 7, 2, 4])
>>> list(bst.inorder())
[2, 3, 4, 5, 7]

---

📚 Data Structures Roadmap

1. Linear Structures

Stacks ✅

• Stack backed by Python list
• Operations: push, pop, peek, is_empty, __len__, clear, extend, to_list
• Iteration support (__iter__)

Queues ✅

• Queue backed by Python list
• Operations: enqueue, dequeue, peek, is_empty, __len__, clear, extend, to_list
• Iteration support (__iter__)

Linked Lists ✅

• SinglyLinkedList
  • append, prepend, insert, remove, pop, find
  • Iteration support (__iter__)
  • Indexing support (__getitem__, __setitem__)
  • head(), tail(), clear()
• DoublyLinkedList
  • Efficient O(1) append and prepend (with tail pointer)
  • Bidirectional traversal (__iter__, reverse_iter)
  • All operations from SinglyLinkedList
  • Optimized indexing with bidirectional search

---

2. Trees

Binary Tree (generic node-based) ✅

• BinaryTree base class with _BinaryNode
• Traversals:
  • Preorder (preorder())
  • Inorder (inorder())
  • Postorder (postorder())
  • Level-order / BFS (level_order())
• Tree height calculation
• Tree visualization (__str__)

Binary Search Tree (BST) ✅

• BinarySearchTree implementation
• Insert
• Search (__contains__)
• Delete (remove) - handles 0, 1, 2 children
• Find min / max (min(), max())
• Inherits all traversals from BinaryTree

Self-Balancing Trees ✅

• AVLTree - self-balancing BST
  • Automatic rebalancing on insert/remove
  • Rotations: left, right, left-right, right-left
  • Balance factor calculation
  • Inherits all BST operations

---

3. Heaps / Priority Queues ✅

Binary Heap

• Heap abstract base class
• MinHeap implementation
• MaxHeap implementation
• Operations: push, pop, peek
• Heap construction from iterable
• heapify_up and heapify_down operations
• Use cases: priority queue, heap sort

---

4. Hash-Based Structures

Hash Map

• Array of buckets
• Collision handling via chaining (linked lists) or open addressing
• Operations: get, set, delete, __contains__
• Basic resizing & load factor

Hash Set

• Built on top of HashMap
• Operations: add, remove, contains, iteration

---

5. Graphs

Graph Representations

• Adjacency list representation
• Optional: adjacency matrix

Algorithms

• BFS (breadth-first search)
• DFS (depth-first search)
• Path search (e.g. has_path(u, v))

Stretch:

• Topological sort
• Dijkstra’s algorithm (weighted graphs)

---

✨ Implemented Features Summary

The following data structures are fully implemented and tested:

• ✅ Stack - LIFO stack with list backing
• ✅ Queue - FIFO queue with list backing
• ✅ SinglyLinkedList - Single-direction linked list
• ✅ DoublyLinkedList - Double-direction linked list with O(1) append/prepend
• ✅ MinHeap - Minimum binary heap
• ✅ MaxHeap - Maximum binary heap
• ✅ BinarySearchTree - Binary search tree with insert, remove, search, min/max
• ✅ AVLTree - Self-balancing AVL tree (extends BST)

---

🧪 Testing

Each data structure gets its own test module under tests/.

Run the whole suite:

uv run pytest

---

🧠 Design Principles

• Prefer clear, readable code over cleverness
• Use type hints everywhere
• Raise the right built-in exceptions
• Document time complexity in docstrings

---

This project is mainly for learning + fun. No guarantees — just data structures implemented by hand.