Circular linked list python implementation.

circular_list.py

"""Circular linked list python implementation."""

from typing import Generator, Generic, Iterable, Protocol, Sized, TypeVar


class EqProtocol(Protocol):
    """Protocol with eq method."""

    def __eq__(self, __value: object) -> bool: ... # noqa


T = TypeVar('T', bound=EqProtocol)


class Node(Generic[T]):
    """Element of SLL."""

    data: T
    _next: 'Node'

    __slots__ = ['data', '_next']

    def __init__(self, data: T) -> None:
        """Create node with element."""
        self.data = data


class CircularLinkedList(Iterable[T], Sized):
    """Circular Linked List."""

    _head: Node[T] | None = None
    _tail: Node[T] | None = None
    _count: int = 0

    def add(self, data: T):
        """Add data to list.

        :param T data: generic data
        """
        node = Node(data)
        if self._head is None:
            self._head = node
            self._tail = node
            self._tail._next = node
        else:
            node._next = self._head
            self._tail._next = node
            self._tail = node

        self._count += 1

    @property
    def is_empty(self) -> bool:
        """Retrun status of list emptyness."""
        return self._count == 0

    def clear(self):
        """Clear list."""
        del self._head
        del self._tail

    def __delitem__(self, data):
        """Delete item with remove."""
        self.remove(data)

    def remove(self, data: T) -> None:
        """Remove `data` from list, raises KeyError if not found."""
        if self.is_empty:
            raise KeyError(data)

        current: Node[T] = self._head
        previous: Node[T] | None = None

        while True:
            if current.data == data:
                if previous is not None:
                    previous._next = current._next
                    if current is self._tail:
                        self._tail = previous

                else:

                    if self._count == 1:
                        del self._tail
                        del self._head
                    else:
                        self._head = current._next
                        self._tail._next = current._next

                self._count -= 1
                return

            previous = current
            current = current._next

            if current == self._head:
                break

        raise KeyError(data)

    def __contains__(self, value: T) -> bool:
        """Check if contains in list."""
        current: Node[T] = self._head

        if current is None:
            return False

        while True:
            if (current.data == value):
                return True
            current = current._next

            if current is self._head:
                return False

    def __len__(self) -> int:
        """Get self size.

        :return int: size
        """
        return self._count

    def __iter__(self) -> 'CircularLinkedList[T]':
        """Iterate over list."""
        return self._iter()

    def _iter(self) -> Generator[T, None, None]:
        current = self._head
        while True:
            if current is not None:
                yield current.data
                current = current._next

            if current is self._head:
                return

    def round_iter(self) -> Generator[T, None, None]:
        """Round generator for list."""
        current = self._head
        while True:
            if current is not None:
                yield current.data
                current = current._next
            else:
                return

    @classmethod
    def from_iterable(cls, iterable: Iterable[T]) -> 'CircularLinkedList[T]':
        """Get CLL from iterable.

        :param Iterable iterable: any iterable
        :return CircularLinkedList[T]: _description_
        """
        container = cls()
        for i in iterable:
            container.add(i)

        return container


def main():  # noqa
    cll = CircularLinkedList.from_iterable(list(range(10)))

    assert list(cll) == list(range(10))
    assert 5 in cll
    assert 11 not in cll

    del cll[9]
    del cll[8]
    del cll[3]

    assert list(cll) == [0, 1, 2, 4, 5, 6, 7]

    cll.add(12)
    assert list(cll) == [0, 1, 2, 4, 5, 6, 7, 12]

    try:
        del CircularLinkedList()[0]
    except KeyError:
        pass
    else:
        raise AssertionError

    assert 0 not in CircularLinkedList()

    print('Successfully ran tests.')


if __name__ == '__main__':
    main()