A Python Linked List implementation modeled after the built-in List object

linked_list.py

"""Example Linked List Implementation"""

from __future__ import annotations
from dataclasses import dataclass
from typing import Any, Iterable, Optional, Type, TypeVar, Generic, cast

import math

T = TypeVar("T")


@dataclass
class _Node(Generic[T]):
    item: T
    next: Optional[_Node] = None


class LLItemIterator(Generic[T]):
    _current_node: Optional[_Node[T]]

    def __init__(self, current_node: Optional[_Node[T]]) -> None:
        self._current_node = current_node
    
    def __iter__(self) -> LLItemIterator[T]:
        return self

    def __next__(self) -> T:
        if self._current_node is None:
            raise StopIteration
        item = self._current_node.item
        self._current_node = self._current_node.next
        return item


class LLNodeIterator(Generic[T]):
    _current_node: Optional[_Node[T]]

    def __init__(self, current_node: Optional[_Node[T]]) -> None:
        self._current_node = current_node

    def __iter__(self) -> LLNodeIterator[T]:
        return self

    def __next__(self) -> _Node[T]:
        if self._current_node is None:
            raise StopIteration
        node = self._current_node
        self._current_node = self._current_node.next
        return node


class LinkedList(Generic[T]):
    _first: Optional[_Node[T]]
    _length: int

    def __init__(self, from_iterable: Iterable[T] = None) -> None:
        """Initialize an empty linked list.
        """
        self._first = None
        self._length = 0

        if from_iterable is not None:
            for n in from_iterable:
                self.append(n)

    def __iter__(self) -> LLItemIterator[T]:
        return LLItemIterator(self._first)

    def _node_iter(self) -> LLNodeIterator[T]:
        return LLNodeIterator(self._first)

    def __contains__(self, query: T) -> bool:
        for item in self:
            if item == query:
                return True

        return False

    def __getitem__(self, index: int) -> T:
        i = 0

        for item in self:
            if i == index:
                return item
            i += 1

        raise IndexError(
            "Index {} out of range {}".format(index, self._length)
        )

    def __setitem__(self, index: int, to: T) -> None:
        i = 0

        for node in self._node_iter():
            if i == index:
                node.item = to
                return
            i += 1

        raise IndexError(
            "Index {} out of range {}".format(index, self._length))

    def insert(self, index: int, item: T) -> None:
        i = 0
        self._length+=1
        for node in self._node_iter():
            if i == index - 1:
                next_node = node.next
                inserted_node = _Node(item)
                node.next = inserted_node
                inserted_node.next = next_node
                return

    def __len__(self) -> int:
        return self._length

    def _get_last_node(self) -> Optional[_Node[T]]:
        curr_node: Optional[_Node[T]] = None

        for node in self._node_iter():
            curr_node = node

        return curr_node

    def append(self, item: T) -> None:
        new_node = _Node(item)

        if self._first is None:
            self._first = new_node
        else:
            cast(_Node, self._get_last_node()).next = new_node

        self._length += 1

    def pop(self, idx: int = -1) -> T:
        i = 0

        if idx == 0:
            if self._first is None:
                raise IndexError("pop from empty list")
            popped = self._first.item
            self._first = self._first.next
            self._length-=1
            return popped

        for node in self._node_iter():
            if (idx < 0 and i == len(self) - 1 + idx) or (idx >= 0 and i == idx - 1):
                popped = cast(_Node[T], node.next)
                after = popped.next
                node.next = after
                self._length-=1
                return popped.item
            i += 1

        raise ValueError("Index out of range")

    def reverse(self) -> None:
        if self._first is None:
            return

        previous_node = self._first

        iterator = self._node_iter()
        next(iterator)
        nodes = list(iterator)
        self._first.next = None

        for node in nodes:
            node.next = previous_node
            previous_node = node

        self._first = previous_node

    def __repr__(self) -> str:
        return "LinkedList[{}]".format(
            ", ".join(repr(item) for item in self)
        )
    
    def extend(self, other: Iterable[T]) -> None:
        for item in other:
            self.append(item)
    
    def count(self, query: T) -> int:
        count = 0

        for item in self:
            if item == query:
                count += 1
        
        return count
    
    def index(self, query: T) -> int:
        i = 0

        for item in self:
            if item == query:
                return i
            i+=1
        
        raise ValueError("{} is not in list".format(repr(query)))

    def remove(self, query: T) -> None:
        index_of = self.index(query)

        self.pop(index_of)
    
    def copy(self) -> LinkedList[T]:
        new: LinkedList[T] = LinkedList()
        
        for item in self:
            new.append(item)
        
        return new
    
    def clear(self) -> None:
        self._first = None
        self._length = 0
    
    def __add__(self, other: Iterable[T]) -> LinkedList[T]:
        copy = self.copy()
        copy.extend(other)
        return copy

if __name__ == "__main__":
    my_list: LinkedList[int] = LinkedList()
    my_list.append(1)
    my_list.append(2)
    my_list.append(3)
    print(my_list)
    print("length", len(my_list))

    for n in my_list:
        print(n)

    print("popped", my_list.pop(2))
    print(my_list)
    my_list.extend([3, 4])
    print(my_list)
    my_list.reverse()

    print(my_list + [0, -1, -2])
    print(4 in my_list)