|
""" |
|
Linked List |
|
=========== |
|
|
|
Visualization : |
|
--------------- |
|
head |
|
\ |
|
\ |
|
None <- [1st elem] <=> [2nd elem] <=> [3rd elem] ..... <=> [nth elem] -> None |
|
\ |
|
\ |
|
tail |
|
|
|
`<-` : denotes a link to left side |
|
`->` : denotes a link to right side |
|
`<=>` : denotes a coloated visualisation of link from left and right. |
|
* `<-` + `->` = `<=>` |
|
|
|
Notes : |
|
------- |
|
* Every element have `left` and `right` link . |
|
* Hence a link between two elements is double . |
|
* we can traverse from [1st elem] to [nth elem] as well as from [nth elem] to [1st elem] . |
|
""" |
|
import sys |
|
import inspect |
|
import dataclasses |
|
import datetime |
|
from typing import Any, Optional, TypeVar, Dict, Union, Iterable, Generator, Tuple, Type, Self |
|
from collections.abc import Iterator |
|
|
|
T = TypeVar('T') |
|
|
|
class MemoryBlock: |
|
""" |
|
Represents a memory block in a doubly linked list. |
|
|
|
Attributes: |
|
data (Any): The data stored in the memory block. |
|
left (Optional[MemoryBlock]): The left (previous) memory block. |
|
right (Optional[MemoryBlock]): The right (next) memory block. |
|
""" |
|
|
|
def __init__(self, data: Any, left: Optional['MemoryBlock'] = None, right: Optional['MemoryBlock'] = None): |
|
""" |
|
Initializes a MemoryBlock instance. |
|
|
|
Args: |
|
data (Any): The data to store in the memory block. |
|
left (Optional[MemoryBlock]): The left memory block. |
|
right (Optional[MemoryBlock]): The right memory block. |
|
""" |
|
self._data = data |
|
self._left = left |
|
self._right = right |
|
|
|
@property |
|
def data(self) -> 'MemoryBlock': |
|
"""Gets the data stored in the memory block.""" |
|
return self._data |
|
|
|
@property |
|
def left(self) -> 'MemoryBlock': |
|
"""Gets the left memory block.""" |
|
return self._left |
|
|
|
@property |
|
def right(self) -> 'MemoryBlock': |
|
"""Gets the right memory block.""" |
|
return self._right |
|
|
|
@data.setter |
|
def data(self, value: T) -> T: |
|
"""Sets the data in the memory block.""" |
|
self._data = value |
|
return self._data |
|
|
|
@left.setter |
|
def left(self, value: T) -> T: |
|
"""Sets the left memory block.""" |
|
self._left = value |
|
return self._left |
|
|
|
@right.setter |
|
def right(self, value: T) -> T: |
|
"""Sets the right memory block.""" |
|
self._right = value |
|
return self._right |
|
|
|
def __str__(self) -> str: |
|
"""Returns a string representation of the memory block.""" |
|
return f"{self._data}" |
|
|
|
def __repr__(self): |
|
"""Returns a detailed string representation of the memory block.""" |
|
return f"MemoryBlock({self._data}, left={self._left}, right={self._right})" |
|
|
|
@dataclasses.dataclass(frozen=True) |
|
class Metadata: |
|
""" |
|
Metadata for a LinkedList Node. |
|
""" |
|
created_at: Optional[str] = datetime.datetime.now() |
|
|
|
|
|
class LinkedListNode(MemoryBlock): |
|
""" |
|
Represents a node in a doubly linked list. |
|
|
|
Attributes: |
|
metadata (Metadata): Metadata associated with the node. |
|
""" |
|
|
|
def __init__(self, data, left=None, right=None, metadata: Metadata = Metadata()): |
|
""" |
|
Initializes a LinkedListNode instance. |
|
|
|
Args: |
|
data (Any): The data to store in the node. |
|
left (Optional[MemoryBlock]): The left memory block. |
|
right (Optional[MemoryBlock]): The right memory block. |
|
metadata (Metadata): Metadata associated with the node. |
|
""" |
|
self._metadata = metadata |
|
super().__init__(data, left, right) |
|
|
|
@property |
|
def metadata(self): |
|
"""Gets the metadata associated with the node.""" |
|
return self._metadata |
|
|
|
|
|
class LRIterator(Iterator): |
|
""" |
|
Iterator for traversing a linked list from left to right. |
|
|
|
Attributes: |
|
_pointer (Optional[MemoryBlock]): The current memory block being traversed. |
|
""" |
|
|
|
def __init__(self, ll: 'LinkedList'): |
|
""" |
|
Initializes the iterator. |
|
|
|
Args: |
|
ll (LinkedList): The linked list to iterate over. |
|
""" |
|
self._pointer: Optional[MemoryBlock] = ll.head.right |
|
|
|
def __next__(self): |
|
""" |
|
Returns the next memory block in the iteration. |
|
|
|
Raises: |
|
StopIteration: If the end of the list is reached. |
|
""" |
|
if self._pointer: |
|
value = self._pointer |
|
self._pointer = self._pointer.right |
|
return value |
|
else: |
|
raise StopIteration |
|
|
|
|
|
class RLIterator(Iterator): |
|
""" |
|
Iterator for traversing a linked list from right to left. |
|
|
|
Attributes: |
|
_pointer (Optional[MemoryBlock]): The current memory block being traversed. |
|
""" |
|
|
|
def __init__(self, ll: 'LinkedList'): |
|
""" |
|
Initializes the iterator. |
|
|
|
Args: |
|
ll (LinkedList): The linked list to iterate over. |
|
""" |
|
self._pointer: Optional[MemoryBlock] = ll.tail.left |
|
|
|
def __next__(self): |
|
""" |
|
Returns the next memory block in the iteration. |
|
|
|
Raises: |
|
StopIteration: If the start of the list is reached. |
|
""" |
|
if self._pointer: |
|
value = self._pointer |
|
self._pointer = self._pointer.left |
|
return value |
|
else: |
|
raise StopIteration |
|
|
|
class LinkedList: |
|
""" |
|
Doubly Linked List Implementation |
|
|
|
----- |
|
Usage |
|
----- |
|
|
|
# Prepare |
|
>>> ll = LinkedList() |
|
>>> ll.append(3) |
|
>>> ll.prepend(4) |
|
>>> ll.append(8) |
|
>>> print(ll) |
|
[4, 3, 8] |
|
|
|
# Fetch Node data |
|
>>> value=ll[1] |
|
>>> value.data |
|
3 |
|
|
|
# Prepend Node |
|
>>> ll.prepend(6) |
|
>>> print(ll) |
|
[6, 4, 3, 8] |
|
|
|
# Get Node by Index |
|
>>> value=ll[2] |
|
>>> value.data |
|
3 |
|
|
|
# Index Map |
|
>>> ll.index_store |
|
{0: MemoryBlock(6, left=None, right=4), 1: MemoryBlock(4, left=6, right=3), 2: MemoryBlock(3, left=4, right=8), 3: MemoryBlock(8, left=3, right=None)} |
|
|
|
# Length |
|
>>> len(ll) |
|
4 |
|
|
|
# Iteration |
|
>>> [v.data for v in ll] |
|
[6, 4, 3, 8] |
|
|
|
# Reverse Iteration |
|
# # ( It Sets the order of linkedlist in reverse ) |
|
>>> ll.root_iterator_cls=RLIterator |
|
>>> [v.data for v in ll] |
|
[8, 3, 4, 6] |
|
|
|
# Reverse Iteration : Method 2 |
|
# # - using Operations.reversed(...) function |
|
>>> ll.root_iterator_cls=LRIterator |
|
>>> print([v.data for v in Operations.reversed(ll)]) |
|
[8, 3, 4, 6] |
|
|
|
# Reverse Iteration : Method 3 |
|
# # - using builtin reversed(...) function |
|
>>> ll.root_iterator_cls=LRIterator |
|
>>> print([v.data for v in reversed(ll)]) |
|
[8, 3, 4, 6] |
|
|
|
--- |
|
|
|
NOTES |
|
- does not support -ve indices as of now |
|
|
|
""" |
|
|
|
def __init__(self, root_iterator_cls: Union[str, Type[Iterator]] = 'LRIterator'): |
|
""" |
|
Initializes a LinkedList instance. |
|
|
|
Args: |
|
root_iterator_cls (Iterator): The iterator class used for traversal. |
|
""" |
|
# Positioning Markers |
|
self._head = LinkedListNode(-1) |
|
self._tail = LinkedListNode(-1) |
|
# Initialization |
|
self._head._right = self._tail |
|
self._head._left = None |
|
self._tail._left = self._head |
|
self._tail._right = None |
|
# Index Map |
|
self._index_store: Dict[int, LinkedListNode] = {} |
|
# Config |
|
# # Root Iterator |
|
self.root_iterator_cls: Iterator = root_iterator_cls |
|
|
|
@property |
|
def head(self) -> LinkedListNode: |
|
"""Gets the head node of the list.""" |
|
return self._head |
|
|
|
@property |
|
def tail(self) -> LinkedListNode: |
|
"""Gets the tail node of the list.""" |
|
return self._tail |
|
|
|
@property |
|
def index_store(self) -> LinkedListNode: |
|
"""Gets the index store of the list.""" |
|
return self._index_store |
|
|
|
def append(self, data: Any): |
|
""" |
|
Adds a new element at the end of the list. |
|
|
|
Args: |
|
data (Any): The data to append. |
|
|
|
Complexity: |
|
O(1) |
|
""" |
|
# current : last-element <--- Tail |
|
# new : last-element <--- . <--- Tail |
|
last_element: LinkedListNode = self._tail.left |
|
|
|
# adjusting indexes |
|
index = self._tail.data |
|
index += 1 |
|
# creation |
|
new_node: LinkedListNode = LinkedListNode(data, metadata=Metadata()) |
|
self._tail.left = new_node |
|
if last_element is self._head: |
|
# last_element is head |
|
last_element.right = new_node |
|
new_node.left = None |
|
self._head.data += 1 |
|
else: |
|
self._joint(last_element, new_node) |
|
# storing adjusted indexes |
|
self._index_store[index] = new_node |
|
self._tail.data = index |
|
|
|
def prepend(self, data: Any): |
|
""" |
|
Adds a new element at the beginning of the list. |
|
|
|
Args: |
|
data (Any): The data to prepend. |
|
|
|
Complexity: |
|
O(N) |
|
""" |
|
# current : Head ---> first-element |
|
# new : Head ---> . ---> first-element |
|
first_element: LinkedListNode = self._head.right |
|
# creation |
|
new_node: LinkedListNode = LinkedListNode(data, metadata=Metadata()) |
|
self._head.right = new_node |
|
if first_element is self._tail: |
|
# first_element is tail |
|
self._tail.left = new_node |
|
new_node.right = None |
|
self._head.data += 1 |
|
else: |
|
self._joint(new_node, first_element) |
|
# adjusting indexes |
|
index = self._tail.data |
|
index += 1 |
|
for idx in range(index, 0, -1): |
|
self._index_store[idx] = self._index_store[idx-1] |
|
else: |
|
self._index_store[0] = new_node |
|
self._tail.data = index |
|
|
|
def sort(self): |
|
raise NotImplementedError('...') |
|
|
|
def reverse(self): |
|
""" |
|
Reverses a linked list |
|
|
|
Complexity: |
|
O(1) |
|
""" |
|
temp = self._head._right |
|
while temp: |
|
current_node = temp |
|
next_node = temp._right |
|
current_node._left, current_node._right = current_node._right, current_node._left |
|
temp = next_node |
|
self._head._right, self._tail._left = self._tail._left, self._head._right |
|
|
|
def pop(self): |
|
raise NotImplementedError('...') |
|
|
|
def insert(self): |
|
raise NotImplementedError('...') |
|
|
|
def index(self): |
|
raise NotImplementedError('...') |
|
|
|
def extend(self): |
|
raise NotImplementedError('...') |
|
|
|
def count(self): |
|
raise NotImplementedError('...') |
|
|
|
def copy(self): |
|
raise NotImplementedError('...') |
|
|
|
def clear(self): |
|
raise NotImplementedError('...') |
|
|
|
def remove(self): |
|
raise NotImplementedError('...') |
|
|
|
def delete(self, node: LinkedListNode): |
|
""" |
|
special functionality |
|
- it saves the time to search the node |
|
""" |
|
raise NotImplementedError('...') |
|
|
|
def _joint(self, left_node: LinkedListNode, right_node: LinkedListNode) -> None: |
|
""" |
|
Joins two memory blocks. |
|
|
|
Args: |
|
left_node (LinkedListNode): The left memory block. |
|
right_node (LinkedListNode): The right memory block. |
|
""" |
|
left_node.right = right_node |
|
right_node.left = left_node |
|
|
|
def __rmul__(self): |
|
raise NotImplementedError('...') |
|
|
|
def __mul__(self, value: int): |
|
_ll = LinkedList() |
|
while value: |
|
_pointer = self._head._right |
|
while _pointer: |
|
_ll.append(_pointer._data) |
|
_pointer=_pointer._right |
|
value -= 1 |
|
return _ll |
|
|
|
def __imul__(self, value: int) -> 'LinkedList': |
|
self_last_node = self._tail.left |
|
while value: |
|
_pointer = self._head._right |
|
while _pointer != self_last_node: |
|
self.append(_pointer.data) |
|
_pointer=_pointer._right |
|
else: |
|
self.append(self_last_node) |
|
value -= 1 |
|
return self |
|
|
|
def __add__(self, other: 'LinkedList') -> 'LinkedList': |
|
new_ll = LinkedList() |
|
_pointer = self._head._right |
|
while _pointer: |
|
new_ll.append(_pointer.data) |
|
_pointer = _pointer.right |
|
_pointer = other._head._right |
|
while _pointer: |
|
new_ll.append(_pointer.data) |
|
_pointer = _pointer.right |
|
return new_ll |
|
|
|
def __iadd__(self, other: 'LinkedList') -> Self: |
|
# first node @ self |
|
self_last_element_pointer = self._tail._left |
|
# last node @ other |
|
other_first_element_pointer = other._head._right |
|
# linking |
|
self_last_element_pointer._right = other_first_element_pointer |
|
other_first_element_pointer.left = self_last_element_pointer |
|
self._tail = other._tail |
|
return self |
|
|
|
def __lt__(self, other: 'LinkedList') -> Optional[bool]: |
|
|
|
self_pointer = self._head._right |
|
other_pointer = other._head._right |
|
|
|
# iterative check for inequality resolution |
|
while self_pointer and other_pointer: |
|
if self_pointer.data < other_pointer.data: |
|
return True |
|
if self_pointer.data > other_pointer.data: |
|
return False |
|
# elements are equal |
|
self_pointer = self_pointer._right |
|
other_pointer = other_pointer.right |
|
# exact equality case |
|
if self_pointer == other_pointer == None: |
|
return False |
|
# shorter length case |
|
if self_pointer == None: |
|
return True |
|
if other_pointer == None: |
|
return False |
|
|
|
|
|
def __ge__(self, other: 'LinkedList'): |
|
self_pointer = self._head._right |
|
other_pointer = other._head._right |
|
|
|
# iterative check for inequality resolution |
|
while self_pointer and other_pointer: |
|
if self_pointer.data > other_pointer.data: |
|
return True |
|
if self_pointer.data < other_pointer.data: |
|
return False |
|
# elements are equal |
|
self_pointer = self_pointer._right |
|
other_pointer = other_pointer.right |
|
# exact equality case |
|
if self_pointer == other_pointer == None: |
|
return True |
|
# shorter length case |
|
if self_pointer == None: # LHS shorter |
|
return False |
|
if other_pointer == None: # RHS shorter |
|
return True |
|
|
|
def __gt__(self, other: 'LinkedList'): |
|
|
|
self_pointer = self._head._right |
|
other_pointer = other._head._right |
|
|
|
# iterative check for inequality resolution |
|
while self_pointer and other_pointer: |
|
if self_pointer.data > other_pointer.data: |
|
return True |
|
if self_pointer.data < other_pointer.data: |
|
return False |
|
# elements are equal |
|
self_pointer = self_pointer._right |
|
other_pointer = other_pointer.right |
|
# exact equality case |
|
if self_pointer == other_pointer == None: |
|
return False |
|
# shorter length case |
|
if self_pointer == None: # LHS shorter |
|
return False |
|
if other_pointer == None: # RHS shorter |
|
return True |
|
|
|
|
|
def __le__(self, other: 'LinkedList'): |
|
self_pointer = self._head._right |
|
other_pointer = other._head._right |
|
|
|
# iterative check for inequality resolution |
|
while self_pointer and other_pointer: |
|
if self_pointer.data < other_pointer.data: |
|
return True |
|
if self_pointer.data > other_pointer.data: |
|
return False |
|
# elements are equal |
|
self_pointer = self_pointer._right |
|
other_pointer = other_pointer.right |
|
# exact equality case |
|
if self_pointer == other_pointer == None: |
|
return True |
|
# shorter length case |
|
if self_pointer == None: |
|
return True |
|
if other_pointer == None: |
|
return False |
|
|
|
def __eq__(self, other: 'LinkedList'): |
|
""" |
|
Comapring two linked lists for equlity |
|
""" |
|
self_pointer = self._head._right |
|
other_pointer = other.head.right |
|
|
|
while self_pointer and other_pointer: |
|
if self_pointer.data != other_pointer.data: |
|
return False |
|
self_pointer = self_pointer._right |
|
other_pointer = other_pointer.right |
|
if self_pointer == other_pointer == None: |
|
return True |
|
return False |
|
|
|
def __ne__(self, other: 'LinkedList'): |
|
return not self.__eq__(other) |
|
|
|
def __delitem__(self, index: int): |
|
|
|
_pointer = self._head._right |
|
index_counter = 0 |
|
while _pointer: |
|
if index_counter == index: |
|
prev_node = _pointer.left |
|
next_node = _pointer.right |
|
# link prev --> next |
|
if prev_node: |
|
prev_node.right = next_node |
|
else: # this means current pointer is first node |
|
self._head.right = next_node |
|
# link next <-- prev |
|
if next_node: |
|
next_node.left = prev_node |
|
else: # this means current pointer is last node |
|
self._tail.left = prev_node |
|
# resume the pointer |
|
_pointer = _pointer.right |
|
index_counter += 1 |
|
break # break from here & resume in next loop --- (1) |
|
_pointer = _pointer.right |
|
index_counter += 1 |
|
else: |
|
# if loop completes without being able to search a valid index |
|
return |
|
|
|
# post node deletion : adjust the indexes in index_store. |
|
# decrement the indexes of remaining nodes --- (1) resuming from prev loop break |
|
while _pointer: |
|
self._index_store[index_counter-1] = _pointer |
|
_pointer = _pointer.right |
|
index_counter += 1 |
|
else: |
|
# updating tail with last index value |
|
self._tail._data = index_counter-2 |
|
# removing the stale index entry from index_store |
|
self._index_store.pop(index_counter-1, None) |
|
|
|
def __contains__(self, value: Union[Any, LinkedListNode]) -> bool: |
|
_pointer = self._head.right |
|
while _pointer: |
|
if (isinstance(value, LinkedListNode) and _pointer.data == value.data) or _pointer.data == value: |
|
return True |
|
_pointer = _pointer.right |
|
return False |
|
|
|
def __getitem__(self, key): |
|
""" |
|
Gets an item from the linked list by index or slice. |
|
|
|
Args: |
|
key (int or slice): The index or slice to retrieve. |
|
|
|
Returns: |
|
LinkedListNode or LinkedList: The node or sublist corresponding to the key. |
|
|
|
Raises: |
|
TypeError: If the key is not an integer or slice. |
|
""" |
|
if isinstance(key, int): |
|
# Handle integer indexing |
|
return self._index_store[key] |
|
elif isinstance(key, slice): |
|
# Handle slicing |
|
_ll = LinkedList() |
|
step = key.step if key.step is not None else 1 |
|
stop = key.stop if key.stop and 0 <= key.stop < len(self._index_store) else len(self._index_store) |
|
start = key.start if key.start and 0 <= key.start < len(self._index_store) else 0 |
|
|
|
for idx in range(start, stop, step): |
|
obj = self._index_store[idx] |
|
_ll.append(obj.data) |
|
return _ll |
|
else: |
|
raise TypeError("Invalid key type") |
|
|
|
def __setitem__(self): |
|
raise NotImplementedError('...') |
|
|
|
def __iter__(self): |
|
""" |
|
Returns an iterator for the linked list. |
|
|
|
Returns: |
|
Iterator: The iterator for the linked list. |
|
""" |
|
if inspect.isclass(self.root_iterator_cls): |
|
return self.root_iterator_cls(self) |
|
else: |
|
# memory efficient approach |
|
if self.root_iterator_cls == 'LRIterator': |
|
return LRIterator(self) |
|
if self.root_iterator_cls == 'RLIterator': |
|
return RLIterator(self) |
|
raise NotImplementedError('root_iterator_cls specified isn`t supported yet') |
|
|
|
def __len__(self): |
|
""" |
|
Returns the length of the linked list. |
|
|
|
Returns: |
|
int: The length of the linked list. |
|
""" |
|
return self._tail.data - self._head.data + 1 |
|
|
|
def __sizeof__(self): |
|
# Calculate the size of all nodes |
|
all_nodes_size = sys.getsizeof(self._head) + sys.getsizeof(self._tail) |
|
for node in iter(self): |
|
all_nodes_size += sys.getsizeof(node) |
|
|
|
# Calculate the size of the idex store |
|
index_store_size = sys.getsizeof(self._index_store) |
|
|
|
# Calculate the size of the iterator class reference |
|
iterator_class_ref_size = sys.getsizeof(self.root_iterator_cls) |
|
|
|
# Add the size of the object itself (base object size) |
|
# This is typically the size of an empty instance of the class |
|
base_object_size = super().__sizeof__() |
|
|
|
return base_object_size + iterator_class_ref_size + index_store_size + all_nodes_size |
|
|
|
def print_detailed_size_information(self): |
|
# Calculate the size of all nodes |
|
all_nodes_size = sys.getsizeof(self._head) + sys.getsizeof(self._tail) |
|
for node in iter(self): |
|
all_nodes_size += sys.getsizeof(node) |
|
|
|
# Calculate the size of the idex store |
|
index_store_size = sys.getsizeof(self._index_store) |
|
|
|
# Calculate the size of the iterator class reference |
|
iterator_class_ref_size = sys.getsizeof(self.root_iterator_cls) |
|
|
|
# Add the size of the object itself (base object size) |
|
# This is typically the size of an empty instance of the class |
|
base_object_size = super().__sizeof__() |
|
|
|
total = base_object_size + iterator_class_ref_size + index_store_size + all_nodes_size |
|
percent = lambda field: field/total*100 |
|
cols = ['base_object_size', 'iterator_class_ref_size', 'index_store_size', 'all_nodes_size'] |
|
data = [ |
|
cols, |
|
[locals()[v_name] for v_name in cols] + ['bytes'], |
|
[percent(locals()[v_name]) for v_name in cols] + ['%'] |
|
] |
|
|
|
# Using f-strings (Python 3.6+) |
|
header = f"| {data[0][0]:<10} | {data[0][1]:^5} | {data[0][2]:>10} | {data[0][3]:>10} |" |
|
print("-" * len(header)) |
|
print(header) |
|
print("-" * len(header)) |
|
for row in data[1:]: |
|
print(f"| {row[0]:^16.2f} | {row[1]:^23.2f} | {row[2]:^16.2f} | {row[3]:^14.2f} | {row[4]:^16} | ") |
|
print("-" * len(header)) |
|
print(f"* Total Size : {total}") |
|
print("\n") |
|
|
|
def __reversed__(self): |
|
""" |
|
Returns a reversed iterator for the linked list. |
|
|
|
Returns: |
|
Iterator: The reversed iterator for the linked list. |
|
""" |
|
if self.root_iterator_cls == RLIterator: |
|
for pointer in LRIterator(self): |
|
yield pointer |
|
else: |
|
for pointer in RLIterator(self): |
|
yield pointer |
|
|
|
def __str__(self) -> str: |
|
""" |
|
Returns a string representation of the linked list. |
|
|
|
Returns: |
|
str: The string representation of the linked list. |
|
""" |
|
return f"[{', '.join([str(node.data) for node in iter(self)]).strip(',')}]" |
|
|
|
class Operations: |
|
""" |
|
Utility class for performing operations on linked lists. |
|
""" |
|
|
|
@staticmethod |
|
def reversed(ll: LinkedList, method=1) -> Generator[LinkedListNode, None, None]: |
|
""" |
|
Generates linked list nodes in reverse order. |
|
|
|
Args: |
|
ll (LinkedList): The linked list to reverse. |
|
method (int): The method to use for reversal (1 or 2). |
|
|
|
Returns: |
|
Generator[LinkedListNode, None, None]: A generator for the reversed nodes. |
|
|
|
Complexity: |
|
O(N) |
|
""" |
|
if not issubclass(ll.root_iterator_cls, Iterator): |
|
raise Exception('must implement typing.Iterator class') |
|
|
|
if ll.root_iterator_cls == LRIterator: |
|
if method == 1: |
|
pointer = ll.tail.left |
|
while pointer: |
|
yield pointer |
|
pointer = pointer.left |
|
elif method == 2: |
|
for pointer in RLIterator(ll): |
|
yield pointer |
|
elif ll.root_iterator_cls == RLIterator: |
|
if method == 1: |
|
pointer = ll.head.right |
|
while pointer: |
|
yield pointer |
|
pointer = pointer.right |
|
elif method == 2: |
|
for pointer in RLIterator(ll): |
|
yield pointer |
|
else: |
|
raise NotImplementedError('`root_iterator_cls` not specified') |
|
|
|
@staticmethod |
|
def enumerate(ll: Union[LinkedList, Generator[LinkedListNode, None, None]] ) -> Generator[Tuple[int, LinkedListNode], None, None]: |
|
""" |
|
Enumerates the nodes in the linked list. |
|
|
|
Args: |
|
ll (LinkedList or Generator): The linked list or generator to enumerate. |
|
|
|
Returns: |
|
Generator[Tuple[int, LinkedListNode], None, None]: A generator for the enumerated nodes. |
|
""" |
|
_iterator: Iterator = iter(ll) |
|
index_counter = 0 |
|
for pointer in _iterator: |
|
yield (index_counter, pointer) |
|
index_counter += 1 |
|
|
|
@staticmethod |
|
def ll_from(obj: Iterable) -> LinkedList: |
|
""" |
|
Converts an iterable to a linked list. |
|
|
|
Args: |
|
obj (Iterable): The iterable to convert. |
|
|
|
Returns: |
|
LinkedList: The resulting linked list. |
|
""" |
|
_ll = LinkedList() |
|
for value in obj: |
|
_ll.append(value) |
|
return _ll |
