Skip to content

README.md

Latest commit

 

History

History
200 lines (151 loc) · 5.61 KB

README.md

File metadata and controls

200 lines (151 loc) · 5.61 KB

Python DSA

CI Coverage Python License

Classic data structures and algorithms implemented from scratch in pure Python for learning purposes. Every implementation includes full type hints, ABC interfaces, __repr__/__str__/__eq__/__bool__ support, and comprehensive tests.

Table of Contents

Data Structures

All structures implement common Python protocols: len(), in, bool(), ==, repr(), str(), iteration.

Arrays

Implementation Description Access Append Insert/Remove
StaticArray Fixed-capacity array O(1) O(1) O(n)
DynamicArray Auto-resizing array (2x growth, 1/4 shrink) O(1) O(1)* O(n)

* amortised

Features: negative indexing, slicing (arr[1:3], arr[::-1]), *args construction.

from data_structures.array.static_array import StaticArray
from data_structures.array.dynamic_array import DynamicArray

# Static array — fixed capacity
sa = StaticArray(1, 2, 3)
sa[0]              # 1
sa[-1]             # 3
sa[::2]            # [1, 3]

# Dynamic array — grows and shrinks automatically
da = DynamicArray(1, 2, 3, 4, 5)
str(da)            # "[1, 2, 3, 4, 5]"
da[::-1]           # [5, 4, 3, 2, 1]
da == StaticArray(1, 2, 3, 4, 5)  # True (cross-type equality)

Linked Lists

Implementation Description Push/Pop Front Push/Pop Back
SinglyLinkedList Forward-only traversal O(1) —
DoublyLinkedList Bidirectional traversal O(1) O(1)

Features: reversed() for DoublyLinkedList, cross-type equality, arrow-notation str().

from data_structures.linked_list import SinglyLinkedList, DoublyLinkedList

sll = SinglyLinkedList()
sll.push_front(1)
sll.push_front(2)
str(sll)               # "2 -> 1"

dll = DoublyLinkedList()
dll.push_back(1)
dll.push_back(2)
dll.push_back(3)
str(dll)               # "1 <-> 2 <-> 3"
list(reversed(dll))    # [3, 2, 1]

sll == dll             # True (same elements in same order)

Stacks

Implementation Description Push Pop Peek
ArrayStack Backed by DynamicArray O(1)* O(1)* O(1)
LinkedListStack Backed by SinglyLinkedList O(1) O(1) O(1)
MinStack ArrayStack + O(1) get_min() O(1)* O(1)* O(1)

* amortised

Features: cross-type equality, top-to-bottom str() display.

from data_structures.stack.array_stack import ArrayStack
from data_structures.stack.linked_list_stack import LinkedListStack
from data_structures.stack.min_stack import MinStack

s = ArrayStack()
s.push(1); s.push(2); s.push(3)
str(s)             # "3 -> 2 -> 1"
s.peek()           # 3
s.pop()            # 3
bool(s)            # True

ms = MinStack()
for v in [5, 3, 7, 1]:
    ms.push(v)
ms.get_min()       # 1

Algorithms

Searching

Algorithm Time Space Description
binary_search O(log n) O(1) Index of target in sorted sequence, or -1
lower_bound O(log n) O(1) Index of first element >= target
upper_bound O(log n) O(1) Index of first element > target

Works with any indexable collection (list, StaticArray, DynamicArray).

from algorithms.searching.binary_search import binary_search, lower_bound, upper_bound

binary_search([1, 3, 5, 7, 9], 5)  # 2
binary_search([1, 3, 5, 7, 9], 4)  # -1

lower_bound([1, 3, 3, 3, 5], 3)    # 1  (first >= 3)
upper_bound([1, 3, 3, 3, 5], 3)    # 4  (first > 3)

Getting Started

Requirements: Python >= 3.13, uv

git clone https://github.com/azizjon-aliev/python-dsa.git
cd python-dsa
uv sync --group dev
uv run pre-commit install

Testing

# Unit tests with coverage (248 tests, 97% coverage)
uv run pytest tests/ -v

# Property-based tests (hypothesis)
uv run pytest tests/test_properties.py -v

# Benchmarks
uv run pytest tests/test_benchmarks.py --benchmark-enable --no-cov

# Doctests
uv run pytest --doctest-modules data_structures/ algorithms/ --no-cov

# Lint, format, type check
uv run ruff check . && uv run ruff format --check . && uv run ty check

Project Structure

data_structures/
  array/
    base.py              # IArray ABC
    static_array.py      # StaticArray
    dynamic_array.py     # DynamicArray
  stack/
    base.py              # IStack ABC, StackEmptyError
    array_stack.py       # ArrayStack
    linked_list_stack.py # LinkedListStack
    min_stack.py         # MinStack
  linked_list/
    base.py              # ISinglyLinkedList, IDoublyLinkedList ABCs
    singly_linked_list.py
    doubly_linked_list.py
algorithms/
  searching/
    binary_search.py     # binary_search, lower_bound, upper_bound
tests/
  test_arrays.py         # Array unit tests
  test_stacks.py         # Stack unit tests
  test_linked_lists.py   # Linked list unit tests
  test_binary_search.py  # Binary search unit tests
  test_benchmarks.py     # Performance benchmarks (pytest-benchmark)
  test_properties.py     # Property-based tests (hypothesis)

Contributing

See CONTRIBUTING.md for guidelines.

License

MIT