data_structures

 5class NodeCore:
 6    """This is the fundamental class that's used & inherited for linear data structures.
 7
 8    Attributes:
 9        value (any): Value (data) stored in node.
10        next_node (Node | None): A pointer to the next node if exists.
11    """
12
13    def __init__(self, value, next_node=None):
14        """Initialize a NodeCore object.
15
16        Args:
17            value (Any, optional): First value to add to the list. Defaults to None.
18            next_node (NodeCore, optional): Node class used to create list nodes. Defaults to Node.
19        """
20        self._value = value
21        self._next_node = next_node
22
23    @property
24    def value(self):
25        """Any: The stored value in the `Node` object."""
26        return self._value
27
28    @property
29    def next_node(self):
30        """Return the next node. If there are no next node, returns `None`."""
31        return self._next_node
32
33    @next_node.setter
34    def next_node(self, node):
35        """Set the next node.
36
37        Args:
38            node (Node | None): new `Node` object or None if it's the tail node.
39        """
40        self._next_node = node

43class NodePriorityQueue(NodeCore):
44    """This is the base node used to construct a priority queue. Inherits the NodeCore.
45
46    Attributes:
47        value (any): Value (data) stored in node.
48        priority (int): Priority value for each node.
49        next_node (Node | None): Next node for the current node.
50    """
51
52    def __init__(self, value, priority=None, next_node=None):
53        """Initialize a NodePriorityQueue object. This is used for creating priority queues. Inherits NodeCore.
54
55        Args:
56            value (Any, optional): First value to add to the list. Defaults to None.
57            next_node (type, optional): Node class used to create list nodes. Defaults to Node.
58            priority (int): The priority value for the node. This will set the position of the node in the list.
59        """
60        super().__init__(value, next_node)
61        self.priority = priority

 64class TreeNode:
 65    """This is the base node used when implementing binary search trees.
 66
 67    Args:
 68        value (Any): The stored value in the node.
 69        left_child (Node | None): Left child of the current node.
 70        right_child (Node | None): Right child of the current node.
 71        parent (Node | None): Parent node of the current node.
 72    """
 73
 74    def __init__(self, value=None, left_child=None, right_child=None, parent=None):
 75        """Initialize a TreeNode object. Used in data_structures.BinarySearchTree.
 76
 77        Args:
 78            value (Any): The stored value in the node.
 79            left_child (Node | None): Left child of the current node.
 80            right_child (Node | None): Right child of the current node.
 81            parent (Node | None): Parent node of the current node.
 82        """
 83        self._value = value
 84        self._left_child = left_child
 85        self._right_child = right_child
 86        self._parent = parent
 87
 88    @property
 89    def value(self):
 90        """Any: The stored value in the `TreeNode` object."""
 91        return self._value
 92
 93    @value.setter
 94    def value(self, value):
 95        """Set a new value for the node.
 96
 97        Args:
 98            value (Any): The new value of the node.
 99        """
