Skip to content

Data Structures (alnoms.dsa.structures)

Low-latency, memory-efficient structures designed for high-scale environments.

📏 Linear Structures

Bag (Unordered Collection).

Defines a lightweight collection type that supports insertion but does not support removal. A Bag is useful for collecting items and iterating over them without imposing any ordering guarantees. Internally, the Bag is backed by a singly linked list, enabling O(1) insertion.

Design Characteristics: - Unordered collection - O(1) insertion at the front - O(N) iteration - No removal operations

Classes:

Name Description
Bag

A simple unordered collection supporting fast insertion.

Bag

Bases: Generic[T]

An unordered collection supporting fast insertion.

Items are stored in a singly linked list. The Bag does not support removal; its purpose is to collect items and allow iteration over them. The iteration order is LIFO due to front insertion, but the order is not semantically meaningful.

Source code in src/alnoms/dsa/structures/bag.py 
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
class Bag(Generic[T]):
    """An unordered collection supporting fast insertion.

    Items are stored in a singly linked list. The Bag does not support
    removal; its purpose is to collect items and allow iteration over
    them. The iteration order is LIFO due to front insertion, but the
    order is not semantically meaningful.
    """

    def __init__(self):
        """Initializes an empty Bag.

        Attributes:
            _first (Optional[Node]): Reference to the first node.
            _n (int): Number of items stored.
        """
        self._first: Optional[Node] = None
        self._n: int = 0

    def is_empty(self) -> bool:
        """Checks whether the Bag is empty.

        Returns:
            bool: True if the Bag contains no items.
        """
        return self._first is None

    def size(self) -> int:
        """Returns the number of items in the Bag.

        Returns:
            int: Total number of stored items.
        """
        return self._n

    def add(self, item: T) -> None:
        """Adds an item to the Bag.

        This operation runs in O(1) time by inserting the new item at the
        front of the linked list.

        Args:
            item (T): The item to add.
        """
        old_first = self._first
        self._first = Node(item)
        self._first.next = old_first
        self._n += 1

    def __iter__(self) -> Iterator[T]:
        """Iterates over the items in the Bag.

        Yields:
            T: Items stored in the Bag. Order is LIFO but not meaningful.
        """
        current = self._first
        while current:
            yield current.data
            current = current.next
__init__()

Initializes an empty Bag.

Attributes:

Name Type Description
_first Optional[Node]

Reference to the first node.
_n int

Number of items stored.
Source code in src/alnoms/dsa/structures/bag.py 
34
35
36
37
38
39
40
41
42
def __init__(self):
    """Initializes an empty Bag.

    Attributes:
        _first (Optional[Node]): Reference to the first node.
        _n (int): Number of items stored.
    """
    self._first: Optional[Node] = None
    self._n: int = 0
__iter__()

Iterates over the items in the Bag.

Yields:

Name Type Description
T T

Items stored in the Bag. Order is LIFO but not meaningful.
Source code in src/alnoms/dsa/structures/bag.py 
74
75
76
77
78
79
80
81
82
83
def __iter__(self) -> Iterator[T]:
    """Iterates over the items in the Bag.

    Yields:
        T: Items stored in the Bag. Order is LIFO but not meaningful.
    """
    current = self._first
    while current:
        yield current.data
        current = current.next
add(item)

Adds an item to the Bag.

This operation runs in O(1) time by inserting the new item at the front of the linked list.

Parameters:

Name Type Description Default
item T

The item to add.

 required
Source code in src/alnoms/dsa/structures/bag.py 
60
61
62
63
64
65
66
67
68
69
70
71
72
def add(self, item: T) -> None:
    """Adds an item to the Bag.

    This operation runs in O(1) time by inserting the new item at the
    front of the linked list.

    Args:
        item (T): The item to add.
    """
    old_first = self._first
    self._first = Node(item)
    self._first.next = old_first
    self._n += 1
is_empty()

Checks whether the Bag is empty.

Returns:

Name Type Description
bool bool

True if the Bag contains no items.
Source code in src/alnoms/dsa/structures/bag.py 
44
45
46
47
48
49
50
def is_empty(self) -> bool:
    """Checks whether the Bag is empty.

    Returns:
        bool: True if the Bag contains no items.
    """
    return self._first is None
size()

Returns the number of items in the Bag.

Returns:

Name Type Description
int int

Total number of stored items.
Source code in src/alnoms/dsa/structures/bag.py 
52
53
54
55
56
57
58
def size(self) -> int:
    """Returns the number of items in the Bag.

    Returns:
        int: Total number of stored items.
    """
    return self._n

Alnoms Data Structure: FIFO Queue (Linked‑List Backed).

Provides a generic, type‑safe FIFO (First‑In First‑Out) queue implementation using a singly linked list with explicit head and tail references. This design guarantees O(1) enqueue and dequeue operations without requiring array resizing or circular‑buffer bookkeeping.

The queue supports:

  • O(1) enqueue at the tail
  • O(1) dequeue from the head
  • Safe iteration from front to back
  • Deterministic memory behavior with no hidden reallocations

This module is part of the Alnoms OSS data‑structures suite and is optimized for teaching, benchmarking, and algorithmic experimentation. All operations are implemented with predictable worst‑case complexity.

Queue

Bases: Generic[T]

A FIFO (First‑In First‑Out) queue implemented using a linked list.

This implementation maintains references to both the head (_first) and tail (_last) nodes, ensuring O(1) enqueue and dequeue operations. The queue grows dynamically without requiring array resizing, making it suitable for workloads requiring predictable constant‑time behavior.

Source code in src/alnoms/dsa/structures/queue.py 
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
class Queue(Generic[T]):
    """A FIFO (First‑In First‑Out) queue implemented using a linked list.

    This implementation maintains references to both the head (``_first``)
    and tail (``_last``) nodes, ensuring O(1) enqueue and dequeue
    operations. The queue grows dynamically without requiring array
    resizing, making it suitable for workloads requiring predictable
    constant‑time behavior.
    """

    def __init__(self):
        """Initializes an empty queue.

        Attributes:
            _first (Optional[Node]): Reference to the front of the queue.
            _last (Optional[Node]): Reference to the end of the queue.
            _n (int): Number of items currently stored.
        """
        self._first: Optional[Node] = None
        self._last: Optional[Node] = None
        self._n: int = 0

    def is_empty(self) -> bool:
        """Checks whether the queue is empty.

        Returns:
            bool: True if the queue contains no items, otherwise False.
        """
        return self._first is None

    def size(self) -> int:
        """Returns the number of items in the queue.

        Returns:
            int: The number of elements stored.
        """
        return self._n

    def enqueue(self, item: T) -> None:
        """Adds an item to the end of the queue.

        This operation runs in O(1) time by inserting a new node at the
        tail of the linked list.

        Args:
            item (T): The item to add to the queue.
        """
        old_last = self._last
        self._last = Node(item)
        self._last.next = None

        if self.is_empty():
            self._first = self._last
        else:
            old_last.next = self._last

        self._n += 1

    def dequeue(self) -> T:
        """Removes and returns the item at the front of the queue.

        This operation runs in O(1) time by removing the head node.

        Returns:
            T: The item previously at the front of the queue.

        Raises:
            IndexError: If the queue is empty.
        """
        if self.is_empty():
            raise IndexError("Queue underflow")

        item = self._first.data
        self._first = self._first.next
        self._n -= 1

        if self.is_empty():
            self._last = None  # Avoid loitering

        return item

    def peek(self) -> T:
        """Returns the item at the front of the queue without removing it.

        Returns:
            T: The item currently at the front.

        Raises:
            IndexError: If the queue is empty.
        """
        if self.is_empty():
            raise IndexError("Queue underflow")
        return self._first.data

    def __iter__(self) -> Iterator[T]:
        """Iterates over the queue from front to back.

        Yields:
            T: Items in FIFO order, starting from the front.
        """
        current = self._first
        while current:
            yield current.data
            current = current.next
__init__()

Initializes an empty queue.

Attributes:

Name Type Description
_first Optional[Node]

Reference to the front of the queue.
_last Optional[Node]

Reference to the end of the queue.
_n int

Number of items currently stored.
Source code in src/alnoms/dsa/structures/queue.py 
37
38
39
40
41
42
43
44
45
46
47
def __init__(self):
    """Initializes an empty queue.

    Attributes:
        _first (Optional[Node]): Reference to the front of the queue.
        _last (Optional[Node]): Reference to the end of the queue.
        _n (int): Number of items currently stored.
    """
    self._first: Optional[Node] = None
    self._last: Optional[Node] = None
    self._n: int = 0
__iter__()

Iterates over the queue from front to back.

Yields:

Name Type Description
T T

Items in FIFO order, starting from the front.
Source code in src/alnoms/dsa/structures/queue.py 
121
122
123
124
125
126
127
128
129
130
def __iter__(self) -> Iterator[T]:
    """Iterates over the queue from front to back.

    Yields:
        T: Items in FIFO order, starting from the front.
    """
    current = self._first
    while current:
        yield current.data
        current = current.next
dequeue()

Removes and returns the item at the front of the queue.

This operation runs in O(1) time by removing the head node.

Returns:

Name Type Description
T T

The item previously at the front of the queue.

Raises:

Type Description
IndexError

If the queue is empty.
Source code in src/alnoms/dsa/structures/queue.py 
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
def dequeue(self) -> T:
    """Removes and returns the item at the front of the queue.

    This operation runs in O(1) time by removing the head node.

    Returns:
        T: The item previously at the front of the queue.

    Raises:
        IndexError: If the queue is empty.
    """
    if self.is_empty():
        raise IndexError("Queue underflow")

    item = self._first.data
    self._first = self._first.next
    self._n -= 1

    if self.is_empty():
        self._last = None  # Avoid loitering

    return item
enqueue(item)

Adds an item to the end of the queue.

This operation runs in O(1) time by inserting a new node at the tail of the linked list.

Parameters:

Name Type Description Default
item T

The item to add to the queue.

 required
Source code in src/alnoms/dsa/structures/queue.py 
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
def enqueue(self, item: T) -> None:
    """Adds an item to the end of the queue.

    This operation runs in O(1) time by inserting a new node at the
    tail of the linked list.

    Args:
        item (T): The item to add to the queue.
    """
    old_last = self._last
    self._last = Node(item)
    self._last.next = None

    if self.is_empty():
        self._first = self._last
    else:
        old_last.next = self._last

    self._n += 1
is_empty()

