implementation of double ended queue deque data structure operations appendval any none appendleftval any none extenditerable iterable none extendleftiterable iterable none pop any popleft any observers isempty bool attributes front node front of the deque a k a the first element back node back of the element a k a the last element len int the number of nodes representation of a node contains a value and a pointer to the next node as well as to the previous one helper class for iteration will be used to implement iteration attributes cur node the current node of the iteration ourdeque deque1 2 3 iterator iterourdeque ourdeque deque1 2 3 iterator iterourdeque nextiterator 1 nextiterator 2 nextiterator 3 finished iterating append every value to the deque adds val to the end of the deque time complexity o1 ourdeque1 deque1 2 3 ourdeque1 append4 ourdeque1 1 2 3 4 ourdeque2 deque ab ourdeque2 append c ourdeque2 a b c from collections import deque dequecollections1 deque1 2 3 dequecollections1 append4 dequecollections1 deque1 2 3 4 dequecollections2 deque ab dequecollections2 append c dequecollections2 deque a b c listourdeque1 listdequecollections1 true listourdeque2 listdequecollections2 true front back connect nodes make sure there were no errors adds val to the beginning of the deque time complexity o1 ourdeque1 deque2 3 ourdeque1 appendleft1 ourdeque1 1 2 3 ourdeque2 deque bc ourdeque2 appendleft a ourdeque2 a b c from collections import deque dequecollections1 deque2 3 dequecollections1 appendleft1 dequecollections1 deque1 2 3 dequecollections2 deque bc dequecollections2 appendleft a dequecollections2 deque a b c listourdeque1 listdequecollections1 true listourdeque2 listdequecollections2 true front back connect nodes make sure there were no errors appends every value of iterable to the end of the deque time complexity on ourdeque1 deque1 2 3 ourdeque1 extend4 5 ourdeque1 1 2 3 4 5 ourdeque2 deque ab ourdeque2 extend cd ourdeque2 a b c d from collections import deque dequecollections1 deque1 2 3 dequecollections1 extend4 5 dequecollections1 deque1 2 3 4 5 dequecollections2 deque ab dequecollections2 extend cd dequecollections2 deque a b c d listourdeque1 listdequecollections1 true listourdeque2 listdequecollections2 true appends every value of iterable to the beginning of the deque time complexity on ourdeque1 deque1 2 3 ourdeque1 extendleft0 1 ourdeque1 1 0 1 2 3 ourdeque2 deque cd ourdeque2 extendleft ba ourdeque2 a b c d from collections import deque dequecollections1 deque1 2 3 dequecollections1 extendleft0 1 dequecollections1 deque1 0 1 2 3 dequecollections2 deque cd dequecollections2 extendleft ba dequecollections2 deque a b c d listourdeque1 listdequecollections1 true listourdeque2 listdequecollections2 true removes the last element of the deque and returns it time complexity o1 returns topop val the value of the node to pop ourdeque1 deque1 ourpopped1 ourdeque1 pop ourpopped1 1 ourdeque1 ourdeque2 deque1 2 3 15182 ourpopped2 ourdeque2 pop ourpopped2 15182 ourdeque2 1 2 3 from collections import deque dequecollections deque1 2 3 15182 collectionspopped dequecollections pop collectionspopped 15182 dequecollections deque1 2 3 listourdeque2 listdequecollections true ourpopped2 collectionspopped true make sure the deque has elements to pop if only one element in the queue point the front and back to none else remove one element from back drop the last node python will deallocate memory automatically removes the first element of the deque and returns it time complexity o1 returns topop val the value of the node to pop ourdeque1 deque1 ourpopped1 ourdeque1 pop ourpopped1 1 ourdeque1 ourdeque2 deque15182 1 2 3 ourpopped2 ourdeque2 popleft ourpopped2 15182 ourdeque2 1 2 3 from collections import deque dequecollections deque15182 1 2 3 collectionspopped dequecollections popleft collectionspopped 15182 dequecollections deque1 2 3 listourdeque2 listdequecollections true ourpopped2 collectionspopped true make sure the deque has elements to pop if only one element in the queue point the front and back to none else remove one element from front checks if the deque is empty time complexity o1 ourdeque deque1 2 3 ourdeque isempty false ouremptydeque deque ouremptydeque isempty true from collections import deque emptydequecollections deque listouremptydeque listemptydequecollections true implements len function returns the length of the deque time complexity o1 ourdeque deque1 2 3 lenourdeque 3 ouremptydeque deque lenouremptydeque 0 from collections import deque dequecollections deque1 2 3 lendequecollections 3 emptydequecollections deque lenemptydequecollections 0 lenouremptydeque lenemptydequecollections true implements operator returns if self is equal to other time complexity on ourdeque1 deque1 2 3 ourdeque2 deque1 2 3 ourdeque1 ourdeque2 true ourdeque3 deque1 2 ourdeque1 ourdeque3 false from collections import deque dequecollections1 deque1 2 3 dequecollections2 deque1 2 3 dequecollections1 dequecollections2 true dequecollections3 deque1 2 dequecollections1 dequecollections3 false ourdeque1 ourdeque2 dequecollections1 dequecollections2 true ourdeque1 ourdeque3 dequecollections1 dequecollections3 true if the length of the dequeues are not the same they are not equal compare every value implements iteration time complexity o1 ourdeque deque1 2 3 for v in ourdeque printv 1 2 3 from collections import deque dequecollections deque1 2 3 for v in dequecollections printv 1 2 3 implements representation of the deque represents it as a list with its values between and time complexity on ourdeque deque1 2 3 ourdeque 1 2 3 append the values in a list to display deque data structure operations append val any none appendleft val any none extend iterable iterable none extendleft iterable iterable none pop any popleft any observers is_empty bool attributes _front _node front of the deque a k a the first element _back _node back of the element a k a the last element _len int the number of nodes representation of a node contains a value and a pointer to the next node as well as to the previous one helper class for iteration will be used to implement iteration attributes _cur _node the current node of the iteration our_deque deque 1 2 3 iterator iter our_deque our_deque deque 1 2 3 iterator iter our_deque next iterator 1 next iterator 2 next iterator 3 finished iterating append every value to the deque adds val to the end of the deque time complexity o 1 our_deque_1 deque 1 2 3 our_deque_1 append 4 our_deque_1 1 2 3 4 our_deque_2 deque ab our_deque_2 append c our_deque_2 a b c from collections import deque deque_collections_1 deque 1 2 3 deque_collections_1 append 4 deque_collections_1 deque 1 2 3 4 deque_collections_2 deque ab deque_collections_2 append c deque_collections_2 deque a b c list our_deque_1 list deque_collections_1 true list our_deque_2 list deque_collections_2 true front back connect nodes assign new back to the new node make sure there were no errors adds val to the beginning of the deque time complexity o 1 our_deque_1 deque 2 3 our_deque_1 appendleft 1 our_deque_1 1 2 3 our_deque_2 deque bc our_deque_2 appendleft a our_deque_2 a b c from collections import deque deque_collections_1 deque 2 3 deque_collections_1 appendleft 1 deque_collections_1 deque 1 2 3 deque_collections_2 deque bc deque_collections_2 appendleft a deque_collections_2 deque a b c list our_deque_1 list deque_collections_1 true list our_deque_2 list deque_collections_2 true front back connect nodes assign new front to the new node make sure there were no errors appends every value of iterable to the end of the deque time complexity o n our_deque_1 deque 1 2 3 our_deque_1 extend 4 5 our_deque_1 1 2 3 4 5 our_deque_2 deque ab our_deque_2 extend cd our_deque_2 a b c d from collections import deque deque_collections_1 deque 1 2 3 deque_collections_1 extend 4 5 deque_collections_1 deque 1 2 3 4 5 deque_collections_2 deque ab deque_collections_2 extend cd deque_collections_2 deque a b c d list our_deque_1 list deque_collections_1 true list our_deque_2 list deque_collections_2 true appends every value of iterable to the beginning of the deque time complexity o n our_deque_1 deque 1 2 3 our_deque_1 extendleft 0 1 our_deque_1 1 0 1 2 3 our_deque_2 deque cd our_deque_2 extendleft ba our_deque_2 a b c d from collections import deque deque_collections_1 deque 1 2 3 deque_collections_1 extendleft 0 1 deque_collections_1 deque 1 0 1 2 3 deque_collections_2 deque cd deque_collections_2 extendleft ba deque_collections_2 deque a b c d list our_deque_1 list deque_collections_1 true list our_deque_2 list deque_collections_2 true removes the last element of the deque and returns it time complexity o 1 returns topop val the value of the node to pop our_deque1 deque 1 our_popped1 our_deque1 pop our_popped1 1 our_deque1 our_deque2 deque 1 2 3 15182 our_popped2 our_deque2 pop our_popped2 15182 our_deque2 1 2 3 from collections import deque deque_collections deque 1 2 3 15182 collections_popped deque_collections pop collections_popped 15182 deque_collections deque 1 2 3 list our_deque2 list deque_collections true our_popped2 collections_popped true make sure the deque has elements to pop if only one element in the queue point the front and back to none else remove one element from back set new back drop the last node python will deallocate memory automatically removes the first element of the deque and returns it time complexity o 1 returns topop val the value of the node to pop our_deque1 deque 1 our_popped1 our_deque1 pop our_popped1 1 our_deque1 our_deque2 deque 15182 1 2 3 our_popped2 our_deque2 popleft our_popped2 15182 our_deque2 1 2 3 from collections import deque deque_collections deque 15182 1 2 3 collections_popped deque_collections popleft collections_popped 15182 deque_collections deque 1 2 3 list our_deque2 list deque_collections true our_popped2 collections_popped true make sure the deque has elements to pop if only one element in the queue point the front and back to none else remove one element from front set new front and drop the first node checks if the deque is empty time complexity o 1 our_deque deque 1 2 3 our_deque is_empty false our_empty_deque deque our_empty_deque is_empty true from collections import deque empty_deque_collections deque list our_empty_deque list empty_deque_collections true implements len function returns the length of the deque time complexity o 1 our_deque deque 1 2 3 len our_deque 3 our_empty_deque deque len our_empty_deque 0 from collections import deque deque_collections deque 1 2 3 len deque_collections 3 empty_deque_collections deque len empty_deque_collections 0 len our_empty_deque len empty_deque_collections true implements operator returns if self is equal to other time complexity o n our_deque_1 deque 1 2 3 our_deque_2 deque 1 2 3 our_deque_1 our_deque_2 true our_deque_3 deque 1 2 our_deque_1 our_deque_3 false from collections import deque deque_collections_1 deque 1 2 3 deque_collections_2 deque 1 2 3 deque_collections_1 deque_collections_2 true deque_collections_3 deque 1 2 deque_collections_1 deque_collections_3 false our_deque_1 our_deque_2 deque_collections_1 deque_collections_2 true our_deque_1 our_deque_3 deque_collections_1 deque_collections_3 true if the length of the dequeues are not the same they are not equal compare every value implements iteration time complexity o 1 our_deque deque 1 2 3 for v in our_deque print v 1 2 3 from collections import deque deque_collections deque 1 2 3 for v in deque_collections print v 1 2 3 implements representation of the deque represents it as a list with its values between and time complexity o n our_deque deque 1 2 3 our_deque 1 2 3 append the values in a list to display
from __future__ import annotations