100        self._value = value
101
102    @property
103    def left_child(self):
104        """None | TreeNode: Returns left child the TreeNode object if exists."""
105        return self._left_child
106
107    @left_child.setter
108    def left_child(self, left_child):
109        """Set the left_child of the TreeNode.
110
111        Args:
112            left_child (TreeNode | None): Left child of the node object.
113        """
114        self._left_child = left_child
115
116    @property
117    def right_child(self):
118        """TreeNode: Returns the right child TreeNode object."""
119        return self._right_child
120
121    @right_child.setter
122    def right_child(self, right_child):
123        """Set the right_child of the TreeNode.
124
125        Args:
126            right_child (TreeNode | None): Right child of the node object.
127        """
128        self._right_child = right_child
129
130    @property
131    def left_value(self):
132        """Any: Value of the left_child node."""
133        return self._left_child.value if self._left_child else None
134
135    @property
136    def right_value(self):
137        """Any: Value of the right_child node."""
138        return self._right_child.value if self._right_child else None
139
140    @property
141    def parent(self):
142        """None | TreeNode: Returns the parent node (TreeNode) object if exists."""
143        return self._parent
144
145    @parent.setter
146    def parent(self, parent):
147        """Set the parent node.
148
149        Args:
150            parent (TreeNode | None): Parent of the node object.
151        """
152        self._parent = parent

  7class LinkedList:
  8    """This is the singly linked list implementation.
  9
 10    Attributes:
 11        _Node (Any): This is the node object used to create a list. Custom node objects can be used. Defaults to NodeCore.
 12        head_node (None or Node): The first node in the list.
 13        tail_node (None or Node): The last node in the list.
 14        size (int): The number of elements in the list.
 15        value (Any): Value of the node.
 16    """
 17
 18    def __init__(self, value=None, node=Node):
 19        """Initialize the `LinkedList`.
 20
 21        Args:
 22            head_node (None or Node): The first node in the list.
 23            tail_node (None or Node): The last node in the list.
 24            size (int): The number of elements in the list.
 25            value (Any): Value of the node.
 26            node (any | Node): Node container to construct a doubly linked list. Defaults to Node.
 27        """
 28        self._Node = node
 29        if value is not None:
 30            self.head_node = self._Node(value)
 31            self.tail_node = self.head_node
 32            self._size = 1
 33        else:
 34            self.head_node = None
 35            self.tail_node = None
 36            self._size = 0
 37
 38    @property
 39    def size(self):
 40        """int: How many elements in the linked list."""
 41        return self._size
 42
 43    def __str__(self):
 44        """str: A string representation of nodes in the list."""
 45        return "[ " + " ".join(str(node) for node in self) + " ]"
 46
 47    def __len__(self):
 48        """int: How many elements in the linked list."""
 49        return self._size
 50
 51    def __getitem__(self, index):
 52        """Make LinkedList class indexable.
 53
 54        Args:
 55            index (int): Index of `LinkedList` object to return the value at that position.
 56
 57        Raises:
 58            IndexError: If the `index` is out of range.
 59        """
 60        if index < 0:
 61            index += self._size
 62        if not 0 <= index < self._size:
 63            raise IndexError(f"Index {index} is out of bounds")
 64        else:
 65            return self.find_by_index(index)
 66
 67    def __iter__(self):
 68        """Dunder method to make `LinkedList` iterable."""
 69        current_node = self.head_node
 70        while current_node:
 71            yield current_node.value
 72            current_node = current_node.next_node
 73
 74    def insert_head(self, value):
 75        """Inserts a value at head. Wraps the value inside the Node object.
 76
 77        Args:
 78            value (any): Value to be inserted.
 79        """
 80        new_node = self._Node(value)
 81        new_node.next_node = self.head_node
 82        self._size += 1
 83        self.head_node = new_node
 84        if self._size == 1:
 85            self.tail_node = new_node
 86
 87    def insert_tail(self, value):
 88        """Inserts a value at tail. Wraps the value inside the Node object.
 89
 90        Args:
 91            value (any): Value to be inserted.
 92        """
 93        new_node = self._Node(value)
 94        if self._size == 0:
 95            self.head_node = new_node
 96            self.tail_node = self.head_node
 97        else:
 98            self.tail_node.next_node = new_node
 99            self.tail_node = new_node