Checks whether the queue is empty.

Returns:

Name Type Description
bool bool

True if the queue contains no items, otherwise False.
Source code in src/alnoms/dsa/structures/queue.py 
49
50
51
52
53
54
55
def is_empty(self) -> bool:
    """Checks whether the queue is empty.

    Returns:
        bool: True if the queue contains no items, otherwise False.
    """
    return self._first is None
peek()

Returns the item at the front of the queue without removing it.

Returns:

Name Type Description
T T

The item currently at the front.

Raises:

Type Description
IndexError

If the queue is empty.
Source code in src/alnoms/dsa/structures/queue.py 
108
109
110
111
112
113
114
115
116
117
118
119
def peek(self) -> T:
    """Returns the item at the front of the queue without removing it.

    Returns:
        T: The item currently at the front.

    Raises:
        IndexError: If the queue is empty.
    """
    if self.is_empty():
        raise IndexError("Queue underflow")
    return self._first.data
size()

Returns the number of items in the queue.

Returns:

Name Type Description
int int

The number of elements stored.
Source code in src/alnoms/dsa/structures/queue.py 
57
58
59
60
61
62
63
def size(self) -> int:
    """Returns the number of items in the queue.

    Returns:
        int: The number of elements stored.
    """
    return self._n

Linked-List-Based Stack.

Implements a generic LIFO (Last-In First-Out) stack using a linked list backing. This design guarantees O(1) worst-case push and pop operations by avoiding array resizing and capacity management.

Features
  • O(1) push and pop
  • Dynamic, node-based storage
  • Type-parameterized (generic) API
  • Safe iteration from top to bottom

Stack

Bases: Generic[T]

A LIFO (Last‑In First‑Out) stack implemented using a linked list.

This implementation guarantees O(1) worst‑case time for both push and pop operations by avoiding the resizing overhead associated with array‑based stacks. The stack grows dynamically through linked nodes, making it suitable for workloads requiring predictable constant‑time operations.

Source code in src/alnoms/dsa/structures/stack.py 
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
class Stack(Generic[T]):
    """A LIFO (Last‑In First‑Out) stack implemented using a linked list.

    This implementation guarantees O(1) worst‑case time for both `push`
    and `pop` operations by avoiding the resizing overhead associated
    with array‑based stacks. The stack grows dynamically through linked
    nodes, making it suitable for workloads requiring predictable
    constant‑time operations.
    """

    def __init__(self):
        """Initializes an empty stack.

        Attributes:
            _first (Optional[Node]): Reference to the top node.
            _n (int): Number of items currently stored.
        """
        self._first: Optional[Node] = None
        self._n: int = 0

    def is_empty(self) -> bool:
        """Checks whether the stack is empty.

        Returns:
            bool: True if the stack contains no items, otherwise False.
        """
        return self._first is None

    def size(self) -> int:
        """Returns the number of items in the stack.

        Returns:
            int: The number of elements stored.
        """
        return self._n

    def push(self, item: T) -> None:
        """Pushes an item onto the top of the stack.

        This operation runs in O(1) time by inserting a new node at the
        head of the linked list.

        Args:
            item (T): The item to push onto the stack.
        """
        old_first = self._first
        self._first = Node(item)
        self._first.next = old_first
        self._n += 1

    def pop(self) -> T:
        """Removes and returns the most recently added item.

        This operation runs in O(1) time by removing the head node.

        Returns:
            T: The item previously at the top of the stack.

        Raises:
            IndexError: If the stack is empty.
        """
        if self.is_empty():
            raise IndexError("Stack underflow")

        item = self._first.data
        self._first = self._first.next
        self._n -= 1
        return item

    def peek(self) -> T:
        """Returns the item at the top of the stack without removing it.

        Returns:
            T: The item currently at the top.

        Raises:
            IndexError: If the stack is empty.
        """
        if self.is_empty():
            raise IndexError("Stack underflow")
        return self._first.data

    def __iter__(self) -> Iterator[T]:
        """Iterates over the stack from top to bottom.

        Yields:
            T: Items in LIFO order, starting from the top.
        """
        current = self._first
        while current:
            yield current.data
            current = current.next
__init__()

Initializes an empty stack.

Attributes:

Name Type Description
_first Optional[Node]

Reference to the top node.
_n int

Number of items currently stored.
Source code in src/alnoms/dsa/structures/stack.py 
31
32
33
34
35
36
37
38
39
def __init__(self):
    """Initializes an empty stack.

    Attributes:
        _first (Optional[Node]): Reference to the top node.
        _n (int): Number of items currently stored.
    """
    self._first: Optional[Node] = None
    self._n: int = 0
__iter__()

Iterates over the stack from top to bottom.

Yields:

Name Type Description
T T

Items in LIFO order, starting from the top.
Source code in src/alnoms/dsa/structures/stack.py 
103
104
105
106
107
108
109
110
111
112
def __iter__(self) -> Iterator[T]:
    """Iterates over the stack from top to bottom.

    Yields:
        T: Items in LIFO order, starting from the top.
    """
    current = self._first
    while current:
        yield current.data
        current = current.next
is_empty()

Checks whether the stack is empty.

Returns:

Name Type Description
bool bool

True if the stack contains no items, otherwise False.
Source code in src/alnoms/dsa/structures/stack.py 
41
42
43
44
45
46
47
def is_empty(self) -> bool:
    """Checks whether the stack is empty.

    Returns:
        bool: True if the stack contains no items, otherwise False.
    """
    return self._first is None
peek()

Returns the item at the top of the stack without removing it.

Returns:

Name Type Description
T T

The item currently at the top.

Raises:

Type Description
IndexError

If the stack is empty.
Source code in src/alnoms/dsa/structures/stack.py 
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
def peek(self) -> T:
    """Returns the item at the top of the stack without removing it.

    Returns:
        T: The item currently at the top.

    Raises:
        IndexError: If the stack is empty.
    """
    if self.is_empty():
        raise IndexError("Stack underflow")
    return self._first.data
pop()

Removes and returns the most recently added item.

This operation runs in O(1) time by removing the head node.

Returns:

Name Type Description
T T

The item previously at the top of the stack.

Raises:

Type Description
IndexError

If the stack is empty.
Source code in src/alnoms/dsa/structures/stack.py 
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
def pop(self) -> T:
    """Removes and returns the most recently added item.

    This operation runs in O(1) time by removing the head node.

    Returns:
        T: The item previously at the top of the stack.

    Raises:
        IndexError: If the stack is empty.
    """
    if self.is_empty():
        raise IndexError("Stack underflow")

    item = self._first.data
    self._first = self._first.next
    self._n -= 1
    return item
push(item)

Pushes an item onto the top of the stack.

This operation runs in O(1) time by inserting a new node at the head of the linked list.

Parameters:

Name Type Description Default
item T

The item to push onto the stack.

 required
Source code in src/alnoms/dsa/structures/stack.py 
57
58
59
60
61
62
63
64
65
66
67
68
69
def push(self, item: T) -> None:
    """Pushes an item onto the top of the stack.

    This operation runs in O(1) time by inserting a new node at the
    head of the linked list.

    Args:
        item (T): The item to push onto the stack.
    """
    old_first = self._first
    self._first = Node(item)
    self._first.next = old_first
    self._n += 1
size()

Returns the number of items in the stack.

Returns:

Name Type Description
int int

The number of elements stored.
Source code in src/alnoms/dsa/structures/stack.py 
49
50
51
52
53
54
55
def size(self) -> int:
    """Returns the number of items in the stack.

    Returns:
        int: The number of elements stored.
    """
    return self._n

Singly Linked List (Foundational Data Structure).

Provides a minimal, textbook‑grade implementation of a singly linked list supporting O(1) insertions at the head and linear‑time traversal. This structure is useful for workloads requiring predictable insertion performance without the resizing overhead of array‑backed lists.

Features

• O(1) insertion at the head • Linear‑time traversal and search • Node‑based dynamic memory allocation • Pythonic iteration support

This module is part of the Alnoms Data Structures suite and is designed for clarity, determinism, and mkdocstrings‑compatible documentation.

SinglyLinkedList

A foundational singly linked list implementation.

This structure supports O(1) insertions at the head and linear-time traversal from head to tail. It is suitable for workloads requiring predictable insertion performance without the resizing overhead of array-backed lists.

Source code in src/alnoms/dsa/structures/singly_linked_list.py 
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
class SinglyLinkedList:
    """A foundational singly linked list implementation.

    This structure supports O(1) insertions at the head and linear-time
    traversal from head to tail. It is suitable for workloads requiring
    predictable insertion performance without the resizing overhead of
    array-backed lists.
    """

    def __init__(self):
        """Initializes an empty singly linked list.

        Attributes:
            head (Optional[Node]): Reference to the first node in the list.
            _size (int): Number of nodes currently stored.
        """
        self.head: Optional[Node] = None
        self._size: int = 0

    def __len__(self) -> int:
        """Returns the number of nodes in the list.

        Returns:
            int: The total number of elements.
        """
        return self._size

    def __iter__(self) -> Iterator[Any]:
        """Iterates through the list from head to tail.

        Yields:
            Any: The data stored in each node.
        """
        current = self.head
        while current:
            yield current.data
            current = current.next

    def is_empty(self) -> bool:
        """Checks whether the list contains any elements.

        Returns:
            bool: True if the list is empty, otherwise False.
        """
        return self.head is None

    def insert_at_head(self, data: Any) -> None:
        """Inserts a new node at the beginning of the list.

        This operation runs in O(1) time by updating the head pointer.

        Args:
            data (Any): The value to insert.
        """
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
        self._size += 1

    def append(self, data: Any) -> None:
        """Appends a new node to the end of the list.

        This operation runs in O(N) time due to the need to traverse
        to the tail.

        Args:
            data (Any): The value to append.
        """
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            self._size += 1
            return

        current = self.head
        while current.next:
            current = current.next

        current.next = new_node
        self._size += 1

    def remove(self, data: Any) -> bool:
        """Removes the first occurrence of a value from the list.

        This operation runs in O(N) time due to linear search.

        Args:
            data (Any): The value to remove.

        Returns:
            bool: True if a node was removed, otherwise False.
        """
        if not self.head:
            return False

        if self.head.data == data:
            self.head = self.head.next
            self._size -= 1
            return True

        current = self.head
        while current.next:
            if current.next.data == data:
                current.next = current.next.next
                self._size -= 1
                return True
            current = current.next

        return False

    def display(self) -> str:
        """Returns a string representation of the list.

        Useful for debugging and visualization.

        Returns:
            str: A formatted representation such as ``"1 -> 2 -> NULL"``.
        """
        elements = [str(data) for data in self]
        return " -> ".join(elements) + " -> NULL" if elements else "EMPTY"
