Positional Linked List ADT

PositionalLinkedList (ABC)

A positional linked list is a linked list whose nodes are identifiable by their position within the list. Using the position of a node, operations such as insertion, retrieval, and deletion of elements can be performed on neighbouring nodes without the need to traverse the list from its head or tail to that specific position.

A positional linked list can be implemented based on any linked list data structure, such as singly linked list, doubly linked list, etc. The operations that can be performed on the neighbouring nodes of a certain position, for a running time of O(1), are limited to the directions of traversal offered by the data structure used to implement the positional linked list. When using a linked list data structure where each node has a reference to the node succeeding it but not the one preceding it, only operations referencing the next neighbours of a specific position are achievable at constant running time. If the linked data structure contains nodes where each node contains references to both its previous and next nodes, operations referencing both the previous and next neighbours of a specific position are achievable at constant running time.

append(self, data)

Alias of insert_last

Parameters:

Name	Type	Description	Default
data	Any	item to insert	required

Returns:

Type	Description
_Position	the position of the added item

Source code in positional_linked_lists/positional_linked_list.py

def append(self, data: Any) -> _Position:
    """Alias of insert_last

    :param data: item to insert
    :returns: the position of the added item
    """
    return self.insert_last(data)

get_after(self, position)

Return the position just after the passed position, None if the referenced after position doesn't exist

Parameters:

Name	Type	Description	Default
position	_Position	reference position	required

Returns:

Type	Description
Optional[data_structures.positional_linked_lists.positional_linked_list.PositionalLinkedList._Position]	the position just after the passed position

Source code in positional_linked_lists/positional_linked_list.py

@abstractmethod
def get_after(self, position: _Position) -> Union[_Position, None]:
    """Return the position just after the passed position, None if the referenced after position doesn't exist

    :param position: reference position
    :returns: the position just after the passed position
    """
    if not position.is_owned_by(self):
        raise ValueError("Position doesn't belong to this list")

get_before(self, position)

Return the position just before the passed position, None if the referenced before position doesn't exist

Parameters:

Name	Type	Description	Default
position	_Position	reference position	required

Returns:

Type	Description
Optional[data_structures.positional_linked_lists.positional_linked_list.PositionalLinkedList._Position]	the position just before the passed position

Source code in positional_linked_lists/positional_linked_list.py

@abstractmethod
def get_before(self, position: _Position) -> Union[_Position, None]:
    """Return the position just before the passed position, None if the referenced before position doesn't exist

    :param position: reference position
    :returns: the position just before the passed position
    """
    if not position.is_owned_by(self):
        raise ValueError("Position doesn't belong to this list")

get_first(self)

Return the position of the item at the head of the list, None if the list is empty

Returns:

Type	Description
Optional[data_structures.positional_linked_lists.positional_linked_list.PositionalLinkedList._Position]	the position of the item at the head of the list

Source code in positional_linked_lists/positional_linked_list.py

@abstractmethod
def get_first(self) -> Union[_Position, None]:
    """Return the position of the item at the head of the list, None if the list is empty

    :returns: the position of the item at the head of the list
    """
    pass

get_last(self)

Return the position of the item at the tail of the list, None if the list is empty

Returns:

Type	Description
Optional[data_structures.positional_linked_lists.positional_linked_list.PositionalLinkedList._Position]	the position of the item at the tail of the list

Source code in positional_linked_lists/positional_linked_list.py

@abstractmethod
def get_last(self) -> Union[_Position, None]:
    """Return the position of the item at the tail of the list, None if the list is empty

    :returns: the position of the item at the tail of the list
    """
    pass

insert_after(self, position, data)

Add item after the defined position within the list

Parameters:

Name	Type	Description	Default
position	_Position	reference position	required
data	Any	item to insert	required

Returns:

Type	Description
_Position	the position of the added item

Source code in positional_linked_lists/positional_linked_list.py

@abstractmethod
def insert_after(self, position: _Position, data: Any) -> _Position:
    """Add item after the defined position within the list

    :param position: reference position
    :param data: item to insert
    :returns: the position of the added item
    """
    if not position.is_owned_by(self):
        raise ValueError("Position doesn't belong to this list")

insert_before(self, position, data)

Add item before the defined position within the list

Parameters:

Name	Type	Description	Default
position	_Position	reference position	required
data	Any	item to insert	required

Returns:

