src.pydasa.structs.lists.sllt#

Module for the custom SingleLinkedList data structure in PyDASA. Essential for Dimensional Analysis and Data Science operations.

Classes:

SingleLinkedList: Implements a single linked list with methods for insertion, deletion, and traversal.

IMPORTANT: based on the implementations proposed by the following authors/books:

  1. Algorithms, 4th Edition, Robert Sedgewick and Kevin Wayne.

  2. Data Structure and Algorithms in Python, M.T. Goodrich, R. Tamassia, M.H. Goldwasser.

Classes#

SingleLinkedList

SingleLinkedList implements a single linked list data structure for PyDASA.

Module Contents#

class src.pydasa.structs.lists.sllt.SingleLinkedList#

Bases: Generic[pydasa.structs.types.generics.T]

SingleLinkedList implements a single linked list data structure for PyDASA.

Parameters:

Generic (T) – Generic type for a Python data structure.

Returns:

a generic single linked list data structure with the following attributes:

  • cmp_function: function to compare elements in the list.

  • key: key to identify the elements in the list.

  • first: reference to the first node of the list.

  • last: reference to the last node of the list.

  • _size: size of the list.

Return type:

SingleLinkedList

cmp_function: Callable[[pydasa.structs.types.generics.T, pydasa.structs.types.generics.T], int] | None = None#

Customizable comparison function for SingleLinkedList elements. Defaults to dflt_cmp_function_lt() from PyDASA, but can be overridden by the user.

_first: pydasa.structs.lists.ndlt.SLNode[pydasa.structs.types.generics.T] | None = None#

Reference to the first node of the SingleLinkedList.

_last: pydasa.structs.lists.ndlt.SLNode[pydasa.structs.types.generics.T] | None = None#

Reference to the last node of the SingleLinkedList.

key: str | None = '_idx'#

Customizable key name for identifying elements in the SingleLinkedList. Defaults to DFLT_DICT_KEY = ‘_id’ from PyDASA, but can be overridden by the user.

_size: int = 0#

Size of the SingleLinkedList, starting at 0 and updated with each modification.

iodata: List[pydasa.structs.types.generics.T] | None = None#

Optional Python list for loading external data intho the SingleLinkedList. Defaults to None but can be provided during creation.

default_compare(elm1, elm2)#
default_compare() Default comparison function for SingleLinkedList elements. Compares two elements and returns:

  • 0 if they are equal,

  • 1 if the first is greater,

  • -1 if the first is smaller.

Parameters:

  • elm1 (Any) – First element to compare.

  • elm2 (Any) – Second element to compare.

Returns:

Comparison result.

Return type:

int

property size: int#

size() Property to retrieve the number of elements in the SingleLinkedList.

Returns:

number of elements in the SingleLinkedList.

Return type:

int

property empty: bool#

empty() Property to check if the SingleLinkedList is empty.

Returns:

True if the SingleLinkedList is empty, False otherwise.

Return type:

bool

clear()#

clear() clears the SingleLinkedList by removing all elements and resetting the size to 0.

NOTE: This method is used to empty the SingleLinkedList without deleting the object itself.

Return type:

None

prepend(elm)#

prepend() adds an element to the beginning of the SingleLinkedList.

Parameters:

elm (T) – element to be added to the beginning of the structure.

Return type:

None

append(elm)#

append() adds an element to the end of the SingleLinkedList.

Parameters:

elm (T) – element to be added to the end of the structure.

Return type:

None

insert(elm, pos)#

insert() adds an element to the SingleLinkedList at a specific position.

Parameters:

  • elm (T) – element to be added to the structure.

  • pos (int) – position where the element will be added.

Raises:

  • IndexError – error if the structure is empty.

  • IndexError – error if the position is invalid.

  • TypeError – error if the element type is invalid.

Return type:

None

property first: pydasa.structs.types.generics.T#

first Property to read the first element of the SingleLinkedList.

Raises:

IndexError – error if the structure is empty.

Returns:

the first element of the SingleLinkedList.

Return type:

T

property last: pydasa.structs.types.generics.T#

last Property to read the last element of the SingleLinkedList.

Raises:

Exception – error if the structure is empty.

Returns:

the last element of the SingleLinkedList.

Return type:

T

get(pos)#

get() retrieves an element from the SingleLinkedList at a specific position.

Parameters:

pos (int) – position of the element to be retrieved.

Raises:
Returns:

the element at the specified position in the SingleLinkedList.

Return type:

T

pop_first()#

pop_first() removes the first element from the SingleLinkedList.

Raises:

IndexError – error if the structure is empty.

Returns:

the first element of the SingleLinkedList.

Return type:

T

pop_last()#

pop_last() removes the last element from the SingleLinkedList.

Raises:

IndexError – error if the structure is empty.

Returns:

the last element of the SingleLinkedList.

Return type:

T

remove(pos)#

remove() removes an element from the SingleLinkedList at a specific position.

Parameters:

pos (int) – position of the element to be removed.

Raises:
Returns:

the element removed from the SingleLinkedList.

Return type:

T

compare(elem1, elem2)#

compare() compares two elements using the comparison function defined in the SingleLinkedList.

Parameters:

  • elem1 (T) – first element to compare.

  • elem2 (T) – second element to compare.

Raises:

TypeError – error if the cmp_function is not defined.

Returns:

-1 if elem1 < elem2, 0 if elem1 == elem2, 1 if elem1 > elem2.

Return type:

int

index_of(elm)#

index_of() searches for the first occurrence of an element in the SingleLinkedList. If the element is found, it returns its index; otherwise, it returns -1.

Parameters:

elm (T) – element to search for in the SingleLinkedList.

Returns:

index of the element in the SingleLinkedList or -1 if not found.

Return type:

int

update(new_data, pos)#

update() updates an element in the SingleLinkedList at a specific position.

Parameters:

  • new_data (T) – new data to be updated in the structure.

  • pos (int) – position of the element to be updated.

Raises:
Return type:

None

swap(pos1, pos2)#

swap() swaps two elements in the SingleLinkedList at specific positions.

Parameters:

  • pos1 (int) – position of the first element to swap.

  • pos2 (int) – position of the second element to swap.

Raises:

  • IndexError – error if the structure is empty.

  • IndexError – error if the first position is invalid.

  • IndexError – error if the second position is invalid.

Return type:

None

sublist(start, end)#

sublist() creates a new SingleLinkedList containing a sublist of elements from the original SingleLinkedList. The sublist is defined by the start and end indices.

NOTE: The start index is inclusive, and the end index is inclusive.

Parameters:

  • start (int) – start index of the sublist.

  • end (int) – end index of the sublist.

Raises:

  • IndexError – error if the structure is empty.

  • IndexError – error if the start or end index are invalid.

Returns:

a new SingleLinkedList containing the sublist of elements.

Return type:

SingleLinkedList[T]

concat(other)#

concat() concatenates two SingleLinkedList objects. The elements of the second list are added to the end of the first list.

NOTE: The cmp_function and key attributes of the two lists must be the same.

Parameters:

other (SingleLinkedList[T]) – the second SingleLinkedList to be concatenated.

Raises:

  • TypeError – error if the other argument is not an SingleLinkedList.

  • TypeError – error if the key attributes are not the same.

  • TypeError – error if the cmp_function are not the same.

Returns:

the concatenated SingleLinkedList in the first list.

Return type:

SingleLinkedList[T]

clone()#

clone() creates a copy of the SingleLinkedList. The new list is independent of the original list.

NOTE: The elements of the new list are the same as the original list, but they are not references to the same objects.

Returns:

a new SingleLinkedList with the same elements as the original list.

Return type:

SingleLinkedList[T]

_error_handler(err)#

_error_handler() to process the context (package/class), function name (method), and the error (exception) that was raised to format a detailed error message and traceback.

Parameters:

err (Exception) – Python raised exception.

Return type:

None

_validate_type(elm)#

_validate_type() checks if the type of the element is valid. If the structure is empty, the type is valid. If the structure is not empty, the type must be the same as the first element in the list. This is used to check the type of the element before adding it to the list.

Parameters:

elm (T) – element to be added to the structure.

Raises:

TypeError – error if the type of the element is not valid.

Returns:

True if the type is valid, False otherwise.

Return type:

bool