__init__()

Initializes an empty singly linked list.

Attributes:

Name Type Description
head Optional[Node]

Reference to the first node in the list.
_size int

Number of nodes currently stored.
Source code in src/alnoms/dsa/structures/singly_linked_list.py 
34
35
36
37
38
39
40
41
42
def __init__(self):
    """Initializes an empty singly linked list.

    Attributes:
        head (Optional[Node]): Reference to the first node in the list.
        _size (int): Number of nodes currently stored.
    """
    self.head: Optional[Node] = None
    self._size: int = 0
__iter__()

Iterates through the list from head to tail.

Yields:

Name Type Description
Any Any

The data stored in each node.
Source code in src/alnoms/dsa/structures/singly_linked_list.py 
52
53
54
55
56
57
58
59
60
61
def __iter__(self) -> Iterator[Any]:
    """Iterates through the list from head to tail.

    Yields:
        Any: The data stored in each node.
    """
    current = self.head
    while current:
        yield current.data
        current = current.next
__len__()

Returns the number of nodes in the list.

Returns:

Name Type Description
int int

The total number of elements.
Source code in src/alnoms/dsa/structures/singly_linked_list.py 
44
45
46
47
48
49
50
def __len__(self) -> int:
    """Returns the number of nodes in the list.

    Returns:
        int: The total number of elements.
    """
    return self._size
append(data)

Appends a new node to the end of the list.

This operation runs in O(N) time due to the need to traverse to the tail.

Parameters:

Name Type Description Default
data Any

The value to append.

 required
Source code in src/alnoms/dsa/structures/singly_linked_list.py 
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
def append(self, data: Any) -> None:
    """Appends a new node to the end of the list.

    This operation runs in O(N) time due to the need to traverse
    to the tail.

    Args:
        data (Any): The value to append.
    """
    new_node = Node(data)
    if not self.head:
        self.head = new_node
        self._size += 1
        return

    current = self.head
    while current.next:
        current = current.next

    current.next = new_node
    self._size += 1
display()

Returns a string representation of the list.

Useful for debugging and visualization.

Returns:

Name Type Description
str str

A formatted representation such as "1 -> 2 -> NULL".
Source code in src/alnoms/dsa/structures/singly_linked_list.py 
135
136
137
138
139
140
141
142
143
144
def display(self) -> str:
    """Returns a string representation of the list.

    Useful for debugging and visualization.

    Returns:
        str: A formatted representation such as ``"1 -> 2 -> NULL"``.
    """
    elements = [str(data) for data in self]
    return " -> ".join(elements) + " -> NULL" if elements else "EMPTY"
insert_at_head(data)

Inserts a new node at the beginning of the list.

This operation runs in O(1) time by updating the head pointer.

Parameters:

Name Type Description Default
data Any

The value to insert.

 required
Source code in src/alnoms/dsa/structures/singly_linked_list.py 
71
72
73
74
75
76
77
78
79
80
81
82
def insert_at_head(self, data: Any) -> None:
    """Inserts a new node at the beginning of the list.

    This operation runs in O(1) time by updating the head pointer.

    Args:
        data (Any): The value to insert.
    """
    new_node = Node(data)
    new_node.next = self.head
    self.head = new_node
    self._size += 1
is_empty()

Checks whether the list contains any elements.

Returns:

Name Type Description
bool bool

True if the list is empty, otherwise False.
Source code in src/alnoms/dsa/structures/singly_linked_list.py 
63
64
65
66
67
68
69
def is_empty(self) -> bool:
    """Checks whether the list contains any elements.

    Returns:
        bool: True if the list is empty, otherwise False.
    """
    return self.head is None
remove(data)

Removes the first occurrence of a value from the list.

This operation runs in O(N) time due to linear search.

Parameters:

Name Type Description Default
data Any

The value to remove.

 required

Returns:

Name Type Description
bool bool

True if a node was removed, otherwise False.
Source code in src/alnoms/dsa/structures/singly_linked_list.py 
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
def remove(self, data: Any) -> bool:
    """Removes the first occurrence of a value from the list.

    This operation runs in O(N) time due to linear search.

    Args:
        data (Any): The value to remove.

    Returns:
        bool: True if a node was removed, otherwise False.
    """
    if not self.head:
        return False

    if self.head.data == data:
        self.head = self.head.next
        self._size -= 1
        return True

    current = self.head
    while current.next:
        if current.next.data == data:
            current.next = current.next.next
            self._size -= 1
            return True
        current = current.next

    return False

Doubly Linked List.

Provides a bidirectional linked list supporting O(1) insertion at both the head and tail. Each node maintains references to its predecessor and successor, enabling efficient traversal and structural updates.

Design Characteristics: - Bidirectional traversal - O(1) prepend and append - O(N) search and removal - Deterministic memory behavior

Classes:

Name Description
DoublyLinkedList

A doubly linked list supporting head/tail operations.

DoublyLinkedList

Bases: Generic[T]

A doubly linked list supporting bidirectional traversal.

The list maintains references to both the head and tail nodes, enabling O(1) insertion at either end. Removal of arbitrary values runs in O(N) time due to linear search.

Source code in src/alnoms/dsa/structures/doubly_linked_list.py 
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
class DoublyLinkedList(Generic[T]):
    """A doubly linked list supporting bidirectional traversal.

    The list maintains references to both the head and tail nodes,
    enabling O(1) insertion at either end. Removal of arbitrary values
    runs in O(N) time due to linear search.
    """

    def __init__(self):
        """Initializes an empty doubly linked list.

        Attributes:
            head (Optional[DoublyNode]): First node in the list.
            tail (Optional[DoublyNode]): Last node in the list.
            _size (int): Number of nodes in the list.
        """
        self.head: Optional[DoublyNode] = None
        self.tail: Optional[DoublyNode] = None
        self._size: int = 0

    def __len__(self) -> int:
        """Returns the number of nodes in the list.

        Returns:
            int: The size of the list.
        """
        return self._size

    def __iter__(self) -> Iterator[Any]:
        """Iterates through the list from head to tail.

        Yields:
            Any: The data stored in each node.
        """
        current = self.head
        while current:
            yield current.data
            current = current.next

    def is_empty(self) -> bool:
        """Checks whether the list is empty.

        Returns:
            bool: True if the list contains no elements.
        """
        return self.head is None

    def append(self, data: Any) -> None:
        """Appends a node to the end of the list.

        This operation runs in O(1) time.

        Args:
            data (Any): The value to append.
        """
        new_node = DoublyNode(data)

        if not self.head:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.prev = self.tail
            if self.tail:
                self.tail.next = new_node
            self.tail = new_node

        self._size += 1

    def prepend(self, data: Any) -> None:
        """Inserts a node at the beginning of the list.

        This operation runs in O(1) time.

        Args:
            data (Any): The value to prepend.
        """
        new_node = DoublyNode(data)

        if not self.head:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node

        self._size += 1

    def remove(self, data: Any) -> bool:
        """Removes the first occurrence of a specific value.

        This operation runs in O(N) time due to linear search.

        Args:
            data (Any): The value to remove.

        Returns:
            bool: True if a node was removed, otherwise False.
        """
        current = self.head

        while current:
            if current.data == data:
                # Update previous link
                if current.prev:
                    current.prev.next = current.next
                else:
                    self.head = current.next

                # Update next link
                if current.next:
                    current.next.prev = current.prev
                else:
                    self.tail = current.prev

                self._size -= 1
                return True

            current = current.next

        return False

    def display_forward(self) -> str:
        """Returns a string representation from head to tail.

        Returns:
            str: A formatted representation of the list.
        """
        elements = [str(data) for data in self]
        return " <-> ".join(elements) if elements else "EMPTY"
__init__()

Initializes an empty doubly linked list.

Attributes:

Name Type Description
head Optional[DoublyNode]

First node in the list.
tail Optional[DoublyNode]

Last node in the list.
_size int

Number of nodes in the list.
Source code in src/alnoms/dsa/structures/doubly_linked_list.py 
32
33
34
35
36
37
38
39
40
41
42
def __init__(self):
    """Initializes an empty doubly linked list.

    Attributes:
        head (Optional[DoublyNode]): First node in the list.
        tail (Optional[DoublyNode]): Last node in the list.
        _size (int): Number of nodes in the list.
    """
    self.head: Optional[DoublyNode] = None
    self.tail: Optional[DoublyNode] = None
    self._size: int = 0
__iter__()

Iterates through the list from head to tail.

Yields:

Name Type Description
Any Any

The data stored in each node.
Source code in src/alnoms/dsa/structures/doubly_linked_list.py 
52
53
54
55
56
57
58
59
60
61
def __iter__(self) -> Iterator[Any]:
    """Iterates through the list from head to tail.

    Yields:
        Any: The data stored in each node.
    """
    current = self.head
    while current:
        yield current.data
        current = current.next
__len__()

Returns the number of nodes in the list.

Returns:

Name Type Description
int int

The size of the list.
Source code in src/alnoms/dsa/structures/doubly_linked_list.py 
44
45
46
47
48
49
50
def __len__(self) -> int:
    """Returns the number of nodes in the list.

    Returns:
        int: The size of the list.
    """
    return self._size
append(data)

Appends a node to the end of the list.

This operation runs in O(1) time.

Parameters:

Name Type Description Default
data Any

The value to append.

 required
Source code in src/alnoms/dsa/structures/doubly_linked_list.py 
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
def append(self, data: Any) -> None:
    """Appends a node to the end of the list.

    This operation runs in O(1) time.

    Args:
        data (Any): The value to append.
    """
    new_node = DoublyNode(data)

    if not self.head:
        self.head = new_node
        self.tail = new_node
    else:
        new_node.prev = self.tail
        if self.tail:
            self.tail.next = new_node
        self.tail = new_node

    self._size += 1
display_forward()

Returns a string representation from head to tail.

Returns:

Name Type Description
str str

A formatted representation of the list.
Source code in src/alnoms/dsa/structures/doubly_linked_list.py 
146
147
148
149
150
151
152
153
def display_forward(self) -> str:
    """Returns a string representation from head to tail.

    Returns:
        str: A formatted representation of the list.
    """
    elements = [str(data) for data in self]
    return " <-> ".join(elements) if elements else "EMPTY"
