Sometimes it is useful to have a linked list with pointers to both the next and previous nodes. This is called a doubly linked list and may be declared as shown.

     struct dblNode
     {
          int info;
          dblNode* prev;
          dblNode * next;
     };
     dblNode* start;

In this example, note that prev of the first node is set to NULL.

1. Consider doubly linked lists.

       a. What are the advantages that this structure offers?

       b. What are the disadvantages?

       c. Compare doubly linked lists with singly linked lists. When would you choose to use one rather then the other?

2. Write a search function for a doubly linked list.

3. Write a fragment of code to delete the node containing 190 from the doubly linked list shown above. How would the code change if you were asked to delete the node containing 90 or 290 instead?

4. Write the following functions based on the stated pre- and post-conditions.

     void MakeDL(dblNode* &L)
     // pre-condition:   L is singly-linked and possibly empty; see the first diagram
     // post-condition: L is made doubly linked as shown above in the second diagram
     {




     void printForwardandBackward(dblNode* L)
     // pre -condition: L is doubly linked and possibly empty
     // post-condition: The integers stored in L are printed both forward and  backward 
     //			on two lines; for example, line 1:  < 82 85 88 90 97 > 
     //						   line 2:  < 97 90 88 85 82 > 
     {