linked list to implement deque would be inefficient we can use doubly linked listhoweverto implement deque efficiently as discussed in section inserting or removing elements at either end of doubly linked list is straightforward to do in ( timeif we use sentinel nodes for the header and trailer for an insertion of new element ewe can have access to the node before the place should go and the node after the place should go to insert new element between the two nodes and (either or both of which could be sentinels)we create new node thave ' prev and next links respectively refer to and qand then have ' next link refer to tand have ' prev link refer to likewiseto remove an element stored at node twe can access the nodes and on either side of (and these nodes must existsince we are using sentinelsto remove node between nodes and qwe simply have and point to each other instead of we need not change any of the fields in tfor now can be reclaimed by the garbage collectorsince no one is pointing to table shows the running times of methods for deque implemented with doubly linked list note that every method runs in ( time table performance of deque realized by doubly linked list method time sizeisempty ( getfirstgetlast ( add firstaddlast ( removefirstremovelast (