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.

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.

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.

__post_init__()#

__post_init__() Initializes the SingleLinkedList after creation by setting attributes like cmp_function, key, first, last, and iodata.

NOTE: Special method called automatically after object creation.

Return type:

None

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

__getitem__(pos)#

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

NOTE: This method is used to access the elements of the SingleLinkedList using the square brackets notation.

Parameters:

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

Raises:
Returns:

the element at the specified position in the SingleLinkedList.

Return type:

Optional[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]

__iter__()#

__iter__() to iterate over the elements of the SingleLinkedList. This method returns an iterator object that can be used to iterate over the elements of the list.

NOTE: This is used to iterate over the nodes of the list using a for loop.

Returns:

an iterator object that can be used to iterate over the nodes of the list.

Return type:

Iterator[T]

__len__()#

__len__() to get the number of elements in the SingleLinkedList. This method returns the size of the list.

Returns:

the number of elements in the SingleLinkedList.

Return type:

int

__str__()#

__str__() to get the string representation of the SingleLinkedList. This method returns a string with the elements of the list separated by commas.

Returns:

string representation of the SingleLinkedList.

Return type:

str

__repr__()#

__repr__() get the string representation of the SingleLinkedList. This method returns a string representation,

Returns:

string representation of the SingleLinkedList.

Return type:

str