Skip to content

Data Structure - Bi-Directional Links

BiDirection

Bases: Generic[_BiDirectionT]

Source code in ures/data_structure/bi_directional_links.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
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
245
246
247
248
class BiDirection(Generic[_BiDirectionT]):
    def __init__(self, value: Any):
        """
        Create a bi-directional linked node.

        Initializes a node with the given value and sets its previous and next pointers to itself,
        forming a circular structure when isolated.

        Args:
            value (Any): The value to store in the node.

        Returns:
            None

        Example:
            >>> node = BiDirection("A")
            >>> node.value
            'A'
            >>> node.prev is node
            True
            >>> node.next is node
            True
        """
        self._prev: _BiDirectionT = cast(_BiDirectionT, self)
        self._next: _BiDirectionT = cast(_BiDirectionT, self)
        self._value: Any = value
        self._id = uuid.uuid4().hex

    @property
    def prev(self) -> _BiDirectionT:
        """
        Get the previous node in the linked structure.

        Returns:
            BiDirection: The previous node.

        Example:
            >>> node = BiDirection("A")
            >>> node.prev is node
            True
        """
        return self._prev

    @property
    def next(self) -> _BiDirectionT:
        """
        Get the next node in the linked structure.

        Returns:
            BiDirection: The next node.

        Example:
            >>> node = BiDirection("A")
            >>> node.next is node
            True
        """
        return self._next

    @property
    def value(self) -> Any:
        """
        Retrieve the value stored in the node.

        Returns:
            Any: The node's value.

        Example:
            >>> node = BiDirection(123)
            >>> node.value
            123
        """
        return self._value

    @property
    def id(self) -> str:
        """
        Get the unique identifier of the node.

        Returns:
            str: A hexadecimal string representing the node's unique ID.

        Example:
            >>> node = BiDirection("A")
            >>> isinstance(node.id, str)
            True
        """
        return self._id

    def insert_after(self, node: _BiDirectionT) -> None:
        """
        Insert a node immediately after the current node.

        Adjusts pointers so that the new node is placed between the current node and its next node.

        Args:
            node (BiDirection): The node to be inserted after the current node.

        Returns:
            None

        Example:
            >>> node1 = BiDirection("A")
            >>> node2 = BiDirection("B")
            >>> node1.insert_after(node2)
            >>> node1.next is node2
            True
            >>> node2.prev is node1
            True
        """
        node._prev = self
        node._next = self._next
        self._next._prev = node
        self._next = node

    def insert_before(self, node: _BiDirectionT) -> None:
        """
        Insert a node immediately before the current node.

        Adjusts pointers so that the new node is placed between the current node's previous node and the current node.

        Args:
            node (BiDirection): The node to be inserted before the current node.

        Returns:
            None

        Example:
            >>> node1 = BiDirection("A")
            >>> node2 = BiDirection("B")
            >>> node1.insert_before(node2)
            >>> node1.prev is node2
            True
            >>> node2.next is node1
            True
        """
        node._prev = self._prev
        node._next = self
        self._prev._next = node
        self._prev = node

    def remove(self) -> None:
        """
        Remove the current node from the linked structure.

        Adjusts the previous and next nodes to bypass the current node and resets the current node's
        pointers to point to itself.

        Returns:
            None

        Example:
            >>> node1 = BiDirection("A")
            >>> node2 = BiDirection("B")
            >>> node1.insert_after(node2)
            >>> node2.remove()
            >>> node1.next is node1
            True
        """
        self._prev._next = self._next
        self._next._prev = self._prev
        self._prev = cast(_BiDirectionT, self)
        self._next = cast(_BiDirectionT, self)

    def search(self, value: Any) -> Optional[_BiDirectionT]:
        """
        Search for a node with the specified value in the linked structure.

        Starting from the current node, traverse through the chain until the value is found or the search
        returns to the starting node.

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

        Returns:
            Optional[BiDirection]: The node with the matching value, or None if not found.

        Example:
            >>> node1 = BiDirection("A")
            >>> node2 = BiDirection("B")
            >>> node3 = BiDirection("C")
            >>> node1.insert_after(node2)
            >>> node2.insert_after(node3)
            >>> found = node1.search("C")
            >>> found.value
            'C'
            >>> not_found = node1.search("D")
            >>> not_found is None
            True
        """
        node: _BiDirectionT = cast(_BiDirectionT, self)
        while node.value != value and node.next != self:
            node = node.next
        return node if node.value == value else None

    def __eq__(self, other: _BiDirectionT) -> bool:
        """
        Check equality between two nodes based on their unique IDs.

        Args:
            other (BiDirection): Another node to compare with.

        Returns:
            bool: True if both nodes have the same unique ID, False otherwise.

        Example:
            >>> node1 = BiDirection("A")
            >>> node2 = BiDirection("A")
            >>> node1 == node1
            True
            >>> node1 == node2
            False
        """
        return self.id == other.id

    def __str__(self) -> str:
        """
        Get the string representation of the node.

        Returns:
            str: A string representing the node's value.

        Example:
            >>> node = BiDirection("Hello")
            >>> str(node)
            'Hello'
        """
        return str(self.value)

    def __repr__(self) -> str:
        """
        Get a detailed string representation of the node.

        Returns:
            str: A string in the format "BiDirection(<value>)" representing the node.

        Example:
            >>> node = BiDirection("World")
            >>> repr(node)
            'BiDirection(World)'
        """
        return f"BiDirection({self.value})"

