Skip to content

ofnodes Docs

This site contains the project documentation for the ofnodes project. The ofnodes project consists of data structures and algoritms written in python>=3.11.5. The author uses node objects, structure objects, and algorithms to illustrate the following programming concepts:

- Packaging
- Version Control
- Automated CI/CD
- API
- TDD
- OOP: modular and maintainable code

Table Of Contents

The documentation follows the best practice for project documentation as described by Daniele Procida in the Diátaxis documentation framework and consists of four separate parts:

  1. Tutorials
  2. How-To Guides
  3. Reference
  4. Explanation

Quickly find what you're looking for depending on your use case by looking at the different pages.

Project Overview

RandomAccessArray

Bases: BubbleSortMixin, InsertionSortMixin, ReverseOrderMixin

An array supporting random access with bubble sort and order reversal capabilities.

This class represents an array that supports random access operations and also provides functionality for sorting elements using bubble sort algorithm and reversing the order of elements.

Parameters:

Name Type Description Default
size int

The size of the array.

 required

Attributes:

Name Type Description
_data list

The underlying list to store array elements.
Note

This class inherits from BubbleSortMixin and ReverseOrderMixin to leverage the bubble sort and order reversal functionalities.

Examples:

>>> raarray = RandomAccessArray(5)
>>> raarray
RandomAccessArray([None, None, None, None, None])
>>> raarray[0] = 8
>>> raarray
RandomAccessArray([8, None, None, None, None])
>>> [raarray.__setitem__(i+1, val) for i, val in enumerate([2, 6, 4, 5])]
[None, None, None, None]
>>> raarray
RandomAccessArray([8, 2, 6, 4, 5])
>>> str(raarray)
'[8, 2, 6, 4, 5]'
Source code in src/ofnodes/structures/randomaccessarray.py 
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 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
156
157
class RandomAccessArray(BubbleSortMixin, InsertionSortMixin, ReverseOrderMixin):
    """An array supporting random access with bubble sort and order reversal capabilities.

    This class represents an array that supports random access operations and also provides
    functionality for sorting elements using bubble sort algorithm and reversing the order
    of elements.

    Args:
        size (int): The size of the array.

    Attributes:
        _data (list): The underlying list to store array elements.

    Note:
        This class inherits from BubbleSortMixin and ReverseOrderMixin to leverage the
        bubble sort and order reversal functionalities.

    Examples:
        >>> raarray = RandomAccessArray(5)
        >>> raarray
        RandomAccessArray([None, None, None, None, None])
        >>> raarray[0] = 8
        >>> raarray
        RandomAccessArray([8, None, None, None, None])
        >>> [raarray.__setitem__(i+1, val) for i, val in enumerate([2, 6, 4, 5])]
        [None, None, None, None]
        >>> raarray
        RandomAccessArray([8, 2, 6, 4, 5])
        >>> str(raarray)
        '[8, 2, 6, 4, 5]'
    """
    def __init__(self, size):
        self._data = [None] * size

    def __getitem__(self, index):
        return self._data[index]

    def __setitem__(self, index, value):
        self._data[index] = value

    def __len__(self):
        return len(self._data)

    def __dir__(self) -> list[str]:
        # Get the list of attributes and methods from the parent classes
        parent_dir = set(super().__dir__())
        # Filter out private attributes and methods
        excluded = {'_head', '_tail', '_target', 'reference_based_reverse_order', 'reference_based_bubble_sort','index_based_bubble_sort', 'index_based_reverse_order'}
        parent_dir = {attr for attr in parent_dir if attr not in excluded}
        # Return a sorted list of all attributes and methods
        return sorted(parent_dir)

    def __repr__(self):
        """Returns a string representation of the array.

        Returns:
            str: A string representation of the array.

        Example:
            >>> raarray = RandomAccessArray(5)
            >>> [raarray.__setitem__(i, val) for i, val in enumerate([8, 2, 6, 4, 5])]
            >>> raarray
            RandomAccessArray([8, 2, 6, 4, 5])

        """
        return f"RandomAccessArray({self._data})"

    def __str__(self):
        """Returns a string representation of the array.

        Returns:
            str: A string representation of the array.

        Example:
            >>> raarray = RandomAccessArray(5)
            >>> [raarray.__setitem__(i, val) for i, val in enumerate([8, 2, 6, 4, 5])]
            >>> str(raarray)
            '[8, 2, 6, 4, 5]'
        """
        return f"[{', '.join(str(item) for item in self._data)}]"

    def bubble_sort(self, ascending=True):
        """Sorts the elements of the data structure using bubble sort.

        This method sorts the elements of the data structure in place using the
        bubble sort algorithm. It supports both ascending and descending order
        based on the `ascending` parameter.

        Args:
            ascending (bool): If True, sorts the elements in ascending order.
                If False, sorts the elements in descending order. Defaults to True.
        Examples:
            >>> raarray = RandomAccessArray(5)
            >>> [raarray.__setitem__(i, val) for i, val in enumerate([8, 2, 6, 4, 5])]
            [None, None, None, None, None]
            >>> raarray.bubble_sort()
            >>> raarray
            RandomAccessArray([2, 4, 5, 6, 8])
            >>> raarray.bubble_sort(ascending=False)
            >>> raarray
            RandomAccessArray([8, 6, 5, 4, 2])
        """
        return super().index_based_bubble_sort(ascending)

    def reverse_order(self):
        """
        Examples:
            >>> raarray = RandomAccessArray(5)
            >>> [raarray.__setitem__(i, val) for i, val in enumerate([8, 2, 6, 4, 5])]
            [None, None, None, None, None]
            >>> raarray.reverse_order()
            >>> raarray
            RandomAccessArray([5, 4, 6, 2, 8])"""
        return super().index_based_reverse_order()

    def insertion_sort(self, ascending=True, key=None):
        """
        Sorts the elements of the RandomAccessArray using the insertion sort algorithm.

        This method sorts the elements in place either in ascending or descending order based on the
        specified parameters. An optional key function can be provided to customize the comparison
        behavior.

        Args:
            ascending (bool): Determines the sort order. Defaults to True for ascending order. Set to False for descending order.
            key (Callable, optional): A function that serves as a key for the sort comparison. Defaults to None.

        Examples:
            >>> # Custom comparison function
            >>> def by_length(s):
            ...     return len(s)

            >>> strings = ["strawberry", "peach", "cherry", "date",]
            >>> raarray = RandomAccessArray(len(strings))

            >>> for i, val in enumerate(strings):
            ...     raarray[i] = val

            >>> raarray
            RandomAccessArray(['strawberry', 'peach', 'cherry', 'date'])

            >>> raarray.insertion_sort()
            >>> raarray
            RandomAccessArray(['cherry', 'date', 'peach', 'strawberry'])

            >>> raarray.insertion_sort(key=by_length)
            >>> raarray
            RandomAccessArray(['date', 'peach', 'cherry', 'strawberry'])

            >>> raarray.insertion_sort(ascending=False, key=by_length)
            >>> raarray
            RandomAccessArray(['strawberry', 'cherry', 'peach', 'date'])
        Returns:
            None
        """
        return super().index_based_insertion_sort(ascending, key)

