deque doubly Algorithm
The deque doubly algorithm, also known as the double-ended queue algorithm, is a versatile data structure that allows users to efficiently insert or remove elements from both ends of the queue. It is implemented using a doubly-linked list, where each node in the list contains a data element and two pointers, one pointing to the previous node and the other to the next node in the sequence. This structure allows for constant-time access, insertion, and removal of elements at both the front and the rear of the deque, providing a highly flexible and efficient data manipulation mechanism. The deque doubly algorithm is particularly well-suited for applications that require frequent updates at both ends of a sequence or when the data needs to be processed in a last-in-first-out (LIFO) or first-in-first-out (FIFO) manner.
In addition to its efficiency and versatility, the deque doubly algorithm also provides several key operations, including push_front, push_back, pop_front, and pop_back. The push_front operation adds an element to the front of the deque, while the push_back operation appends an element to the end of the deque. Conversely, the pop_front operation removes and returns the first element from the deque, and the pop_back operation removes and returns the last element from the deque. These operations can be implemented in constant time, making the deque doubly algorithm an ideal choice for solving complex problems that require dynamic manipulation of data structures. Moreover, the deque doubly algorithm can be easily adapted to support additional functionality, such as searching for specific elements within the deque, iterating through the elements in a specific order, or modifying the deque's size and capacity as needed.
"""
Implementing Deque using DoublyLinkedList ...
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)
"""
class _DoublyLinkedBase:
""" A Private class (to be inherited) """
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 " Prev -> {0}, Next -> {1}".format(
self._prev is not None, 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):
# Create new_node by setting it's prev.link -> header
# 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
class LinkedDeque(_DoublyLinkedBase):
def first(self):
""" return first element
>>> d = LinkedDeque()
>>> d.add_first('A').first()
'A'
>>> d.add_first('B').first()
'B'
"""
if self.is_empty():
raise Exception("List is empty")
return self._header._next._data
def last(self):
""" return last element
>>> d = LinkedDeque()
>>> d.add_last('A').last()
'A'
>>> d.add_last('B').last()
'B'
"""
if self.is_empty():
raise Exception("List is empty")
return self._trailer._prev._data
# DEque Insert Operations (At the front, At the end)
def add_first(self, element):
""" insertion in the front
>>> LinkedDeque().add_first('AV').first()
'AV'
"""
return self._insert(self._header, element, self._header._next)
def add_last(self, element):
""" insertion in the end
>>> LinkedDeque().add_last('B').last()
'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 = 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
<linked_list.deque_doubly.LinkedDeque object at ...
>>> d.remove_first()
'A'
>>> d.is_empty()
True
"""
if self.is_empty():
raise IndexError("remove_first from empty list")
return self._delete(self._header._next)
def remove_last(self):
""" 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
<linked_list.deque_doubly.LinkedDeque object at ...
>>> d.remove_last()
'A'
>>> d.is_empty()
True
"""
if self.is_empty():
raise IndexError("remove_first from empty list")
return self._delete(self._trailer._prev)