id property

Get the unique identifier of the node.

Returns:

Name Type Description
str str

A hexadecimal string representing the node's unique ID.
Example

node = BiDirection("A") isinstance(node.id, str) True

next property

Get the next node in the linked structure.

Returns:

Name Type Description
BiDirection _BiDirectionT

The next node.
Example

node = BiDirection("A") node.next is node True

prev property

Get the previous node in the linked structure.

Returns:

Name Type Description
BiDirection _BiDirectionT

The previous node.
Example

node = BiDirection("A") node.prev is node True

value property

Retrieve the value stored in the node.

Returns:

Name Type Description
Any Any

The node's value.
Example

node = BiDirection(123) node.value 123

__eq__(other)

Check equality between two nodes based on their unique IDs.

Parameters:

Name Type Description Default
other BiDirection

Another node to compare with.

 required

Returns:

Name Type Description
bool bool

True if both nodes have the same unique ID, False otherwise.
Example

node1 = BiDirection("A") node2 = BiDirection("A") node1 == node1 True node1 == node2 False

Source code in ures/data_structure/bi_directional_links.py 
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
def __eq__(self, other: _BiDirectionT) -> bool:
    """
    Check equality between two nodes based on their unique IDs.

    Args:
        other (BiDirection): Another node to compare with.

    Returns:
        bool: True if both nodes have the same unique ID, False otherwise.

    Example:
        >>> node1 = BiDirection("A")
        >>> node2 = BiDirection("A")
        >>> node1 == node1
        True
        >>> node1 == node2
        False
    """
    return self.id == other.id

__init__(value)

Create a bi-directional linked node.

Initializes a node with the given value and sets its previous and next pointers to itself, forming a circular structure when isolated.

Parameters:

Name Type Description Default
value Any

The value to store in the node.

 required

Returns:

Type Description

None
Example

node = BiDirection("A") node.value 'A' node.prev is node True node.next is node True

Source code in ures/data_structure/bi_directional_links.py 
 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
def __init__(self, value: Any):
    """
    Create a bi-directional linked node.

    Initializes a node with the given value and sets its previous and next pointers to itself,
    forming a circular structure when isolated.

    Args:
        value (Any): The value to store in the node.

    Returns:
        None

    Example:
        >>> node = BiDirection("A")
        >>> node.value
        'A'
        >>> node.prev is node
        True
        >>> node.next is node
        True
    """
    self._prev: _BiDirectionT = cast(_BiDirectionT, self)
    self._next: _BiDirectionT = cast(_BiDirectionT, self)
    self._value: Any = value
    self._id = uuid.uuid4().hex

