Deque Doubly

```"""
Operations:
1. insertion in the front -> O(1)
2. insertion in the end -> O(1)
3. remove from the front -> O(1)
4. remove from the end -> O(1)
"""

"""A Private class (to be inherited)"""

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

self._data = element

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

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

def __len__(self):
return self._size

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

def _insert(self, predecessor, e, successor):
# setting it's next.link -> trailer
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

def first(self):
"""return first element
'A'
'B'
"""
if self.is_empty():
raise Exception("List is empty")

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

# DEque Insert Operations (At the front, At the end)

"""insertion in the front
'AV'
"""

"""insertion in the end
'B'
"""
return self._insert(self._trailer._prev, element, self._trailer)

# DEqueu Remove Operations (At the front, At the end)

def remove_first(self):
"""removal from the front
>>> d.is_empty()
True
>>> d.remove_first()
Traceback (most recent call last):
...
IndexError: remove_first from empty list
>>> d.remove_first()
'A'
>>> d.is_empty()
True
"""
if self.is_empty():
raise IndexError("remove_first from empty list")

def remove_last(self):
"""removal in the end
>>> d.is_empty()
True
>>> d.remove_last()
Traceback (most recent call last):
...
IndexError: remove_first from empty list