from collections.abc import Iterable
from dataclasses import dataclass
from typing import Any


class Deque:
    

    __slots__ = ("_front", "_back", "_len")

    @dataclass
    class _Node:
        

        val: Any = None
        next_node: Deque._Node | None = None
        prev_node: Deque._Node | None = None

    class _Iterator:
        

        __slots__ = ("_cur",)

        def __init__(self, cur: Deque._Node | None) -> None:
            self._cur = cur

        def __iter__(self) -> Deque._Iterator:
            
            return self

        def __next__(self) -> Any:
            
            if self._cur is None:
                
                raise StopIteration
            val = self._cur.val
            self._cur = self._cur.next_node

            return val

    def __init__(self, iterable: Iterable[Any] | None = None) -> None:
        self._front: Any = None
        self._back: Any = None
        self._len: int = 0

        if iterable is not None:
            
            for val in iterable:
                self.append(val)

    def append(self, val: Any) -> None:
        
        node = self._Node(val, None, None)
        if self.is_empty():
            
            self._front = self._back = node
            self._len = 1
        else:
            
            self._back.next_node = node
            node.prev_node = self._back
            self._back = node  

            self._len += 1

            
            assert not self.is_empty(), "Error on appending value."

    def appendleft(self, val: Any) -> None:
        
        node = self._Node(val, None, None)
        if self.is_empty():
            
            self._front = self._back = node
            self._len = 1
        else:
            
            node.next_node = self._front
            self._front.prev_node = node
            self._front = node  

            self._len += 1

            
            assert not self.is_empty(), "Error on appending value."

    def extend(self, iterable: Iterable[Any]) -> None:
        
        for val in iterable:
            self.append(val)

    def extendleft(self, iterable: Iterable[Any]) -> None:
        
        for val in iterable:
            self.appendleft(val)

    def pop(self) -> Any:
        
        
        assert not self.is_empty(), "Deque is empty."

        topop = self._back
        
        
        if self._front == self._back:
            self._front = None
            self._back = None
        else:
            self._back = self._back.prev_node  
            
            self._back.next_node = None

        self._len -= 1

        return topop.val

    def popleft(self) -> Any:
        
        
        assert not self.is_empty(), "Deque is empty."

        topop = self._front
        
        
        if self._front == self._back:
            self._front = None
            self._back = None
        else:
            self._front = self._front.next_node  
            self._front.prev_node = None

        self._len -= 1

        return topop.val

    def is_empty(self) -> bool:
        
        return self._front is None

    def __len__(self) -> int:
        
        return self._len

    def __eq__(self, other: object) -> bool:
        

        if not isinstance(other, Deque):
            return NotImplemented

        me = self._front
        oth = other._front

        
        if len(self) != len(other):
            return False

        while me is not None and oth is not None:
            
            if me.val != oth.val:
                return False
            me = me.next_node
            oth = oth.next_node

        return True

    def __iter__(self) -> Deque._Iterator:
        
        return Deque._Iterator(self._front)

    def __repr__(self) -> str:
        
        values_list = []
        aux = self._front
        while aux is not None:
            
            values_list.append(aux.val)
            aux = aux.next_node

        return f"[{', '.join(repr(val) for val in values_list)}]"


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    dq = Deque([3])
    dq.pop()