Linked List ADT

LinkedList (ABC)

A linked list is a collection of nodes, with each node containing a reference to the node preceding it, or the node succeeding it, or both. Data structures that implement this abstract data type include:

1. singly linked list
2. circularly singly linked list
3. doubly linked list
4. circularly doubly linked list

For each of these data structures, the implementation details may defer between one implementation and another. One implementation may use sentinel nodes to denote the head and tail nodes, whereas another may use normal nodes with references to items within the list for the head and tail. The implementation details may also change depending on the context that these data structures will be used in, so as to best optimise them to the tasks within that specific context.

The implementation of the various linked list data structures defined within this project is meant to provide a uniform behaviour for all the data structures, such that one data structure may be replaced with another seamlessly.

__delitem__(self, idx) special

Delete item at a specific index. Time complexity: O(n).

Parameters:

Name	Type	Description	Default
idx	int	index of item to be deleted	required

Exceptions:

Type	Description
IndexError	when the index passed is out of range

Source code in linked_lists/linked_list.py

def __delitem__(self, idx: int) -> Any:
    """Delete item at a specific index. Time complexity: O(n).

    :param idx: index of item to be deleted
    :raises IndexError: when the index passed is out of range
    """
    if idx < 0 or idx >= self._length:
        raise IndexError("Index out of range")

    self._length -= 1
    previous_node = self._head
    current_node = previous_node.next_node

    for i in range(idx):
        previous_node = current_node
        current_node = current_node.next_node

    self._remove_between(previous_node, current_node.next_node)

__getitem__(self, idx) special

Get item at a specific index, or items in a slice range of the list. Time complexity: O(n).

Parameters:

Name	Type	Description	Default
idx	Union[int, slice]	index or slice range of items within the list	required

Returns:

Type	Description
Any	item at a specific index, or items in a slice range

Exceptions:

Type	Description
IndexError	when the index or slice passed is out of range
ValueError	when the step of the slice passed is less than one

Source code in linked_lists/linked_list.py

def __getitem__(self, idx: Union[int, slice]) -> Any:
    """Get item at a specific index, or items in a slice range of the list. Time complexity: O(n).

    :param idx: index or slice range of items within the list
    :return: item at a specific index, or items in a slice range
    :raises IndexError: when the index or slice passed is out of range
    :raises ValueError: when the step of the slice passed is less than one
    """
    if isinstance(idx, int):
        if idx < 0 or idx >= self._length:
            raise IndexError("Index out of range")

        current_node = self._head.next_node

        for i in range(idx):
            current_node = current_node.next_node

        return current_node.data

    elif isinstance(idx, slice):
        start = 0 if idx.start is None else idx.start
        stop = self._length if idx.stop is None else idx.stop
        step = 1 if idx.step is None else idx.step

        if step <= 0:
            raise ValueError("Step needs to be greater than zero")

        if start < 0 or start > self._length or stop < 0 or stop > self._length:
            raise IndexError("Index out of range")

        current_node = self._head.next_node
        a_list = copy.deepcopy(self)
        i = 0
        skipped = 0

        a_list.remove_all()

        while i < stop:
            if i == start or (i >= start and skipped == step):
                a_list.append(current_node.data)
                skipped = 0

            current_node = current_node.next_node
            i += 1
            skipped += 1

        return a_list

    else:
        raise TypeError

__iter__(self) special

Get a linked list iterable. Time complexity: O(1). To iterate through all the items using the returned iterable, time complexity is O(n).

Returns:

Type	Description
Iterable	linked list iterable

Source code in linked_lists/linked_list.py

def __iter__(self) -> Iterable:
    """Get a linked list iterable. Time complexity: O(1). To iterate through all the items using the returned
    iterable, time complexity is O(n).

    :return: linked list iterable
    """
    return self

__len__(self) special

Get the total number of items in list. Time complexity: O(1).

Returns:

Type	Description
int	count of items in list

Source code in linked_lists/linked_list.py

def __len__(self) -> int:
    """Get the total number of items in list. Time complexity: O(1).

    :return: count of items in list
    """
    return self._length

__next__(self) special

Get the next item of linked list iterator. Time complexity: O(1).

Returns:

Type	Description
Any	next item

Exceptions:

Type	Description
StopIteration	when the cursor denoting the current item surpasses the last item of the list

Source code in linked_lists/linked_list.py

def __next__(self) -> Any:
    """Get the next item of linked list iterator. Time complexity: O(1).

    :return: next item
    :raises StopIteration: when the cursor denoting the current item surpasses the last item of the list
    """
    self.__current_node = (
        self._head if self.__current_node is None else self.__current_node.next_node
    )
    next_node = self.__current_node.next_node

    if isinstance(next_node, LinkedList._SentinelNode):
        self.__current_node = None
        raise StopIteration

    return next_node.data

