Write a Python classDequethat implements a double ended queue (deque) supporting the following operations: insert_front(x)— Insertsxat front of queue delete_front()— Deletes and returns element at...

Write a Python classDequethat implements a double ended queue (deque) supporting the following operations:

• insert_front(x)— Insertsxat front of queue


• delete_front()— Deletes and returns element at front of queue


• insert_rear(x)— Insertsxat rear of queue


• delete_rear()— Deletes and returns element at rear of queue

All four operations should take constant time, independent of the size of the deque. The two delete functions should generate anIndexErrorexception with a suitable message if the deque is empty.

To build the deque, write another Python classDoublenodethat defines nodes with three internal variables: one to store a value and two to point to the next and previous node in the list. (This is called a "doubly-linked list".) Don't cheat and use Python's built in list type to store the data in the deque!

TheDequeclass should define a header node that is not part of the deque itself, with pointers to the first and lastDoublenodenodes in the deque. See the supplementary notes below for details on how this could work for a normal list.

The__init__function for Deque should allow the creation of a deque with an initial list of values. The default is to create an empty deque. The optional argument to__init__should be a normal Python list, whose values are then inserted into the deque so that the order is preserved.

You should also define an appropriate__str__function forDequeto display the contents of a deque in sequence, from front to rear.

DequeandDoublenodeshould be separate classes (i.e., do not nestDoublenodeinsideDeque). Include both class definitions in your submissionassignment5.py.

Supplementary notes

Another implementation of lists in Python

Here is a slightly different, and possibly cleaner, way to implement lists using Python classes. Instead of having a single class to represent nodes in the list, we have two classes:

1. 
   

   classList

   
   

   This will define a "header" node for each list. It has one attribute, which we shall callhead. Ifself.headisNone, the list is empty, otherwiseself.headpoints to the first real node in the list.

   
   


2. 
   

   classNode

   
   

   These have two internal attributes,valueandnext, as in the implementation discussed in class. However,valueis neverNoneandnextisNoneonly for the last node in the list.

   
   

Thus, a list with two values[7,8]would look as follows,

List             Node       -------------   -------------- l --> | head | o--|-->| value | 7  |           Node       -------------   --------+-----     ----------------                       | next  | o--|---->| value |  8   |                       --------------     --------+-------                                          | next  | None |                                          ----------------

while an empty list would just look like this:

List       --------------- l --> | head | None |       ---------------

The header node allows us to represent an empty list more cleanly than with only one type of node, where a node withvalue == Noneindicates an empty list.

In this new representation, we can defineappend,insertanddeletemore neatly:

append(recursive):

• 
  

  InList:

  
  

  if self.head is None         # List is empty    make self.head point to a new Node with value x else    append x into self.head
  

  
  


• 
  

  InNode:

  
  

  if self.next is empty        # last node    make self.next point to a new Node with value x else    append x into self.next
  

  
  

insert:

• 
  

  InList:

  
  

  if self.head is None         # List is empty     make self.head point to a new Node with value x else     create newnode with value x     set newnode.next to self.head     set self.head to newnode
  

  
  

delete:(recursive)

• 
  

  InList:

  
  

  if self.head is not None      # List is not empty    if self.head.value is x    # first node to be deleted       set self.head to self.head.next    else       delete x from self.head
  

  
  


• 
  

  InNode:

  
  

  if self.next is not None    if self.next.value is x   # next node to be deleted       set self.next to self.next.next    else       delete x from self.next
  

  
  

Note that we have functionsappend/deletedefined both in the classListand in the classNode. Typically, the version inListonly handles the special case of the empty list and the real work is done insideNode.