linked_list.py

from __future__ import annotations

import typing
from typing import Generic, TypeVar

T = TypeVar("T")


class LinkedListError(Exception):
    pass


class EmptyLinkedList(LinkedListError):
    pass


class LinkedListNode(Generic[T]):
    def __init__(self, data: T = None, prev_node: LinkedListNode = None, next_node: LinkedListNode = None):
        self.data = data
        self.prev = prev_node
        self.next = next_node
        if prev_node:
            prev_node.next = self
        if next_node:
            next_node.prev = self


class LinkedList(Generic[T]):
    def __init__(self):
        self.head: LinkedListNode[T] = LinkedListNode()
        self.tail: LinkedListNode[T] = LinkedListNode(None, self.head, None)
        self._size = 0

    @property
    def empty(self) -> bool:
        return self._size == 0

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

    def push_front(self, data: T) -> LinkedListNode[T]:
        node = LinkedListNode(data, self.head, self.head.next)
        self._size += 1
        return node

    def push_back(self, data: T) -> LinkedListNode[T]:
        node = LinkedListNode(data, self.tail.prev, self.tail)
        self._size += 1
        return node

    def _remove_after(self, node: LinkedListNode[T]) -> LinkedListNode[T]:
        self._size -= 1
        target = node.next
        node.next = target.next
        target.next.prev = node
        return target

    def pop_front(self) -> T:
        if self.empty:
            raise EmptyLinkedList()
        return self._remove_after(self.head).data

    def pop_back(self) -> T:
        if self.empty:
            raise EmptyLinkedList()
        return self._remove_after(self.tail.prev.prev).data

    def __iter__(self) -> T:
        current = self.head.next
        while current is not self.tail:
            yield current.data
            current = current.next

    def __str__(self) -> str:
        return "[" + ", ".join(map(str, self)) + "]"

    def __repr__(self) -> str:
        return str(self)

    def clear(self) -> None:
        self.head: LinkedListNode[T] = LinkedListNode()
        self.tail: LinkedListNode[T] = LinkedListNode(None, None, self.head)
        self._size = 0

    def remove_if(self, predicate: typing.Callable[[T], bool]) -> int:
        removed = 0
        current = self.head.next
        while current is not self.tail:
            if predicate(current.data):
                current = current.next
                self._remove_after(current.prev.prev)
                removed += 1
            else:
                current = current.next
        return removed


if __name__ == '__main__':
    data = LinkedList()
    data.push_back(10)
    data.push_back(20)
    data.push_back(30)
    print(data)
    print(data.pop_front() + 20)
    data.push_front(30)
    print(data)
    print(sorted(data))
    
    data.remove_if(lambda x: x == 30)
    print(data)