Type	Description
_Position	the position of the added item

Source code in positional_linked_lists/positional_linked_list.py

@abstractmethod
def insert_before(self, position: _Position, data: Any) -> _Position:
    """Add item before the defined position within the list

    :param position: reference position
    :param data: item to insert
    :returns: the position of the added item
    """
    if not position.is_owned_by(self):
        raise ValueError("Position doesn't belong to this list")

insert_first(self, data)

Add item at the head of the list

Parameters:

Name	Type	Description	Default
data	Any	item to insert	required

Returns:

Type	Description
_Position	the position of the added item

Source code in positional_linked_lists/positional_linked_list.py

@abstractmethod
def insert_first(self, data: Any) -> _Position:
    """Add item at the head of the list

    :param data: item to insert
    :returns: the position of the added item
    """
    pass

insert_last(self, data)

Add item at the tail of the list

Parameters:

Name	Type	Description	Default
data	Any	item to insert	required

Returns:

Type	Description
_Position	the position of the added item

Source code in positional_linked_lists/positional_linked_list.py

@abstractmethod
def insert_last(self, data: Any) -> _Position:
    """Add item at the tail of the list

    :param data: item to insert
    :returns: the position of the added item
    """
    pass

is_empty(self)

Return True if list is empty, else False

Returns:

Type	Description
bool	True if list is empty, else False

Source code in positional_linked_lists/positional_linked_list.py

@abstractmethod
def is_empty(self) -> bool:
    """Return True if list is empty, else False

    :return: True if list is empty, else False
    """
    pass

remove(self, position)

Delete item at a specific position

Parameters:

Name	Type	Description	Default
position	_Position	position containing item to be deleted	required

Returns:

Type	Description
Any	the deleted item

Source code in positional_linked_lists/positional_linked_list.py

@abstractmethod
def remove(self, position: _Position) -> Any:
    """Delete item at a specific position

    :param position: position containing item to be deleted
    :returns: the deleted item
    """
    if not position.is_owned_by(self):
        raise ValueError("Position doesn't belong to this list")

remove_after(self, position)

Delete item just after the passed position

Parameters:

Name	Type	Description	Default
position	_Position	reference position	required

Returns:

Type	Description
Any	the deleted item

Source code in positional_linked_lists/positional_linked_list.py

@abstractmethod
def remove_after(self, position: _Position) -> Any:
    """Delete item just after the passed position

    :param position: reference position
    :returns: the deleted item
    """
    if not position.is_owned_by(self):
        raise ValueError("Position doesn't belong to this list")

remove_before(self, position)

Delete item just before the passed position

Parameters:

Name	Type	Description	Default
position	_Position	reference position	required

Returns:

Type	Description
Any	the deleted item

Source code in positional_linked_lists/positional_linked_list.py

@abstractmethod
def remove_before(self, position: _Position) -> Any:
    """Delete item just before the passed position

    :param position: reference position
    :returns: the deleted item
    """
    if not position.is_owned_by(self):
        raise ValueError("Position doesn't belong to this list")

remove_first(self)

Delete item at the head of the list

Returns:

Type	Description
Any	the deleted item

Source code in positional_linked_lists/positional_linked_list.py

def remove_first(self) -> Any:
    """Delete item at the head of the list

    :returns: the deleted item
    """
    pass

remove_last(self)

Delete item at the tail of the list

Returns:

Type	Description
Any	the deleted item

Source code in positional_linked_lists/positional_linked_list.py

@abstractmethod
def remove_last(self) -> Any:
    """Delete item at the tail of the list

    :returns: the deleted item
    """
    pass

replace(self, position, data)

Replace item at a specific position. Time complexity: O(1).

Parameters:

Name	Type	Description	Default
position	_Position	reference position	required
data	Any	item to replace the existing item at the reference position	required

Returns:

Type	Description
Any	the item replaced from the reference position

Source code in positional_linked_lists/positional_linked_list.py

def replace(self, position: _Position, data: Any) -> Any:
    """Replace item at a specific position. Time complexity: O(1).

    :param position: reference position
    :param data: item to replace the existing item at the reference position
    :returns: the item replaced from the reference position
    """
    if not position.is_owned_by(self):
        raise ValueError("Position doesn't belong to this list")

    node = position.manipulate_node(self, "_validate_node", *[])
    current_data = node.data
    node.data = data

    return current_data