linked_list.py

from typing import Any
from icecream import ic  # type: ignore # pip install icecream


class Node:
    def __init__(self, data: Any):
        self.data: Any = data
        self.prev: Node
        self.next: Node


class List:
    def __init__(self, items=None):
        if items == None:
            items = []
        self.head: Node = Node(None)
        self.tail: Node = Node(None)
        self.head.next = self.tail
        self.tail.prev = self.head
        for item in items:
            self.push_back(item)

    def push_front(self, data: Any) -> None:
        node = Node(data)
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def push_back(self, data: Any) -> None:
        node = Node(data)
        node.prev = self.tail.prev
        node.next = self.tail
        self.tail.prev.next = node
        self.tail.prev = node

    def remove(self, node: Node | None) -> None:
        if not node: return
        node.prev.next = node.next
        node.next.prev = node.prev
        del node

    def move_front(self, node: Node | None) -> None:
        if not node: return
        self.remove(node)
        self.push_front(node.data)

    def move_back(self, node: Node | None) -> None:
        if not node: return
        self.remove(node)
        self.push_back(node.data)

    def back(self) -> Node | None:
        if self.tail.prev == self.head: return None
        return self.tail.prev

    def front(self) -> Node | None:
        if self.tail.prev == self.head: return None
        return self.head.next

    def search(self, target: Any) -> Node | None:
        current = self.head.next
        while current != self.tail:
            if current.data == target:
                return current
            current = current.next
        return None

    def reverse(self):
        i = self.head.next
        j = self.tail.prev
        while i != self.tail and j != self.head and i != j and i.prev != j:
            i.data, j.data = j.data, i.data
            i = i.next
            j = j.prev

    def __repr__(self):
        ans = ""
        current = self.head.next
        while current != self.tail:
            if len(ans) != 0:
                ans += " "
            ans += str(current.data)
            current = current.next
        return f"List({ans})"

    def __bool__(self) -> bool:
        return self.head.next != self.tail


if __name__ == '__main__':
    list = List([1, 2, 3])
    ic(list)

    list.push_back(4)
    ic(list)

    list.push_front(0)
    ic(list)

    list.move_back(list.front())
    ic(list)

    list.move_front(list.back())
    ic(list)

    node = list.search(2)
    if node:
        ic(node.data)
        list.remove(node)
        ic(list)

    list.reverse()
    ic(list)

    while list:
        list.remove(list.front())
    ic(list)

    list.push_front(0)
    ic(list)

    ic("OK")