is_empty()

Checks whether the list is empty.

Returns:

Name Type Description
bool bool

True if the list contains no elements.
Source code in src/alnoms/dsa/structures/doubly_linked_list.py 
63
64
65
66
67
68
69
def is_empty(self) -> bool:
    """Checks whether the list is empty.

    Returns:
        bool: True if the list contains no elements.
    """
    return self.head is None
prepend(data)

Inserts a node at the beginning of the list.

This operation runs in O(1) time.

Parameters:

Name Type Description Default
data Any

The value to prepend.

 required
Source code in src/alnoms/dsa/structures/doubly_linked_list.py 
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
def prepend(self, data: Any) -> None:
    """Inserts a node at the beginning of the list.

    This operation runs in O(1) time.

    Args:
        data (Any): The value to prepend.
    """
    new_node = DoublyNode(data)

    if not self.head:
        self.head = new_node
        self.tail = new_node
    else:
        new_node.next = self.head
        self.head.prev = new_node
        self.head = new_node

    self._size += 1
remove(data)

Removes the first occurrence of a specific value.

This operation runs in O(N) time due to linear search.

Parameters:

Name Type Description Default
data Any

The value to remove.

 required

Returns:

Name Type Description
bool bool

True if a node was removed, otherwise False.
Source code in src/alnoms/dsa/structures/doubly_linked_list.py 
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
def remove(self, data: Any) -> bool:
    """Removes the first occurrence of a specific value.

    This operation runs in O(N) time due to linear search.

    Args:
        data (Any): The value to remove.

    Returns:
        bool: True if a node was removed, otherwise False.
    """
    current = self.head

    while current:
        if current.data == data:
            # Update previous link
            if current.prev:
                current.prev.next = current.next
            else:
                self.head = current.next

            # Update next link
            if current.next:
                current.next.prev = current.prev
            else:
                self.tail = current.prev

            self._size -= 1
            return True

        current = current.next

    return False

🌳 Trees & Graphs

Binary Search Tree (BST).

Provides a recursive implementation of an ordered symbol table using a binary search tree. Keys must be comparable, and the structure supports ordered operations such as min, max, floor, rank, and sorted iteration. Deletion uses Hibbard's algorithm.

Design Characteristics: - Ordered key‑value storage - In‑order traversal yields sorted keys - Hibbard deletion for node removal - Rank and selection operations supported - Worst‑case height O(N) if unbalanced

Classes:

Name Description
BinarySearchTree

Ordered symbol table implemented using a BST.

BinarySearchTree

Binary Search Tree (BST) symbol table.

Keys are maintained in sorted order. Supports search, insertion, deletion (Hibbard), and ordered operations such as min, max, and floor. All operations are implemented recursively.

Source code in src/alnoms/dsa/structures/binary_search_tree.py 
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
class BinarySearchTree:
    """Binary Search Tree (BST) symbol table.

    Keys are maintained in sorted order. Supports search, insertion,
    deletion (Hibbard), and ordered operations such as min, max, and
    floor. All operations are implemented recursively.
    """

    def __init__(self):
        """Initializes an empty BST."""
        self._root: Optional[_Node] = None

    def size(self) -> int:
        """Returns the number of key‑value pairs in the table.

        Returns:
            int: Total number of stored entries.
        """
        return self._size(self._root)

    def _size(self, x: Optional[_Node]) -> int:
        """Returns the size of the subtree rooted at ``x``."""
        return 0 if x is None else x.size

    def is_empty(self) -> bool:
        """Checks whether the BST is empty.

        Returns:
            bool: True if empty, otherwise False.
        """
        return self.size() == 0

    def get(self, key: Any) -> Optional[Any]:
        """Returns the value associated with ``key``.

        Args:
            key (Any): Key to search for.

        Returns:
            Optional[Any]: Value if found, otherwise None.
        """
        return self._get(self._root, key)

    def _get(self, x: Optional[_Node], key: Any) -> Optional[Any]:
        if x is None:
            return None

        if key < x.key:
            return self._get(x.left, key)
        if key > x.key:
            return self._get(x.right, key)
        return x.val

    def contains(self, key: Any) -> bool:
        """Checks whether the BST contains ``key``.

        Returns:
            bool: True if present, otherwise False.
        """
        return self.get(key) is not None

    def put(self, key: Any, val: Any) -> None:
        """Inserts or updates a key‑value pair.

        If ``val`` is None, the key is deleted.

        Args:
            key (Any): Key to insert.
            val (Any): Value to associate.
        """
        if val is None:
            self.delete(key)
            return
        self._root = self._put(self._root, key, val)

    def _put(self, x: Optional[_Node], key: Any, val: Any) -> _Node:
        if x is None:
            return _Node(key, val, 1)

        if key < x.key:
            x.left = self._put(x.left, key, val)
        elif key > x.key:
            x.right = self._put(x.right, key, val)
        else:
            x.val = val

        x.size = 1 + self._size(x.left) + self._size(x.right)
        return x

    def min(self) -> Any:
        """Returns the smallest key.

        Raises:
            ValueError: If the BST is empty.
        """
        if self.is_empty():
            raise ValueError("min() called on empty BST")
        return self._min(self._root).key

    def _min(self, x: _Node) -> _Node:
        return x if x.left is None else self._min(x.left)

    def max(self) -> Any:
        """Returns the largest key.

        Raises:
            ValueError: If the BST is empty.
        """
        if self.is_empty():
            raise ValueError("max() called on empty BST")
        return self._max(self._root).key

    def _max(self, x: _Node) -> _Node:
        return x if x.right is None else self._max(x.right)

    def floor(self, key: Any) -> Optional[Any]:
        """Returns the largest key ≤ ``key``.

        Args:
            key (Any): Target key.

        Returns:
            Optional[Any]: Floor key, or None if no such key exists.
        """
        if self.is_empty():
            return None
        x = self._floor(self._root, key)
        return None if x is None else x.key

    def _floor(self, x: Optional[_Node], key: Any) -> Optional[_Node]:
        if x is None:
            return None

        if key == x.key:
            return x
        if key < x.key:
            return self._floor(x.left, key)

        t = self._floor(x.right, key)
        return t if t is not None else x

    def delete_min(self) -> None:
        """Deletes the smallest key."""
        if self.is_empty():
            raise ValueError("delete_min() called on empty BST")
        self._root = self._delete_min(self._root)

    def _delete_min(self, x: _Node) -> Optional[_Node]:
        if x.left is None:
            return x.right
        x.left = self._delete_min(x.left)
        x.size = 1 + self._size(x.left) + self._size(x.right)
        return x

    def delete(self, key: Any) -> None:
        """Deletes ``key`` from the BST using Hibbard deletion."""
        if not self.contains(key):
            return
        self._root = self._delete(self._root, key)

    def _delete(self, x: _Node, key: Any) -> Optional[_Node]:
        if x is None:
            return None

        if key < x.key:
            x.left = self._delete(x.left, key)
        elif key > x.key:
            x.right = self._delete(x.right, key)
        else:
            # Node with one or zero children
            if x.right is None:
                return x.left
            if x.left is None:
                return x.right

            # Node with two children: replace with successor
            t = x
            x = self._min(t.right)
            x.right = self._delete_min(t.right)
            x.left = t.left

        x.size = 1 + self._size(x.left) + self._size(x.right)
        return x

    def keys(self) -> List[Any]:
        """Returns all keys in sorted order.

        Returns:
            List[Any]: Sorted list of keys.
        """
        result: List[Any] = []
        self._keys(self._root, result)
        return result

    def _keys(self, x: Optional[_Node], result: List[Any]) -> None:
        if x is None:
            return
        self._keys(x.left, result)
        result.append(x.key)
        self._keys(x.right, result)
__init__()

Initializes an empty BST.

Source code in src/alnoms/dsa/structures/binary_search_tree.py 
53
54
55
def __init__(self):
    """Initializes an empty BST."""
    self._root: Optional[_Node] = None
contains(key)

Checks whether the BST contains key.

Returns:

Name Type Description
bool bool

True if present, otherwise False.
Source code in src/alnoms/dsa/structures/binary_search_tree.py 
 98
 99
100
101
102
103
104
def contains(self, key: Any) -> bool:
    """Checks whether the BST contains ``key``.

    Returns:
        bool: True if present, otherwise False.
    """
    return self.get(key) is not None
delete(key)

Deletes key from the BST using Hibbard deletion.

Source code in src/alnoms/dsa/structures/binary_search_tree.py 
199
200
201
202
203
def delete(self, key: Any) -> None:
    """Deletes ``key`` from the BST using Hibbard deletion."""
    if not self.contains(key):
        return
    self._root = self._delete(self._root, key)
delete_min()

Deletes the smallest key.

Source code in src/alnoms/dsa/structures/binary_search_tree.py 
186
187
188
189
190
def delete_min(self) -> None:
    """Deletes the smallest key."""
    if self.is_empty():
        raise ValueError("delete_min() called on empty BST")
    self._root = self._delete_min(self._root)
floor(key)

Returns the largest key ≤ key.

Parameters:

Name Type Description Default
key Any

Target key.

 required

Returns:

Type Description
Optional[Any]

Optional[Any]: Floor key, or None if no such key exists.
Source code in src/alnoms/dsa/structures/binary_search_tree.py 
160
161
162
163
164
165
166
167
168
169
170
171
172
def floor(self, key: Any) -> Optional[Any]:
    """Returns the largest key ≤ ``key``.

    Args:
        key (Any): Target key.

    Returns:
        Optional[Any]: Floor key, or None if no such key exists.
    """
    if self.is_empty():
        return None
    x = self._floor(self._root, key)
    return None if x is None else x.key
get(key)

Returns the value associated with key.

Parameters:

Name Type Description Default
key Any

Key to search for.

 required

Returns:

Type Description
Optional[Any]

Optional[Any]: Value if found, otherwise None.
Source code in src/alnoms/dsa/structures/binary_search_tree.py 
77
78
79
80
81
82
83
84
85
86
def get(self, key: Any) -> Optional[Any]:
    """Returns the value associated with ``key``.

    Args:
        key (Any): Key to search for.

    Returns:
        Optional[Any]: Value if found, otherwise None.
    """
    return self._get(self._root, key)
is_empty()

Checks whether the BST is empty.

Returns:

Name Type Description
bool bool