__repr__()

Get a detailed string representation of the node.

Returns:

Name Type Description
str str

A string in the format "BiDirection()" representing the node.
Example

node = BiDirection("World") repr(node) 'BiDirection(World)'

Source code in ures/data_structure/bi_directional_links.py 
236
237
238
239
240
241
242
243
244
245
246
247
248
def __repr__(self) -> str:
    """
    Get a detailed string representation of the node.

    Returns:
        str: A string in the format "BiDirection(<value>)" representing the node.

    Example:
        >>> node = BiDirection("World")
        >>> repr(node)
        'BiDirection(World)'
    """
    return f"BiDirection({self.value})"

__str__()

Get the string representation of the node.

Returns:

Name Type Description
str str

A string representing the node's value.
Example

node = BiDirection("Hello") str(node) 'Hello'

Source code in ures/data_structure/bi_directional_links.py 
222
223
224
225
226
227
228
229
230
231
232
233
234
def __str__(self) -> str:
    """
    Get the string representation of the node.

    Returns:
        str: A string representing the node's value.

    Example:
        >>> node = BiDirection("Hello")
        >>> str(node)
        'Hello'
    """
    return str(self.value)

insert_after(node)

Insert a node immediately after the current node.

Adjusts pointers so that the new node is placed between the current node and its next node.

Parameters:

Name Type Description Default
node BiDirection

The node to be inserted after the current node.

 required

Returns:

Type Description
None

None
Example

node1 = BiDirection("A") node2 = BiDirection("B") node1.insert_after(node2) node1.next is node2 True node2.prev is node1 True

Source code in ures/data_structure/bi_directional_links.py 
 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
def insert_after(self, node: _BiDirectionT) -> None:
    """
    Insert a node immediately after the current node.

    Adjusts pointers so that the new node is placed between the current node and its next node.

    Args:
        node (BiDirection): The node to be inserted after the current node.

    Returns:
        None

    Example:
        >>> node1 = BiDirection("A")
        >>> node2 = BiDirection("B")
        >>> node1.insert_after(node2)
        >>> node1.next is node2
        True
        >>> node2.prev is node1
        True
    """
    node._prev = self
    node._next = self._next
    self._next._prev = node
    self._next = node

insert_before(node)

Insert a node immediately before the current node.

Adjusts pointers so that the new node is placed between the current node's previous node and the current node.

Parameters:

Name Type Description Default
node BiDirection

The node to be inserted before the current node.

 required

Returns:

Type Description
None

None
Example

node1 = BiDirection("A") node2 = BiDirection("B") node1.insert_before(node2) node1.prev is node2 True node2.next is node1 True

Source code in ures/data_structure/bi_directional_links.py 
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
def insert_before(self, node: _BiDirectionT) -> None:
    """
    Insert a node immediately before the current node.

    Adjusts pointers so that the new node is placed between the current node's previous node and the current node.

    Args:
        node (BiDirection): The node to be inserted before the current node.

    Returns:
        None

    Example:
        >>> node1 = BiDirection("A")
        >>> node2 = BiDirection("B")
        >>> node1.insert_before(node2)
        >>> node1.prev is node2
        True
        >>> node2.next is node1
        True
    """
    node._prev = self._prev
    node._next = self
    self._prev._next = node
    self._prev = node

remove()

Remove the current node from the linked structure.

Adjusts the previous and next nodes to bypass the current node and resets the current node's pointers to point to itself.

Returns:

Type Description
None

None
Example

node1 = BiDirection("A") node2 = BiDirection("B") node1.insert_after(node2) node2.remove() node1.next is node1 True

Source code in ures/data_structure/bi_directional_links.py 
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
def remove(self) -> None:
    """
    Remove the current node from the linked structure.

    Adjusts the previous and next nodes to bypass the current node and resets the current node's
    pointers to point to itself.

    Returns:
        None

    Example:
        >>> node1 = BiDirection("A")
        >>> node2 = BiDirection("B")
        >>> node1.insert_after(node2)
        >>> node2.remove()
        >>> node1.next is node1
        True
    """
    self._prev._next = self._next
    self._next._prev = self._prev
    self._prev = cast(_BiDirectionT, self)
    self._next = cast(_BiDirectionT, self)

