deque 이중연결리스트

# deque with doubly linked list
class Node:
    def __init__(self, datum, pre=None, _next=None):
        self.datum = datum
        self.pre = pre
        self.next = _next


def insert_behind(front: Node, to_insert: Node):
    to_insert.next = front.next
    if front.next:
        front.next.pre = to_insert

    front.next = to_insert
    to_insert.pre = front


def remove_node(to_remove: Node):
    if to_remove.pre:
        to_remove.pre.next = to_remove.next
    if to_remove.next:
        to_remove.next.pre = to_remove.pre

    to_remove.next, to_remove.pre = None, Node


class DoublyLList:
    def __init__(self):
        self.head = Node(None)
        self.tail = Node(None)
        insert_behind(self.head, self.tail)
        self.len = 0

    def add_front(self, datum):
        insert_behind(self.head, Node(datum))
        self.len += 1

    def remove_front(self):
        if self.len != 0:
            remove_node(self.head.next)

        self.len -= 1

    def add_last(self, datum):
        insert_behind(self.tail.pre, Node(datum))
        self.len += 1

    def remove_last(self):
        if self.len != 0:
            remove_node(self.tail.pre)

        self.len -= 1


class Deq(DoublyLList):

    def append(self, datum):
        self.add_last(datum)

    def pop(self):
        popped = self.tail.pre.datum
        self.remove_last()
        return popped

    def append_left(self, datum):
        self.add_front(datum)

    def pop_left(self):
        popped = self.head.next.datum
        self.remove_front()
        return popped