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)

LANGUAGE:

DARK MODE:

PROGRAMMING LANGUAGES:

Python

Java

Javascript

C#

C++

C

Ruby

Scala

MATLAB

Kotlin

Rust

R

Go