Skip to content

How-To Guides

Defines a node for a singly linked list.

This module contains the definition for the SinglyNode class, which represents a node in a singly linked list. Each node contains data and a reference to the next node in the list.

Example

Typical usage example:

uni_node = SinglyNode("a string of characters")

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)

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