__repr__()

Returns a string representation of the array.

Returns:

Name Type Description
str

A string representation of the array.
Example

raarray = RandomAccessArray(5) [raarray.setitem(i, val) for i, val in enumerate([8, 2, 6, 4, 5])] raarray RandomAccessArray([8, 2, 6, 4, 5])

Source code in src/ofnodes/structures/randomaccessarray.py 
54
55
56
57
58
59
60
61
62
63
64
65
66
67
def __repr__(self):
    """Returns a string representation of the array.

    Returns:
        str: A string representation of the array.

    Example:
        >>> raarray = RandomAccessArray(5)
        >>> [raarray.__setitem__(i, val) for i, val in enumerate([8, 2, 6, 4, 5])]
        >>> raarray
        RandomAccessArray([8, 2, 6, 4, 5])

    """
    return f"RandomAccessArray({self._data})"

__str__()

Returns a string representation of the array.

Returns:

Name Type Description
str

A string representation of the array.
Example

raarray = RandomAccessArray(5) [raarray.setitem(i, val) for i, val in enumerate([8, 2, 6, 4, 5])] str(raarray) '[8, 2, 6, 4, 5]'

Source code in src/ofnodes/structures/randomaccessarray.py 
69
70
71
72
73
74
75
76
77
78
79
80
81
def __str__(self):
    """Returns a string representation of the array.

    Returns:
        str: A string representation of the array.

    Example:
        >>> raarray = RandomAccessArray(5)
        >>> [raarray.__setitem__(i, val) for i, val in enumerate([8, 2, 6, 4, 5])]
        >>> str(raarray)
        '[8, 2, 6, 4, 5]'
    """
    return f"[{', '.join(str(item) for item in self._data)}]"

