the other two methods of our class are the nonpublic utilitiesinsert between and delete node these provide generic support for insertions and deletionsrespectivelybut require one or more node references as parameters the implementation of the insert between method is modeled upon the algorithm that was previously portrayed in figure it creates new nodewith that node' fields initialized to link to the specified neighboring nodes then the fields of the neighboring nodes are updated to include the newest node in the list for later conveniencethe method returns reference to the newly created node the implementation of the delete node method is modeled upon the algorithm portrayed in figure the neighbors of the node to be deleted are linked directly to each otherthereby bypassing the deleted node from the list as formalitywe intentionally reset the prevnextand element fields of the deleted node to none (after recording the element to be returnedalthough the deleted node will be ignored by the rest of the listsetting its fields to none is advantageous as it may help python' garbage collectionsince unnecessary links to the other nodes and the stored element are eliminated we will also rely on this configuration to recognize node as "deprecatedwhen it is no longer part of the list implementing deque with doubly linked list the double-ended queue (dequeadt was introduced in section with an array-based implementationwe achieve all operations in amortized ( timedue to the occasional need to resize the array with an implementation based upon doubly linked listwe can achieve all deque operation in worst-case ( time we provide an implementation of linkeddeque class (code fragment that inherits from the doublylinkedbase class of the preceding section we do not provide an explicit init method for the linkeddeque classas the inherited version of that method suffices to initialize new instance we also rely on the inherited methods len and is empty in meeting the deque adt with the use of sentinelsthe key to our implementation is to remember that the header does not store the first element of the deque--it is the node just after the header that stores the first element (assuming the deque is nonemptysimilarlythe node just before the trailer stores the last element of the deque we use the inherited insert between method to insert at either end of the deque to insert an element at the front of the dequewe place it immediately between the header and the node just after the header an insertion at the end of deque is placed immediately before the trailer node note that these operations succeedeven when the deque is emptyin such situationthe new node is placed between the two sentinels when deleting an element from nonempty dequewe rely upon the inherited delete node methodknowing that the designated node is assured to have neighbors on each side