Examples of three types of linked lists

linked_lists.py

"""
These are classes I coded up to understand how different linked lists worked.
They all accept and return the items held, not node instances.
"""
from abc import ABC, abstractmethod
from collections.abc import Iterable, Reversible
from typing import Optional


class AbstractLinkedNode(ABC):
    def __init__(self, value, next_node: Optional['AbstractLinkedNode'] = None):
        self.value = value
        self.next_node = next_node

    def __str__(self):
        return str(self.value)


class AbstractLinkedList(ABC, Iterable):
    head: AbstractLinkedNode

    def __iter__(self):
        current = self.head
        while current is not None:
            yield current.value
            current = current.next_node

    def __bool__(self):
        return self.head is not None

    def __repr__(self):
        return f'{self.__class__.__name__}({repr(list(self))})'

    @abstractmethod
    def add(self, item) -> None:
        pass

    @abstractmethod
    def insert(self, index: int, item) -> None:
        pass

    @abstractmethod
    def __delitem__(self, key: int) -> None:
        pass

    @abstractmethod
    def reverse(self) -> None:
        pass


class LinkedNode(AbstractLinkedNode):
    pass


class LinkedList(AbstractLinkedList):
    def __init__(self, items: Iterable = ()):
        last_node = None
        self.head: Optional[LinkedNode] = None
        for item in items:
            node = LinkedNode(item)
            if last_node is not None:
                last_node.next_node = node
            else:
                self.head = node
            last_node = node

    def add(self, item):
        self.head = LinkedNode(item, self.head)

    def insert(self, index: int, item):
        if not index or not self:
            self.add(item)
            return
        current = self.head
        for _ in range(index-1):
            if current.next_node is None:
                break
            current = current.next_node
        current.next_node = LinkedNode(item, current.next_node)

    def __delitem__(self, key: int):
        if key == 0:
            if self.head is None:
                raise IndexError
            else:
                self.head = self.head.next_node
                return
        last_node = None
        current_node = self.head
        for _ in range(key):
            if current_node is None:
                raise IndexError
            last_node = current_node
            current_node = current_node.next_node
        last_node.next_node = current_node.next_node

    def reverse(self):
        last_node = None
        current = self.head
        while current is not None:
            current.next_node, current, last_node = last_node, current.next_node, current
        self.head = last_node


class CircleLinkedList(AbstractLinkedList):
    def __init__(self, items: Iterable = ()):
        self.head: Optional[LinkedNode] = None
        self.tail: Optional[LinkedNode] = None
        last_node = None
        for item in items:
            node = LinkedNode(item)
            if last_node is not None:
                last_node.next_node = node
            else:
                self.head = node
            last_node = node
        if last_node is not None:
            last_node.next_node = self.head
            self.tail = last_node

    def __iter__(self):
        current = self.head
        while current is not None:
            yield current.value
            current = current.next_node if current is not self.tail else None

    def add(self, item):
        self.head = LinkedNode(item, self.head)
        if self.tail is not None:
            self.tail.next_node = self.head
        else:
            self.tail = self.head
            self.head.next_node = self.head

    def append(self, item):
        if not self:
            self.add(item)
            return
        self.tail.next_node = self.tail = LinkedNode(item, self.head)

    def insert(self, index: int, item):
        if not index or not self:
            self.add(item)
            return
        current = self.head
        for _ in range(index-1):
            if current.next_node is None:
                break
            current = current.next_node
        next_node = current.next_node
        current.next_node = LinkedNode(item, next_node)
        if current is self.tail:
            self.tail = current.next_node

    def __delitem__(self, key: int):
        last_node = None
        current_node = self.head
        for _ in range(key):
            if current_node is None:
                raise IndexError
            last_node = current_node
            current_node = current_node.next_node
        last_node.next_node = current_node.next_node
        if current_node is self.tail:
            self.tail = last_node

    def reverse(self):
        if not self:
            return
        last_node = self.tail
        current = self.head
        while current is not self.tail:
            current.next_node, current, last_node = last_node, current.next_node, current
        current.next_node, current, last_node = last_node, current.next_node, current
        self.tail, self.head = self.head, self.tail


class DoubleLinkedNode(AbstractLinkedNode):
    def __init__(self,
                 value,
                 next_node: Optional['DoubleLinkedNode'] = None,
                 last_node: Optional['DoubleLinkedNode'] = None
                 ):
        self.last_node = last_node
        super().__init__(value, next_node)


class DoubleLinkedList(AbstractLinkedList, Reversible):
    def __init__(self, items: Iterable =()):
        self.head: Optional[DoubleLinkedNode] = None
        last_node = None
        for item in items:
            node = DoubleLinkedNode(item, last_node=last_node)
            if last_node is not None:
                last_node.next_node = node
            else:
                self.head = node
            last_node = node
        self.tail = last_node

    def __reversed__(self):
        current = self.tail
        while current is not None:
            yield current.value
            current = current.last_node

    def add(self, item):
        self.head = DoubleLinkedNode(item, self.head)
        if self.tail is None:
            self.tail = self.head
        elif self.head.next_node is not None:
            self.head.next_node.last_node = self.head

    def append(self, item):
        if not self:
            self.add(item)
        self.tail = DoubleLinkedNode(item, None, self.tail)
        self.tail.last_node.next_node = self.tail

    def insert(self, index: int, item):
        if not index or not self:
            self.add(item)
            return
        current = self.head
        for _ in range(index-1):
            if current.next_node is None:
                break
            current = current.next_node
        next_node = current.next_node
        new_node = DoubleLinkedNode(item, next_node, current)
        current.next_node = new_node
        if next_node is None:
            self.tail = new_node
        else:
            next_node.last_node = new_node

    def __delitem__(self, key: int):
        last_node = None
        current_node = self.head
        for _ in range(key):
            if current_node is None:
                raise IndexError
            last_node = current_node
            current_node = current_node.next_node
        next_node = current_node.next_node
        last_node.next_node = next_node
        if next_node is not None:
            next_node.last_node = last_node

    def reverse(self):
        current = self.head
        while current is not None:
            current.next_node, current.last_node, current = current.last_node, current.next_node, current.next_node
        self.head, self.tail = self.tail, self.head


if __name__ == '__main__':
    s = 'ABCDEFGH'
    single = LinkedList(s)
    circle = LinkedList(s)
    double = DoubleLinkedList(s)