True if empty, otherwise False.
Source code in src/alnoms/dsa/structures/binary_search_tree.py 
69
70
71
72
73
74
75
def is_empty(self) -> bool:
    """Checks whether the BST is empty.

    Returns:
        bool: True if empty, otherwise False.
    """
    return self.size() == 0
keys()

Returns all keys in sorted order.

Returns:

Type Description
List[Any]

List[Any]: Sorted list of keys.
Source code in src/alnoms/dsa/structures/binary_search_tree.py 
229
230
231
232
233
234
235
236
237
def keys(self) -> List[Any]:
    """Returns all keys in sorted order.

    Returns:
        List[Any]: Sorted list of keys.
    """
    result: List[Any] = []
    self._keys(self._root, result)
    return result
max()

Returns the largest key.

Raises:

Type Description
ValueError

If the BST is empty.
Source code in src/alnoms/dsa/structures/binary_search_tree.py 
147
148
149
150
151
152
153
154
155
def max(self) -> Any:
    """Returns the largest key.

    Raises:
        ValueError: If the BST is empty.
    """
    if self.is_empty():
        raise ValueError("max() called on empty BST")
    return self._max(self._root).key
min()

Returns the smallest key.

Raises:

Type Description
ValueError

If the BST is empty.
Source code in src/alnoms/dsa/structures/binary_search_tree.py 
134
135
136
137
138
139
140
141
142
def min(self) -> Any:
    """Returns the smallest key.

    Raises:
        ValueError: If the BST is empty.
    """
    if self.is_empty():
        raise ValueError("min() called on empty BST")
    return self._min(self._root).key
put(key, val)

Inserts or updates a key‑value pair.

If val is None, the key is deleted.

Parameters:

Name Type Description Default
key Any

Key to insert.

 required
val Any

Value to associate.

 required
Source code in src/alnoms/dsa/structures/binary_search_tree.py 
106
107
108
109
110
111
112
113
114
115
116
117
118
def put(self, key: Any, val: Any) -> None:
    """Inserts or updates a key‑value pair.

    If ``val`` is None, the key is deleted.

    Args:
        key (Any): Key to insert.
        val (Any): Value to associate.
    """
    if val is None:
        self.delete(key)
        return
    self._root = self._put(self._root, key, val)
size()

Returns the number of key‑value pairs in the table.

Returns:

Name Type Description
int int

Total number of stored entries.
Source code in src/alnoms/dsa/structures/binary_search_tree.py 
57
58
59
60
61
62
63
def size(self) -> int:
    """Returns the number of key‑value pairs in the table.

    Returns:
        int: Total number of stored entries.
    """
    return self._size(self._root)

Graph Data Structures.

Provides a lightweight, adjacency‑list–based undirected graph optimized for algorithmic experimentation, teaching, and benchmarking. The graph supports efficient edge insertion and adjacency iteration while maintaining predictable memory usage proportional to V + E.

Design Characteristics: - Representation: Adjacency lists (space complexity O(V + E)). - Performance: - Add edge: O(1) - Iterate adjacency: O(degree(v)) - Check membership: O(degree(v)) - Self‑loops and parallel edges are permitted by default.

Classes:

Name Description
Graph

Undirected graph implemented using adjacency lists.

Graph

Undirected graph implemented using adjacency lists.

Each vertex maintains a list of its adjacent vertices. The structure is optimized for sparse graphs and supports efficient adjacency iteration and constant‑time edge insertion.

Source code in src/alnoms/dsa/structures/graphs.py 
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
class Graph:
    """Undirected graph implemented using adjacency lists.

    Each vertex maintains a list of its adjacent vertices. The structure
    is optimized for sparse graphs and supports efficient adjacency
    iteration and constant‑time edge insertion.
    """

    def __init__(self, V: int):
        """Initializes an empty graph with ``V`` vertices and zero edges.

        Args:
            V (int): Number of vertices in the graph.

        Raises:
            ValueError: If ``V`` is negative.
        """
        if V < 0:
            raise ValueError("Number of vertices must be non-negative")

        self._V = V
        self._E = 0
        self._adj: List[List[int]] = [[] for _ in range(V)]

    def V(self) -> int:
        """Returns the number of vertices in the graph.

        Returns:
            int: Total vertex count.
        """
        return self._V

    def E(self) -> int:
        """Returns the number of edges in the graph.

        Returns:
            int: Total edge count.
        """
        return self._E

    def add_edge(self, v: int, w: int) -> None:
        """Adds an undirected edge between vertices ``v`` and ``w``.

        Both vertices must be valid indices in the range ``0`` to
        ``V - 1``. Parallel edges and self‑loops are allowed.

        Args:
            v (int): First vertex.
            w (int): Second vertex.

        Raises:
            IndexError: If either vertex index is out of bounds.
        """
        self._validate_vertex(v)
        self._validate_vertex(w)

        self._adj[v].append(w)
        self._adj[w].append(v)
        self._E += 1

    def adj(self, v: int) -> Iterable[int]:
        """Returns the vertices adjacent to ``v``.

        Args:
            v (int): The vertex whose neighbors are requested.

        Returns:
            Iterable[int]: A list of adjacent vertices.
        """
        self._validate_vertex(v)
        return self._adj[v]

    def degree(self, v: int) -> int:
        """Returns the degree of vertex ``v``.

        Args:
            v (int): The vertex whose degree is requested.

        Returns:
            int: Number of adjacent vertices.
        """
        self._validate_vertex(v)
        return len(self._adj[v])

    def _validate_vertex(self, v: int) -> None:
        """Validates that ``v`` is a legal vertex index.

        Args:
            v (int): Vertex index to validate.

        Raises:
            IndexError: If ``v`` is outside the valid range.
        """
        if v < 0 or v >= self._V:
            raise IndexError(f"Vertex {v} is not between 0 and {self._V - 1}")

    def __repr__(self) -> str:
        """Returns a string representation of the graph.

        The format lists each vertex followed by its adjacency list.

        Returns:
            str: Human‑readable representation of the graph.
        """
        lines = [f"{self._V} vertices, {self._E} edges\n"]
        for v in range(self._V):
            neighbors = " ".join(str(w) for w in self._adj[v])
            lines.append(f"{v}: {neighbors}\n")
        return "".join(lines)
E()

Returns the number of edges in the graph.

Returns:

Name Type Description
int int

Total edge count.
Source code in src/alnoms/dsa/structures/graphs.py 
56
57
58
59
60
61
62
def E(self) -> int:
    """Returns the number of edges in the graph.

    Returns:
        int: Total edge count.
    """
    return self._E
V()

Returns the number of vertices in the graph.

Returns:

Name Type Description
int int

Total vertex count.
Source code in src/alnoms/dsa/structures/graphs.py 
48
49
50
51
52
53
54
def V(self) -> int:
    """Returns the number of vertices in the graph.

    Returns:
        int: Total vertex count.
    """
    return self._V
__init__(V)

Initializes an empty graph with V vertices and zero edges.

Parameters:

Name Type Description Default
V int

Number of vertices in the graph.

 required

Raises:

Type Description
ValueError

If V is negative.
Source code in src/alnoms/dsa/structures/graphs.py 
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
def __init__(self, V: int):
    """Initializes an empty graph with ``V`` vertices and zero edges.

    Args:
        V (int): Number of vertices in the graph.

    Raises:
        ValueError: If ``V`` is negative.
    """
    if V < 0:
        raise ValueError("Number of vertices must be non-negative")

    self._V = V
    self._E = 0
    self._adj: List[List[int]] = [[] for _ in range(V)]
__repr__()

Returns a string representation of the graph.

The format lists each vertex followed by its adjacency list.

Returns:

Name Type Description
str str

Human‑readable representation of the graph.
Source code in src/alnoms/dsa/structures/graphs.py 
120
121
122
123
124
125
126
127
128
129
130
131
132
def __repr__(self) -> str:
    """Returns a string representation of the graph.

    The format lists each vertex followed by its adjacency list.

    Returns:
        str: Human‑readable representation of the graph.
    """
    lines = [f"{self._V} vertices, {self._E} edges\n"]
    for v in range(self._V):
        neighbors = " ".join(str(w) for w in self._adj[v])
        lines.append(f"{v}: {neighbors}\n")
    return "".join(lines)
add_edge(v, w)

Adds an undirected edge between vertices v and w.

Both vertices must be valid indices in the range 0 to V - 1. Parallel edges and self‑loops are allowed.

Parameters:

Name Type Description Default
v int

First vertex.

 required
w int

Second vertex.

 required

Raises:

Type Description
IndexError

If either vertex index is out of bounds.
Source code in src/alnoms/dsa/structures/graphs.py 
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
def add_edge(self, v: int, w: int) -> None:
    """Adds an undirected edge between vertices ``v`` and ``w``.

    Both vertices must be valid indices in the range ``0`` to
    ``V - 1``. Parallel edges and self‑loops are allowed.

    Args:
        v (int): First vertex.
        w (int): Second vertex.

    Raises:
        IndexError: If either vertex index is out of bounds.
    """
    self._validate_vertex(v)
    self._validate_vertex(w)

    self._adj[v].append(w)
    self._adj[w].append(v)
    self._E += 1
adj(v)

Returns the vertices adjacent to v.

Parameters:

Name Type Description Default
v int

The vertex whose neighbors are requested.

 required

Returns:

Type Description
Iterable[int]

Iterable[int]: A list of adjacent vertices.
Source code in src/alnoms/dsa/structures/graphs.py 
84
85
86
87
88
89
90
91
92
93
94
def adj(self, v: int) -> Iterable[int]:
    """Returns the vertices adjacent to ``v``.

    Args:
        v (int): The vertex whose neighbors are requested.

    Returns:
        Iterable[int]: A list of adjacent vertices.
    """
    self._validate_vertex(v)
    return self._adj[v]
degree(v)

Returns the degree of vertex v.

Parameters:

Name Type Description Default
v int

The vertex whose degree is requested.

 required

Returns:

Name Type Description
int int

Number of adjacent vertices.
Source code in src/alnoms/dsa/structures/graphs.py 
 96
 97
 98
 99
100
101
102
103
104
105
106
def degree(self, v: int) -> int:
    """Returns the degree of vertex ``v``.

    Args:
        v (int): The vertex whose degree is requested.

    Returns:
        int: Number of adjacent vertices.
    """
    self._validate_vertex(v)
    return len(self._adj[v])

Directed Graph (Digraph).

