Linked List¶

py_ds.datastructures.linked_lists.singly_linked.LinkedList ¶

LinkedList(items: Iterable[T] | None = None)

Bases: Generic[T]

A singly linked list supporting typical operations.

Supports append/prepend, insert at index, remove by value, iteration, and length/truthiness operations.

Initialize the list with optional items.

Parameters:

Name	Type	Description	Default
`items`	`Iterable[T] \| None`	Optional iterable of items to initialize the list with. If None, creates an empty list.	`None`

Source code in src/py_ds/datastructures/linked_lists/singly_linked.py

def __init__(self, items: Iterable[T] | None = None) -> None:
    """Initialize the list with optional items.

    Args:
        items: Optional iterable of items to initialize the list with.
            If None, creates an empty list.
    """
    self._head: _Node[T] | None = None
    self._tail: _Node[T] | None = None
    self._length: int = 0
    for item in items or []:
        self.append(item)

Functions¶

append ¶

append(value: T) -> None

Add a value to the end of the list.

Parameters:

Name	Type	Description	Default
`value`	`T`	The value to append to the list.	required

Time complexity: O(n).

Source code in src/py_ds/datastructures/linked_lists/singly_linked.py

def append(self, value: T) -> None:
    """Add a value to the end of the list.

    Args:
        value: The value to append to the list.

    Time complexity: O(n).
    """
    new_node = _Node(value=value)
    if self._head is None:
        self._head = self._tail = new_node
    else:
        self._tail.next = new_node
        self._tail = new_node
    self._length += 1

prepend ¶

prepend(value: T) -> None

Add a value to the beginning of the list.

Parameters:

Name	Type	Description	Default
`value`	`T`	The value to prepend to the list.	required

Time complexity: O(1).

Source code in src/py_ds/datastructures/linked_lists/singly_linked.py

def prepend(self, value: T) -> None:
    """Add a value to the beginning of the list.

    Args:
        value: The value to prepend to the list.

    Time complexity: O(1).
    """
    new_node = _Node(value=value)
    if self._head is None:
        self._head = self._tail = new_node
    else:
        new_node.next = self._head
        self._head = new_node
    self._length += 1

insert ¶

insert(index: int, value: T) -> None

Insert a value at a specific index.

Parameters:

Name	Type	Description	Default
`index`	`int`	0-based index, negative indexes supported (Python style).	required
`value`	`T`	The value to insert.	required

Raises:

Type	Description
`IndexError`	If index is out of bounds.

Time complexity: O(n).

Source code in src/py_ds/datastructures/linked_lists/singly_linked.py

def insert(self, index: int, value: T) -> None:
    """Insert a value at a specific index.

    Args:
        index: 0-based index, negative indexes supported (Python style).
        value: The value to insert.

    Raises:
        IndexError: If index is out of bounds.

    Time complexity: O(n).
    """
    index = self._get_positive_index(index) + int(index < 0)
    if index < 0 or index > self._length:
        raise IndexError('index out of bounds on list')
    if index == 0:
        self.prepend(value)
    elif index == self._length:
        self.append(value)
    else:
        new_node = _Node(value=value)
        prev = self._get_node_at(index - 1)
        new_node.next = prev.next
        prev.next = new_node
        self._length += 1

remove ¶

remove(value: T) -> None

Remove the first occurrence of value from the list.

Parameters:

Name	Type	Description	Default
`value`	`T`	The value to remove from the list.	required

Raises:

Type	Description
`ValueError`	If the value is not found.

Time complexity: O(n).

Source code in src/py_ds/datastructures/linked_lists/singly_linked.py

def remove(self, value: T) -> None:
    """Remove the first occurrence of `value` from the list.

    Args:
        value: The value to remove from the list.

    Raises:
        ValueError: If the value is not found.

    Time complexity: O(n).
    """
    prev, curr = None, self._head
    while curr and curr.value != value:
        prev = curr
        curr = curr.next
    if not curr or curr.value != value:
        raise ValueError('value not found')

    if prev:
        prev.next = curr.next
        if curr == self._tail:
            self._tail = prev
    else:
        self._head = self._head.next
        if self._head is None:
            self._tail = None
    self._length -= 1

pop ¶

pop(index: int = -1) -> T

Remove and return the item at the given index.

Parameters:

Name	Type	Description	Default
`index`	`int`	0-based index, negative indexes supported (Python style). Defaults to -1 (last element).	`-1`

Returns:

Type	Description
`T`	The value at the specified index.

Raises:

Type	Description
`IndexError`	If the list is empty or index is invalid.

Time complexity: O(n).

Source code in src/py_ds/datastructures/linked_lists/singly_linked.py

def pop(self, index: int = -1) -> T:
    """Remove and return the item at the given index.

    Args:
        index: 0-based index, negative indexes supported (Python style).
            Defaults to -1 (last element).

    Returns:
        The value at the specified index.

    Raises:
        IndexError: If the list is empty or index is invalid.

    Time complexity: O(n).
    """
    idx = self._get_positive_index(index)
    if idx < 0 or idx >= self._length:
        raise IndexError('invalid index')
    try:
        assert idx - 1 >= 0
        prev_node = self._get_node_at(idx - 1)
        value = prev_node.next.value
        prev_node.next = prev_node.next.next
        if prev_node.next is None:
            self._tail = prev_node
    except AssertionError:
        value = self._head.value
        self._head = self._head.next
        if self._head is None:
            self._tail = None
    self._length -= 1
    return value

clear ¶

clear() -> None

Remove all elements from the list.

Time complexity: O(1).

Source code in src/py_ds/datastructures/linked_lists/singly_linked.py

def clear(self) -> None:
    """Remove all elements from the list.

    Time complexity: O(1).
    """
    self._head = self._tail = None
    self._length = 0

