implementing deque using doublylinkedlist operations 1 insertion in the front o1 2 insertion in the end o1 3 remove from the front o1 4 remove from the end o1 a private class to be inherited class node slots prev data next def initself linkp element linkn self prev linkp self data element self next linkn def hasnextandprevself return f prev self prev is not none next self next is not none def initself self header self nodenone none none self trailer self nodenone none none self header next self trailer self trailer prev self header self size 0 def lenself return self size def isemptyself return self len 0 def insertself predecessor e successor create newnode by setting it s prev link header setting it s next link trailer newnode self nodepredecessor e successor predecessor next newnode successor prev newnode self size 1 return self def deleteself node predecessor node prev successor node next predecessor next successor successor prev predecessor self size 1 temp node data node prev node next node data none del node return temp class linkeddequedoublylinkedbase def firstself if self isempty raise exceptionlist is empty return self header next data def lastself if self isempty raise exceptionlist is empty return self trailer prev data deque insert operations at the front at the end def addfirstself element return self insertself header element self header next def addlastself element return self insertself trailer prev element self trailer dequeu remove operations at the front at the end def removefirstself if self isempty raise indexerrorremovefirst from empty list return self deleteself header next def removelastself if self isempty raise indexerrorremovefirst from empty list return self deleteself trailer prev a private class to be inherited create new_node by setting it s prev link header setting it s next link trailer return first element d linkeddeque d add_first a first a d add_first b first b return last element d linkeddeque d add_last a last a d add_last b last b deque insert operations at the front at the end insertion in the front linkeddeque add_first av first av insertion in the end linkeddeque add_last b last b dequeu remove operations at the front at the end removal from the front d linkeddeque d is_empty true d remove_first traceback most recent call last indexerror remove_first from empty list d add_first a doctest ellipsis data_structures linked_list deque_doubly linkeddeque object at d remove_first a d is_empty true removal in the end d linkeddeque d is_empty true d remove_last traceback most recent call last indexerror remove_first from empty list d add_first a doctest ellipsis data_structures linked_list deque_doubly linkeddeque object at d remove_last a d is_empty true
class _DoublyLinkedBase:
    

    class _Node:
        __slots__ = "_prev", "_data", "_next"

        def __init__(self, link_p, element, link_n):
            self._prev = link_p
            self._data = element
            self._next = link_n

        def has_next_and_prev(self):
            return (
                f" Prev -> {self._prev is not None}, Next -> {self._next is not None}"
            )

    def __init__(self):
        self._header = self._Node(None, None, None)
        self._trailer = self._Node(None, None, None)
        self._header._next = self._trailer
        self._trailer._prev = self._header
        self._size = 0

    def __len__(self):
        return self._size

    def is_empty(self):
        return self.__len__() == 0

    def _insert(self, predecessor, e, successor):
        
        
        new_node = self._Node(predecessor, e, successor)
        predecessor._next = new_node
        successor._prev = new_node
        self._size += 1
        return self

    def _delete(self, node):
        predecessor = node._prev
        successor = node._next

        predecessor._next = successor
        successor._prev = predecessor
        self._size -= 1
        temp = node._data
        node._prev = node._next = node._data = None
        del node
        return temp


class LinkedDeque(_DoublyLinkedBase):
    def first(self):
        
        if self.is_empty():
            raise Exception("List is empty")
        return self._header._next._data

    def last(self):
        
        if self.is_empty():
            raise Exception("List is empty")
        return self._trailer._prev._data

    

    def add_first(self, element):
        
        return self._insert(self._header, element, self._header._next)

    def add_last(self, element):
        
        return self._insert(self._trailer._prev, element, self._trailer)

    

    def remove_first(self):
        
        if self.is_empty():
            raise IndexError("remove_first from empty list")
        return self._delete(self._header._next)

    def remove_last(self):
        
        if self.is_empty():
            raise IndexError("remove_first from empty list")
        return self._delete(self._trailer._prev)