search(value)

Search for a node with the specified value in the linked structure.

Starting from the current node, traverse through the chain until the value is found or the search returns to the starting node.

Parameters:

Name Type Description Default
value Any

The value to search for.

 required

Returns:

Type Description
Optional[_BiDirectionT]

Optional[BiDirection]: The node with the matching value, or None if not found.
Example

node1 = BiDirection("A") node2 = BiDirection("B") node3 = BiDirection("C") node1.insert_after(node2) node2.insert_after(node3) found = node1.search("C") found.value 'C' not_found = node1.search("D") not_found is None True

Source code in ures/data_structure/bi_directional_links.py 
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
def search(self, value: Any) -> Optional[_BiDirectionT]:
    """
    Search for a node with the specified value in the linked structure.

    Starting from the current node, traverse through the chain until the value is found or the search
    returns to the starting node.

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

    Returns:
        Optional[BiDirection]: The node with the matching value, or None if not found.

    Example:
        >>> node1 = BiDirection("A")
        >>> node2 = BiDirection("B")
        >>> node3 = BiDirection("C")
        >>> node1.insert_after(node2)
        >>> node2.insert_after(node3)
        >>> found = node1.search("C")
        >>> found.value
        'C'
        >>> not_found = node1.search("D")
        >>> not_found is None
        True
    """
    node: _BiDirectionT = cast(_BiDirectionT, self)
    while node.value != value and node.next != self:
        node = node.next
    return node if node.value == value else None

Bases: BiDirection['NonCircularBiLink']

Source code in ures/data_structure/bi_directional_links.py 
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
class NonCircularBiLink(BiDirection["NonCircularBiLink"]):
    __slots__ = ("_prev", "_next", "_value")

    def __init__(self, value: Any):
        """Create a non-circular doubly linked list node.

        Args:
                value (Any): The value of the node.
        """
        super().__init__(value)
        self._prev: Optional[NonCircularBiLink] = None
        self._next: Optional[NonCircularBiLink] = None

    @property
    def prev(self) -> Optional[NonCircularBiLink]:
        return self._prev

    @property
    def next(self) -> Optional[NonCircularBiLink]:
        return self._next

    def insert_after(self, node: NonCircularBiLink):
        """Insert a node after the current node.

        Args:
                node (NonCircularDoublyLinkedNode): The node to be inserted.

        Returns:
                None
        """
        node._prev = self
        node._next = self._next
        if self._next:
            self._next._prev = node
        self._next = node

    def insert_before(self, node: NonCircularBiLink):
        """Insert a node before the current node.

        Args:
                node (NonCircularDoublyLinkedNode): The node to be inserted.

        Returns:
                None
        """
        node._next = self
        node._prev = self._prev
        if self._prev:
            self._prev._next = node
        self._prev = node

    def remove(self):
        """Remove the current node from the list.

        Returns:
                None
        """
        if self._prev:
            self._prev._next = self._next
        if self._next:
            self._next._prev = self._prev
        self._prev = None
        self._next = None

    def get_head(self) -> NonCircularBiLink:
        """Get the head of the list starting from the current node.

        Returns:
                NonCircularBiLink: The head node of the list.
        """
        node = self
        while node.prev:
            node = node.prev
        return node

    def search(self, value: Any) -> Optional[NonCircularBiLink]:
        """Search a node by value starting from the current node.

        Args:
                value (Any): The value to be searched.

        Returns:
                Optional[NonCircularDoublyLinkedNode]: The node with the value if found, else None.
        """
        node = self.get_head()
        # traverse the list until the end
        while node:
            if node.value == value:
                return node
            node = node.next
        return None

    def total_nodes(self):
        """Count the total number of nodes in the list starting from the current node.

        Returns:
                int: The total number of nodes in the list.
        """
        count = 0
        node = self.get_head()
        while node:
            count += 1
            node = node.next
        return count