head ¶

head() -> T | None

Return the first value in the list.

Returns:

Type	Description
`T \| None`	The first value in the list, or None if the list is empty.

Time complexity: O(1).

Source code in src/py_ds/datastructures/linked_lists/singly_linked.py

def head(self) -> T | None:
    """Return the first value in the list.

    Returns:
        The first value in the list, or None if the list is empty.

    Time complexity: O(1).
    """
    return self._head.value if self._head else None

tail ¶

tail() -> T | None

Return the last value in the list.

Returns:

Type	Description
`T \| None`	The last value in the list, or None if the list is empty.

Time complexity: O(n).

Source code in src/py_ds/datastructures/linked_lists/singly_linked.py

def tail(self) -> T | None:
    """Return the last value in the list.

    Returns:
        The last value in the list, or None if the list is empty.

    Time complexity: O(n).
    """
    return self._tail.value if self._tail else None

find ¶

find(value: T) -> int

Return the index of the first occurrence of a value.

Parameters:

Name	Type	Description	Default
`value`	`T`	The value to search for.	required

Returns:

Type	Description
`int`	The index of the first occurrence of the value.

Raises:

Type	Description
`ValueError`	If the value is not found in the list.

Source code in src/py_ds/datastructures/linked_lists/singly_linked.py

def find(self, value: T) -> int:
    """Return the index of the first occurrence of a value.

    Args:
        value: The value to search for.

    Returns:
        The index of the first occurrence of the value.

    Raises:
        ValueError: If the value is not found in the list.
    """
    for i, node_value in enumerate(self):
        if value == node_value:
            return i
    raise ValueError('value not found')

len ¶

__len__() -> int

Return the number of elements in the list.

Returns:

Type	Description
`int`	The number of elements in the linked list.

Source code in src/py_ds/datastructures/linked_lists/singly_linked.py

def __len__(self) -> int:
    """Return the number of elements in the list.

    Returns:
        The number of elements in the linked list.
    """
    return self._length

bool ¶

__bool__() -> bool

Return the truthiness of the list.

Returns:

Type	Description
`bool`	False if the list is empty, True otherwise.

Source code in src/py_ds/datastructures/linked_lists/singly_linked.py

def __bool__(self) -> bool:
    """Return the truthiness of the list.

    Returns:
        False if the list is empty, True otherwise.
    """
    return self._length > 0

getitem ¶

__getitem__(index: int) -> T

Get the value at the given index.

Parameters:

Name	Type	Description	Default
`index`	`int`	0-based index, negative indexes supported (Python style).	required

Returns:

Type	Description
`T`	The value at the specified index.

Raises:

Type	Description
`IndexError`	If the index is out of range.

Source code in src/py_ds/datastructures/linked_lists/singly_linked.py

def __getitem__(self, index: int) -> T:
    """Get the value at the given index.

    Args:
        index: 0-based index, negative indexes supported (Python style).

    Returns:
        The value at the specified index.

    Raises:
        IndexError: If the index is out of range.
    """
    return self._get_node_at(index).value

setitem ¶

__setitem__(index: int, value: T) -> None

Set item at the specified index.

Parameters:

Name	Type	Description	Default
`index`	`int`	The position at which to set the value. 0-based index, negative indexes supported (Python style).	required
`value`	`T`	The value to set.	required

Raises:

Type	Description
`IndexError`	If index is out of bounds.

Time complexity: O(n).

Source code in src/py_ds/datastructures/linked_lists/singly_linked.py

def __setitem__(self, index: int, value: T) -> None:
    """Set item at the specified index.

    Args:
        index: The position at which to set the value.
            0-based index, negative indexes supported (Python style).
        value: The value to set.

    Raises:
        IndexError: If index is out of bounds.

    Time complexity: O(n).
    """
    self._get_node_at(index).value = value

iter ¶

__iter__() -> Iterator[T]

Iterate through values in the list.

Yields:

Type	Description
`T`	The values in the list from head to tail.

Source code in src/py_ds/datastructures/linked_lists/singly_linked.py

def __iter__(self) -> Iterator[T]:
    """Iterate through values in the list.

    Yields:
        The values in the list from head to tail.
    """
    curr = self._head
    while curr:
        yield curr.value
        curr = curr.next

repr ¶

__repr__() -> str

Return a string representation of the linked list.

Returns:

Type	Description
`str`	A string representation showing the class name and list contents.

Source code in src/py_ds/datastructures/linked_lists/singly_linked.py

def __repr__(self) -> str:
    """Return a string representation of the linked list.

    Returns:
        A string representation showing the class name and list contents.
    """
    return f'{self.__class__.__name__}({list(self)})'

str ¶

__str__() -> str

Return a string representation of the linked list.

Returns:

Type	Description
`str`	A visual representation of the linked list.

Time complexity: O(n).

Source code in src/py_ds/datastructures/linked_lists/singly_linked.py

def __str__(self) -> str:
    """Return a string representation of the linked list.

    Returns:
        A visual representation of the linked list.

    Time complexity: O(n).
    """
    if not self:
        return 'HEAD → TAIL'
    return 'HEAD → ' + ' → '.join(str(item) for item in self) + ' → TAIL'

Linked List¶

py_ds.datastructures.linked_lists.singly_linked.LinkedList ¶

Functions¶

append ¶

prepend ¶

insert ¶

remove ¶

pop ¶

clear ¶

head ¶

tail ¶

find ¶

__len__ ¶

__bool__ ¶

__getitem__ ¶

__setitem__ ¶

__iter__ ¶

__repr__ ¶

__str__ ¶

len ¶

bool ¶

getitem ¶

setitem ¶

iter ¶

repr ¶

str ¶