__repr__(self) special

Get a string representation of the list. Time complexity: O(n).

Returns:

Type	Description
str	string representation of the list

Source code in linked_lists/linked_list.py

def __repr__(self) -> str:
    """Get a string representation of the list. Time complexity: O(n).

    :return: string representation of the list
    """
    if self._length == 0:
        return "[]"

    current_node = self._head.next_node
    s = "["

    while not isinstance(current_node, LinkedList._SentinelNode):
        s += f"{current_node.data}, "
        current_node = current_node.next_node

    return f"{s[:-2]}]"

__setitem__(self, idx, data) special

Replace item at a specific index. Time complexity: O(n).

Parameters:

Name	Type	Description	Default
idx	int	index of item to be replaced	required
data	Any	new item to replace existing item	required

Exceptions:

Type	Description
IndexError	when the index passed is out of range

Source code in linked_lists/linked_list.py

def __setitem__(self, idx: int, data: Any) -> None:
    """Replace item at a specific index. Time complexity: O(n).

    :param idx: index of item to be replaced
    :param data: new item to replace existing item
    :raises IndexError: when the index passed is out of range
    """
    if idx < 0 or idx >= self._length:
        raise IndexError("Index out of range")

    current_node = self._head.next_node

    for i in range(idx):
        current_node = current_node.next_node

    current_node.data = data

append(self, data)

Alias of insert_last

Parameters:

Name	Type	Description	Default
data	Any	item to insert	required

Source code in linked_lists/linked_list.py

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

    :param data: item to insert
    """
    self.insert_last(data)

get_first(self)

Return item at the head of the list. Time complexity: O(1).

Returns:

Type	Description
Any	first item in list

Exceptions:

Type	Description
Empty	when the list is empty

Source code in linked_lists/linked_list.py

def get_first(self) -> Any:
    """Return item at the head of the list. Time complexity: O(1).

    :return: first item in list
    :raises Empty: when the list is empty
    """
    if self._length == 0:
        raise Empty("List is empty")

    return self._head.next_node.data

get_last(self)

Return item at the tail of the list

Returns:

Type	Description
Any	last item in list

Source code in linked_lists/linked_list.py

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

    :return: last item in list
    """
    pass

insert(self, idx, data)

Add item at a specific index of the list. Time complexity: O(n).

Parameters:

Name	Type	Description	Default
idx	int	index to insert item at	required
data	Any	item to insert	required

Exceptions:

Type	Description
IndexError	when the index passed is out of range

Source code in linked_lists/linked_list.py

def insert(self, idx: int, data: Any) -> None:
    """Add item at a specific index of the list. Time complexity: O(n).

    :param idx: index to insert item at
    :param data: item to insert
    :raises IndexError: when the index passed is out of range
    """
    if idx < 0 or idx >= self._length:
        raise IndexError("Index out of range")

    self._length += 1
    previous_node = self._head
    current_node = previous_node.next_node

    for i in range(idx):
        previous_node = current_node
        current_node = current_node.next_node

    self._insert_between(LinkedList._Node(data), previous_node, current_node)

insert_first(self, data)

Add item at the head of the list. Time complexity: O(1).

Parameters:

Name	Type	Description	Default
data	Any	item to insert	required

Source code in linked_lists/linked_list.py

def insert_first(self, data: Any) -> None:
    """Add item at the head of the list. Time complexity: O(1).

    :param data: item to insert
    """
    self._length += 1
    self._insert_between(LinkedList._Node(data), self._head, self._head.next_node)

insert_last(self, data)

Add item at the tail of the list

Parameters:

Name	Type	Description	Default
data	Any	item to insert	required

Source code in linked_lists/linked_list.py

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

    :param data: item to insert
    """
    pass

remove_all(self)

Delete all items from the list. Time complexity: O(1).

Source code in linked_lists/linked_list.py

def remove_all(self) -> None:
    """Delete all items from the list. Time complexity: O(1)."""
    self.__init__()

remove_first(self)

Delete item at the head of the list. Time complexity: O(1).

Exceptions:

Type	Description
Empty	when the list is empty

Source code in linked_lists/linked_list.py

def remove_first(self) -> None:
    """Delete item at the head of the list. Time complexity: O(1).

    :raises Empty: when the list is empty
    """
    if self._length == 0:
        raise Empty("List is empty")

    self._length -= 1
    current_node = self._head.next_node

    self._remove_between(self._head, current_node.next_node)

remove_last(self)

Delete item at the tail of the list

Source code in linked_lists/linked_list.py

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