bubble_sort(ascending=True)

Sorts the elements of the data structure using bubble sort.

This method sorts the elements of the data structure in place using the bubble sort algorithm. It supports both ascending and descending order based on the ascending parameter.

Parameters:

Name Type Description Default
ascending bool

If True, sorts the elements in ascending order. If False, sorts the elements in descending order. Defaults to True.

 True

Examples: >>> raarray = RandomAccessArray(5) >>> [raarray.setitem(i, val) for i, val in enumerate([8, 2, 6, 4, 5])] [None, None, None, None, None] >>> raarray.bubble_sort() >>> raarray RandomAccessArray([2, 4, 5, 6, 8]) >>> raarray.bubble_sort(ascending=False) >>> raarray RandomAccessArray([8, 6, 5, 4, 2])

Source code in src/ofnodes/structures/randomaccessarray.py 
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
def bubble_sort(self, ascending=True):
    """Sorts the elements of the data structure using bubble sort.

    This method sorts the elements of the data structure in place using the
    bubble sort algorithm. It supports both ascending and descending order
    based on the `ascending` parameter.

    Args:
        ascending (bool): If True, sorts the elements in ascending order.
            If False, sorts the elements in descending order. Defaults to True.
    Examples:
        >>> raarray = RandomAccessArray(5)
        >>> [raarray.__setitem__(i, val) for i, val in enumerate([8, 2, 6, 4, 5])]
        [None, None, None, None, None]
        >>> raarray.bubble_sort()
        >>> raarray
        RandomAccessArray([2, 4, 5, 6, 8])
        >>> raarray.bubble_sort(ascending=False)
        >>> raarray
        RandomAccessArray([8, 6, 5, 4, 2])
    """
    return super().index_based_bubble_sort(ascending)

insertion_sort(ascending=True, key=None)

Sorts the elements of the RandomAccessArray using the insertion sort algorithm.

This method sorts the elements in place either in ascending or descending order based on the specified parameters. An optional key function can be provided to customize the comparison behavior.

Parameters:

Name Type Description Default
ascending bool

Determines the sort order. Defaults to True for ascending order. Set to False for descending order.

 True
key Callable

A function that serves as a key for the sort comparison. Defaults to None.

 None

Examples:

>>> # Custom comparison function
>>> def by_length(s):
...     return len(s)

>>> strings = ["strawberry", "peach", "cherry", "date",]
>>> raarray = RandomAccessArray(len(strings))

>>> for i, val in enumerate(strings):
...     raarray[i] = val

>>> raarray
RandomAccessArray(['strawberry', 'peach', 'cherry', 'date'])

>>> raarray.insertion_sort()
>>> raarray
RandomAccessArray(['cherry', 'date', 'peach', 'strawberry'])

>>> raarray.insertion_sort(key=by_length)
>>> raarray
RandomAccessArray(['date', 'peach', 'cherry', 'strawberry'])

>>> raarray.insertion_sort(ascending=False, key=by_length)
>>> raarray
RandomAccessArray(['strawberry', 'cherry', 'peach', 'date'])

Returns: None

Source code in src/ofnodes/structures/randomaccessarray.py 
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
def insertion_sort(self, ascending=True, key=None):
    """
    Sorts the elements of the RandomAccessArray using the insertion sort algorithm.

    This method sorts the elements in place either in ascending or descending order based on the
    specified parameters. An optional key function can be provided to customize the comparison
    behavior.

    Args:
        ascending (bool): Determines the sort order. Defaults to True for ascending order. Set to False for descending order.
        key (Callable, optional): A function that serves as a key for the sort comparison. Defaults to None.

    Examples:
        >>> # Custom comparison function
        >>> def by_length(s):
        ...     return len(s)

        >>> strings = ["strawberry", "peach", "cherry", "date",]
        >>> raarray = RandomAccessArray(len(strings))

        >>> for i, val in enumerate(strings):
        ...     raarray[i] = val

        >>> raarray
        RandomAccessArray(['strawberry', 'peach', 'cherry', 'date'])

        >>> raarray.insertion_sort()
        >>> raarray
        RandomAccessArray(['cherry', 'date', 'peach', 'strawberry'])

        >>> raarray.insertion_sort(key=by_length)
        >>> raarray
        RandomAccessArray(['date', 'peach', 'cherry', 'strawberry'])

        >>> raarray.insertion_sort(ascending=False, key=by_length)
        >>> raarray
        RandomAccessArray(['strawberry', 'cherry', 'peach', 'date'])
    Returns:
        None
    """
    return super().index_based_insertion_sort(ascending, key)