Defines a lightweight adjacency‑list–based directed graph. Each vertex maintains a list of outgoing edges, and indegree counts are tracked explicitly. The structure supports efficient adjacency iteration, constant‑time edge insertion, and construction of the graph's reverse.

Design Characteristics: - Representation: Adjacency lists of integers. - Performance: - Add edge: O(1) - Iterate outgoing edges: O(outdegree(v)) - Compute reverse graph: O(V + E) - Self‑loops and parallel edges are permitted.

Classes:

Name Description
Digraph

Directed graph with adjacency lists and indegree tracking.

Digraph

Directed graph implemented using adjacency lists.

Each vertex maintains a list of outgoing edges. Indegree counts are stored explicitly to support algorithms that rely on incoming edge information. The structure is suitable for topological sorting, SCC algorithms, and general directed graph processing.

Source code in src/alnoms/dsa/structures/digraph.py 
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
class Digraph:
    """Directed graph implemented using adjacency lists.

    Each vertex maintains a list of outgoing edges. Indegree counts are
    stored explicitly to support algorithms that rely on incoming edge
    information. The structure is suitable for topological sorting,
    SCC algorithms, and general directed graph processing.
    """

    def __init__(self, V: int):
        """Initializes an empty digraph with ``V`` vertices.

        Args:
            V (int): Number of vertices.

        Raises:
            ValueError: If ``V`` is negative.
        """
        if V < 0:
            raise ValueError("Number of vertices must be non-negative")

        self._V = V
        self._E = 0
        self._adj: List[List[int]] = [[] for _ in range(V)]
        self._indegree: List[int] = [0] * V

    def V(self) -> int:
        """Returns the number of vertices in the digraph.

        Returns:
            int: Total vertex count.
        """
        return self._V

    def E(self) -> int:
        """Returns the number of edges in the digraph.

        Returns:
            int: Total edge count.
        """
        return self._E

    def add_edge(self, v: int, w: int) -> None:
        """Adds a directed edge from ``v`` to ``w``.

        Args:
            v (int): Source vertex.
            w (int): Destination vertex.

        Raises:
            IndexError: If either vertex index is out of bounds.
        """
        self._validate_vertex(v)
        self._validate_vertex(w)

        self._adj[v].append(w)
        self._indegree[w] += 1
        self._E += 1

    def adj(self, v: int) -> Iterable[int]:
        """Returns all vertices reachable from ``v`` via outgoing edges.

        Args:
            v (int): The source vertex.

        Returns:
            Iterable[int]: Outgoing neighbors of ``v``.
        """
        self._validate_vertex(v)
        return self._adj[v]

    def out_degree(self, v: int) -> int:
        """Returns the number of edges leaving vertex ``v``.

        Args:
            v (int): The vertex.

        Returns:
            int: Outdegree of ``v``.
        """
        self._validate_vertex(v)
        return len(self._adj[v])

    def in_degree(self, v: int) -> int:
        """Returns the number of edges entering vertex ``v``.

        Args:
            v (int): The vertex.

        Returns:
            int: Indegree of ``v``.
        """
        self._validate_vertex(v)
        return self._indegree[v]

    def reverse(self) -> "Digraph":
        """Returns a new digraph with all edges reversed.

        Useful for algorithms such as strongly connected components (SCC)
        where reverse graph traversal is required.

        Returns:
            Digraph: A new digraph with reversed edge directions.
        """
        R = Digraph(self._V)
        for v in range(self._V):
            for w in self._adj[v]:
                R.add_edge(w, v)
        return R

    def _validate_vertex(self, v: int) -> None:
        """Validates that ``v`` is a legal vertex index.

        Args:
            v (int): Vertex index to validate.

        Raises:
            IndexError: If ``v`` is outside the valid range.
        """
        if v < 0 or v >= self._V:
            raise IndexError(f"Vertex {v} is not between 0 and {self._V - 1}")
E()

Returns the number of edges in the digraph.

Returns:

Name Type Description
int int

Total edge count.
Source code in src/alnoms/dsa/structures/digraph.py 
58
59
60
61
62
63
64
def E(self) -> int:
    """Returns the number of edges in the digraph.

    Returns:
        int: Total edge count.
    """
    return self._E
V()

Returns the number of vertices in the digraph.

Returns:

Name Type Description
int int

Total vertex count.
Source code in src/alnoms/dsa/structures/digraph.py 
50
51
52
53
54
55
56
def V(self) -> int:
    """Returns the number of vertices in the digraph.

    Returns:
        int: Total vertex count.
    """
    return self._V
__init__(V)

Initializes an empty digraph with V vertices.

Parameters:

Name Type Description Default
V int

Number of vertices.

 required

Raises:

Type Description
ValueError

If V is negative.
Source code in src/alnoms/dsa/structures/digraph.py 
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
def __init__(self, V: int):
    """Initializes an empty digraph with ``V`` vertices.

    Args:
        V (int): Number of vertices.

    Raises:
        ValueError: If ``V`` is negative.
    """
    if V < 0:
        raise ValueError("Number of vertices must be non-negative")

    self._V = V
    self._E = 0
    self._adj: List[List[int]] = [[] for _ in range(V)]
    self._indegree: List[int] = [0] * V
add_edge(v, w)

Adds a directed edge from v to w.

Parameters:

Name Type Description Default
v int

Source vertex.

 required
w int

Destination vertex.

 required

Raises:

Type Description
IndexError

If either vertex index is out of bounds.
Source code in src/alnoms/dsa/structures/digraph.py 
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
def add_edge(self, v: int, w: int) -> None:
    """Adds a directed edge from ``v`` to ``w``.

    Args:
        v (int): Source vertex.
        w (int): Destination vertex.

    Raises:
        IndexError: If either vertex index is out of bounds.
    """
    self._validate_vertex(v)
    self._validate_vertex(w)

    self._adj[v].append(w)
    self._indegree[w] += 1
    self._E += 1
adj(v)

Returns all vertices reachable from v via outgoing edges.

Parameters:

Name Type Description Default
v int

The source vertex.

 required

Returns:

Type Description
Iterable[int]

Iterable[int]: Outgoing neighbors of v.
Source code in src/alnoms/dsa/structures/digraph.py 
83
84
85
86
87
88
89
90
91
92
93
def adj(self, v: int) -> Iterable[int]:
    """Returns all vertices reachable from ``v`` via outgoing edges.

    Args:
        v (int): The source vertex.

    Returns:
        Iterable[int]: Outgoing neighbors of ``v``.
    """
    self._validate_vertex(v)
    return self._adj[v]
in_degree(v)

Returns the number of edges entering vertex v.

Parameters:

Name Type Description Default
v int

The vertex.

 required

Returns:

Name Type Description
int int

Indegree of v.
Source code in src/alnoms/dsa/structures/digraph.py 
107
108
109
110
111
112
113
114
115
116
117
def in_degree(self, v: int) -> int:
    """Returns the number of edges entering vertex ``v``.

    Args:
        v (int): The vertex.

    Returns:
        int: Indegree of ``v``.
    """
    self._validate_vertex(v)
    return self._indegree[v]
out_degree(v)

Returns the number of edges leaving vertex v.

Parameters:

Name Type Description Default
v int

The vertex.

 required

Returns:

Name Type Description
int int

Outdegree of v.
Source code in src/alnoms/dsa/structures/digraph.py 
 95
 96
 97
 98
 99
100
101
102
103
104
105
def out_degree(self, v: int) -> int:
    """Returns the number of edges leaving vertex ``v``.

    Args:
        v (int): The vertex.

    Returns:
        int: Outdegree of ``v``.
    """
    self._validate_vertex(v)
    return len(self._adj[v])
reverse()

Returns a new digraph with all edges reversed.

Useful for algorithms such as strongly connected components (SCC) where reverse graph traversal is required.

Returns:

Name Type Description
Digraph Digraph

A new digraph with reversed edge directions.
Source code in src/alnoms/dsa/structures/digraph.py 
119
120
121
122
123
124
125
126
127
128
129
130
131
132
def reverse(self) -> "Digraph":
    """Returns a new digraph with all edges reversed.

    Useful for algorithms such as strongly connected components (SCC)
    where reverse graph traversal is required.

    Returns:
        Digraph: A new digraph with reversed edge directions.
    """
    R = Digraph(self._V)
    for v in range(self._V):
        for w in self._adj[v]:
            R.add_edge(w, v)
    return R

Edge‑Weighted Graph.

Provides an undirected graph where each edge carries an associated weight. This structure is used in classical graph algorithms such as Minimum Spanning Trees (MST) and Shortest Paths. The graph is stored using adjacency lists, with each vertex maintaining a list of incident weighted edges.

Design Characteristics: - Representation: Adjacency lists of Edge objects. - Performance: - Add edge: O(1) - Iterate adjacency: O(degree(v)) - Parallel edges and self‑loops are permitted.

Classes:

Name Description
EdgeWeightedGraph

Undirected weighted graph backed by adjacency lists.

EdgeWeightedGraph

Undirected weighted graph implemented using adjacency lists.

Each vertex maintains a list of incident Edge objects. The graph supports efficient adjacency iteration and constant‑time edge insertion. This structure is suitable for MST and shortest‑path algorithms that operate on weighted graphs.

