pyTooling.LinkedList

An object-oriented doubly linked-list data structure for Python.

Exceptions

LinkedListException: Base-exception of all exceptions raised by pyTooling.LinkedList.

Classes

Node: The node in an object-oriented doubly linked-list.
LinkedList: An object-oriented doubly linked-list.

Exceptions

exception pyTooling.LinkedList.LinkedListException[source]

Base-exception of all exceptions raised by pyTooling.LinkedList.

Inheritance

Classes

class pyTooling.LinkedList.Node(value, key=None, previousNode=None, nextNode=None)[source]

The node in an object-oriented doubly linked-list.

It contains a reference to the doubly linked list (_list), the previous node (_previous), the next node (_next) and the data (_value). Optionally, a key (_key) can be stored for sorting purposes.

The _previous field of the first node in a doubly linked list is None. Similarly, the _next field of the last node is None. None represents the end of the linked list when iterating it node-by-node.

Inheritance

Parameters:

value (_NodeValue)
key (_NodeKey | None)
previousNode (Node[_NodeKey, _NodeValue] | None)
nextNode (Node[_NodeKey, _NodeValue] | None)

__init__(value, key=None, previousNode=None, nextNode=None)[source]

Initialize a linked list node.

Parameters:

value (TypeVar(_NodeValue)) – Value to store in the node.
key (Optional[TypeVar(_NodeKey)]) – Optional sortable key to store in the node.
previousNode (Optional[Node[TypeVar(_NodeKey), TypeVar(_NodeValue)]]) – Optional reference to the previous node.
nextNode (Optional[Node[TypeVar(_NodeKey), TypeVar(_NodeValue)]]) – Optional reference to the next node.

Raises:

TypeError – If parameter ‘previous’ is not of type Node.
TypeError – If parameter ‘next’ is not of type Node.

Return type:

None

_value: TypeVar(_NodeValue): The value of the node.

_key: Optional[TypeVar(_NodeKey)]: The sortable key of the node.

_nextNode: Optional[Node[_NodeKey, _NodeValue]]: Reference to the next node.

_previousNode: Optional[Node[_NodeKey, _NodeValue]]: Reference to the previous node.

_linkedList: Optional[LinkedList[_NodeValue]]: Reference to the doubly linked list instance.

property List: LinkedList[_NodeValue] | None

Read-only property to access the linked list, this node belongs to.

Returns:: The linked list, this node is part of, or None.

property PreviousNode: Node[_NodeKey, _NodeValue] | None

Read-only property to access nodes predecessor.

This reference is None if the node is the first node in the doubly linked list.

Returns:: The node before the current node or None.

property NextNode: Node[_NodeKey, _NodeValue] | None

Read-only property to access nodes successor.

This reference is None if the node is the last node in the doubly linked list.

Returns:: The node after the current node or None.

property Key: _NodeKey

Property to access the node’s internal key.

The key can be a scalar or a reference to an object.

Returns:: The node’s key.

property Value: _NodeValue

Property to access the node’s internal data.

The data can be a scalar or a reference to an object.

Returns:: The node’s value.

InsertNodeBefore(node)[source]

Insert a node before this node.

Parameters:

node (Node[TypeVar(_NodeKey), TypeVar(_NodeValue)]) – Node to insert.

Raises:

ValueError – If parameter ‘node’ is None.
TypeError – If parameter ‘node’ is not of type Node.
LinkedListException – If parameter ‘node’ is already part of another linked list.

Return type:

None

InsertNodeAfter(node)[source]

Insert a node after this node.

Parameters:

node (Node[TypeVar(_NodeKey), TypeVar(_NodeValue)]) – Node to insert.

Raises:

ValueError – If parameter ‘node’ is None.
TypeError – If parameter ‘node’ is not of type Node.
LinkedListException – If parameter ‘node’ is already part of another linked list.

Return type:

None

Remove()[source]

Remove this node from the linked list.

Return type:: TypeVar(_NodeValue)

IterateToFirst(includeSelf=False)[source]

Return a generator iterating backward from this node to the list’s first node.

Optionally, this node can be included into the generated sequence.

Parameters:: includeSelf (bool) – If True, include this node into the sequence, otherwise start at previous node.
Return type:: Generator[Node[TypeVar(_NodeKey), TypeVar(_NodeValue)], None, None]
Returns:: A sequence of nodes towards the list’s first node.

IterateToLast(includeSelf=False)[source]

Return a generator iterating forward from this node to the list’s last node.

Optionally, this node can be included into the generated sequence by setting.

Parameters:: includeSelf (bool) – If True, include this node into the sequence, otherwise start at next node.
Return type:: Generator[Node[TypeVar(_NodeKey), TypeVar(_NodeValue)], None, None]
Returns:: A sequence of nodes towards the list’s last node.

__repr__()[source]

Return repr(self).

Return type:: str

class pyTooling.LinkedList.LinkedList(nodes=None)[source]

An object-oriented doubly linked-list.

Inheritance

Parameters:: nodes (Iterable[Node[_NodeKey, _NodeValue]] | None)

__init__(nodes=None)[source]

Initialize an empty linked list.

Optionally, an iterable can be given to initialize the linked list. The order is preserved.

Parameters:

nodes (Optional[Iterable[Node[TypeVar(_NodeKey), TypeVar(_NodeValue)]]]) – Optional iterable to initialize the linked list.

Raises:

TypeError – If parameter ‘nodes’ is not an iterable.
TypeError – If parameter ‘nodes’ items are not of type Node.
LinkedListException – If parameter ‘nodes’ contains items which are already part of another linked list.

Return type:

None

_firstNode: Optional[Node[TypeVar(_NodeKey), TypeVar(_NodeValue)]]: Reference to the first node of the linked list.

_lastNode: Optional[Node[TypeVar(_NodeKey), TypeVar(_NodeValue)]]: Reference to the last node of the linked list.

_count: int: Number of nodes in the linked list.

property IsEmpty: int

Read-only property to access the number of .

This reference is None if the node is the last node in the doubly linked list.

Returns:: True if linked list is empty, otherwise False

property Count: int

Read-only property to access the number of nodes in the linked list.

Returns:: Number of nodes.

property FirstNode: Node[_NodeKey, _NodeValue] | None

Read-only property to access the first node in the linked list.

In case the list is empty, None is returned.

Returns:: First node.

property LastNode: Node[_NodeKey, _NodeValue] | None

Read-only property to access the last node in the linked list.

In case the list is empty, None is returned.

Returns:: Last node.

Clear()[source]

Clear the linked list.

Return type:: None

InsertBeforeFirst(node)[source]

Insert a node before the first node.

Parameters:

node (Node[TypeVar(_NodeKey), TypeVar(_NodeValue)]) – Node to insert.

Raises:

ValueError – If parameter ‘node’ is None.
TypeError – If parameter ‘node’ is not of type Node.
LinkedListException – If parameter ‘node’ is already part of another linked list.

Return type:

None

InsertAfterLast(node)[source]

Insert a node after the last node.

Parameters:

node (Node[TypeVar(_NodeKey), TypeVar(_NodeValue)]) – Node to insert.

Raises:

ValueError – If parameter ‘node’ is None.
TypeError – If parameter ‘node’ is not of type Node.
LinkedListException – If parameter ‘node’ is already part of another linked list.

Return type:

None

RemoveFirst()[source]

Remove first node from linked list.

Return type:: Node[TypeVar(_NodeKey), TypeVar(_NodeValue)]
Returns:: First node.
Raises:: LinkedListException – If linked list is empty.

RemoveLast()[source]

Remove last node from linked list.

Return type:: Node[TypeVar(_NodeKey), TypeVar(_NodeValue)]
Returns:: Last node.
Raises:: LinkedListException – If linked list is empty.

GetNodeByIndex(index)[source]

Access a node in the linked list by position.

Parameters:: index (int) – Node position to access.
Return type:: Node[TypeVar(_NodeKey), TypeVar(_NodeValue)]
Returns:: Node at the given position.
Raises:: ValueError – If parameter ‘position’ is out of range.

Note

The algorithm starts iterating nodes from the shorter end.

Reverse()[source]

Reverse the order of nodes in the linked list.

Return type:: None

Sort(key=None, reverse=False)[source]

Sort the linked list in ascending or descending order.

The sort operation is stable.

Parameters:

key (Optional[Callable[[Node[TypeVar(_NodeKey), TypeVar(_NodeValue)]], Any]]) – Optional function to access a user-defined key for sorting.
reverse (bool) – Optional parameter, if True sort in descending order, otherwise in ascending order.

Return type:

None

Note

The linked list is converted to an array, which is sorted by quicksort using the builtin sort(). Afterward, the sorted array is used to reconstruct the linked list in requested order.

IterateFromFirst()[source]

Return a generator iterating forward from list’s first node to list’s last node.

Return type:: Generator[Node[TypeVar(_NodeKey), TypeVar(_NodeValue)], None, None]
Returns:: A sequence of nodes towards the list’s last node.

IterateFromLast()[source]

Return a generator iterating backward from list’s last node to list’s first node.

Return type:: Generator[Node[TypeVar(_NodeKey), TypeVar(_NodeValue)], None, None]
Returns:: A sequence of nodes towards the list’s first node.

ToList(reverse=False)[source]

Convert the linked list to a list.

Optionally, the resulting list can be constructed in reverse order.

Parameters:: reverse (bool) – Optional parameter, if True return in reversed order, otherwise in normal order.
Return type:: List[Node[TypeVar(_NodeKey), TypeVar(_NodeValue)]]
Returns:: A list (array) of this linked list’s values.

ToTuple(reverse=False)[source]

Convert the linked list to a tuple.

Optionally, the resulting tuple can be constructed in reverse order.

Parameters:: reverse (bool) – Optional parameter, if True return in reversed order, otherwise in normal order.
Return type:: Tuple[Node[TypeVar(_NodeKey), TypeVar(_NodeValue)], ...]
Returns:: A tuple of this linked list’s values.

__len__()[source]

Returns the number of nodes in the linked list.

Return type:: int
Returns:: Number of nodes.

__getitem__(index)[source]

Access a node’s value by its index.

Parameters:: index (int) – Node index to access.
Return type:: TypeVar(_NodeValue)
Returns:: Node’s value at the given index.
Raises:: ValueError – If parameter ‘index’ is out of range.

Note

The algorithm starts iterating nodes from the shorter end.

__setitem__(index, value)[source]

Set the value of node at the given position.

Parameters:

index (int) – Index of the node to modify.
value (TypeVar(_NodeValue)) – New value for the node’s value addressed by index.

Return type:

None

__delitem__(index)[source]

Remove a node at the given index.

Parameters:: index (int) – Index of the node to remove.
Return type:: Node[TypeVar(_NodeKey), TypeVar(_NodeValue)]
Returns:: Removed node.