reverse_order()

Examples:

>>> raarray = RandomAccessArray(5)
>>> [raarray.__setitem__(i, val) for i, val in enumerate([8, 2, 6, 4, 5])]
[None, None, None, None, None]
>>> raarray.reverse_order()
>>> raarray
RandomAccessArray([5, 4, 6, 2, 8])
Source code in src/ofnodes/structures/randomaccessarray.py 
106
107
108
109
110
111
112
113
114
115
def reverse_order(self):
    """
    Examples:
        >>> raarray = RandomAccessArray(5)
        >>> [raarray.__setitem__(i, val) for i, val in enumerate([8, 2, 6, 4, 5])]
        [None, None, None, None, None]
        >>> raarray.reverse_order()
        >>> raarray
        RandomAccessArray([5, 4, 6, 2, 8])"""
    return super().index_based_reverse_order()

SinglyLinkedList

Bases: CycleDetectionMixin, InsertionSortMixin, SearchMixin, RemoveMixin, InsertHeadMixin, InsertTailMixin, InsertAfterTargetMixin, InsertBeforeTargetMixin, PrintMixin, BubbleSortMixin, ReverseOrderMixin

A class representing a singly linked list.

This class provides functionality to create and manipulate a singly linked list data structure. Each node in the linked list contains a reference to the next node in the sequence.

Attributes:

Name Type Description
_head Optional[SinglyNode]

The head of the linked list.
_tail Optional[SinglyNode]

The tail of the linked list.
_target Optional[Any]

The target data or node instance.

Examples:

>>> linked_list = SinglyLinkedList()
>>> linked_list
SinglyLinkedList(head=None, tail=None, target=None)
Source code in src/ofnodes/structures/singlylinkedlist.py 
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 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
156
157
158
159
160
161
162
class SinglyLinkedList(CycleDetectionMixin, InsertionSortMixin, SearchMixin, RemoveMixin, InsertHeadMixin, InsertTailMixin, InsertAfterTargetMixin, InsertBeforeTargetMixin, PrintMixin, BubbleSortMixin, ReverseOrderMixin):
    """A class representing a singly linked list.

    This class provides functionality to create and manipulate a singly linked list
    data structure. Each node in the linked list contains a reference to the next
    node in the sequence.

    Attributes:
        _head (Optional[SinglyNode]): The head of the linked list.
        _tail (Optional[SinglyNode]): The tail of the linked list.
        _target (Optional[Any]): The target data or node instance.

    Examples:
        >>> linked_list = SinglyLinkedList()
        >>> linked_list
        SinglyLinkedList(head=None, tail=None, target=None)
    """

    __slots__ = ('_head', '_tail', '_target',)
    head = Head()
    tail = Tail()
    target = Target()
    def __init__(self, values=None) -> None:
        self._head: Optional[SinglyNode] = None
        self._tail: Optional[SinglyNode] = None
        self._target: Optional[Any|SinglyNode] = None
        if values:
            for value in values:
                self.tail = value

    def __add__(self, other):
        self.tail = other  # tail attr will validate

    def __repr__(self) -> str:
        #return f"{type(self).__name__}(head={type(self.head).__name__}, tail={self.tail})"
        if not self._head:
            return "SinglyLinkedList()"
        node = self._head
        nodes = []
        while node:
            nodes.append(repr(node.data))
            node = node.next
        return f"{type(self).__name__}([" + ', '.join(nodes) + "])"

    def __str__(self) -> str:
        if not self._head:
            return "Empty Singly Linked List"
        node = self._head
        nodes = []
        while node:
            nodes.append(str(node.data))
            node = node.next
        return ' -> '.join(nodes)

    def __dir__(self) -> list[str]:
        # Get the list of attributes and methods from the parent classes
        parent_dir = set(super().__dir__())
        # Filter out private attributes and methods
        excluded = {'_head', '_tail', '_target', 'reference_based_reverse_order', 'reference_based_bubble_sort','index_based_bubble_sort', 'index_based_reverse_order', 'index_based_insertion_sort', 'reference_based_insertion_sort'}
        parent_dir = {attr for attr in parent_dir if attr not in excluded}
        # Return a sorted list of all attributes and methods
        return sorted(parent_dir)

    def insertion_sort(self, ascending=True, key=None):
        """Sorts the nodes of a reference-based object using insertion sort.

        This method sorts a singly linked list using the insertion sort algorithm. It traverses the list,
        starting from the second element, and divides it into sorted and unsorted portions. Each element
        in the unsorted portion is iteratively placed in the correct position within the sorted portion.

        Args:
            ascending (bool): Determines the sort order. Defaults to True. If True, sorts in ascending order;
                if False, sorts in descending order.

        Raises:
            TypeError: If the method is used on data structures that do not support reference-based operations.
            ValueError: If the singly linked list is empty or contains only one node.

        Returns:
            None

        Example:
            >>> def by_length(s):
            ...     return len(s)

            >>> fruits = ['cherry', 'strawberry', 'fig', 'peach']
            >>> sllist = SinglyLinkedList(fruits)
            >>> sllist.insertion_sort(ascending=False, key=by_length)
            >>> sllist
            SinglyLinkedList(['strawberry', 'cherry', 'peach', 'fig']
        """
        return super().reference_based_insertion_sort(ascending, key)

    def bubble_sort(self, ascending=True, key=None):
        """Sorts the nodes of the singly linked data structure.

        Args:
            ascending (bool, optional): Specifies whether to sort the elements in ascending order (default) or descending order.

        Returns:
            None: This method modifies the original linked list in place.

        Examples:
            >>> sllist = SinglyLinkedList([8, 2, 6, 4, 5])
            >>> sllist.bubble_sort()
            >>> sllist
            SinglyLinkedList([2, 4, 5, 6, 8])
            >>> sllist.bubble_sort(ascending=False)
            >>> sllist
            SinglyLinkedList([8, 6, 5, 4, 2])

        Notes:
            - The comparison operation (`>`) is used for elements. For non-numeric data types,
            ensure that the `__gt__` method is defined appropriately for comparison.
            - Time Complexity:
                - Best Case: O(n), when the list is already sorted.
                - Worst Case: O(n^2), when the list is in reverse order.
                - Average Case: O(n^2).
        """
        return super().reference_based_bubble_sort(ascending)

    def reverse_order(self):
        """Reverses the order of elements in the singly linked data structure.

        Returns:
            None: This method modifies the original linked list in place.

        Examples:
            >>> sllist = SinglyLinkedList([8, 2, 6, 4, 5])
            >>> sllist.reverse_order()
            >>> sllist
            SinglyLinkedList([5, 4, 6, 2, 8])

        Notes:
            - Time Complexity: O(n), where n is the number of elements in the linked list.
        """
        return super().reference_based_reverse_order()

    def cycle_detection(self):
        """Detects if the singly linked list instance contains a cycle.

        This method checks whether the linked list contains a cycle using Floyd's Tortoise and Hare algorithm.

        Returns:
            bool: True if a cycle is detected, False otherwise.

        Examples:
            >>> sllist = SinglyLinkedList([8, 2, 6, 4, 5])
            >>> sllist.cycle_detection()
            False
            >>> setattr(sllist.head.next, '_next', sllist.head.next)
            >>> sllist.cycle_detection()
            True
        """
        return super().reference_based_cycle_detection()

bubble_sort(ascending=True, key=None)

Sorts the nodes of the singly linked data structure.

Parameters:

Name Type Description Default
ascending bool

Specifies whether to sort the elements in ascending order (default) or descending order.

 True

Returns:

Name Type Description
None

This method modifies the original linked list in place.

Examples:

>>> sllist = SinglyLinkedList([8, 2, 6, 4, 5])
>>> sllist.bubble_sort()
>>> sllist
SinglyLinkedList([2, 4, 5, 6, 8])
>>> sllist.bubble_sort(ascending=False)
>>> sllist
SinglyLinkedList([8, 6, 5, 4, 2])
Notes
  • The comparison operation (>) is used for elements. For non-numeric data types, ensure that the __gt__ method is defined appropriately for comparison.
  • Time Complexity:
    • Best Case: O(n), when the list is already sorted.
    • Worst Case: O(n^2), when the list is in reverse order.
    • Average Case: O(n^2).