__init__(value)

Create a non-circular doubly linked list node.

Parameters:

Name Type Description Default
value Any

The value of the node.

 required
Source code in ures/data_structure/bi_directional_links.py 
254
255
256
257
258
259
260
261
262
def __init__(self, value: Any):
    """Create a non-circular doubly linked list node.

    Args:
            value (Any): The value of the node.
    """
    super().__init__(value)
    self._prev: Optional[NonCircularBiLink] = None
    self._next: Optional[NonCircularBiLink] = None

get_head()

Get the head of the list starting from the current node.

Returns:

Name Type Description
NonCircularBiLink NonCircularBiLink

The head node of the list.
Source code in ures/data_structure/bi_directional_links.py 
315
316
317
318
319
320
321
322
323
324
def get_head(self) -> NonCircularBiLink:
    """Get the head of the list starting from the current node.

    Returns:
            NonCircularBiLink: The head node of the list.
    """
    node = self
    while node.prev:
        node = node.prev
    return node

insert_after(node)

Insert a node after the current node.

Parameters:

Name Type Description Default
node NonCircularDoublyLinkedNode

The node to be inserted.

 required

Returns:

Type Description

None
Source code in ures/data_structure/bi_directional_links.py 
272
273
274
275
276
277
278
279
280
281
282
283
284
285
def insert_after(self, node: NonCircularBiLink):
    """Insert a node after the current node.

    Args:
            node (NonCircularDoublyLinkedNode): The node to be inserted.

    Returns:
            None
    """
    node._prev = self
    node._next = self._next
    if self._next:
        self._next._prev = node
    self._next = node

insert_before(node)

Insert a node before the current node.

Parameters:

Name Type Description Default
node NonCircularDoublyLinkedNode

The node to be inserted.

 required

Returns:

Type Description

None
Source code in ures/data_structure/bi_directional_links.py 
287
288
289
290
291
292
293
294
295
296
297
298
299
300
def insert_before(self, node: NonCircularBiLink):
    """Insert a node before the current node.

    Args:
            node (NonCircularDoublyLinkedNode): The node to be inserted.

    Returns:
            None
    """
    node._next = self
    node._prev = self._prev
    if self._prev:
        self._prev._next = node
    self._prev = node

remove()

Remove the current node from the list.

Returns:

Type Description

None
Source code in ures/data_structure/bi_directional_links.py 
302
303
304
305
306
307
308
309
310
311
312
313
def remove(self):
    """Remove the current node from the list.

    Returns:
            None
    """
    if self._prev:
        self._prev._next = self._next
    if self._next:
        self._next._prev = self._prev
    self._prev = None
    self._next = None

search(value)

Search a node by value starting from the current node.

Parameters:

Name Type Description Default
value Any

The value to be searched.

 required

Returns:

Type Description
Optional[NonCircularBiLink]

Optional[NonCircularDoublyLinkedNode]: The node with the value if found, else None.
Source code in ures/data_structure/bi_directional_links.py 
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
def search(self, value: Any) -> Optional[NonCircularBiLink]:
    """Search a node by value starting from the current node.

    Args:
            value (Any): The value to be searched.

    Returns:
            Optional[NonCircularDoublyLinkedNode]: The node with the value if found, else None.
    """
    node = self.get_head()
    # traverse the list until the end
    while node:
        if node.value == value:
            return node
        node = node.next
    return None

total_nodes()

Count the total number of nodes in the list starting from the current node.

Returns:

Name Type Description
int

The total number of nodes in the list.
Source code in ures/data_structure/bi_directional_links.py 
343
344
345
346
347
348
349
350
351
352
353
354
def total_nodes(self):
    """Count the total number of nodes in the list starting from the current node.

    Returns:
            int: The total number of nodes in the list.
    """
    count = 0
    node = self.get_head()
    while node:
        count += 1
        node = node.next
    return count