100        self._size += 1
101
102    def insert_index(self, index, value):
103        """Insert the value inside the given index. Shifts the elements coming after that index.
104
105        Args:
106            index (int): Index position to insert the node.
107            value (any): Value wrapped inside a Node to be inserted.
108
109        Raises:
110            IndexError: If the `index` is out of range.
111        """
112        if index < 0 or index > self._size - 1:
113            raise IndexError(f"Index {index} out of bounds for insertion")
114        else:
115            if index == 0:
116                self.insert_head(value)
117                return
118            current_node = self.head_node
119            counter = 0
120            while counter < index - 1:
121                current_node = current_node.next_node
122                counter += 1
123            new_node = self._Node(value)
124            next_node = current_node.next_node
125            current_node.next_node = new_node
126            self._size += 1
127            new_node.next_node = next_node
128
129    def delete_head(self):
130        """Delete the first element in the list.
131
132        Raises:
133            Exception: If the list is empty.
134        """
135        if self.head_node is None:
136            raise Exception("Cannot delete from an empty list")
137        second_node = self.head_node.next_node
138        self._size -= 1
139        self.head_node = second_node
140
141    def delete_tail(self):
142        """Delete the last element in the list.
143
144        Raises:
145            Exception: If the `head_node` is None.
146        """
147        if self.head_node is None:
148            raise Exception("Cannot delete from an empty list")
149        elif self._size == 1:
150            self.head_node = None
151            self.tail_node = None
152        else:
153            current_node = self.head_node
154            while current_node.next_node.next_node is not None:
155                current_node = current_node.next_node
156            self.tail_node = current_node
157            current_node.next_node = None
158        self._size -= 1
159
160    def delete_index(self, index):
161        """Delete the element at the given index.
162
163        Args:
164            index (int): The index where the node will be deleted.
165
166        Raises:
167            IndexError: If the `index` is out of range.
168        """
169        if index < 0 or index > self._size - 1:
170            raise IndexError(
171                f"Index {index} is out of bounds for deletion - List size: {self._size}"
172            )
173        current_node = self.head_node
174        counter = 0
175        if self._size == 1 or index == 0:
176            self.delete_head()
177        else:
178            while (
179                counter < index - 1
180            ):  # get to the previous node of the node we want to delete
181                current_node = current_node.next_node
182                counter += 1
183            next_node = current_node.next_node.next_node
184            current_node.next_node = next_node
185            self._size -= 1
186
187    def delete_value(self, value):
188        """Delete a node with the given value.
189
190        Args:
191            value (any): Value that a node contains.
192
193        Raises:
194            Exception: If the list is empty.
195            ValueError: If the `value` is not found in the list.
196        """
197        current_node = self.head_node
198        previous_node = None
199
200        while current_node is not None:
201            if current_node.value == value:
202                if previous_node is None:
203                    self.delete_head()
204                    return
205                else:
206                    previous_node.next_node = current_node.next_node
207                    self._size -= 1
208                    return
209            previous_node = current_node
210            current_node = current_node.next_node
211
212        raise ValueError(f"{value} is not in the list")
213
214    def find_by_index(self, index):
215        """Find and return the value of a node of a given index.
216
217        Args:
218            index (int): The index of the node whose value is wanted.
219
220        Returns:
221            any: value of the node at `index`
222
223        Raises:
224            IndexError: If the `index` is out of range.
225        """
226        if index < 0:
227            index += self._size
228        if index > self._size - 1:
229            raise IndexError(f"Index {index} is out of bounds for check")
230        current_node = self.head_node
231        counter = 0
232        while current_node is not None:
233            if counter == index:
234                return current_node.value
235            else:
236                current_node = current_node.next_node
237                counter += 1
238
239    def traverse(self):
240        """Traverse and print the each value in the list."""
241        current_node = self.head_node
242        while current_node is not None:
243            print(current_node.value)
244            current_node = current_node.next_node

 7class Node(NodeCore):
 8    """Base node for DoublyLinkedList. Inherits all attributes from NodeCore.
 9
10    Attributes:
11        prev_node (None | Node): Pointer to the previous node.
12    """
13
14    def __init__(self, value, next_node=None, prev_node=None):
15        """Initialize a Node.
16
17        Args:
18            value
19            value (any): Value (data) stored in node.
20            next_node (Node | None): A pointer to the next node if exists.
21            prev_node (Node | None): A pointer to the previous node if exists.
22        """
23        super().__init__(value, next_node)
24        self._prev_node = prev_node
25
26    @property
27    def prev_node(self):
28        """Node | None: Return the previous node."""
29        return self._prev_node
30
31    @prev_node.setter
32    def prev_node(self, value):
33        """Set the previous node's value.
34
35        Args:
36            value (any): Value of the previous `Node` object.
37        """
38        self._prev_node = value

 41class DoublyLinkedList:
 42    """This is the doubly linked list implementation.
 43
 44    Attributes:
 45        _Node (Any): This is the node object used to create a list. Custom node objects can be used. Defaults to NodeCore.
 46        head_node (None or Node): The first node in the list.
 47        tail_node (None or Node): The last node in the list.
 48        size (int): The number of elements in the list.
 49        value (Any): Value of the node.
 50    """
 51
 52    def __init__(self, value=None, node=Node):
 53        """Initialize the `DoublyLinkedList`.
 54
 55        Args:
 56            head_node (None or Node): The first node in the list.
 57            tail_node (None or Node): The last node in the list.
 58            size (int): The number of elements in the list.
 59            value (Any): Value of the node.
 60            node (any | Node): Node container to construct a doubly linked list. Defaults to Node.
 61        """
 62        self._Node = node
 63        if value is not None:
 64            self.head_node = self._Node(value)
 65            self.tail_node = self.head_node
 66            self._size = 1
 67        else:
 68            self.head_node = None
 69            self.tail_node = None
 70            self._size = 0
 71
 72    def __str__(self):
 73        """Return the string representation of the `LinkedList` object."""
 74        return "[ " + " ".join(str(node) for node in self) + " ]"
 75
 76    def __len__(self):
 77        """Return the size of the linked list."""
 78        return self._size
 79
 80    def __getitem__(self, index):
 81        """Make LinkedList class indexable.
 82
 83        Args:
 84            index (int): Index of `LinkedList` object to return the value at that position.
 85
 86        Raises:
 87            IndexError: If the `index` is out of range.
 88        """
 89        if index < 0:
 90            index += self._size
 91        if not 0 <= index < self._size:
 92            raise IndexError(f"Index {index} is out of bounds")
 93        else:
 94            return self.find_by_index(index)
 95
 96    def __iter__(self):
 97        """Dunder method to make `LinkedList` iterable."""
 98        current_node = self.head_node
 99        while current_node:
100            yield current_node.value
101            current_node = current_node.next_node
102
103    def insert_head(self, value):
104        """Inserts a value at head. Wraps the value inside the Node object.
105
106        Args:
107            value (any): Value to be inserted.
108        """
109        if self._size == 0:
110            self.head_node = self._Node(value)
111            self.tail_node = self.head_node
112        else:
113            new_node = self._Node(value)
114            new_node.next_node = self.head_node
115            self.head_node.prev_node = new_node
116            self.head_node = new_node
117        self._size += 1
118
119    def insert_tail(self, value):
120        """Inserts a value at tail. Wraps the value inside the Node object.
121
122        Args:
123            value (any): Value to be inserted.
124        """
125        new_node = self._Node(value)
126        if self._size == 0:
127            self.head_node = new_node
128            self.tail_node = self.head_node
129        else:
130            self.tail_node.next_node = new_node
131            final_node = self.tail_node.next_node
132            final_node.prev_node = self.tail_node
133            self.tail_node = final_node
134        self._size += 1
135
136    def delete_head(self):
137        """Delete the first element in the list.
138
139        Raises:
140            Exception: If the list is empty.
141        """
142        if self._size == 0:
143            raise Exception("Cannot delete from an empty list")
144        elif self._size == 1:
145            self.head_node = None
146            self.tail_node = None
147        else:
148            self.head_node = self.head_node.next_node
149            self.head_node.prev_node = None
150        self._size -= 1
151
152    def delete_tail(self):
153        """Delete the last element in the list.
154
155        Raises:
156            Exception: If the size is 0.
157        """
158        if self._size == 0:
159            raise Exception("Cannot delete from an empty list")
160        elif self._size == 1:
161            self.head_node = None
162            self.tail_node = None
163        else:
164            self.tail_node = self.tail_node.prev_node
165            self.tail_node.next_node = None
166        self._size -= 1
167
168    def delete_index(self, index):
169        """Delete the element at the given index.
170
171        Args:
172            index (int): The index where the node will be deleted.
173
174        Raises:
175            IndexError: If the `index` is out of range.
176        """
177        if index < 0 or index > self._size - 1:
178            raise IndexError(f"Index {index} is out of bounds")
179        current_node = self.head_node
180        counter = 0
181        if self._size == 1 or index == 0:
182            self.delete_head()
183        else:
184            while counter < index - 1:
185                current_node = current_node.next_node
186                counter += 1
187            next_node = current_node.next_node.next_node
188            current_node.next_node = next_node
189            if next_node is None:
190                self.tail_node = current_node
191            else:
192                next_node.prev_node = current_node
193            self._size -= 1
194            return
195
196    def delete_value(self, value):
197        """Delete a node with the given value.
198
199        Args:
200            value (any): Value that a node contains.
201
202        Raises:
203            Exception: If the list is empty.
204            ValueError: If the `value` is not found in the list.
205        """
206        if self._size == 0:
207            raise Exception(f"Cannot delete from an empty list")
208        else:
209            current_node = self.head_node
210            prev_node = None
211            while current_node is not None:
212                if current_node.value == value:
213                    if prev_node is None:  # if it's the first node
214                        self.delete_head()
215                    else:
216                        next_node = current_node.next_node
217                        prev_node.next_node = next_node
218                        if next_node is None:
219                            self.tail_node = prev_node
220                        else:
221                            next_node.prev_node = prev_node
222                        self._size -= 1
223                    return
224                prev_node = current_node
225                current_node = current_node.next_node
226        raise ValueError(f"{value} cannot be found in the list")
227
228    def find_by_index(self, index):
229        """Find and return the value of a node of a given index.
230
231        Args:
232            index (int): The index of the node whose value is wanted.
233
234        Returns:
235            any: value of the node at `index`
236
237        Raises:
238            IndexError: If the `index` is out of range.
239        """
240        if index < 0 or index > self._size - 1:
241            raise IndexError(f"Index {index} is out of bounds")
242        counter = 0
243        current_node = self.head_node
244        while current_node is not None:
245            if counter == index:
246                return current_node.value
247            current_node = current_node.next_node
248            counter += 1
249
250    def find_by_value(self, value):
251        """Find the first occurence of a node by value.
252
253        Args:
254            value (any): Value of the node.
255
256        Raises:
257            Exception: If the list is empty.
258            ValueError: If the `value` is not found in the list.
259        """
260        if self._size == 0:
261            raise Exception("Cannot find a value in an empty list.")
262        else:
263            current_node = self.head_node
264            idx = 0
265            while current_node is not None:
266                if current_node.value == value:
267                    print(f"{value} is found at index {idx}")
268                    return
269                else:
270                    current_node = current_node.next_node
271                    idx += 1
272        raise ValueError(f"{value} cannot be found in the list")
273
274    def reverse_find_by_value(self, value):
275        """Find the last occurence of the value. Starts traversing from the tail node.
276
277        Args:
278            value (any): Value of the node.
279
280        Raises:
281            Exception: If the `value` isn't found in the list.
282        """
283        if self._size == 0:
284            raise Exception("Cannot find a value in an empty list.")
285        current_node = self.tail_node
286        reverse_idx = 0
287        while current_node is not None:
288            if current_node.value == value:
289                print(f"{value} is found at index {self._size - reverse_idx - 1}")
290                return
291            current_node = current_node.prev_node
292            reverse_idx += 1
293        raise Exception("f{value} cannot be found in the list")
294
295    def traverse(self):
296        """Traverse the list and print each value."""
297        current_node = self.head_node
298        while current_node is not None:
299            print(current_node.value)
300            current_node = current_node.next_node