Source code in src/ofnodes/structures/singlylinkedlist.py 
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
def bubble_sort(self, ascending=True, key=None):
    """Sorts the nodes of the singly linked data structure.

    Args:
        ascending (bool, optional): Specifies whether to sort the elements in ascending order (default) or descending order.

    Returns:
        None: This method modifies the original linked list in place.

    Examples:
        >>> sllist = SinglyLinkedList([8, 2, 6, 4, 5])
        >>> sllist.bubble_sort()
        >>> sllist
        SinglyLinkedList([2, 4, 5, 6, 8])
        >>> sllist.bubble_sort(ascending=False)
        >>> sllist
        SinglyLinkedList([8, 6, 5, 4, 2])

    Notes:
        - The comparison operation (`>`) is used for elements. For non-numeric data types,
        ensure that the `__gt__` method is defined appropriately for comparison.
        - Time Complexity:
            - Best Case: O(n), when the list is already sorted.
            - Worst Case: O(n^2), when the list is in reverse order.
            - Average Case: O(n^2).
    """
    return super().reference_based_bubble_sort(ascending)

cycle_detection()

Detects if the singly linked list instance contains a cycle.

This method checks whether the linked list contains a cycle using Floyd's Tortoise and Hare algorithm.

Returns:

Name Type Description
bool

True if a cycle is detected, False otherwise.

Examples:

>>> sllist = SinglyLinkedList([8, 2, 6, 4, 5])
>>> sllist.cycle_detection()
False
>>> setattr(sllist.head.next, '_next', sllist.head.next)
>>> sllist.cycle_detection()
True
Source code in src/ofnodes/structures/singlylinkedlist.py 
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
def cycle_detection(self):
    """Detects if the singly linked list instance contains a cycle.

    This method checks whether the linked list contains a cycle using Floyd's Tortoise and Hare algorithm.

    Returns:
        bool: True if a cycle is detected, False otherwise.

    Examples:
        >>> sllist = SinglyLinkedList([8, 2, 6, 4, 5])
        >>> sllist.cycle_detection()
        False
        >>> setattr(sllist.head.next, '_next', sllist.head.next)
        >>> sllist.cycle_detection()
        True
    """
    return super().reference_based_cycle_detection()

insertion_sort(ascending=True, key=None)

Sorts the nodes of a reference-based object using insertion sort.

This method sorts a singly linked list using the insertion sort algorithm. It traverses the list, starting from the second element, and divides it into sorted and unsorted portions. Each element in the unsorted portion is iteratively placed in the correct position within the sorted portion.

Parameters:

Name Type Description Default
ascending bool

Determines the sort order. Defaults to True. If True, sorts in ascending order; if False, sorts in descending order.

 True

Raises:

Type Description
TypeError

If the method is used on data structures that do not support reference-based operations.
ValueError

If the singly linked list is empty or contains only one node.

Returns:

Type Description

None
Example

def by_length(s): ... return len(s)