Source code in src/alnoms/dsa/structures/edge_weighted_graph.py 
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
class EdgeWeightedGraph:
    """Undirected weighted graph implemented using adjacency lists.

    Each vertex maintains a list of incident ``Edge`` objects. The graph
    supports efficient adjacency iteration and constant‑time edge
    insertion. This structure is suitable for MST and shortest‑path
    algorithms that operate on weighted graphs.
    """

    def __init__(self, V: int):
        """Initializes an empty weighted graph with ``V`` vertices.

        Args:
            V (int): Number of vertices.

        Raises:
            ValueError: If ``V`` is negative.
        """
        if V < 0:
            raise ValueError("Number of vertices must be non-negative")

        self._V = V
        self._E = 0
        self._adj: List[List[Edge]] = [[] for _ in range(V)]

    def V(self) -> int:
        """Returns the number of vertices in the graph.

        Returns:
            int: Total vertex count.
        """
        return self._V

    def E(self) -> int:
        """Returns the number of edges in the graph.

        Returns:
            int: Total edge count.
        """
        return self._E

    def add_edge(self, e: Edge) -> None:
        """Adds a weighted undirected edge to the graph.

        The edge is inserted into the adjacency lists of both endpoints.
        Parallel edges and self‑loops are allowed.

        Args:
            e (Edge): The edge to add.

        Raises:
            IndexError: If either endpoint is out of bounds.
        """
        v = e.either()
        w = e.other(v)

        self._validate_vertex(v)
        self._validate_vertex(w)

        self._adj[v].append(e)
        self._adj[w].append(e)
        self._E += 1

    def adj(self, v: int) -> Iterable[Edge]:
        """Returns all weighted edges incident to vertex ``v``.

        Args:
            v (int): The vertex whose incident edges are requested.

        Returns:
            Iterable[Edge]: List of edges adjacent to ``v``.
        """
        self._validate_vertex(v)
        return self._adj[v]

    def edges(self) -> Iterable[Edge]:
        """Returns all edges in the graph without duplicates.

        For each undirected edge, only the instance where the opposite
        endpoint is greater than the current vertex is included.

        Returns:
            Iterable[Edge]: All unique edges in the graph.
        """
        all_edges = []
        for v in range(self._V):
            for e in self._adj[v]:
                if e.other(v) > v:
                    all_edges.append(e)
        return all_edges

    def _validate_vertex(self, v: int) -> None:
        """Validates that ``v`` is a legal vertex index.

        Args:
            v (int): Vertex index to validate.

        Raises:
            IndexError: If ``v`` is outside the valid range.
        """
        if v < 0 or v >= self._V:
            raise IndexError(f"Vertex {v} is not between 0 and {self._V - 1}")
E()

Returns the number of edges in the graph.

Returns:

Name Type Description
int int

Total edge count.
Source code in src/alnoms/dsa/structures/edge_weighted_graph.py 
58
59
60
61
62
63
64
def E(self) -> int:
    """Returns the number of edges in the graph.

    Returns:
        int: Total edge count.
    """
    return self._E
V()

Returns the number of vertices in the graph.

Returns:

Name Type Description
int int

Total vertex count.
Source code in src/alnoms/dsa/structures/edge_weighted_graph.py 
50
51
52
53
54
55
56
def V(self) -> int:
    """Returns the number of vertices in the graph.

    Returns:
        int: Total vertex count.
    """
    return self._V
__init__(V)

Initializes an empty weighted graph with V vertices.

Parameters:

Name Type Description Default
V int

Number of vertices.

 required

Raises:

Type Description
ValueError

If V is negative.
Source code in src/alnoms/dsa/structures/edge_weighted_graph.py 
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
def __init__(self, V: int):
    """Initializes an empty weighted graph with ``V`` vertices.

    Args:
        V (int): Number of vertices.

    Raises:
        ValueError: If ``V`` is negative.
    """
    if V < 0:
        raise ValueError("Number of vertices must be non-negative")

    self._V = V
    self._E = 0
    self._adj: List[List[Edge]] = [[] for _ in range(V)]
add_edge(e)

Adds a weighted undirected edge to the graph.

The edge is inserted into the adjacency lists of both endpoints. Parallel edges and self‑loops are allowed.

Parameters:

Name Type Description Default
e Edge

The edge to add.

 required

Raises:

Type Description
IndexError

If either endpoint is out of bounds.
Source code in src/alnoms/dsa/structures/edge_weighted_graph.py 
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
def add_edge(self, e: Edge) -> None:
    """Adds a weighted undirected edge to the graph.

    The edge is inserted into the adjacency lists of both endpoints.
    Parallel edges and self‑loops are allowed.

    Args:
        e (Edge): The edge to add.

    Raises:
        IndexError: If either endpoint is out of bounds.
    """
    v = e.either()
    w = e.other(v)

    self._validate_vertex(v)
    self._validate_vertex(w)

    self._adj[v].append(e)
    self._adj[w].append(e)
    self._E += 1
adj(v)

Returns all weighted edges incident to vertex v.

Parameters:

Name Type Description Default
v int

The vertex whose incident edges are requested.

 required

Returns:

Type Description
Iterable[Edge]

Iterable[Edge]: List of edges adjacent to v.
Source code in src/alnoms/dsa/structures/edge_weighted_graph.py 
88
89
90
91
92
93
94
95
96
97
98
def adj(self, v: int) -> Iterable[Edge]:
    """Returns all weighted edges incident to vertex ``v``.

    Args:
        v (int): The vertex whose incident edges are requested.

    Returns:
        Iterable[Edge]: List of edges adjacent to ``v``.
    """
    self._validate_vertex(v)
    return self._adj[v]
edges()

Returns all edges in the graph without duplicates.

For each undirected edge, only the instance where the opposite endpoint is greater than the current vertex is included.

Returns:

Type Description
Iterable[Edge]

Iterable[Edge]: All unique edges in the graph.
Source code in src/alnoms/dsa/structures/edge_weighted_graph.py 
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
def edges(self) -> Iterable[Edge]:
    """Returns all edges in the graph without duplicates.

    For each undirected edge, only the instance where the opposite
    endpoint is greater than the current vertex is included.

    Returns:
        Iterable[Edge]: All unique edges in the graph.
    """
    all_edges = []
    for v in range(self._V):
        for e in self._adj[v]:
            if e.other(v) > v:
                all_edges.append(e)
    return all_edges

Edge‑Weighted Directed Graph.

Provides a directed graph where each edge carries an associated weight. The structure is implemented using adjacency lists, with each vertex maintaining a list of outgoing DirectedEdge objects. This design supports efficient adjacency iteration and constant‑time edge insertion.

Design Characteristics: - Representation: Adjacency lists of DirectedEdge objects. - Performance: - Add edge: O(1) - Iterate outgoing edges: O(outdegree(v)) - Parallel edges and self‑loops are permitted.

Classes:

Name Description
EdgeWeightedDigraph

Directed weighted graph backed by adjacency lists.

EdgeWeightedDigraph

Directed weighted graph implemented using adjacency lists.

Each vertex maintains a list of outgoing DirectedEdge objects. The structure is suitable for shortest‑path algorithms such as Dijkstra, Bellman‑Ford, and DAG relaxations.

Source code in src/alnoms/dsa/structures/edge_weighted_digraph.py 
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
class EdgeWeightedDigraph:
    """Directed weighted graph implemented using adjacency lists.

    Each vertex maintains a list of outgoing ``DirectedEdge`` objects.
    The structure is suitable for shortest‑path algorithms such as
    Dijkstra, Bellman‑Ford, and DAG relaxations.
    """

    def __init__(self, V: int):
        """Initializes an empty edge‑weighted digraph with ``V`` vertices.

        Args:
            V (int): Number of vertices.

        Raises:
            ValueError: If ``V`` is negative.
        """
        if V < 0:
            raise ValueError("Number of vertices must be non-negative")

        self._V = V
        self._E = 0
        self._adj: List[List[DirectedEdge]] = [[] for _ in range(V)]

    def V(self) -> int:
        """Returns the number of vertices in the digraph.

        Returns:
            int: Total vertex count.
        """
        return self._V

    def E(self) -> int:
        """Returns the number of edges in the digraph.

        Returns:
            int: Total edge count.
        """
        return self._E

    def add_edge(self, e: DirectedEdge) -> None:
        """Adds a directed weighted edge to the digraph.

        The edge is inserted into the adjacency list of its source
        vertex. Parallel edges and self‑loops are allowed.

        Args:
            e (DirectedEdge): The edge to add.

        Raises:
            IndexError: If either endpoint is out of bounds.
        """
        v = e.from_vertex()
        w = e.to_vertex()

        self._validate_vertex(v)
        self._validate_vertex(w)

        self._adj[v].append(e)
        self._E += 1

    def adj(self, v: int) -> Iterable[DirectedEdge]:
        """Returns all outgoing edges from vertex ``v``.

        Args:
            v (int): The source vertex.

        Returns:
            Iterable[DirectedEdge]: Outgoing edges from ``v``.
        """
        self._validate_vertex(v)
        return self._adj[v]

    def edges(self) -> Iterable[DirectedEdge]:
        """Returns all edges in the digraph.

        Returns:
            Iterable[DirectedEdge]: All directed edges.
        """
        all_edges = []
        for v in range(self._V):
            all_edges.extend(self._adj[v])
        return all_edges

    def _validate_vertex(self, v: int) -> None:
        """Validates that ``v`` is a legal vertex index.

        Args:
            v (int): Vertex index to validate.

        Raises:
            IndexError: If ``v`` is outside the valid range.
        """
        if v < 0 or v >= self._V:
            raise IndexError(f"Vertex {v} is not between 0 and {self._V - 1}")
E()

Returns the number of edges in the digraph.

Returns:

Name Type Description
int int

Total edge count.
Source code in src/alnoms/dsa/structures/edge_weighted_digraph.py 
56
57
58
59
60
61
62
def E(self) -> int:
    """Returns the number of edges in the digraph.

    Returns:
        int: Total edge count.
    """
    return self._E
V()

Returns the number of vertices in the digraph.

Returns:

Name Type Description
int int

Total vertex count.
Source code in src/alnoms/dsa/structures/edge_weighted_digraph.py 
48
49
50
51
52
53
54
def V(self) -> int:
    """Returns the number of vertices in the digraph.

    Returns:
        int: Total vertex count.
    """
    return self._V
__init__(V)

Initializes an empty edge‑weighted digraph with V vertices.

Parameters:

Name Type Description Default
V int

Number of vertices.

 required

Raises:

Type Description
ValueError

If V is negative.
Source code in src/alnoms/dsa/structures/edge_weighted_digraph.py 
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
def __init__(self, V: int):
    """Initializes an empty edge‑weighted digraph with ``V`` vertices.

    Args:
        V (int): Number of vertices.

    Raises:
        ValueError: If ``V`` is negative.
    """
    if V < 0:
        raise ValueError("Number of vertices must be non-negative")

    self._V = V
    self._E = 0
    self._adj: List[List[DirectedEdge]] = [[] for _ in range(V)]
add_edge(e)

Adds a directed weighted edge to the digraph.

The edge is inserted into the adjacency list of its source vertex. Parallel edges and self‑loops are allowed.

Parameters:

Name Type Description Default
e DirectedEdge

The edge to add.

 required

Raises:

Type Description
IndexError

