pyTooling.LinkedList

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

See also

pyTooling.Tree: → A tree data structure.
pyTooling.Graph: → A graph data structure.

Exceptions

LinkedListError: Base-exception of all exceptions raised by pyTooling.LinkedList.
InternalError: The exception is raised when the linked list’s internal state became inconsistent.
NotInAListError: The exception is raised when a node is not assigned to any linked list.
NotInSameListError: The exception is raised when a node is assigned to a different linked list than expected.
EmptyListError: The exception is raised when an operation needs at least one element, but the linked list is empty.
NodeNotFoundError: The exception is raised when no node matching the search criterion was found.

Classes

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

Exceptions

exception pyTooling.LinkedList.LinkedListError[source]

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

Inheritance

__init__(*args, **kwargs)

classmethod __new__(*args, **kwargs)

exception pyTooling.LinkedList.InternalError[source]

The exception is raised when the linked list’s internal state became inconsistent.

The exception message states the discovered inconsistency. Please create a bug report if this exception is raised.

Inheritance

__init__(*args, **kwargs)

classmethod __new__(*args, **kwargs)

exception pyTooling.LinkedList.NotInAListError[source]

The exception is raised when a node is not assigned to any linked list.

Inheritance

__init__(*args, **kwargs)

classmethod __new__(*args, **kwargs)

exception pyTooling.LinkedList.NotInSameListError[source]

The exception is raised when a node is assigned to a different linked list than expected.

Inheritance

__init__(*args, **kwargs)

classmethod __new__(*args, **kwargs)

exception pyTooling.LinkedList.EmptyListError[source]

The exception is raised when an operation needs at least one element, but the linked list is empty.

Inheritance

__init__(*args, **kwargs)

classmethod __new__(*args, **kwargs)

exception pyTooling.LinkedList.NodeNotFoundError[source]

The exception is raised when no node matching the search criterion was found.

Inheritance

__init__(*args, **kwargs)

classmethod __new__(*args, **kwargs)

Classes

class pyTooling.LinkedList.Node[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

__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.
ValueError – If parameter ‘value’ is None.
ValueError – If previous and next belong to different linked lists.
A node can only be inserted between two neighbours of the same linked list.

Return type:

None

_value: _NodeValue: The value of the node.

_key: Nullable[_NodeKey]: The sortable key of the node.

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

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

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

property List: Nullable[LinkedList[_NodeValue]]

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 node’s 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 node’s 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.
NotInSameListError – If parameter ‘node’ is already part of another linked list.
NotInAListError – If this node is not part of a 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.
NotInSameListError – If parameter ‘node’ is already part of another linked list.
NotInAListError – If this node is not part of a linked list.

Return type:

None

Remove()[source]

Remove this node from the linked list.

Return type:: TypeVar(_NodeValue)
Returns:: The value of the removed node.

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) – Optional, 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) – Optional, 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 a detailed string representation of this node.

Return type:: str
Returns:: The node’s value, prefixed by its kind.

classmethod GetMethodsWithAttributes(predicate: Nullable[TAttributeFilter[TAttr]] = None) → dict[Callable[..., Any], tuple[Attribute, ...]]

Return the class’ methods that carry at least one matching attribute.

Parameters:

predicate (Nullable[TAttributeFilter[TAttr]]) – Optional, an attribute class, an iterable of attribute classes, or None to accept every attribute.

Return type:

dict[Callable[…, Any], tuple[Attribute, …]]

Returns:

Dictionary of methods and the matching attributes attached to them.

Raises:

ValueError – If an element of parameter ‘predicate’ is not a sub-class of Attribute.
ValueError – If parameter ‘predicate’ is neither an attribute class nor an iterable of those.

__getstate__() → dict[str, Any]

Return the object’s state for pickling, collecting every slot of the class hierarchy.

Return type:: dict[str, Any]
Returns:: Dictionary of slot names and their values.
Raises:: ExtendedTypeError – If a slot was never assigned, so it has no value to serialize.

__setstate__(state: dict[str, Any]) → None

Restore the object’s state from unpickling, requiring exactly the slots of the class hierarchy.

Parameters:: state (dict[str, Any]) – Dictionary of slot names and their values.
Raises:: ExtendedTypeError – If the given state misses a slot or carries an unexpected one.
Return type:: None

class pyTooling.LinkedList.LinkedList[source]

An object-oriented doubly linked-list.

Inheritance

__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.
NotInSameListError – If parameter ‘nodes’ contains items which are already part of another linked list.

Return type:

None

_firstNode: Node[_NodeKey, _NodeValue] | None: Reference to the first node of the linked list.

_lastNode: Node[_NodeKey, _NodeValue] | None: Reference to the last node of the linked list.

classmethod GetMethodsWithAttributes(predicate: Nullable[TAttributeFilter[TAttr]] = None) → dict[Callable[..., Any], tuple[Attribute, ...]]

Return the class’ methods that carry at least one matching attribute.

Parameters:

predicate (Nullable[TAttributeFilter[TAttr]]) – Optional, an attribute class, an iterable of attribute classes, or None to accept every attribute.

Return type:

dict[Callable[…, Any], tuple[Attribute, …]]

Returns:

Dictionary of methods and the matching attributes attached to them.

Raises:

ValueError – If an element of parameter ‘predicate’ is not a sub-class of Attribute.
ValueError – If parameter ‘predicate’ is neither an attribute class nor an iterable of those.

__getstate__() → dict[str, Any]

Return the object’s state for pickling, collecting every slot of the class hierarchy.

Return type:: dict[str, Any]
Returns:: Dictionary of slot names and their values.
Raises:: ExtendedTypeError – If a slot was never assigned, so it has no value to serialize.

__setstate__(state: dict[str, Any]) → None

Restore the object’s state from unpickling, requiring exactly the slots of the class hierarchy.

Parameters:: state (dict[str, Any]) – Dictionary of slot names and their values.
Raises:: ExtendedTypeError – If the given state misses a slot or carries an unexpected one.
Return type:: None

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

property IsEmpty: int

Read-only property to return 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.
NotInSameListError – 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.
NotInSameListError – 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:: EmptyListError – If linked list is empty.

RemoveLast()[source]

Remove last node from linked list.

Return type:: Node[TypeVar(_NodeKey), TypeVar(_NodeValue)]
Returns:: Last node.
Raises:: EmptyListError – 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, which includes an empty list.
InternalError – If the node at that position could not be reached, so the list’s internal state is inconsistent.

Note

The algorithm starts iterating nodes from the shorter end.

Search(predicate, reverse=False)[source]

Search the list for the first node matching a predicate.

Parameters:

predicate (Callable[[Node], bool]) – Filter function accepting a node and returning a boolean.
reverse (bool) – Optional, if True, search from the last node towards the first.

Return type:

Node[TypeVar(_NodeKey), TypeVar(_NodeValue)]

Returns:

The first matching node.

Raises:

EmptyListError – If the list is empty.
NodeNotFoundError – If no node matches the predicate.

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.