fruits = ['cherry', 'strawberry', 'fig', 'peach'] sllist = SinglyLinkedList(fruits) sllist.insertion_sort(ascending=False, key=by_length) sllist SinglyLinkedList(['strawberry', 'cherry', 'peach', 'fig']

Source code in src/ofnodes/structures/singlylinkedlist.py 
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
def insertion_sort(self, ascending=True, key=None):
    """Sorts the nodes of a reference-based object using insertion sort.

    This method sorts a singly linked list using the insertion sort algorithm. It traverses the list,
    starting from the second element, and divides it into sorted and unsorted portions. Each element
    in the unsorted portion is iteratively placed in the correct position within the sorted portion.

    Args:
        ascending (bool): Determines the sort order. Defaults to True. If True, sorts in ascending order;
            if False, sorts in descending order.

    Raises:
        TypeError: If the method is used on data structures that do not support reference-based operations.
        ValueError: If the singly linked list is empty or contains only one node.

    Returns:
        None

    Example:
        >>> def by_length(s):
        ...     return len(s)

        >>> fruits = ['cherry', 'strawberry', 'fig', 'peach']
        >>> sllist = SinglyLinkedList(fruits)
        >>> sllist.insertion_sort(ascending=False, key=by_length)
        >>> sllist
        SinglyLinkedList(['strawberry', 'cherry', 'peach', 'fig']
    """
    return super().reference_based_insertion_sort(ascending, key)

reverse_order()

Reverses the order of elements in the singly linked data structure.

Returns:

Name Type Description
None

This method modifies the original linked list in place.

Examples:

>>> sllist = SinglyLinkedList([8, 2, 6, 4, 5])
>>> sllist.reverse_order()
>>> sllist
SinglyLinkedList([5, 4, 6, 2, 8])
Notes
  • Time Complexity: O(n), where n is the number of elements in the linked list.
Source code in src/ofnodes/structures/singlylinkedlist.py 
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
def reverse_order(self):
    """Reverses the order of elements in the singly linked data structure.

    Returns:
        None: This method modifies the original linked list in place.

    Examples:
        >>> sllist = SinglyLinkedList([8, 2, 6, 4, 5])
        >>> sllist.reverse_order()
        >>> sllist
        SinglyLinkedList([5, 4, 6, 2, 8])

    Notes:
        - Time Complexity: O(n), where n is the number of elements in the linked list.
    """
    return super().reference_based_reverse_order()

SinglyNode

Bases: AddMixin

Represents a node in a singly linked list.

Attributes:

Name Type Description
data

The data stored in the node.
next

Reference to the next node in the linked list. Defaults to None.
Source code in src/ofnodes/nodes/singlynode.py 
18
19
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
class SinglyNode(AddMixin):
    """Represents a node in a singly linked list.

    Attributes:
        data: The data stored in the node.
        next: Reference to the next node in the linked list. Defaults to None.
    """

    __slots__ = ('_data', '_next')

    data = Data()
    next = Next()

    def __init__(self, data: Any) -> None:
        self._data: Optional[Any] = data
        self._next: Optional[SinglyNode] = None

    def __dir__(self) -> list[str]:
        # Get the list of attributes and methods from the parent classes
        parent_dir = set(super().__dir__())
        # Filter out private attributes and methods
        parent_dir = {attr for attr in parent_dir if attr not in {'_data', '_next',}}
        # Return a sorted list of all attributes and methods
        return sorted(parent_dir)

    def __repr__(self) -> str:
        return (
            f"{type(self).__name__}"
            "("
            f"data={repr(self.data)}"
            ")"
        )

    def __str__(self) -> str:
        return str(self.data)

Stack

Bases: RemoveMixin, PrintMixin

Support for a reference-based LIFO object.

The head is considered the last node. The head is popped and a node pushed onto the stack becomes the new head.

Source code in src/ofnodes/structures/stack.py 
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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
class Stack(RemoveMixin, PrintMixin):
    """Support for a reference-based LIFO object.

    The head is considered the last node. The head is popped
    and a node pushed onto the stack becomes the new head."""

    __slots__ = ('_head',)

    head = Head()

    def __init__(self, values=None) -> None:
        self._head: Optional[SinglyNode] = None
        if values:
            for value in values:
                self.head = value

    def __dir__(self) -> list[str]:
        # Get the list of attributes and methods from the parent classes
        parent_dir = set(super().__dir__())
        # Filter out private attributes and methods
        parent_dir = {attr for attr in parent_dir if attr not in {'_head', '_tail', '_target'}}
        # Return a sorted list of all attributes and methods
        return sorted(parent_dir)

    def __repr__(self) -> str:
        #return f"{type(self).__name__}(head={type(self.head).__name__}, tail={self.tail})"
        if not self._head:
            return f"{type(self).__name__}()"
        node = self._head
        nodes = []
        while node:
            nodes.append(repr(node.data))
            node = node.next
        return f"{type(self).__name__}([" + ', '.join(nodes) + "])"

    def __str__(self) -> str:
        if not self._head:
            return f"Empty {type(self).__name__}"
        node = self._head
        nodes = []
        while node:
            nodes.append(str(node.data))
            node = node.next
        return ' -> '.join(nodes)

    def push(self, data):
        self.head = data  # trigger the setter, setter validates data

    def pop(self):
        return self.remove_head()

    def peek(self):
        if self._head:
            return self._head.data
        raise IndexError("Stack is empty, cannot peek at top element")

    def display(self):
        self.print_node_data()

    def is_empty(self):
        return self._head is None

Acknowledgements

I want to thank my house plants for providing me with a negligible amount of oxygen each day. Also, I want to thank the sun for providing more than half of their nourishment free of charge.

Special thanks to OpenAI's ChatGPT for valuable insights and assistance.