[Python] Linked List

linked_list.py

from __future__ import annotations

from collections.abc import Callable
from typing import Any


class Node:
    def __init__(self, value: object):
        self.value = value
        self.next_node: Node | None = None

    def __repr__(self) -> str:
        return f"{self.__class__.__name__}({self.value = })"


class LinkedList:
    def __init__(self, head: Node | None = None):
        self.head = head
        self.tail = head
        self.length = 0
        if head is not None:
            current_head = head
            while current_head.next_node is not None:
                self.length += 1
                current_head = current_head.next_node
            self.tail = current_head

    def __bool__(self) -> bool:
        return len(self) != 0
    
    def __iter__(self):
        return LinkedListIterator(self)

    def __len__(self) -> int:
        return self.length
    
    def __str__(self) -> str:
        values = ', '.join(map(lambda n: str(n.value), self))
        return f"{self.__class__.__name__}([{values}])"

    def append(self, value: Node | object) -> None:
        if not isinstance(value, Node):
            value = Node(value)

        if self.tail is not None:
            self.tail.next_node = value
            self.tail = self.tail.next_node
        else:
            self.head = value
            self.tail = self.head

        self.length += 1

    def clear(self) -> None:
        if not self:
            return
        
        list_iter = iter(self)
        current_node = next(list_iter)

        for next_node in list_iter:
            del current_node
            current_node = next_node
        
        del current_node

        self.head = None
        self.tail = None
        self.length = 0

    def copy(self) -> LinkedList:
        new_list = LinkedList()
        for node in self:
            new_list.append(node)

        return new_list

    def count(self, value: object) -> int:
        return sum(
            node.value == value
            for node in self
        )

    def extend(self, other: LinkedList) -> None:
        for node in other:
            self.append(node)

    def index(self, value: object) -> int:
        for idx, node in enumerate(self):
            if node.value == value:
                return idx

        raise ValueError("Value not found")

    def insert(self, index: int, value: object) -> None:
        if index > len(self):
            raise IndexError("Index not in list")

        if index == 0:
            next_node = self.head
            self.head = Node(value)
            self.head.next_node = next_node

        else:
            for idx, node in enumerate(self):
                if idx == index-1:
                    next_node = node.next_node
                    node.next_node = Node(value)
                    node.next_node.next_node = next_node

        self.length += 1

    def pop(self, index: int | None = None):
        if index is None:
            self.tail = None
            index = len(self)-1

        for idx, node in enumerate(self):
            if idx == index-1:
                temp = node.next_node
                node.next_node = None
                self.length -= 1
                return temp

    def remove(self, value: object) -> None:
        if not self:
            raise ValueError("Value not found")

        list_iter = iter(self)
        current_node = next(list_iter)

        for next_node in list_iter:
            if next_node.value == value:
                current_node.next_node = next_node.next_node
            current_node = next_node

        self.length -= 1

    def reverse(self) -> None:
        nodes = [node for node in self]
        self.clear()
        print(nodes)
        while nodes:
            self.append(nodes.pop().value)

    def sort(self, key: Callable[[Node], Any] | None = None) -> None:
        nodes = [node for node in self]
        nodes.sort(key)
        self.clear()
        for node in nodes:
            self.append(node)


class LinkedListIterator:
    def __init__(self, linked_list: LinkedList):
        self.node = linked_list.head
    
    def __iter__(self):
        return self
    
    def __next__(self):
        if self.node is None:
            raise StopIteration
        
        node = self.node
        self.node = self.node.next_node
        
        return node


if __name__ == '__main__':
    nums = LinkedList()
    for num in range(10):
        nums.append(num)

    print(nums)  # LinkedList([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
    print(len(nums))  # 10

    nums.pop()

    print(nums)  # LinkedList([0, 1, 2, 3, 4, 5, 6, 7, 8])
    print(len(nums))  # 9

    nums.pop()

    print(nums)  # LinkedList([0, 1, 2, 3, 4, 5, 6, 7])
    print(len(nums))  # 8

    nums.clear()

    print(nums)  # LinkedList([])
    print(len(nums))  # 0

    for num in range(1000, 1010):
        nums.append(num)

    print(nums)  # LinkedList([1000, 1001, 1002, 1003, 1004, 1005, 1006, 1007, 1008, 1009])
    print(len(nums))  # 10

    nums.remove(1004)

    print(nums)  # LinkedList([1000, 1001, 1002, 1003, 1005, 1006, 1007, 1008, 1009])
    print(len(nums))  # 9

    nums.insert(4, 1004)

    print(nums)  # LinkedList([1000, 1001, 1002, 1003, 1004, 1005, 1006, 1007, 1008, 1009])
    print(len(nums))  # 10

    print(nums.count(1008))  # 1
    print(nums.count(25565))  # 0

    copied = nums.copy()

    nums.reverse()

    print(nums)  # LinkedList([1009, 1008, 1007, 1006, 1005, 1004, 1003, 1002, 1001, 1000])
    print(len(nums))  # 10

    print(copied)  # LinkedList([1000, 1001, 1002, 1003, 1004, 1005, 1006, 1007, 1008, 1009])
    print(len(copied))  # 10