If either endpoint is out of bounds.
Source code in src/alnoms/dsa/structures/edge_weighted_digraph.py 
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
def add_edge(self, e: DirectedEdge) -> None:
    """Adds a directed weighted edge to the digraph.

    The edge is inserted into the adjacency list of its source
    vertex. Parallel edges and self‑loops are allowed.

    Args:
        e (DirectedEdge): The edge to add.

    Raises:
        IndexError: If either endpoint is out of bounds.
    """
    v = e.from_vertex()
    w = e.to_vertex()

    self._validate_vertex(v)
    self._validate_vertex(w)

    self._adj[v].append(e)
    self._E += 1
adj(v)

Returns all outgoing edges from vertex v.

Parameters:

Name Type Description Default
v int

The source vertex.

 required

Returns:

Type Description
Iterable[DirectedEdge]

Iterable[DirectedEdge]: Outgoing edges from v.
Source code in src/alnoms/dsa/structures/edge_weighted_digraph.py 
85
86
87
88
89
90
91
92
93
94
95
def adj(self, v: int) -> Iterable[DirectedEdge]:
    """Returns all outgoing edges from vertex ``v``.

    Args:
        v (int): The source vertex.

    Returns:
        Iterable[DirectedEdge]: Outgoing edges from ``v``.
    """
    self._validate_vertex(v)
    return self._adj[v]
edges()

Returns all edges in the digraph.

Returns:

Type Description
Iterable[DirectedEdge]

Iterable[DirectedEdge]: All directed edges.
Source code in src/alnoms/dsa/structures/edge_weighted_digraph.py 
 97
 98
 99
100
101
102
103
104
105
106
def edges(self) -> Iterable[DirectedEdge]:
    """Returns all edges in the digraph.

    Returns:
        Iterable[DirectedEdge]: All directed edges.
    """
    all_edges = []
    for v in range(self._V):
        all_edges.extend(self._adj[v])
    return all_edges

🔑 Hash Tables

Hash Table Implementations.

Provides classic symbol table implementations based on hashing, including separate chaining and (optionally) linear probing variants. Designed as textbook-grade, inspectable data structures for algorithmic education and performance governance experiments.

Features
  • Hash-based key-value storage
  • Separate chaining collision handling
  • Hashable keys, arbitrary values
  • Deterministic, reference-friendly implementation

SeparateChainingHashST

Hash table implementation using separate chaining.

This symbol table stores key–value pairs in an array of buckets, where each bucket is a Python list of (key, value) tuples. Collisions are resolved by chaining, and average search time is proportional to O(N / M) where:

• ``N`` = number of key–value pairs
• ``M`` = number of buckets

This implementation is simple, predictable, and suitable for workloads where hash distribution is reasonably uniform.

Source code in src/alnoms/dsa/structures/separate_chaining_hash_st.py 
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
class SeparateChainingHashST:
    """Hash table implementation using separate chaining.

    This symbol table stores key–value pairs in an array of buckets,
    where each bucket is a Python list of ``(key, value)`` tuples.
    Collisions are resolved by chaining, and average search time is
    proportional to ``O(N / M)`` where:

        • ``N`` = number of key–value pairs
        • ``M`` = number of buckets

    This implementation is simple, predictable, and suitable for workloads
    where hash distribution is reasonably uniform.
    """

    def __init__(self, m: int = 997):
        """Initializes the hash table.

        Args:
            m (int): Number of buckets (chains). Defaults to 997, a prime
                number that helps reduce clustering.

        Attributes:
            _m (int): Number of buckets.
            _n (int): Number of stored key–value pairs.
            _st (List[List[Tuple[Any, Any]]]): Array of buckets.
        """
        self._m = m
        self._n = 0
        self._st: List[List[Tuple[Any, Any]]] = [[] for _ in range(m)]

    def _hash(self, key: Any) -> int:
        """Computes the bucket index for a given key.

        Args:
            key (Any): A hashable key.

        Returns:
            int: The bucket index in the range ``[0, M)``.
        """
        return (hash(key) & 0x7FFFFFFF) % self._m

    def size(self) -> int:
        """Returns the number of key–value pairs stored.

        Returns:
            int: Total number of entries.
        """
        return self._n

    def is_empty(self) -> int:
        """Checks whether the table contains any entries.

        Returns:
            bool: True if the table is empty, otherwise False.
        """
        return self._n == 0

    def contains(self, key: Any) -> bool:
        """Checks whether the table contains the given key.

        Args:
            key (Any): The key to search for.

        Returns:
            bool: True if the key exists, otherwise False.
        """
        return self.get(key) is not None

    def get(self, key: Any) -> Optional[Any]:
        """Retrieves the value associated with a key.

        Args:
            key (Any): The key to search for.

        Returns:
            Optional[Any]: The associated value if found, otherwise None.
        """
        i = self._hash(key)
        for k, v in self._st[i]:
            if k == key:
                return v
        return None

    def put(self, key: Any, val: Any) -> None:
        """Inserts or updates a key–value pair.

        If the key already exists, its value is updated.
        If ``val`` is ``None``, the key is removed.

        Args:
            key (Any): The key to insert.
            val (Any): The value to associate with the key.
        """
        if val is None:
            self.delete(key)
            return

        i = self._hash(key)

        # Update existing key
        for idx, (k, v) in enumerate(self._st[i]):
            if k == key:
                self._st[i][idx] = (key, val)
                return

        # Insert new key–value pair
        self._st[i].append((key, val))
        self._n += 1

    def delete(self, key: Any) -> None:
        """Removes a key and its associated value.

        Args:
            key (Any): The key to remove.
        """
        i = self._hash(key)
        bucket = self._st[i]

        for idx, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[idx]
                self._n -= 1
                return

    def keys(self) -> List[Any]:
        """Returns all keys stored in the table.

        Returns:
            List[Any]: A list containing all keys.
        """
        all_keys = []
        for bucket in self._st:
            for k, _ in bucket:
                all_keys.append(k)
        return all_keys
__init__(m=997)

Initializes the hash table.

Parameters:

Name Type Description Default
m int

Number of buckets (chains). Defaults to 997, a prime number that helps reduce clustering.

 997

Attributes:

Name Type Description
_m int

Number of buckets.
_n int

Number of stored key–value pairs.
_st List[List[Tuple[Any, Any]]]

Array of buckets.
Source code in src/alnoms/dsa/structures/separate_chaining_hash_st.py 
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
def __init__(self, m: int = 997):
    """Initializes the hash table.

    Args:
        m (int): Number of buckets (chains). Defaults to 997, a prime
            number that helps reduce clustering.

    Attributes:
        _m (int): Number of buckets.
        _n (int): Number of stored key–value pairs.
        _st (List[List[Tuple[Any, Any]]]): Array of buckets.
    """
    self._m = m
    self._n = 0
    self._st: List[List[Tuple[Any, Any]]] = [[] for _ in range(m)]
contains(key)

Checks whether the table contains the given key.

Parameters:

Name Type Description Default
key Any

The key to search for.

 required

Returns:

Name Type Description
bool bool

True if the key exists, otherwise False.
Source code in src/alnoms/dsa/structures/separate_chaining_hash_st.py 
78
79
80
81
82
83
84
85
86
87
def contains(self, key: Any) -> bool:
    """Checks whether the table contains the given key.

    Args:
        key (Any): The key to search for.

    Returns:
        bool: True if the key exists, otherwise False.
    """
    return self.get(key) is not None
delete(key)

Removes a key and its associated value.

Parameters:

Name Type Description Default
key Any

The key to remove.

 required
Source code in src/alnoms/dsa/structures/separate_chaining_hash_st.py 
130
131
132
133
134
135
136
137
138
139
140
141
142
143
def delete(self, key: Any) -> None:
    """Removes a key and its associated value.

    Args:
        key (Any): The key to remove.
    """
    i = self._hash(key)
    bucket = self._st[i]

    for idx, (k, v) in enumerate(bucket):
        if k == key:
            del bucket[idx]
            self._n -= 1
            return
get(key)

Retrieves the value associated with a key.

Parameters:

Name Type Description Default
key Any

The key to search for.

 required

Returns:

Type Description
Optional[Any]

Optional[Any]: The associated value if found, otherwise None.
Source code in src/alnoms/dsa/structures/separate_chaining_hash_st.py 
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
def get(self, key: Any) -> Optional[Any]:
    """Retrieves the value associated with a key.

    Args:
        key (Any): The key to search for.

    Returns:
        Optional[Any]: The associated value if found, otherwise None.
    """
    i = self._hash(key)
    for k, v in self._st[i]:
        if k == key:
            return v
    return None
is_empty()

Checks whether the table contains any entries.

Returns:

Name Type Description
bool int

True if the table is empty, otherwise False.
Source code in src/alnoms/dsa/structures/separate_chaining_hash_st.py 
70
71
72
73
74
75
76
def is_empty(self) -> int:
    """Checks whether the table contains any entries.

    Returns:
        bool: True if the table is empty, otherwise False.
    """
    return self._n == 0
keys()

Returns all keys stored in the table.

Returns:

Type Description
List[Any]

List[Any]: A list containing all keys.
Source code in src/alnoms/dsa/structures/separate_chaining_hash_st.py 
145
146
147
148
149
150
151
152
153
154
155
def keys(self) -> List[Any]:
    """Returns all keys stored in the table.

    Returns:
        List[Any]: A list containing all keys.
    """
    all_keys = []
    for bucket in self._st:
        for k, _ in bucket:
            all_keys.append(k)
    return all_keys
put(key, val)

Inserts or updates a key–value pair.

If the key already exists, its value is updated. If val is None, the key is removed.

Parameters:

Name Type Description Default
key Any

The key to insert.

 required
val Any

The value to associate with the key.

 required
Source code in src/alnoms/dsa/structures/separate_chaining_hash_st.py 
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
def put(self, key: Any, val: Any) -> None:
    """Inserts or updates a key–value pair.

    If the key already exists, its value is updated.
    If ``val`` is ``None``, the key is removed.

    Args:
        key (Any): The key to insert.
        val (Any): The value to associate with the key.
    """
    if val is None:
        self.delete(key)
        return

    i = self._hash(key)

    # Update existing key
    for idx, (k, v) in enumerate(self._st[i]):
        if k == key:
            self._st[i][idx] = (key, val)
            return

    # Insert new key–value pair
    self._st[i].append((key, val))
    self._n += 1
size()

Returns the number of key–value pairs stored.

Returns:

Name Type Description
int int

Total number of entries.
Source code in src/alnoms/dsa/structures/separate_chaining_hash_st.py 
62
63
64
65
66
67
68
def size(self) -> int:
    """Returns the number of key–value pairs stored.

    Returns:
        int: Total number of entries.
    """
    return self._n